Ukkonen's algorithm

In computer science, Ukkonen's algorithm is a linear-time, online algorithm for constructing suffix trees, proposed by Esko Ukkonen in 1995.^[1] 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. The original algorithm presented by Peter Weiner proceeded backward from the last character to the first one from the shortest to the longest suffix.^[2] A simpler algorithm was found by Edward M. McCreight, going from the longest to the shortest suffix.^[3]

Implicit suffix tree

While generating suffix tree using Ukkonen's algorithm, we will see implicit suffix tree in intermediate steps depending on characters in string S. In implicit suffix trees, there will be no edge with $(or any other termination character) label and no internal node with only one edge going out of it.

Run time

The naive implementation for generating a suffix tree going forward requires $O (n 2)$ or even $O (n 3)$ time complexity in big O notation, where $n$ is the length of the string. By exploiting a number of algorithmic techniques, Ukkonen reduced this to $O (n)$ (linear) time, for constant-size alphabets, and $O (n log n)$ in general, matching the runtime performance of the earlier two algorithms.

References

^ Ukkonen, E. (1995). "On-line construction of suffix trees" (PDF). Algorithmica. 14 (3): 249–260. CiteSeerX 10.1.1.10.751. doi:10.1007/BF01206331. S2CID 6027556.
^ Weiner, Peter (1973). "Linear pattern matching algorithms" (PDF). 14th Annual Symposium on Switching and Automata Theory (SWAT 1973). pp. 1–11. CiteSeerX 10.1.1.474.9582. doi:10.1109/SWAT.1973.13.
^ McCreight, Edward Meyers (1976). "A Space-Economical Suffix Tree Construction Algorithm". Journal of the ACM. 23 (2): 262–272. CiteSeerX 10.1.1.130.8022. doi:10.1145/321941.321946. S2CID 9250303.

External links

Detailed explanation in plain English
Fast String Searching With Suffix Trees Mark Nelson's tutorial. Has an implementation example written with C++.
Implementation in C with detailed explanation
Lecture slides by Guy Blelloch
Ukkonen's homepage
Text-Indexing project (Ukkonen's linear-time construction of suffix trees)
Implementation in C Part 1 Part 2 Part 3 Part 4 Part 5 Part 6

This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.

[1] Ukkonen, E. (1995). "On-line construction of suffix trees" (PDF). Algorithmica. 14 (3): 249–260. CiteSeerX 10.1.1.10.751. doi:10.1007/BF01206331. S2CID 6027556.

[2] Weiner, Peter (1973). "Linear pattern matching algorithms" (PDF). 14th Annual Symposium on Switching and Automata Theory (SWAT 1973). pp. 1–11. CiteSeerX 10.1.1.474.9582. doi:10.1109/SWAT.1973.13.

[3] McCreight, Edward Meyers (1976). "A Space-Economical Suffix Tree Construction Algorithm". Journal of the ACM. 23 (2): 262–272. CiteSeerX 10.1.1.130.8022. doi:10.1145/321941.321946. S2CID 9250303.

[1]

[2]

[3]