Drzewo sufiksowe

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Drzewo sufiksowestruktura 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[edytuj]

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

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

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

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

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

Szczegóły implementacji[edytuj]

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.

Bibliografia[edytuj]

  • 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

  1. Weiner, P. "Linear pattern matching algorithm". 14th Annual IEEE Symposium on Switching and Automata Theory (1973): 1-11.
  2. Ukkonen, E. "On-line construction of suffix trees". Algorithmica 14, 1995, ss. 249--260.[1]