Class TreeBuilder

java.lang.Object
  TreeBuilder

public final class TreeBuilder

extends java.lang.Object

Used to build the tree; the tree structure itself is very simple. Implements Ukkonen algorithm.

Field Summary

private java.util.LinkedList	current the current node; it is always the node where the substring S[ j..i] ends (where j is the index of the previous phase)
private java.lang.String	gamma if the current internal node was just inserted, it does not have a suffix link attached to it; in this case, we have to remeber the string that labels the branch leading to this node (gamma will be followed down from the node at the end of the suffix link starting form the parent of this node
private int	gammaLen store the gamma length, so that we don't have to call gamma.length() each time (expensive)
private int	lastExtPhase records the last extension phase, so that we know where to start form when inserting a new suffix in the tree
private SuffixTree	myTree the tree in which the string is added
private int	noNodes number of nodes added to the tree during the insertion of this string
private java.util.LinkedList	previous preserves the internal node that was previously added to the tree, as well as its parent this is necesary when the chain of explicit extensions ends in the current phase, so that we can restore the starting point for the next phase
private int	startPos the index of the first char ofthis string, relatively to the first char of the first string inserted in the tree
private java.lang.String	token the string that is currently inserted
private int	tokenIndex the index of the current token; it is assigned in the order of insertion of the strings in the tree
private int	tokenLen store the token length, so that we don't have to call token.length() each time (expensive)

Constructor Summary

TreeBuilder(SuffixTree tree)
Initialized always at the root of the tree, each time a new string is added to the tree.

Method Summary

void	addToken(java.lang.String token) add a string to the tree this builder is constructed for
private boolean	extend(int phase, int extension)
private boolean	findChild(char branchStart) finds the child of the current node that has branchStart as its first character; this function will succeed in finding the child since the string S[j-1..i] is already in the tree returns true if there are more branches to be followed
private void	goDown() walks down from node s(v) along the path gamma, using skip/count trick
private void	goToLastExplicit() just before ending the current phase, after an implicit extension was made
private void	goUp(int currentSuffix, int currentRightEnd) currentSuffix is the j index of the current phase, and the last explicit extension index + 1

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

current

private java.util.LinkedList current

the current node; it is always the node where the substring S[ j..i] ends (where j is the index of the previous phase)

myTree

private SuffixTree myTree

the tree in which the string is added

gamma

private java.lang.String gamma

if the current internal node was just inserted, it does not have a suffix link attached to it; in this case, we have to remeber the string that labels the branch leading to this node (gamma will be followed down from the node at the end of the suffix link starting form the parent of this node

tokenIndex

private int tokenIndex

the index of the current token; it is assigned in the order of insertion of the strings in the tree

previous

private java.util.LinkedList previous

preserves the internal node that was previously added to the tree, as well as its parent this is necesary when the chain of explicit extensions ends in the current phase, so that we can restore the starting point for the next phase

lastExtPhase

private int lastExtPhase

records the last extension phase, so that we know where to start form when inserting a new suffix in the tree

token

private java.lang.String token

the string that is currently inserted

startPos

private int startPos

the index of the first char ofthis string, relatively to the first char of the first string inserted in the tree

noNodes

private int noNodes

number of nodes added to the tree during the insertion of this string

tokenLen

private int tokenLen

store the token length, so that we don't have to call token.length() each time (expensive)

gammaLen

private int gammaLen

store the gamma length, so that we don't have to call gamma.length() each time (expensive)

Constructor Detail

TreeBuilder

public TreeBuilder(SuffixTree tree)

Initialized always at the root of the tree, each time a new string is added to the tree.

Method Detail

addToken

public final void addToken(java.lang.String token)

add a string to the tree this builder is constructed for

goUp

private void goUp(int currentSuffix,
                  int currentRightEnd)

currentSuffix is the j index of the current phase, and the last explicit extension index + 1

goDown

private void goDown()

walks down from node s(v) along the path gamma, using skip/count trick

findChild

private boolean findChild(char branchStart)

finds the child of the current node that has branchStart as its first character; this function will succeed in finding the child since the string S[j-1..i] is already in the tree returns true if there are more branches to be followed

extend

private boolean extend(int phase,
                       int extension)

goToLastExplicit

private void goToLastExplicit()

just before ending the current phase, after an implicit extension was made