Constant-time $\psi$ queries in $O \left( r \log \frac{n}{r} + r \log \sigma \right)$ bits

Autor:	Gagie, Travis, Manzini, Giovanni, Navarro, Gonzalo, Sciortino, Marinella
Rok vydání:	2024
Předmět:	Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	Given a text $T [1..n]$ over an alphabet of size $\sigma$ whose BWT has $r$ runs, we can store $T$ in $O \left( r \log \frac{n}{r} + r \log \sigma \right)$ bits such that we can answer $\psi$ queries in constant time.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2408.04537 Zobrazit plný text záznamu View this record from Arxiv