Z Wikipedii

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.

[edytuj] Definicja

Drzewo sufiksowe dla słowa S nad alfabetem Σ 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 χα (gdzie ), przechowywane jest łącze do węzła reprezentującego podsłowo α.

[edytuj] Historia

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

[edytuj] 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.

[edytuj] 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).

[edytuj] 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 . 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
• znajdowanie wszystkich z wystąpień wzorca P długości m w słowie S w czasie
• znajdowanie najdłuższego wspólnego podsłowa (spójnego podciągu) dwóch napisów długości n₁ i n₂ w czasie
• znajdowanie najdłuższego podsłowa słowa S które powtarza się w tym słowie w czasie

[edytuj] Zobacz też

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

[edytuj] 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.

[edytuj] Ź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. 

Przypisy