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.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/d/d2/Suffix_tree_BANANA.svg/250px-Suffix_tree_BANANA.svg.png)
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 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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/f/f6/Suffix_tree_ABAB_BABA.png/250px-Suffix_tree_ABAB_BABA.png)
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
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.
Przypisy
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.