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.

Reference[уреди]


Planovi za budućnost:[уреди]

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

Spoljašnje veze[уреди]