Tablica suffixowa jest strukturą danych, która jest przeznaczona do wydajnego wyszukiwania dużego tekstu. Ta struktura danych najprościej ujmując jest tablicą zawierającą wszystkie wskaźniki do przyrostków tekstowych, które są posortowane w sposób alfabetyczny. Każdy przyrostek jest łańcuchem, który zaczyna się w pewnej pozycji w tekście i kończy razem z jego końcem. Wyszukiwanie tekstu może być wykonywane przez przeszukiwanie binarne przy użyciu tablicy suffixowej (przyrostków).

Konstrukcja tablicy suffixowej (przyrostków) - załóżmy, że mamy przykładowy tekst - "abracadabra" i chcemy zbudować tablicę dla tego tekstu.

Po pierwsze należy przypisać indeksy kolejnym literom tekstu przykładowego. Indeksy określają pozycje, które mogą być przeszukiwane. W naszym przykładzie indeksy są przypisane dla każdego znaku, tak więc możemy później przeszukać przykładowy tekst w dowolnych pozycjach używając tablicy suffixowej.




Po drugie powinniśmy uporządkować indeksy zgodnie z ich odpowiednimi przyrostkami. Zgodność między indeksami, a przyrostkami wygląda następująco:




Po sortowaniu:




Finalnie rezultat sortowania sprawia iż indeksy stają się tablicą suffixową dla przykładowego tekstu.




Szukanie w przykładowym tekście może być wykonane przez wyszukiwanie binarne za pomocą utworzonej tablicy suffixowej. Poniższa ilustracja przedstawia proces poszukiwania w przykładowym tekście ciągu znaków "ra". Numerowane strzałki pokazują kolejność przetwarzania.




Użyłem algorytmu SearchLeft do znalezienia wzorca wyszukiwania w danym ciągu. Przeskakiwanie algorytmu w całych wierszach tablicy suffixowej są rejestrowane i wyświetlane jako 'route'. Wzorzec wyszukiwania zostanie uznany za występujący po raz pierwszy jeśli pójdziemy tą drogą. Przykład poniżej:
Wzór: cad
Cały ciąg: abracadabra
SearchLeft algorytm zajmie 0.05 sekund
ShiftAnd algorytm zajmie 0.11 sekund

Implementacja dostępna w pliku SuffixArray.zip, który znajduje się pod adresem:
http://cs.elitepc.pl/SuffixArray
lub
tutaj



Autor: Krzysztof Wołk