r-index
The r-index is a compressed full-text index that supports counting and locating pattern matches in space bounded by the number of BWT runs.
Mechanism: Here r counts maximal equal-symbol runs in the BWT, not runs in the original text. Run-boundary suffix-array samples maintain one known match during backward search, a toehold. Separate navigation support enumerates the other matches. Counting alone does not return their text positions. [1]
Space: The basic result uses O(r) machine words, not O(r) bits. Its locate bound has a loglogarithmic factor per occurrence; the same paper obtains O(m+occ) time with O(r log(n/r)) words. These are distinct trade-offs, with n text length and m pattern length. [1]
Example: abab abab without the space and babbaaba each contain four a and four b symbols. With a unique trailing $, their BWTs have 3 and 8 runs respectively. The executable example checks run-boundary toeholds against exact suffix-array positions; it is not a compressed r-index implementation. [3]
Evaluation: A 2026 variable-length-blocking preprint separates count latency per pattern from locate latency per reported occurrence, filters its locate workload by occurrence count, and does not measure construction time. Its query results cannot establish build-memory requirements or universal speedups. [2]
Relations
Limitations
- The educational model demonstrates one match per nonempty search interval, not the full occurrence-enumeration structure or its time and space bounds. [3]
Citations
- Gagie, Navarro and Prezza: Optimal-Time Text Indexing in BWT-runs Bounded Space, SODA 2018, sections 2-3 and Table 2
- Diaz-Dominguez and Makinen: Adaptive encodings for small and fast compressed suffix arrays, arXiv:2602.17201v1 (2026), sections 2.3 and 8.1
- Hesela: BWT run counts and run-boundary toeholds, executable finite example
Sources & caveats
- Primary-source explanation of a research index; research status is not a claim that the algorithm lacks working implementations.
- The example uses constructed lowercase ASCII strings and a reserved terminator. It measures neither throughput nor physical storage savings.