Suffix-Tree impl

This program is free software.  You can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more details.

Author

© 2012 Jörg Seebohn

A suffix tree is built from an input string and it stores all suffixes.

The tree is initialized as empty where the root is denoted by “*”.

[0] empty tree
    *

Now we build a suffix from the input string “ccxccxccc”.  It is built character by character starting from left until the end of string is reached.  In following diagram an arrow top to bottom is a pointer from parent to child.  A node matches its contained character.  No two childs of the same parent can match the same character.

An end node matches a suffix.  It is marked with a subscript ₀,₁,...  An input string of length n has n matching end nodes.  The value of the subscript is the start offset of a matched suffix.

An arrow from child to parent is called the suffix link.  The suffix link of a node points to the node which matches the next substring without the first character.  For example the child

A possible suffix tree may look like this

[1] add "ccxccxccc" │  [2] add "ccxccxccc" │  [3] add "ccxccxccc"
         ^          │            ^         │             ^
    *               │      *               │      * ──────╮
    ↓               │      ↓               │      ↓       ↓
    c₀              │   ╭> c₁              │   ╭> c ──╮ ╭>x₂
                    │   │  ↓               │   │  ↓   ↓ │
                    │   ╰─ c₀              │   ╰─ c ╭>x₁╯
                    │                      │      ↓ │
                    │                      │      x₀╯

For example the child node “x₀” matches the string “ccx”.  Its suffix link points to “x₁” which matches “cx” the next smaller suffix of “ccx” (without the first character).  The suffix links which point to the root (root matches empty string) are omitted.

[4] add "ccxccxccc" │  [5] add "ccxccxccc" │  [6] add "ccxccxccc"
            ^       │               ^      │                ^
     * ─────╮       │       * ──────╮      │       * ────────╮
     ↓      ↓       │   ╭───↓───────↓──╮   │   ╭───↓─────────↓──╮
 ╭>╭>c₃ ─╮╭>x       │   ╰>╭>c₃ ─╮╭─>x  │   │   ╰>╭>c ──╮ ╭─> x₅ │
 │ │ ↓   ↓│ ↓       │     │ ↓   ↓│  ↓  │   │     │ ↓   ↓ │   ↓  │
 │ ╰ c╭─>x╯ c₂<╮    │   ╭>╰ c₄╭>x╯  c<╮╯   │   ╭>╰ c ╭>x₃╯╭─>c ─╯
 ╰───↓│──↓──╯  │    │   ╰───↓╭╯─↓───↓─│─╮  │   ╰───↓╭╯──↓─┼──↓──╮
     x╯╭>c₁────╯    │       x╯╭>c╮╭>c₂┼─╯  │       x₄╭> c ╯╭>c──╯
     ↓ │            │       ↓╭╯ ↓╰┼───╯    │       ↓╭╯  ↓ ╭╯ ↓
     c₀╯            │       c╯╭>c₁╯        │       c╯╭> c ╯╭>x₂
                    │       ↓ │            │       ↓ │  ↓ ╭╯
                    │       c₀╯            │       c ╯╭>x₁╯
                    │                      │       ↓  │
                    │                      │       x₀ ╯

As you can see the construction takes all end nodes with a subscript and append a new node matching the next character.  The subscript value is moved to the appended node.  If a child already exists with the same matching character this child becomes the new end node with the subscript value.

All nodes which matches a suffix (end nodes) lie on a (the outermost) suffix link chain as you can see in the above diagram.  So appending a new character becomes following the suffix link chain which is O(i) for a suffix tree which matches i suffixes.  To construct the whole tree for input length n we need the time O(1+2+3+...+n) which is O(n*n).

1.  Node matches x characters

To be able to optimize the building process we introduce nodes which can store more than one character.  This allows us to forbid “characters chains” c->c->x where a node has only one child.  Every node has therefore at least two childs or it is a leaf (with no childs).

The characters are not stored in the nodes only start and end pointers into to the input string.  Therefore creating a node is possible in constant time and not dependant on the length of contained characters.

2.  End nodes become leaves and always match a whole suffix

