Backwards Search in Context Bound Text Transformations
Matthias Petri, Gonzalo Navarro, Shane Culpepper, and Simon Puglisi
The Burrows-Wheeler Transform (bwt) is the basis for many of the
most effective compression and self-indexing methods used today.
A key to the versatility of the bwt is the ability to search
for patterns directly in the transformed text.
A backwards search for a pattern P can be performed on a transformed
text by iteratively determining the range of suffixes that match P.
The search can be further enhanced by constructing a wavelet tree over
the output of the bwt in order to emulate a suffix array.
In this paper, we investigate new algorithms for search derived from a
variation of the bwt whereby rotations are only sorted
to a depth k, commonly referred to as a context bound transform.
Interestingly, this bwt variant can be used to mimic
a k-gram index, which are used in a variety of applications
that need to efficiently return occurrences in text position order.
In this paper, we present the first backwards search algorithms on the
k-bwt, and show how to construct a self-index containing many of
the attractive properties of a k-gram index.