3 papers
cs.DS2025
Prefix-free parsing for merging big BWTs
Diego Diaz-Dominguez, Travis Gagie, Veronica Guerrini +5
When building Burrows-Wheeler Transforms (BWTs) of truly huge datasets, prefix-free parsing (PFP) can use an unreasonable amount of memory. In this paper we show how if a dataset c…
cs.DS2024
A Textbook Solution for Dynamic Strings
Zsuzsanna Lipták, Francesco Masillo, Gonzalo Navarro
We consider the problem of maintaining a collection of strings while efficiently supporting splits and concatenations on them, as well as comparing two substrings, and computing th…
cs.DS2024
BAT-LZ Out of Hell
Zsuzsanna Lipták, Francesco Masillo, Gonzalo Navarro
Despite consistently yielding the best compression on repetitive text collections, the Lempel-Ziv parsing has resisted all attempts at offering relevant guarantees on the cost to a…