A leaf matches all characters from its first matching character (offset i) until the end of string This allows us to ignore end nodes after creation except if we need to split them.  Also a leaf node does not have a suffix pointer cause you never follow it.

3.  To understand the optimized algorithm from Ukkonen we need to understand that only nodes (not leaves) of the unoptimized version needs to be updated.  The optimized version does no create a node for every single character.  Therefore a node can implicitly be represented as a prefix of length p from a node or leave which matches more than p characters.

Such nodes (or leaves) must be split so that only the prefix becomes represented in a newly created node and the remainder of the string is matched in the old (splitted) node.

4.  Every added character now checks a node if either the next character of the matching string in the node equals the new added character or if it has a child matching this character.  If not the node is split if necessary and a leave is added.  Noew the next suffix is checked by following the suffix link and the whole step is repeated until root is reached or a node found which already has a child matching the added character.

5.  Our tree only grows by a possible splitting of a node and creating a new leaf.  So having a leaf we never have to update it except if it has to be splitted and a prefix of becomes a node.  It suffices for the algorithm the remember only the last position (possibly root) where it stopped and begin from this position again adding the following character.

6.  For every node created through splitting its suffix pointer is computed.  Which is done in the next iteration of the loop in step 4.

In the following diagram the sequence ‘--^’ marks the position in the tree where the next step will insert the next character.

[1] add "ccxccxccc" │  [2] add "ccxccxccc" │  [3] add "ccxccxccc"
         ^          │            ^         │             ^
    *╮              │      *               │      *╮──────────╮
  --^↓              │      ↓               │    --^↓          ↓
     ccxccxccc₀     │      ccxccxccc₀      │    ╭─>c─────────╮xccxccc₂<╮
                    │    --^               │    │  ↓         ↓         │
                    │                      │    ╰  cxccxccc₀ xccxccc₁──╯

The first step adds the whole string which is a suffix of itself as leaf to the tree.  Cause we have added it to the root we are ready.  In the next step we add “c” which is is the first character of the already added leaf and therefore we need to do nothing except to move our position ‘--^’ to this first character.  In the third step we add x.  The following character of our current position is ‘c’ so we have to split the leaf into node ‘c’ and leaf ‘cxccxccc₀’.  Then we add a new leaf ‘xccxccc₁’ and follow the suffix link of the parent of node ‘c’ (node ‘c’ has an empty suffix link after the split operation).  The parent of ‘c’ is the root node so it has no suffix link and therefore we skip the first character from our current position ‘c’ and follow root with ‘’ which is root.  Then we check if root contains a child beginning with ‘x’.  It does not so we add a new leaf to root (the same as before except it matches at position 2).  The position is root so we are ready.

[4] add "ccxccxccc"      │  [5] add "ccxccxccc"     │  [6] add "ccxccxccc"
            ^            │               ^          │                ^
    *───────────╮        │      *──────────╮        │      *──────────╮
    ↓           ↓        │      ↓          ↓        │      ↓          ↓
    c╮─────────╮xccxccc₂ │      c─────────╮xccxccc₂ │      c─────────╮xccxccc₂
  --^↓         ↓         │      ↓         ↓         │      ↓         ↓
     cxccxccc₀ xccxccc₁  │      cxccxccc₀ xccxccc₁  │      cxccxccc₀ xccxccc₁
                         │    --^                   │     --^

The steps 4 up to 6 are simple they move only the position in the tree.

[7] add "ccxccxccc"      │  [8] add "ccxccxccc"     │  [9] add "ccxccxccc"
               ^         │                  ^       │                   ^
    *───────────╮        │      *──────────╮        │    *───────────────╮
    ↓           ↓        │      ↓          ↓        │    ↓               ↓
    c─────────╮ xccxccc₂ │      c─────────╮xccxccc₂ │    c───────╮  ╭──> xcc───╮
    ↓         ↓          │      ↓         ↓         │    ↓       ↓ ╭╯    ↓     ↓
    cxccxccc₀ xccxccc₁   │      cxccxccc₀ xccxccc₁  │ ╭──c───╮╭─>xcc───╮ xccc₂ c₅
    --^                  │       --^                │ ↓--^╭──↓╯  ↓     ↓
                         │                          │ xcc─╯─╮c₆  xccc₁ c₄
                         │                          │ ↓     ↓
                         │                          │ xccc₀ c₃

