Class NaiveFinder

A ILastFirstFinder implementation which just iterates over BWT and its sorted version SortedBWT every time.

Inheritance
System.Object
NaiveFinder
BinarySearchFinder
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.BurrowsWheelerTransform.Builders.LastFirstFinders
Assembly: MoreStructures.dll
Syntax
public class NaiveFinder : ILastFirstFinder
Remarks

Each operation has Time Complexity = O(n) and Space Complexity = O(1), since no additional structure is precomputed and/or stored.

Constructors

| Improve this Doc View Source

NaiveFinder(RotatedTextWithTerminator, RotatedTextWithTerminator)

Builds an instance of this finder, for the provided lastBWMColumn and firstBWMColumn. Because both columns of the BWM are provided, no sorting happens.

Declaration
public NaiveFinder(RotatedTextWithTerminator lastBWMColumn, RotatedTextWithTerminator firstBWMColumn)
Parameters
Type Name Description
RotatedTextWithTerminator lastBWMColumn

The last column of the Burrows-Wheeler Matrix. Corresponds to the BWT.
RotatedTextWithTerminator firstBWMColumn

The first column of the Burrows-Wheeler Matrix. Corresponds to the SortedBWT.

Properties

| Improve this Doc View Source

BWT

The Burrows-Wheeler Transform. Also, the last column of the Burrows-Wheeler Matrix.

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

CharComparer

The used to compare chars of BWT or SortedBWT.

Declaration
public IComparer<char> CharComparer { get; }
Property Value
Type Description
IComparer<System.Char>
Remarks

The of System.Char cannot be used because the terminator in BWT and SortedBWT has to be treated in a special way (Terminator is always to be considered smaller than any other char: as such it always appears in first position in the SortedBWT).

| Improve this Doc View Source

SortedBWT

The sorted version of the Burrows-Wheeler Transform. Also, the first column of the Burrows-Wheeler Matrix.

Declaration
public RotatedTextWithTerminator SortedBWT { get; }
Property Value
Type Description
RotatedTextWithTerminator

Methods

| Improve this Doc View Source

FindIndexOfNthOccurrenceInBWT(Int32, Int32)

Declaration
public virtual int FindIndexOfNthOccurrenceInBWT(int indexOfCharInBWT, int occurrenceRank)
Parameters
Type Name Description
System.Int32 indexOfCharInBWT
System.Int32 occurrenceRank
Returns
Type Description
System.Int32
Remarks

This implementation just iterates over BWT every time.
Time Complexity = O(n). Space Complexity = O(1).

| Improve this Doc View Source

FindIndexOfNthOccurrenceInSortedBWT(Int32, Int32)

Declaration
public virtual int FindIndexOfNthOccurrenceInSortedBWT(int indexOfCharInBWT, int occurrenceRank)
Parameters
Type Name Description
System.Int32 indexOfCharInBWT
System.Int32 occurrenceRank
Returns
Type Description
System.Int32
Remarks

This implementation just iterates over SortedBWT every time.
Time Complexity = O(n). Space Complexity = O(1).

| Improve this Doc View Source

FindOccurrenceRankOfCharInBWT(Int32)

Declaration
public virtual int FindOccurrenceRankOfCharInBWT(int indexOfCharInBWT)
Parameters
Type Name Description
System.Int32 indexOfCharInBWT
Returns
Type Description
System.Int32
Remarks

This implementation just iterates over BWT every time.
Time Complexity = O(n). Space Complexity = O(1).

| Improve this Doc View Source

FindOccurrenceRankOfCharInSortedBWT(Int32)

Declaration
public virtual int FindOccurrenceRankOfCharInSortedBWT(int indexOfCharInSortedBWT)
Parameters
Type Name Description
System.Int32 indexOfCharInSortedBWT
Returns
Type Description
System.Int32
Remarks

This implementation just iterates over SortedBWT every time.
Time Complexity = O(n). Space Complexity = O(1).

| Improve this Doc View Source

LastToFirst(Int32)

Declaration
public virtual (int indexInSortedBWT, int occurrenceRank) LastToFirst(int indexOfCharInBWT)
Parameters
Type Name Description
System.Int32 indexOfCharInBWT
Returns
Type Description
System.ValueTuple<System.Int32, System.Int32>
Remarks

First executes FindOccurrenceRankOfCharInBWT(Int32), to find the occurrence rank of the char at index indexOfCharInBWT and then uses the last-to-first property to find the corresponding char in SortedBWT by using FindIndexOfNthOccurrenceInSortedBWT(Int32, Int32).
Time and Space Complexity depends on the implementation of FindOccurrenceRankOfCharInBWT(Int32) and FindIndexOfNthOccurrenceInSortedBWT(Int32, Int32).

Implements

Extension Methods