Class SuffixStructureBasedSuffixArrayBuilder<TEdge, TNode>

An algorithm for building the MoreStructures.SuffixArrays.SuffixArray from an already built ISuffixStructureNode<TEdge, TNode> structure for the provided TextWithTerminator.

Inheritance
System.Object
SuffixStructureBasedSuffixArrayBuilder<TEdge, TNode>
Implements
Inherited Members
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.ToString()
Namespace: MoreStructures.SuffixArrays.Builders
Assembly: MoreStructures.dll
Syntax
public class SuffixStructureBasedSuffixArrayBuilder<TEdge, TNode> : ISuffixArrayBuilder where TEdge : ISuffixStructureEdge<TEdge, TNode> where TNode : ISuffixStructureNode<TEdge, TNode>
Type Parameters
Name Description
TEdge

The type of edges of the specific structure.
TNode

The type of nodes of the specific structure.
Remarks

The Suffix Tree for the text "mississippi$" is: 

R
- $ (11)
- i
  - $ (10)
  - ssi
    - p..$ (7)
    - s..$ (4)
- m..$ 
- ...
A DFS visit of the leaves of the tree, navigating edges in lexicographic order, gives { 11, 10, 7, 4, ... }, which is the MoreStructures.SuffixArrays.SuffixArray of "mississippi$".

- The Suffix Tree of the text is provided as input, and the complexity of building or keeping it in memoery is not considered here.
- The DFS of the Tree is linear in m, where m is the number of nodes in the Suffix Tree. m is O(n) for Suffix Trees and O(n^2) for Suffix Tries, where n is the length of the text.
- While DFS itself is linear in m, edges have to be sorted in lexicographic order, which is done via the LINQ method.
- There are O(m) edges in the tree, so sorting can be O(m * log(m)) if the alphabet of the text is O(n), using QuickSort or similar, and O(m) if the alphabet is constant w.r.t. to n, using Counting Sort or similar.
- For each visited node, constant work is done: checking whether the node is a leaf and potentially returning it.
- Therefore Time Complexity is O(n^2 * log(n)) for a Suffix Trie with a non-constant alphabet, O(n^2) for a Suffix Trie with a constant alphabet, O(n * log(n)) for a Suffix Tree with a non-constant alphabet and O(n) for a Suffix Tree with a constant alphabet.
- Space Complexity is dominated by the space required to sort edges in lexicographic order, before visiting them in DFS: O(n^2) for a Suffix Trie and O(n) for a Suffix Tree.

Constructors

| Improve this Doc View Source

SuffixStructureBasedSuffixArrayBuilder(TextWithTerminator, TNode)

Declaration
public SuffixStructureBasedSuffixArrayBuilder(TextWithTerminator text, TNode node)
Parameters
Type Name Description
TextWithTerminator text

TNode node

Properties

| Improve this Doc View Source

Node

The root node of the ISuffixStructureNode<TEdge, TNode> structure, to build the MoreStructures.SuffixArrays.SuffixArray of.

Declaration
public TNode Node { get; }
Property Value
Type Description
TNode
| Improve this Doc View Source

Text

The TextWithTerminator, to build the MoreStructures.SuffixArrays.SuffixArray of.

Declaration
public TextWithTerminator Text { get; }
Property Value
Type Description
TextWithTerminator

Methods

| Improve this Doc View Source

Build()

Builds the MoreStructures.SuffixArrays.SuffixArray for .

Declaration
public SuffixArray Build()
Returns
Type Description
MoreStructures.SuffixArrays.SuffixArray

Implements

Extension Methods