Steps 7 and 8 only move the position in the tree.  Step 9 is more interesting.  It is shown in the next diagrams splitted into 5 substeps.

[9.1] add "ccxccxccc"    │  [9.2] add "ccxccxccc"   │  [9.3] add "ccxccxccc"
                   ^     │                     ^    │                     ^
    *──────────╮         │      *──────────╮        │      *──────────────╮
    ↓          ↓         │      ↓          ↓        │      ↓              ↓
    c─────────╮xccxccc₂  │      c──────╮   xccxccc₂ │      c──────╮  ╭──> xcc───╮
    ↓         ↓          │      ↓      ↓   --^      │      ↓  ╭─╮ ↓ ╭╯    ↓     ↓
    cxcc──╮   xccxccc₁   │   ╭──cxcc──>xcc───╮      │   ╭─ cxcc ╰>xcc───╮ xccc₂ c₅
    ↓     ↓   --^        │   ↓     ↓   ↓     ↓      │   ↓--^  ↓   ↓     ↓
    xccc₀ c₃             │   xccc₀ c₃  xccc₁ c₄     │   xccc₀ c₃  xccc₁ c₄

The first substep splits the node where the currrent position is set in step 8.  A new leaf is added.  The suffix “cxcc” is followed which defines the new position in the tree.  Substep 2 splits the node the current position points to into node “xcc” and leave “xccc”.  A new leaf is added to “xcc”.  The suffix “xcc” is followed which defines the new position in the tree.  Substep 3 splits the node the current position points to into node “xcc” and leave “xccc”.  A new leaf is added to “xcc”.  Then the suffix pointer from the created in node in step 2 is set to the new created node.  The suffix “cc” is followed which defines the new position in the tree.

[9.4] add "ccxccxccc"       │  [9.5] add "ccxccxccc"
                   ^        │                     ^
   *───────────────╮        │    *───────────────╮
   ↓╭─────────────╮↓        │    ↓               ↓
   c┼──────╮  ╭──>xcc ───╮  │  ╭>c───────╮  ╭──> xcc───╮
--^↓↓      ↓ ╭╯    ↓     ↓  │  ╰╮↓       ↓ ╭╯    ↓     ↓
╭─ c───╮╭─>xcc───╮ xccc₂ c₅ │ ╭─╰c───╮╭─>xcc───╮ xccc₂ c₅
↓ ╭────↓╯  ↓     ↓          │ ↓--^╭──↓╯  ↓     ↓
xcc───╮c₆  xccc₁ c₄         │ xcc─╯─╮c₆  xccc₁ c₄
↓     ↓                     │ ↓     ↓
xccc₀ c₃                    │ xccc₀ c₃

Substep 4 split node “cxcc” into nodes “c” and “xcc”.  A new leaf is added to “c” and the suffix pointer from the node created in step 3 is set to point to node “c”.  The suffix “c” is followed which defines the new position in the tree.  Substep 5 need not to split the node and checks its childs.  A child with “c” exists so the alogithm ends here.  The suffix pointer from the node created in step 4 is set to point to “c”.

The algorithm has created only leaves 0-6.  The leaves matching position 7 and 8 were not created.  To create them an explicit end-marker (empty string ‘’) is added in step 10.

[10] add "ccxccxccc"
                   ^
          *───────────────╮
       --^↓               ↓
╭───────╭>c───────╮  ╭──> xcc───╮
↓       ╰╮↓       ↓ ╭╯    ↓     ↓
''₈╭───╭─╰c───╮╭─>xcc───╮ xccc₂ c₅
   ↓   ↓   ╭──↓╯  ↓     ↓
   ''₇ xcc─╯─╮c₆  xccc₁ c₄
       ↓     ↓
      xccc₀ c₃

The end-marker which never occurs in the string adds a new leave to the node pointed to by the current position (see step 9.5).  Then it follow the suffix “c” and adds another leave.  The suffix “” is the root but no end-marker is added to the root.  Having reached the root ends the algorithm.