Class IndexModKPartialSuffixArrayAgainstPatternComparer

A SuffixAgainstPatternComparer which uses the provided MoreStructures.SuffixArrays.IndexModKPartialSuffixArray to find the suffix of the provided Text, to compare against the provided Pattern.

Inheritance
System.Object
SuffixAgainstPatternComparer
IndexModKPartialSuffixArrayAgainstPatternComparer
Inherited Members
Namespace: MoreStructures.BurrowsWheelerTransform.Matching.Comparers
Assembly: MoreStructures.dll
Syntax
public class IndexModKPartialSuffixArrayAgainstPatternComparer : SuffixAgainstPatternComparer
Remarks

- This is a generalization of SuffixArrayAgainstPatternComparer, which also supports Partial Suffix Arrays, i.e. Suffix Arrays with incomplete information, and in particular Partial Suffix Arrays of type MoreStructures.SuffixArrays.IndexModKPartialSuffixArray.
- When K = 1, an instance of MoreStructures.SuffixArrays.IndexModKPartialSuffixArray contains the index of all suffixes, and is equivalent to a MoreStructures.SuffixArrays.SuffixArray.

ALGORITHM
- Start from the index I(0) = first term of comparison passed to Compare(Int32, Int32).
- Perform Last-First mapping from I(i) to I(i+1) from BWT to Sorted BWT, until the index I(i) is present in the Partial Suffix Array. While mapping, accumulate all indexes I(0), I(1), ... into a list I.
- Once such index I(n) is found, iterate over I in reverse order, updating the Partial Suffix Array, from I(n) all the way back to I(0).
- Finally, invoke CompareSuffixAgainstPattern(Int32, Int32) on the value of the Partial Suffix Array at index I(0).

COMPLEXITY
- There are at most K iterations, where K is the modulo of the Partial Suffix Array: at each iteration, the Last-First mapping finds the index I(i+1), in the Sorted BWT, of a suffix which augments the previous suffix by 1 (prepending a single char).
- So there are at most K iterations to update the Partial Suffix Array with I(n), I(n-1), ... I(0). The Partial Suffix Array ends up having at most n elements (1 per suffix of the text).
- Finally, there is CompareSuffixAgainstPattern(Int32, Int32).
- Therefore, Time Complexity is O(n * K) and Space Complexity is O(n).

Constructors

| Improve this Doc View Source

IndexModKPartialSuffixArrayAgainstPatternComparer(TextWithTerminator, IndexModKPartialSuffixArray, IEnumerable<Char>, RotatedTextWithTerminator, RotatedTextWithTerminator)

Declaration
public IndexModKPartialSuffixArrayAgainstPatternComparer(TextWithTerminator text, IndexModKPartialSuffixArray partialSuffixArray, IEnumerable<char> pattern, RotatedTextWithTerminator bwt, RotatedTextWithTerminator sbwt)
Parameters
Type Name Description
TextWithTerminator text

The text, to extract suffixes from via partialSuffixArray.
MoreStructures.SuffixArrays.IndexModKPartialSuffixArray partialSuffixArray

The Partial Suffix Array of text, to map (when the Partial Suffix Array contains such item) the first term of comparison to the starting index in text of the corresponding suffix.
IEnumerable<System.Char> pattern

The pattern, to compare against each suffix of text.
RotatedTextWithTerminator bwt

The Burrows-Wheeler Transform of text. Required to instantiate a ILastFirstFinder, to fill-in the gaps of the partialSuffixArray.
RotatedTextWithTerminator sbwt

The sorted version of bwt. Required to instantiate a ILastFirstFinder, to fill-in the gaps of the partialSuffixArray.

Methods

| Improve this Doc View Source

Compare(Int32, Int32)

Compares the suffix of text identified by the x-th element of the Suffix Array, against the pattern. Covers the gap in the provided MoreStructures.SuffixArrays.IndexModKPartialSuffixArray by iteratively using the Last-First Property between BWT and its Sorted version.

Declaration
public override int Compare(int x, int y)
Parameters
Type Name Description
System.Int32 x
System.Int32 y
Returns
Type Description
System.Int32
Overrides
Remarks

Extension Methods