Class BinarySearchFinder

A NaiveFinder refinement which iterates over BWT and uses binary search on SortedBWT, taking advantage of the fact that it is sorted.

Inheritance
System.Object
NaiveFinder
BinarySearchFinder
PrecomputedFinder
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 BinarySearchFinder : NaiveFinder, ILastFirstFinder
Remarks

COMPLEXITY
- Search over BWT has Time Complexity = O(n), as it is not sorted and there's nothing better than a linear scan without precomputing additional structures helping the search.
- Search over SortedBWT has Time Complexity O(log(n)), as it is sorted and binary search can be applied.
- Space Complexity = O(1) for both search operations, as no additional structure is precomputed and/or stored.

Constructors

| Improve this Doc View Source

BinarySearchFinder(RotatedTextWithTerminator, RotatedTextWithTerminator)

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

Properties

| Improve this Doc View Source

OrderedAscListSearch

The ISearch implementation to be used when searching for items in lists sorted in ascending order.

Declaration
protected static ISearch OrderedAscListSearch { get; }
Property Value
Type Description
ISearch

Methods

| Improve this Doc View Source

FindIndexOfNthOccurrenceInSortedBWT(Int32, Int32)

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

This implementation takes advantage of the fact that SortedBWT is sorted.
Time Complexity = O(log(n)). Space Complexity = O(1).

| Improve this Doc View Source

FindOccurrenceRankOfCharInSortedBWT(Int32)

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

This implementation takes advantage of the fact that SortedBWT is sorted.
Time Complexity = O(log(n)). Space Complexity = O(1).

Implements

Extension Methods