Drzewo sufiksowe

Drzewo sufiksowe – struktura danych reprezentująca zbiór sufiksów danego ciągu znaków w sposób umożliwiający efektywne wykonywanie wielu istotnych operacji na łańcuchach znaków.

Drzewo sufiksowe dla słowa BANANA zakończonego znakiem $. Liniami przerywanymi zaznaczono łącza sufiksowe.

Definicja

Drzewo sufiksowe dla słowa S nad alfabetem $\Sigma$ jest skompresowanym drzewem trie dla zbioru wszystkich niepustych sufiksów S. Stąd wynikają następujące własności:

• istnieje jednoznaczna odpowiedniość między liśćmi drzewa a sufiksami S,
• krawędzie drzewa są etykietowane niepustymi łańcuchami znaków,
• wszystkie węzły wewnętrzne mają co najmniej dwóch synów.

Aby zapewnić spełnienie powyższych własności, na końcu słowa S umieszcza się znak spoza alfabetu, co gwarantuje, że żaden sufiks nie jest prefiksem innego sufiksu, a drzewo będzie posiadać dokładnie $n$ liści, po jednym dla każdego niepustego sufiksu słowa S. Ponieważ dodatkowo każdy węzeł wewnętrzny który nie jest korzeniem ma dwóch synów, takich węzłów może być co najwyżej $(n-1),$ więc całe drzewo jest liniowego rozmiaru (zawiera $n (n-1) 1$ wszystkich węzłów).

W drzewie mogą być przechowywane łącza sufiksowe (zaznaczone na rysunku liniami przerywanymi), które są podstawą do jednego ze sposobów konstrukcji drzewa sufiksowego w czasie liniowym względem długości słowa S. W każdym węźle wewnętrznym drzewa niebędącym korzeniem, do którego ścieżka prowadzi przez krawędzie, których etykiety składają się na słowo $\chi \alpha$ (gdzie $\chi \in \Sigma ,\alpha \in \Sigma ^{\ast }$), przechowywane jest łącze do węzła reprezentującego podsłowo $\alpha .$

Historia

Koncepcję drzew sufiksowych (nazwanych wtedy drzewami pozycyjnymi) wprowadził Weiner w 1973 roku. Konstrukcja została uproszczona przez McCreighta (1976). Ukkonen (1995) podał pierwszy liniowy algorytm konstrukcji drzewa sufiksowego online, znany jako Algorytm Ukkonena.

Uogólnione drzewo sufiksowe

Uogólnione drzewo sufiksowe dla słów ABAB (zakończony ciągiem $0) i BABA (zakończony ciągiem $1)

Uogólnione drzewo sufiksowe to drzewo sufiksowe zbudowane dla zbioru słów zamiast dla jednego słowa, reprezentujące wszystkie sufiksy słów z tego zbioru. W tym przypadku konieczne jest zakończenie każdego ze słów unikalnym znakiem lub słowem.

Zastosowania

Drzewa sufiksowe znajdują zastosowanie między innymi w bioinformatyce, gdzie służą do analizy łańcuchów DNA i sekwencji aminokwasów w białkach, oraz w kompresji danych (modyfikacje kompresji LZW).

Funkcjonalności

Drzewo sufiksowe dla słowa długości $n$ i uogólnione drzewo sufiksowe dla słów o łącznej długości $n$ można zbudować w czasie ${\mathcal {O}}(n).$ Po zbudowaniu może służyć między innymi do efektywnego wykonania następujących operacji:

• znajdowanie dowolnego wystąpienia wzorca P długości $m$ jako podsłowa słowa S w czasie ${\mathcal {O}}(m),$
• znajdowanie wszystkich $z$ wystąpień wzorca P długości $m$ w słowie S w czasie ${\mathcal {O}}(m z),$
• znajdowanie najdłuższego wspólnego podsłowa (spójnego podciągu) dwóch napisów długości $n_{1}$ i $n_{2}$ w czasie ${\mathcal {O}}(n_{1} n_{2}),$
• znajdowanie najdłuższego podsłowa słowa S które powtarza się w tym słowie w czasie ${\mathcal {O}}(n).$

Zobacz też

• algorytm Knutha-Morrisa-Pratta – inna metoda szybkiej implementacji działań na łańcuchach znaków
• skompresowane drzewo trie
• tablica sufiksowa

Szczegóły implementacji

Drzewo sufiksowe można przechowywać w pamięci rozmiaru liniowego względem długości słowa S, utrzymując jako etykiety krawędzi drzewa pozycje początkowego i końcowego znaku etykiety zamiast wszystkich jej znaków.

Linki zewnętrzne

• Wizualizacja drzewa sufiksowego

Bibliografia

• Dan Gusfield: Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge [England]: Cambridge University Press, 1997. ISBN 0-521-58519-8. Brak numerów stron w książce