FM-index

En informatique, un FM-index est une structure d'indexation compressée sans perte, fondée sur la Transformée de Burrows-Wheeler, qui a des similitudes avec le tableau des suffixes. Cette structure de données a été créée par Paolo Ferragina et Giovanni Manzini, qui la décrivent comme étant un index multi-usages basé sur une structure de donnée astucieuse. Le nom signifie Modèle:Citation étrangèreModèle:,.

Cet index peut, en plus de la compression, être utilisé pour trouver de façon efficace le nombre d’occurrences d’un motif dans le texte compressé, ainsi que pour localiser la position de chaque occurrence du mot recherché dans le texte compressé. Aussi bien le temps que l'espace de stockage requis ont une complexité sublinéaire par rapport à la taille des données d’entrée. C'est-à-dire que le temps d'exécution et l'espace de stockage requis ne sont pas proportionnels à la taille des données d'entrée.

Le FM-index a été utilisé entre autres en bio-informatique.

Cadre

Utiliser un index est une stratégie commune pour rechercher efficacement dans un vaste corpus de texte. Lorsque le texte est plus grand que ce que peut contenir la mémoire principale de l’ordinateur, il est nécessaire de compresser non seulement le texte, mais aussi l’index. Lorsque le FM-index a été introduit, plusieurs solutions avaient déjà été suggérées pour atteindre ce double but. Elles reposaient sur des méthodes de compression traditionnelles qui essayaient aussi de résoudre le problème de compression d'index. En revanche, FM-index utilise un index compressé de façon native, ce qui signifie qu’il est simultanément capable de compresser les données et d'indexer.

Structures FM-index

Un FM-index est créé en prenant d'abord la transformée de Burrows-Wheeler (BWT) du texte d’entrée. Par exemple, la BWT de la chaîne Modèle:Math « abracadabra » est « ard$ rcaaaabb », et ici elle est représentée par la matrice Modèle:Math où chaque ligne est une rotation du texte, et les lignes ont été triées lexicographiquement. La transformation correspond à la dernière colonne intitulée Modèle:Math.

Modèle:Math	Modèle:Math		Modèle:Math
1	$	abracadabr	a
2	a	$abracadab	r
3	a	bra$abraca	d
4	a	bracadabra	$
5	a	cadabra$ab	r
6	a	dabra$abra	c
7	b	ra$abracad	a
8	b	racadabra$	a
9	c	adabra$abr	a
10	d	abra$abrac	a
11	r	a$abracada	b
12	r	acadabra$a	b

La BWT en soi permet une compression avec, par exemple, move-to-front et le codage de Huffman, mais la BWT à d'autres utilisations. Les lignes de la matrice sont essentiellement les suffixes triés du texte, ce qui correspond au tableau des suffixes. Ce lien entre le tableau des suffixes et la BWT est au cœur du FM-index.

Il est possible de faire un tableau de correspondance entre la dernière et la première colonne Modèle:Math depuis un index i vers un index Modèle:Math, tel que Modèle:Math = Modèle:Math, avec l’aide d’une table Modèle:Math et Modèle:Math. Modèle:Math est une table qui, pour chaque caractère Modèle:Math dans l’alphabet, contient le nombre d’occurrences de caractère lexicalement plus petits qui sont contenus dans le texte. La fonction Modèle:Math est le nombre d’occurrences du caractère Modèle:Math dans le préfixe Modèle:Math. Ferragina et Manzini a montré qu’il est possible de calculer des Modèle:Math en temps constant.

Modèle:Math de "ard$rcaaaabb" Modèle:Math $ a b c d r Modèle:Math 0 1 6 8 9 10

Le tableau de correspondance entre la dernière et la première colonne peut maintenant être défini comme Modèle:Math. Par exemple, en rang 9, Modèle:Math est 'a' et le même 'a' se trouvent sur la ligne 5 dans la première colonne Modèle:Math, donc Modèle:Math devrait être 5 et Modèle:Math. Pour toute ligne Modèle:Math de la matrice, le caractère dans la dernière colonne Modèle:Math précède le caractère dans la première colonne Modèle:Math aussi en T. Enfin, si Modèle:Math, puis Modèle:Math, et en utilisant l’égalité, il est possible d’extraire une chaîne de Modèle:Math de Modèle:Math. Le FM-index lui-même est une compression de la chaîne Modèle:Math avec Modèle:Math et Modèle:Math, mais aussi des informations qui mappe une sélection d’indices en Modèle:Math à des positions dans la chaîne d’origine Modèle:Math.

