Algorytm Ukkonena
Algorytm Ukkonena to metoda konstrukcji drzewa sufiksowego, która została zaproponowana przez Esko Ukkonena w 1995 roku. Działa on w czasie liniowym i ma charakter online.
Budowa zaczyna się od drzewa sufiksowego dla pierwszego znaku danego ciągu. W kolejnych etapach algorytm modyfikuje drzewo, aby stało się drzewem sufiksowym dla ciągu o jeden znak dłuższego. Gdy ostatni znak ciągu zostanie dodany, drzewo sufiksowe jest już gotowe. Taki sposób konstrukcji umożliwia algorytmowi działanie w trybie „on-line”, w przeciwieństwie do wcześniejszych algorytmów, które zaczynały budowę drzewa od ostatniego znaku ciągu. Naiwna implementacja algorytmu ma złożoność O(n2), podczas gdy metoda zaproponowana przez Ukkonena osiąga złożoność 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)]. Doskonały poradnik autorstwa Marka Nelsona. Zawiera przykład implementacji napisany w C++.
