Ukonenov algoritam

• U informatici, Ukonenov algoritam radi u linearnom vremenu, mrežni algoritam za konstruisanje sufiksa drveta, predloženo od strane Esko Ukkonen-a, 1995.

Algoritam počinje sa implicitnim sufiksom stabla koje sadrži prvi karakter stringa.

• Onda korake kroz niz dodajući uzastopne znakove dok drvo ne završi. Ova naredba dodavanje karaktera daje Ukkonen algoritam svoju "mrežnu" imovine. Raniji algoritmi kretali su unazad od poslednjeg znaka ka prvom, tj. od najdužeg do najkraćeg sufiksa, ili od najkraćeg do najdužeg sufiksa. Naivna implementacija za generisanje sufiks drveta zahteva O(n²) ili čak O(n³) vreme, za konstantne veličine pisma, gde je n dužina niza.
• Korišćenjem više algoritamske tehnike, Ukonen-a svodimo na O(n) (linearno),vreme za konstantne velicine alfabeta, i O(n log n) uopšte.

Planovi za budućnost:

• Refaktor da imaju manje globalne varijable
• Ponovno korišćenje Java 'hash'

Dodatna literatura

• „McCreight's paper”. 

Spoljašnje veze

• Original Ukkonen's paper
• Weiner's paper Архивирано на сајту Wayback Machine (3. март 2016)