Namespace MoreStructures.BurrowsWheelerTransform.Builders.LastFirstFinders

Classes

BinarySearchFinder

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

NaiveFinder

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

PrecomputedFinder

A BinarySearchFinder refinement which precalculate an hash-map of all the positions by each char, for both BWT and its sorted version, which takes ~ 2 * n space and makes calls to FindIndexOfNthOccurrenceInBWT(Int32, Int32) and FindIndexOfNthOccurrenceInSortedBWT(Int32, Int32) executed in constant time.

Interfaces

ILastFirstFinder

A stategy used by a IBuilder to find chars in BWT and in its sorted version SortedBWT.