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.
thumb|250px|Drzewo sufiksowe dla słowa BANANA zakończonego znakiem $. Liniami przerywanymi zaznaczono łącza sufiksowe.
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 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 więc całe drzewo jest liniowego rozmiaru (zawiera 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
Historia Koncepcję drzew sufiksowych (nazwanych wtedy drzewami pozycyjnymi) wprowadził Weiner w 1973 rokuWeiner, P. „Linear pattern matching algorithm”. 14th Annual IEEE Symposium on Switching and Automata Theory (1973): 1-11.. Konstrukcja została uproszczona przez McCreighta (1976). Ukkonen (1995) podał pierwszy liniowy algorytm konstrukcji drzewa sufiksowego onlineUkkonen, E. „On-line construction of suffix trees”. Algorithmica 14, 1995, s. 249–260.., znany jako Algorytm Ukkonena.
Uogólnione drzewo sufiksowe thumb|250px|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 i uogólnione drzewo sufiksowe dla słów o łącznej długości 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 jako podsłowa słowa S w czasie znajdowanie wszystkich wystąpień wzorca P długości 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 i w czasie znajdowanie najdłuższego podsłowa słowa S które powtarza się w tym słowie w czasie
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.
Zobacz też algorytm Knutha-Morrisa-Pratta – inna metoda szybkiej implementacji działań na łańcuchach znaków skompresowane drzewo trie
Przypisy
Bibliografia
Linki zewnętrzne Wizualizacja drzewa sufiksowego
Sufiksowe, drzewo Kategoria:Algorytmy tekstowe