|
Title |
Backwards Search in Context Bound Text Transformations |
|
Authors |
Matthias Petri, Gonzalo Navarro, J. Shane Culpepper, Simon Puglisi |
|
Publication date |
2011 |
|
Abstract |
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. |
|
Downloaded |
11 times |
|
Pages |
82-91 |
|
Conference name |
International Conference on Data Compression, Communication and Processing |
|
PDF |
|
