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ż

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

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.

Źródła

• Dan Gusfield: Algorithms on strings, trees, and sequences: computer science and computational biology. Cambridge [England]: Cambridge University Press, 1997. ISBN 0-521-58519-8.