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 S nad alfabetem ${\displaystyle \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 ${\displaystyle 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 ${\displaystyle (n-1),}$ więc całe drzewo jest liniowego rozmiaru (zawiera ${\displaystyle 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 ${\displaystyle \chi \alpha }$ (gdzie ${\displaystyle \chi \in \Sigma ,\alpha \in \Sigma ^{\ast }}$), przechowywane jest łącze do węzła reprezentującego podsłowo ${\displaystyle \alpha .}$

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

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.

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).

Drzewo sufiksowe dla słowa długości ${\displaystyle n}$ i uogólnione drzewo sufiksowe dla słów o łącznej długości ${\displaystyle n}$ można zbudować w czasie ${\displaystyle {\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 ${\displaystyle m}$ jako podsłowa słowa S w czasie ${\displaystyle {\mathcal {O}}(m),}$
• znajdowanie wszystkich ${\displaystyle z}$ wystąpień wzorca P długości ${\displaystyle m}$ w słowie S w czasie ${\displaystyle {\mathcal {O}}(m+z),}$
• znajdowanie najdłuższego wspólnego podsłowa (spójnego podciągu) dwóch napisów długości ${\displaystyle n_{1}}$ i ${\displaystyle n_{2}}$ w czasie ${\displaystyle {\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 ${\displaystyle {\mathcal {O}}(n).}$

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

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.

• Wizualizacja drzewa sufiksowego

• 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