Drzewo sufiksów i próby. Jaka jest różnica?

81

Czytam o Triespowszechnie znanych jako drzewa przedrostków i Suffix Trees.
Chociaż znalazłem kod dla a, Trienie mogę znaleźć przykładu dla Suffix Tree. Mam też wrażenie, że kod budujący a Triejest taki sam, jak kod a, Suffix Treez tą różnicą, że w pierwszym przypadku przechowujemy przedrostki, aw drugim sufiksy.
Czy to prawda? Czy ktoś może mi pomóc wyjaśnić to w mojej głowie? Przykładowy kod byłby bardzo pomocny!

Cratylus
źródło
1
TL; DR Drzewo sufiksów łańcucha to trie patricia wszystkich jego sufiksów. Jedyną specjalną rzeczą jest to, że etykiety krawędzi są podciągami oryginalnego ciągu, więc mogą być reprezentowane jako para indeksów i zajmować tylko stałą przestrzeń. Dlatego też można go budować w czasie liniowym.
Niklas B.

Odpowiedzi:

66

Drzewo sufiksów można postrzegać jako strukturę danych zbudowaną na podstawie próby, w której zamiast po prostu dodawać sam ciąg do trie, można również dodać każdy możliwy sufiks tego ciągu. Na przykład, jeśli chcesz zindeksować ciąg bananowy w drzewie sufiksów, zbudowałbyś trie z następującymi ciągami:

banana
anana
nana
ana
na
a

Gdy to zrobisz, możesz wyszukać dowolny n-gram i sprawdzić, czy jest obecny w indeksowanym ciągu. Innymi słowy, wyszukiwanie n-gramowe to wyszukiwanie przedrostków wszystkich możliwych sufiksów twojego ciągu.

To najprostszy i najwolniejszy sposób na zbudowanie drzewa przyrostków. Okazuje się, że istnieje wiele bardziej wyszukanych wariantów tej struktury danych, które poprawiają zarówno przestrzeń, jak i czas budowy. Nie jestem wystarczająco biegły w tej dziedzinie, aby dać ogólny zarys, ale możesz zacząć od przyjrzenia się tablicom przyrostków lub zaawansowanym strukturom danych tej klasy (wykład 16 i 18).

Ta odpowiedź również świetnie się spisuje, wyjaśniając wariant tej struktury danych.

Ze Blob
źródło
To jest to, co podejrzewałem. Trie służy do budowania drzewa sufiksów i dlatego większość podręczników podaje tylko kod dla prób, ale to jest najgorsza implementacja, co?
Cratylus,
Drzewa sufiksowe @Cratylus są najbardziej przydatne w przypadku bardzo dużych ciągów znaków (np. Indeksowanie wszystkich dzieł Szekspira), gdzie O (n ^ 2) przestrzeń i czas budowy po prostu ich nie przecinają. Na szczęście te granice można nieco obniżyć.
Ze Blob
8

Jeśli wyobrazisz sobie Trie, w którym umieścisz sufiksy jakiegoś słowa, będziesz w stanie bardzo łatwo zapytać go o podciągi łańcucha. To jest główna idea drzewa sufiksów, jest to po prostu „trie sufiksów”.

Ale używając tego naiwnego podejścia, skonstruowanie tego drzewa dla łańcucha o rozmiarze n byłoby O (n ^ 2) i wymagałoby dużo pamięci.

Ponieważ wszystkie wpisy w tym drzewie są sufiksami tego samego ciągu, udostępniają wiele informacji, więc istnieją zoptymalizowane algorytmy, które pozwalają na ich wydajniejsze tworzenie. Na przykład algorytm Ukkonena pozwala na stworzenie online drzewa sufiksów o złożoności czasowej O (n).

Juan Lopes
źródło
2
Więc mówisz, że drzewa i próby przyrostków są takie same?
batman
1

Różnica jest bardzo prosta. Drzewo sufiksów ma mniej węzłów „fikcyjnych” niż trie sufiksów. Te fałszywe węzły to pojedyncze znaki, które zwiększają operację wyszukiwania w drzewie

ciekawy
źródło
0

Węzły Trie mają linki do krótszego kontekstu, „Drzewo” go nie ma. Jeśli węzły drzewa otrzymają link do krótszego kontekstu, to zwraca się do Trie; o)

Stephan Banev
źródło