Class SuffixStructureBasedSnssFinder

Base class for all ISnssFinder concretions which implement Find(IEnumerable<Char>, IEnumerable<Char>) using a suffix structure (a concretions of ISuffixStructureNode<TEdge, TNode>, implementing IRecImmDictIndexedTreeNode<TEdge, TNode>), such as SuffixTreeNode or SuffixTrieNode).

Inheritance
System.Object
SuffixStructureBasedSnssFinder
SuffixTreeBasedSnssFinder
SuffixTrieBasedSnssFinder
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.SuffixStructures.Matching
Assembly: MoreStructures.dll
Syntax
public abstract class SuffixStructureBasedSnssFinder : ISnssFinder

Constructors

| Improve this Doc View Source

SuffixStructureBasedSnssFinder(Char, Char)

Builds an instance with the provided terminators, validating the input by default. All text passed to Find(IEnumerable<Char>, IEnumerable<Char>) must conform with these two terminators.

Declaration
protected SuffixStructureBasedSnssFinder(char terminator1, char terminator2)
Parameters
Type Name Description
System.Char terminator1

System.Char terminator2

Properties

| Improve this Doc View Source

Terminator1

A special char to be used as end delimiter for the first text, used for building the suffix structure. Should not occur in first text, nor in the second, since a single suffix structure is built, embedding both texts (a.k.a. generalized suffix structure).

Declaration
public char Terminator1 { get; }
Property Value
Type Description
System.Char
| Improve this Doc View Source

Terminator2

A special char to be used as end delimiter for the second text, used for building the suffix structure. Should not occur in first text, nor in the second, since a single suffix structure is built, embedding both texts (a.k.a. generalized suffix structure).

Declaration
public char Terminator2 { get; }
Property Value
Type Description
System.Char
| Improve this Doc View Source

ValidateInput

Whether the two sequences of chars (first and second text) should be evaluated, in order to make sure that are valid, i.e. they don't contain Terminator1 nor Terminator2. By default set to true.

Declaration
public bool ValidateInput { get; set; }
Property Value
Type Description
System.Boolean

Methods

| Improve this Doc View Source

CollectPrefixChars<TEdge, TNode>(TextWithTerminator, TNode, IDictionary<TNode, TreeTraversalVisit<TEdge, TNode>>)

Rebuilds the root-to-node prefix, from initialNode up to the root of the Suffix Tree (node with no parent), using the provided cache of visited nodes, cachedVisits, to navigate the Suffix Tree upwards.

Declaration
protected static IEnumerable<string> CollectPrefixChars<TEdge, TNode>(TextWithTerminator text, TNode initialNode, IDictionary<TNode, TreeTraversalVisit<TEdge, TNode>> cachedVisits)
    where TEdge : IRecImmDictIndexedTreeEdge<TEdge, TNode>, TextWithTerminator.ISelector where TNode : IRecImmDictIndexedTreeNode<TEdge, TNode>
Parameters
Type Name Description
TextWithTerminator text

The text used to generate the Suffix Tree, and to be used to rebuild the prefix.
TNode initialNode

The node, to start navigating from.
IDictionary<TNode, TreeTraversalVisit<TEdge, TNode>> cachedVisits

A dictionary of visits by node, to jump from a node to its parent.
Returns
Type Description
IEnumerable<System.String>

A lazily generated sequence of strings, corresponding to the edges from initialNode up to the root of the Suffix Tree. Empty if initialNode is the root of the tree.
Type Parameters
Name Description
TEdge
TNode
| Improve this Doc View Source

Find(IEnumerable<Char>, IEnumerable<Char>)

Returns any substring of text1 which is not present in text2 and has minimal length. Returns null if there is no substring of text1 which is not a substring of text2, i.e. if the two string coincide.

Declaration
public abstract IEnumerable<string> Find(IEnumerable<char> text1, IEnumerable<char> text2)
Parameters
Type Name Description
IEnumerable<System.Char> text1

The sequence of chars of the first text.
IEnumerable<System.Char> text2

The sequence of chars of the second text.
Returns
Type Description
IEnumerable<System.String>

A sequence of strings, each being a substring of text1 not in text2, of minimal length.
| Improve this Doc View Source

ValidateTexts(IEnumerable<Char>, IEnumerable<Char>)

Validates the provided texts against this finder, checking that they are compatible with Terminator1 and Terminator2.

Declaration
protected void ValidateTexts(IEnumerable<char> text1, IEnumerable<char> text2)
Parameters
Type Name Description
IEnumerable<System.Char> text1

The first text to validate.
IEnumerable<System.Char> text2

The second text to validate.

Implements

Extension Methods