Sunday, March 2, 2008

Ukkonen's Linear Suffix Tree Construction (JavaScript Demo)

Input your own the text string in the textfield below and click generate.
Don't forget to put a unique ending character for the text (usually it's '#').

Show Every Split

Each node in the picture is represented by NODE_INDEX(SUFFIX_LINK, SUBSTRING, START_INDEX, END_INDEX) where:

  • NODE_INDEX is an integer generated as new node is created.
  • SUFFIX_LINK is an integer that tells the suffix link of the node.
  • SUBSTRING is the string connecting the parent node to this node.
  • START_INDEX and END_INDEX is the index of the substring in the text.

The JavaScript code skeleton is taken from http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Suffix/. You will find also the step-by-step explanation in creating Suffix Tree for text "mississipi" in that site.

You also can use these text for more understanding on how it works:

If you like this demo, you may also like to see Linear Suffix Array construction's demo by Juha Karkkainen and Peter Sanders.

No comments:

Post a Comment