Tekst źródłowy strony Algorytm Ukkonena

{{Algorytm infobox
 | nazwa            = Algorytm Ukkonena
 | grafika          = Suffix tree BANANA.svg
 | wielkość grafiki = 
 | opis grafiki     = Przykład [[drzewo sufiksowe|drzewa sufiksowego]]
 | rodzaj           = 
 | struktura        = 
 | czas             = <math>O(n)</math>
 | pamięć           = 
}}
'''Algorytm Ukkonena''' – algorytm budowy [[Drzewo sufiksowe|drzewa sufiksowego]] zaproponowany przez Esko Ukkonena w 1995 roku. Algorytm ten działa w czasie liniowym i jest [[algorytm]]em [[Algorytm online|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ść [[Asymptotyczne tempo wzrostu|O(n<sup>2</sup>)]], natomiast zaproponowana przez Ukkonena  [[Asymptotyczne tempo wzrostu|O(n)]].

== Bibliografia ==
* E. Ukkonen. (1995). On-line construction of suffix trees. ''Algorithmica'' '''14'''(3):249-260. [http://www.cs.helsinki.fi/u/ukkonen/SuffixT1.pdf PDF] | [http://www.cs.helsinki.fi/u/ukkonen/SuffixT1withFigs.pdf PDF with figures]

== Zewnętrzne odnośniki ==
* {{Cytuj stronę | url = http://marknelson.us/1996/08/01/suffix-trees | tytuł = Fast String Searching With Suffix Trees | opublikowany = marknelson.us | archiwum = https://web.archive.org/web/20090208165518/http://marknelson.us/1996/08/01/suffix-trees | zarchiwizowano = 2009-02-08}}  Mark Nelson's excellent tutorial.  Has an implementation example written with C++.
* [http://www.cs.helsinki.fi/u/ukkonen/  Ukkonen's homepage]

{{SORTUJ:Ukkonena algorytm}}
[[Kategoria:Algorytmy]]