ITMO University
“Programming Technologies” Department

Ukkonen Algorithm

© 2004 I.R. Akhmetov

Saint-Petersburg State University of Information Technologies, Mechanics and Optics

Project documentation (in Russian)
Source code
Visualizer (online)

Annotation

Suffix tree is a data structure, that allows to present a string in a way, that is very useful in many tasks of string processing. In particular, this data structure is widely used in computational biology presently. This has become possible thanks to the algoriths that build the suffix tree for the string of length n in the O(n) time.

This work contains an implementation of the algorithm, which was recently (in 1995) suggested by E. Ukkonen. It has certain advantages over the earlier suggested by P. Weiner and E.M. McCreight algorithms. For the sake of simplicity a version of the algorithm that works in the O(n²) time is implemented. It reveals the essense of the algorithm more completely and with several modifications can be turned into a version that works in the O(n) time.

The implementation of the algorithm uses the Vizi technology and is a Java-applet, which can demonstrate the algorithm step-by-step on different strings. This technology uses an automata-based approach to visualizer development. The documentation includes algorithm details, description of the applet and source codes of the visualizer.