Loading Blog Search...

Tuesday, January 04, 2005

C++ implementation of Ukkonen's Suffix Tree Construction Algorithm

A very fast linear time suffix tree construction algorithm is elaborately presented by Ukkonen. I like it so much. :-) I give my source codes of a C++ implementation here, under GPL license. Actually, many parts are borrowed from ANSI C Implementation.
What's interesting is the comparison between the C implementation and mine. I compiled both on my debian linux box using gcc 3.3. Without optimization, mine is about half slower than C. With -O3 for both, surprisely enough to me, mine is a bit faster than the C implementation. I like it. :-)

prerequisite software

libpopt
To compile
g++ treekits.cpp spattern.cpp -lpopt
enjoy it. CategoryResearch

4 comments:

Anonymous said...

I'm working too on suffix trees but have an idea about how to alter a suffix tree to a generalized suffix tree with Ukkonen's algorithm, because i have found difficulties to understand Ukkonen's algorithm.

Anonymous said...

I also found Ukkonen's algorithm a bit difficult particularly using of suffix link and the trick to use it linear time. Can you provide a tutorial on this. It may be helpful for me

Andrés said...

Hello Li Zhao,
The link to your code is broken. Can you fix it?
Thanks!

Li-Zhao 李钊 said...

sorry, Andres
It is hosted by google pages, which stopped its service.

I have no backup of these files.