Opis algorytmu Ukkonena dla drzewek przyrostków

Robię trochę pracy z algorytmem Ukkonena do budowania drzewek przyrostków, ale nie rozumiem niektórych części wyjaśnień autora dotyczących jego złożoności w czasie liniowym.Opis algorytmu Ukkonena dla drzewek przyrostków

Nauczyłem się algorytmu i zakodowałem go, ale papier, którego używam jako głównego źródła informacji (połączony poniżej) jest nieco mylący w niektórych częściach, więc nie jest dla mnie jasne, dlaczego algorytm jest liniowy .

Każda pomoc? Dzięki.

Link do papieru Ukkonen: http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf

Źródło

2009-08-20 Vinicius Pinto

Dla każdego, kto znajdzie to pytanie: Podobny pojawił się [tutaj] (http://stackoverflow.com/q/9452701/777186) i tworzymy opis algorytmu jako odpowiedź Stackoverflow [tutaj] (http://stackoverflow.com/a/9513423/777186). – jogojapan

znaleźć kopię Gusfield na string algorithms textbook. Ma najlepszą ekspozycję konstrukcji drzewa sufiksów, jaką widziałem. Liniowość jest zaskakującą konsekwencją szeregu optymalizacji algorytmu wysokiego poziomu.

Źródło

2009-08-29 15:18:45

Czy istnieje animowana wersja tego ukkonen algo? Niestety nie mogłem zrozumieć stałej natury funkcji "aktualizacji". Próbowałem też gusfield, papieru i Google'a: D – Seeker

Chciałbym obejrzeć animację do budowania uogólnionego drzewa sufiksów w czasie liniowym. Ogólnie wyjaśnienie oparte na tekście nie pasuje do mojego umysłu .. :) – Abhi

Rozdział Gusfieldsa na temat drzewek sufiksowych ma tę irytującą cechę, że używa różnych ciągów do zilustrowania różnych kroków - więc tracisz duży obraz. – maasha

Opis algorytmu Ukkonena dla drzewek przyrostków

Odpowiedz

Powiązane problemy