INFTY
INFTY
Upper bound on the length of any path in the tree
Data structure used to maintain a suffix tree for a passage of words.
The suffix tree is constructed using the linear time algorithm of Ukkonen, E. (1995). "On-line construction of suffix trees". Algorithmica 14 (3): 249–260.
$need_sym_link : integer
If in a given step in constructing the suffix tree we split the active edge and insert a new node and then have to do this again in the same step, then we need to create a sym_link between the suffix trees represented by these new nodes. This variable keeps track of the index of the first node so we can do this.
makeNode(integer $start, integer $end = self::INFTY)
Makes a new node for the suffix tree structure. This node is inserted at the end of the tree so far. A node is associative array consisting of the fields "start" whose value is the starting location in $this->text for this node, "end" location in $this->text up to which this node is responsible, "sym_link" is a link to an isomorphic subtree for the purposes of building the suffix tree, and "next" is an array of next children in the tree.
integer | $start | what to use as the start value mentioned above |
integer | $end | what to use as the start value mentioned above |
addSuffixLink(integer $index)
If in a given step in constructing the suffix tree we split the active edge and insert a new node and then have to do this again in the same step, then we need to create a sym_link between the suffix trees represented by these new nodes. If in the current step it is necessary to add a sym_link this method sets the $this->need_sym_link node's "sym_link" field to $index which is supposed be the index of the second created node.
integer | $index | the index of the a created node in a given step. ($this->need_sym_link will be greater than 0 if it is the second created node of the step) |
walkDown(integer $index) : \seekquarry\yioop\library\if
Used to set the active point to the node given by $index
integer | $index | which node to use for setting |
the current active edge is longer than $index's edge length then don't update and return false; otherwise, return true
outputMaximal(integer $index, string $path, integer $len, \seekquarry\yioop\library\array& $maximal)
Recursive function used to compute the maximal phrases in a document as well as their conditional maximal subphrases.
integer | $index | a node in the suffix tree |
string | $path | from root to current node |
integer | $len | number of nodes from root to current node in suffix tree |
\seekquarry\yioop\library\array& | $maximal | assoc array of phrase => (cond_max => pos of conditional maximal subphrase, [0] => pos_1st_occurrence of phrase, [1]=>pos_2nd_occurrence of phrase, etc) |