3 papers
cs.DS2026
Compressed Set Representations based on Set Difference
Travis Gagie, Meng He, Gonzalo Navarro
We introduce a compressed representation of sets of sets that exploits how much they differ from each other. Our representation supports access, membership, predecessor and success…
cs.DS2026
Worst-case optimal adaptive alphabetic prefix-free coding
Travis Gagie
We give the first algorithm for adaptive alphabetic prefix-free coding that is worst-case optimal in terms of time and compression when $Ï\in o \left( \frac{n^{1 / 2}}{\log n} \ri…
cs.DS2025
Faster run-length compressed suffix arrays
Nathaniel K. Brown, Travis Gagie, Giovanni Manzini +2
We first review how we can store a run-length compressed suffix array (RLCSA) for a text of length over an alphabet of size whose Burrows-Wheeler Transform (BWT) consi…