RLBWT Tricks
Nathaniel K. Brown, Travis Gagie, Massimiliano Rossi · 2022
Until recently, most experts would probably have said we cannot backwards-step in constant time with a run-length compressed Burrows-Wheeler Transform (RLBWT), since doing so relies on rank queries on sparse bitvectors and those inherit lower bounds from predecessor queries. At ICALP'21, however, Nishimoto and Tabei [1] described a new, simple and constant-time implementation.