FM-index

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.

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 T = « abracadabra » est « ard$ rcaaaabb », et ici elle est représentée par la matrice M 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 L.

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.

L’opération count prend un motif P [1..p] et retourne le nombre d’occurrences de ce motif dans le texte original T. Comme les lignes de la matrice M sont triées, et qu'elles contiennent chaque suffixe de T, les occurrences du motif P 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 ' a', le dernier caractère dans le motif. L'ensemble de lignes initial est définie sur [ C [a] + 1..C [a + 1] = [2..6]. Cet ensemble de lignes sur L représente chaque caractère de T, qui possède un suffixe commençant par a.
2. Le prochain caractère à rechercher est r. Le nouvel ensemble de lignes est [ C [r] + Occ (r, start-1) + Occ (r, fin), 1..C [r]] = [ 10 + 0 + 1..10 + 2] = [ 11..12], si début est l’index de début de la plage et fin est la fin. Cet ensemble de lignes sur L contient tous les caractères de T qui ont des suffixes commençant par ra.
3. Le dernier caractère à regarder est b. Le nouvel ensemble de lignes est [ C [b] + Occ (b, start-1) + 1..C [b] + Occ (b, fin)] = [ 6 + 0 + 1..6 + 2] = [ 7..8]. cet ensemble de lignes sur L 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 : 8-7 + 1 = 2.

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 P n'est pas présent dans T. Comme OCC (c, k) peut être effectué en temps constant, le comptage peut s'accomplir en temps linéaire proportionnel à la longueur du motif : Temps de O(p).

L’opération localiser prend comme entrée un index d’un caractère dans L et retourne sa position i en T. Par exemple locate(7) = 8. Pour trouver toutes les occurrences d’un motif, il faut tout d’abord trouver la plage de suffixes de T 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 T.

Pour faire correspondre un index dans L en un index dans T, un sous-ensemble des indices en L est associé à une position en T. Si L [j] a une position qui lui est associée, trouver locate(j) est trivial. S'il n’y a pas de positions associée, la recherche se poursuit sur la chaîne avec LF(i) 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 d'occ P [1..p] dans un texte T [1..u] en O (p + occ log ^ε u) temps avec ${\displaystyle O(H_{k}(T)+{{\log \log u} \over {\log ^{\epsilon }u}})}$ bits par symbole d’entrée pour toute k ≥ 0[1].