Modèle:Math de "ard$rcaaaabb" a r d $ r c a a a a b b 1 2 3 4 5 6 7 8 9 10 11 12 $ 0 0 0 1 1 1 1 1 1 1 1 1 a 1 1 1 1 1 1 2 3 4 5 5 5 b 0 0 0 0 0 0 0 0 0 0 1 2 c 0 0 0 0 0 1 1 1 1 1 1 1 d 0 0 1 1 1 1 1 1 1 1 1 1 r 0 1 1 1 2 2 2 2 2 2 2 2

Compter

L’opération count prend un motif Modèle:Math et retourne le nombre d’occurrences de ce motif dans le texte original Modèle:Math. Comme les lignes de la matrice Modèle:Math sont triées, et qu'elles contiennent chaque suffixe de Modèle:Math, les occurrences du motif Modèle:Math seront côte à côte dans une unique plage continue. Cette opération est réitérée de façon rétrograde sur le motif. Pour chaque caractère dans le motif, l'ensemble de lignes qui possède ce caractère comme suffixe, est trouvé. Par exemple, la recherche du motif « bra » dans « abracadabra » suit les étapes suivantes :

1. Le premier caractère que nous recherchons est 'Modèle:Math', le dernier caractère dans le motif. L'ensemble de lignes initial est définie sur Modèle:Math. Cet ensemble de lignes sur Modèle:Math représente chaque caractère de Modèle:Math, qui possède un suffixe commençant par a.
2. Le prochain caractère à rechercher est Modèle:Math. Le nouvel ensemble de lignes est Modèle:Math Modèle:Math Modèle:Math, si Modèle:Math est l’index de début de la plage et Modèle:Math est la fin. Cet ensemble de lignes sur Modèle:Math contient tous les caractères de Modèle:Math qui ont des suffixes commençant par ra.
3. Le dernier caractère à regarder est Modèle:Math. Le nouvel ensemble de lignes est Modèle:Math Modèle:Math Modèle:Math. cet ensemble de lignes sur Modèle:Math consiste en tous les caractères qui ont un suffixe commençant par bra. Maintenant que l'ensemble du motif est traitée, le compte est identique à la taille de la plage : Modèle:Math.

Si la plage est vide ou si les limites de l'ensemble de lignes se croisent mutuellement avant que l’ensemble du motif soit investigué, cela signifie que Modèle:Math n'est pas présent dans Modèle:Math. Comme Modèle:Math peut être effectué en temps constant, le comptage peut s'accomplir en temps linéaire proportionnel à la longueur du motif : Modèle:Math.

Localiser

L’opération localiser prend comme entrée un index d’un caractère dans Modèle:Math et retourne sa position Modèle:Math en Modèle:Math. Par exemple Modèle:Math. Pour trouver toutes les occurrences d’un motif, il faut tout d’abord trouver la plage de suffixes de Modèle:Math dont le motif est préfixe, de la même manière que celle pour l’opération compter. Ensuite, il reste à trouver la position de chaque suffixe de cette plage dans Modèle:Math.

Pour faire correspondre un index dans Modèle:Math en un index dans Modèle:Math, un sous-ensemble des indices en Modèle:Math est associé à une position en Modèle:Math. Si Modèle:Math a une position qui lui est associée, trouver Modèle:Math est trivial. S'il n’y a pas de positions associée, la recherche se poursuit sur la chaîne avec Modèle:Math jusqu'à ce qu’un index associé soit trouvé. En associant un nombre adéquat d’indices, on trouvera une limite supérieure. L’opération trouver peut être implémentée pour trouver les occurrences dModèle:'occ Modèle:Math dans un texte Modèle:Math en Modèle:Math temps avec $O(H_k(T)+\frac{\log \log u}{{\log }^{ϵ}u})$ bits par symbole d’entrée pour toute Modèle:Math.

Améliorations

Les auteurs ont mis au point des améliorations à leur approche première et ont nommé cette nouvelle méthode de compression « FM-Index version 2 ». Une autre amélioration, le FM "respectueux de l’alphabet", combine l’utilisation de la stimulation de compression et les ondelettes pour réduire considérablement l’utilisation de l’espace dans le cas d'utilisation d'alphabets de grande taille.

Applications

Localisation de séquences d'ADN sur un génome

Le FM-index a été appliqué avec succès (> 2000 citations) à l’alignement de séquence génomique, voir http://bowtie-bio.sourceforge.net/index.shtml.