Algorytm Ukkonena

Algorytm Ukkonena

Przykład drzewa sufiksowego
Złożoność
Czasowa	$O(n)$

Algorytm Ukkonena – algorytm budowy drzewa sufiksowego zaproponowany przez Esko Ukkonena w 1995 roku. Algorytm ten działa w czasie liniowym i jest algorytmem online.

Algorytm zaczyna budowę od drzewa sufiksowego dla pierwszego znaku ciągu. W kolejnych krokach algorytm przekształca drzewo tak, aby było ono drzewem sufiksowym dla ciągu o 1 znak dłuższego. W momencie gdy algorytm doda ostatni znak ciągu drzewo sufiksowe jest gotowe. Taki sposób budowy drzewa zapewnia algorytmowi jego właściwość "on-line", poprzednie algorytmy budowały drzewo sufiksowe zaczynając od ostatniego znaku ciągu. Naiwna implementacja algorytmu ma złożoność O(n²), natomiast zaproponowana przez Ukkonena O(n).

Bibliografia

• E. Ukkonen. (1995). On-line construction of suffix trees. Algorithmica 14(3):249-260. PDF | PDF with figures

Zewnętrzne odnośniki

• Fast String Searching With Suffix Trees. marknelson.us. [zarchiwizowane z tego adresu (2009-02-08)]. Mark Nelson's excellent tutorial. Has an implementation example written with C++.
• Ukkonen's homepage