API Documentation
\
Sax
SuffixTree

\Sax\SuffixTreeSuffixTree

Handles creation of the suffix tree.

Based on the implementation of makagonov on http://stackoverflow.com/a/14580102

Summary

Methods
Properties
Constants
__construct()
getSurpriseValue()
getAllSurpriseValues()
hasSubstring()
getOccurence()
__toString()
$nodes
$root
$text
No constants found
No protected methods found
No protected properties found
N/A
build()
addSuffixLink()
getActiveEdge()
walkDown()
newNode()
addChar()
findSurpriseValue()
findSubstring()
$upperBound
$position
$currentNode
$needSuffixLink
$remainder
$activeNode
$activeLength
$activeEdge
N/A

Properties

$nodes

$nodes : array

All nodes of the tree

Type

array

$root

$root : integer

Index of root node

Type

integer

$text

$text : string

String on which this tree is built

Type

string

$upperBound

$upperBound : integer

Representing infinitive

Type

integer

$position

$position : integer

Current position in $text

Type

integer

$currentNode

$currentNode : integer

Index of current node in $nodes

Type

integer

$needSuffixLink

$needSuffixLink : integer

If a node needs a suffix link

Type

integer

$remainder

$remainder : integer

Size of remainder

Type

integer

$activeNode

$activeNode : integer

Index of the node from where a new suffix gets inserted

Type

integer

$activeLength

$activeLength : integer

Length of active edge

Type

integer

$activeEdge

$activeEdge : integer

Index in $text where current active

Type

integer

Methods

__construct()

__construct(string  $pString)

Instantiate new SuffixTree.

Parameters

string $pString

String of which the suffix tree should be built

getSurpriseValue()

getSurpriseValue(string  $pSubstring) : float

Get surprise value of a substring of this tree

Parameters

string $pSubstring

Substring to get surprise value off

Returns

float —

Surprise value for the given substring

getAllSurpriseValues()

getAllSurpriseValues() : array

Returns an array containing the surprise values of each node of this tree.

Returns

array —

The array

hasSubstring()

hasSubstring(string  $pSubstring) : integer

Scan tree for occurences of the given substring.

Parameters

string $pSubstring

String to check whether it is contained or not

Returns

integer —

Returns 1 if found, -1 if not

getOccurence()

getOccurence(string  $pSubstring) : integer

Returns the amount of occurences of the given string in the suffix tree.

Use hasSubstring($pSubstring) to check, if the given string is contained in the suffix tree.

Parameters

string $pSubstring

String to get the amount of occurences

Returns

integer —

Returns -1, if length of $pSubstring is greater

                                than the string represented by the suffix tree.
                                Else returns the amount of occurences of the
                                given string.

__toString()

__toString() : string

Prints a simple representation of this suffix tree

Returns

string —

String to print.

build()

build(string  $pString)

Builds the suffix tree off the given string

Parameters

string $pString

String to build the suffix tree of

addSuffixLink()

addSuffixLink(integer  $pNode)

Adds the given node as target of the current suffix link

Parameters

integer $pNode

Index of target node of the suffix link

getActiveEdge()

getActiveEdge() : string

Returns the first character of the active edge

Returns

string —

The first character on the active edge

walkDown()

walkDown(integer  $pNext) : boolean

Update active triple consisting of ( activeEdge, activeLength, activeNode )

Parameters

integer $pNext

Index of node on which to walk down.

Returns

boolean —

true, if walked down, otherwise false

newNode()

newNode(integer  $pStart, integer  $pEnd) : integer

Creates as new node with given start and end indexes. Increases the current node by one.

Parameters

integer $pStart

Start index of node in string represented

                    by this tree
integer $pEnd

End index of node in string represented

                    by this tree

Returns

integer —

Index of the current node

addChar()

addChar(string  $pChar)

Adds a single character to the suffix tree.

Updates edges as well as nodes

Parameters

string $pChar

A single character

findSurpriseValue()

findSurpriseValue(\Sax\SuffixTree\Node  $pNode, string  $pSubstring) : integer

Tries to find the surprise value of the given substring in the given node.

If not successfull for the given string and a child node starts with the first letter of the given string, it will try its corresponding child. Used in a recursive manner with given node representing the root node at the begin

Parameters

\Sax\SuffixTree\Node $pNode

Node on which to try to find the given substring
string $pSubstring

String to get occurences of

Returns

integer —

Amount of surprise for the given substring

findSubstring()

findSubstring(\Sax\SuffixTree\Node  $pNode, string  $pSubstring) : integer

Tries to find parts of the given substring on the edge to the given node.

If successfull, the part of the given node is cutted of the substring. Children ( if any ), will continue finding the rest of the substring. Used in a recursive manner with given node representing the root node at the begin

Parameters

\Sax\SuffixTree\Node $pNode

Node on which to try to find the given substring
string $pSubstring

String to get occurences of

Returns

integer —

Amount of surprise for the given substring