Мы используем файлы cookie.
Продолжая использовать сайт, вы даете свое согласие на работу с этими файлами.
Algorytm Ukkonena
Другие языки:

Algorytm Ukkonena

Подписчиков: 0, рейтинг: 0
Algorytm Ukkonena
Ilustracja
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


Новое сообщение