Aby zbudować index Farragina Manziniego ℛ musimy najpierw obliczyć uogólniony szereg przyrostków ℛ. Możemy to zrobić tworząc ciąg znaków, który jest połączeniem wszystkich członkówℛ, S=ℛ₁ℛ₂…ℛm , a następnie użyć jednego z wydajnych algorytmów tablicy suffixów aby obliczyć SA_S .

Dane tablicy suffixów zostały wprowadzone jako reprezentacja zwięzłych leksykograficznych przyrostków łańcucha. Tablica suffixów z ciąguX, oznaczona SA_X, jest permutacją liczb {1, 2,…, |X|} takich, że SA_X [i]=j wtedy i tylko wtedy X[j, |X|] jest i-tym leksykograficznie najniższym przyrostkiem X.

Na przykład jeśli X=AAGTA$ wówczas SA_X=[6, 5, 1, 2, 3, 4]. Ponieważ tablica suffixów jest strukturą posortowaną pozycje startowe dla wszystju unstancji wzorca Q w Q wystąpią w przedziale w SA_X. Odwołujemy się do takiego przedziału jako przedziału tablicy suffiksów i kojarzymy z nim parę liczb całkowitych [l, u] oznaczającą pierwszy i ostatni indec w SA_X, który odpowiada oryginalnemu ciągowi X, I, który może być skutecznie znaleziony przy pomocy wyszukiwania binarnego dla Q.

Ferragina i Manzini opracowali metodę indeksowania tekstu zwaną FM-index, która wymaga znacznie mniej pamięci niż tablica suffixów i może obliczyćl oraz u w O(|Q|) czas, niezależnie od rozmiaru poszukiwanego tekstu. Centralny do FM-index jest BWT. Pierwotnie opracowana do kompresji tekstu BWT of X, oznaczona B_X, jest permutacją z symboli X takich, że




Przekształcone, B_X [i] jest symbolem poprzedzającym pierwszy symbol przyrostkiem wyjścia w pozycji SA_X [i]. Ferragina and Manzini przedłużył BWT representcję ciągu poprzez dodanie dwóch dodarkowych struktur danych, aby stworzyć strukturę zwaną FM-index.
Niech C_X (a) jest liczbą symboli w X, które są leksykograficznie mniejsze niż symbol iOcc_X (a, i) będzie liczbą wystąpień symbolu w B_X [1, i]. Zauważmy, że C_X i Occ_X zawiera liczby dla symbolu posterunkowego $. Wykorzystując te dwie tablice, Ferragina and Manzini dostarczono algorytm aby wyszukać ciągQ w X.
Niech S będzie ciągiem, którego końcówka jest znanym przedziałem z tablicy [l, u]. Przedział dla ciągu S może być obliczony z [l, u] przy użyciu C_X oraz Occ_X:





Implementacja dostępna w pliku FerraginaManziniIndex.zip dostępnego pod adresem
http://cs.elitepc.pl/FerraginaManziniIndex
lub
tutaj


Autor: Krzysztof Wołk