My watch list
my.bionity.com  
Login  

Ukkonen's algorithm



In 1995, Esko Ukkonen proposed a linear-time, online algorithm for constructing suffix trees that has come to be known as Ukkonen's algorithm.

The algorithm begins with an implicit suffix tree containing the first character of the string. Then it steps through the string adding successive characters until the tree is complete. This order addition of characters gives Ukkonen's algorithm its "on-line" property; earlier algorithms proceeded backward from the last character. The naive implementation of this algorithm requires O(n2) or even O(n3) time (see Big-O notation), where n is the number of characters in the string, but by exploiting a number of algorithmic techniques this can be reduced to O(n) (linear) time.

References

  • E. Ukkonen. (1995). On-line construction of suffix trees. Algorithmica 14(3):249-260. PDF | PDF with figures


 
This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Ukkonen's_algorithm". A list of authors is available in Wikipedia.
Your browser is not current. Microsoft Internet Explorer 6.0 does not support some functions on Chemie.DE