1. Movelet Trees
- Author
-
Gagie, Travis, Manzini, Giovanni, Navarro, Gonzalo, and Sciortino, Marinella
- Subjects
Computer Science - Data Structures and Algorithms - Abstract
We combine Nishimoto and Tabei's move structure with a wavelet tree to show how, if $T [1..n]$ is over a constant-sized alphabet and its Burrows-Wheeler Transform (BWT) consists of $r$ runs, then we can store $T$ in $O \left( r \log \frac{n}{r} \right)$ bits such that when given a pattern $P [1..m]$, we can find the BWT interval for $P$ in $O (m)$ time.
- Published
- 2024