Class SuffixTreeNode.Intermediate
Builds an intermediate node, i.e. a node with children and their corresponding incoming edges.
Inherited Members
Namespace: MoreStructures.SuffixTrees
Assembly: MoreStructures.dll
Syntax
public class Intermediate : SuffixTreeNode, ISuffixStructureNode<SuffixTreeEdge, SuffixTreeNode>, IRecImmDictIndexedTreeNode<SuffixTreeEdge, SuffixTreeNode>, IEquatable<SuffixTreeNode>, IEquatable<SuffixTreeNode.Intermediate>Constructors
| Improve this Doc View SourceIntermediate(IDictionary<SuffixTreeEdge, SuffixTreeNode>)
Builds an intermediate node, i.e. a node with children and their corresponding incoming edges.
Declaration
public Intermediate(IDictionary<SuffixTreeEdge, SuffixTreeNode> Children)Parameters
| Type | Name | Description |
|---|---|---|
| IDictionary<SuffixTreeEdge, SuffixTreeNode> | Children |
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 override 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. |
Overrides
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).