 Przykład drzewa sufiksowego | |
| Złożoność | |
| Czasowa |
|
|---|---|
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(n2), 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