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

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

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

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

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

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

Szczegóły implementacji[edytuj | edytuj kod]

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

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