Class SuffixTreeNode
An immutable node of an immutable Suffix Tree, recursively pointing to its children nodes via SuffixTreeEdge instances, associated with selector strings.
Implements
Inherited Members
Namespace: MoreStructures.SuffixTrees
Assembly: MoreStructures.dll
Syntax
public abstract class SuffixTreeNode : ISuffixStructureNode<SuffixTreeEdge, SuffixTreeNode>, IRecImmDictIndexedTreeNode<SuffixTreeEdge, SuffixTreeNode>, IEquatable<SuffixTreeNode>Remarks
ADVANTAGES AND DISADVANTAGES
Suffix Trees are more space-efficient than Suffix Tries due to the reduced number of
SuffixTreeEdge and their SuffixTreeNode, compare to the corresponding
SuffixTrieEdge and their SuffixTrieNode, due to entire
paths of single chains of chars in Suffix Tries being coalesced into a single selector string, which is stored
on the edge with path label compression, i.e. using two fixed sized numbers (Start
and Length) instead of a variable-length string of characters.
Furthermore, suffix trees, unlike suffix tries, can be constructed in linear time, for example via the
UkkonenSuffixTreeBuilder.
IMMUTABILITY
Immutability is guaranteed by using ValueReadOnlyCollection<T>.
Constructors
| Improve this Doc View SourceSuffixTreeNode(IDictionary<SuffixTreeEdge, SuffixTreeNode>, Nullable<Int32>)
An immutable node of an immutable Suffix Tree, recursively pointing to its children nodes via SuffixTreeEdge instances, associated with selector strings.
Declaration
protected SuffixTreeNode(IDictionary<SuffixTreeEdge, SuffixTreeNode> Children, int? Start)Parameters
| Type | Name | Description |
|---|---|---|
| IDictionary<SuffixTreeEdge, SuffixTreeNode> | Children | The collection of children for the node, indexed by string edges. |
| System.Nullable<System.Int32> | Start |
Remarks
ADVANTAGES AND DISADVANTAGES
Suffix Trees are more space-efficient than Suffix Tries due to the reduced number of
SuffixTreeEdge and their SuffixTreeNode, compare to the corresponding
SuffixTrieEdge and their SuffixTrieNode, due to entire
paths of single chains of chars in Suffix Tries being coalesced into a single selector string, which is stored
on the edge with path label compression, i.e. using two fixed sized numbers (Start
and Length) instead of a variable-length string of characters.
Furthermore, suffix trees, unlike suffix tries, can be constructed in linear time, for example via the
UkkonenSuffixTreeBuilder.
IMMUTABILITY
Immutability is guaranteed by using ValueReadOnlyCollection<T>.
Properties
| Improve this Doc View SourceChildren
A readonly view of the children private collection of this node. Empty for leaves.
Declaration
public IDictionary<SuffixTreeEdge, SuffixTreeNode> Children { get; }Property Value
| Type | Description |
|---|---|
| IDictionary<SuffixTreeEdge, SuffixTreeNode> |
Item[SuffixTreeEdge]
Indexes into the children of this node, by edge.
Declaration
public SuffixTreeNode this[SuffixTreeEdge edge] { get; }Parameters
| Type | Name | Description |
|---|---|---|
| SuffixTreeEdge | edge |
Property Value
| Type | Description |
|---|---|
| SuffixTreeNode |
Start
The index of the character, the path from the root leading to this leaf starts with. Non-null for leaves only.
Declaration
public int? Start { get; }Property Value
| Type | Description |
|---|---|
| System.Nullable<System.Int32> |
Methods
| Improve this Doc View SourceIsEquivalentTo(SuffixTreeNode, TextWithTerminator[])
Determines whether this SuffixTreeNode structure is equivalent to the provided
other structure, w.r.t. the provided texts.
Declaration
public abstract bool IsEquivalentTo(SuffixTreeNode other, params TextWithTerminator[] texts)Parameters
| Type | Name | Description |
|---|---|---|
| SuffixTreeNode | other | The other tree, to compare this tree against. |
| TextWithTerminator[] | texts | The text, based on which to evaluate the tree equivalence. |
Returns
| Type | Description |
|---|---|
| System.Boolean | True if the two trees are equivalent for the provided text, false otherwise. |
Remarks
DEFINITION
The definition of SuffixTreeNode structures equivalence depends on (a list of)
TextWithTerminator: two trees can be equivalent for some texts, and not equivalent
for others. This is because of the Edge Compression technique used by
SuffixTreeEdge, to store edges in O(1) space, instead of O(n).
Moreover, equivalence is based on the equivalence of edges and of the specific type of node.
- Two SuffixTreeEdge E1 and E2 are equivalent w.r.t. a TextWithTerminator T,
if the string identified by each edge is the same: T[E1] == T[E2].
- Two SuffixTreeNode.Leaf L1 and L2 are equivalent if their LeafStart is the same:
L1.LeafStart == L2.LeafStart.
- Two SuffixTreeNode.Intermediate I1 and I2 are equivalent if there is a 1-to-1 correspondence between
children edges and child nodes pointed by such edges are equivalent:
for each edge e1 of I1.Children there exists exactly one equivalent edge e2 of I2.Children and
I1.Children[e1] is equivalent to I2.Children[e2] w.r.t. T.
COMPLEXITY
- Checking for edges equivalence is a O(n) operation, where n is the number of nodes in the tree, since it
requires decompressing the labels of each of the edges being compare and compare for equality the two
resulting O(n) strings.
- Checking for leaves equivalence is a O(1) operation, since it only requires comparing
LeafStart, which has constant size.
- Checking for intermediate nodes equivalence is a O(n) operation, amortized cost over the total number of
edges in the tree, since there are O(n) edges in total in the tree, an edge is visited multiple times
but always in the context of a single node, and the node equivalence check requires looking for the
equivalent edge.
- In conclusion Time Complexity is O(n^2) and Space Complexity is O(n).
ToString()
Uses a IStringifier<TEdge, TNode> to generate the string which show the node and its
underlying structure.
Declaration
public sealed override string ToString()Returns
| Type | Description |
|---|---|
| System.String |
Overrides
Remarks
Sealed to prevent compiler from superceding ToString() in derived record.