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!
algorithm
data-structures
trie
suffix-tree
Cratylus
źródło
źródło
Odpowiedzi:
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:
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.
źródło
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).
źródło
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
źródło
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)
źródło