Hybrid index speeds searching with medium alphabets in string data
Mixing FM-indexes and CSAs: backward search over an order-1 rank encoding
Data Structures and Algorithms
Summary
Searching text data quickly can be tricky when the set of possible characters is large. The authors create a new hybrid indexing method that changes how text is encoded to make searches more efficient when alphabets are neither very small nor very large. Their approach mixes two existing indexing ideas to get the best of both, speeding up searches on certain types of data with some noise. However, the new method uses more space than some other compressed indexes, and it's unclear if it will be smaller on real-world data.
What this means in practice
- •For data engineers: Implement faster exact pattern searches in text collections with medium-sized alphabets and moderate noise.
- •For bioinformatics developers: Enhance genome sequence indexing tools for repetitive and noisy DNA data by leveraging hybrid rank-based encodings.
Authors
Travis Gagie
Abstract
FM-indexes and compressed suffix arrays (CSAs) are often treated as interchangeable, but they behave differently as the alphabet grows. An FM-index step costs about one cache miss per level of a wavelet tree, so it gets slower with the alphabet size. A CSA step is a binary search whose range shrinks as characters get rarer. We describe a simple hybrid. Each character of the text is replaced by the rank of its frequency among the characters that follow the previous character. We backward-search on this encoding, which is over a small, skewed alphabet, and recover the one piece of information the encoding loses (the first character of the pattern) with a single CSA-like step on an array we call $\PsiE$. Counting is exact, and locating works with standard suffix-array sampling. A prototype on synthetic repetitive data shows that the hybrid is the fastest of the indexes we tried at intermediate alphabet sizes with 1\% noise, but even its compact version is 1.7 to 3.9 times larger than a compressed run-length CSA or FM-index of the original text, because the encoding and $\PsiE$ together have more runs than the original Burrows--Wheeler transform. Whether that changes on real data, such as parses and minimizer digests, is the main open question.