6 papers
Incongruity-sensitive access to highly compressed strings
Ferdinando Cicalese, Zsuzsanna Lipták, Travis Gagie +3
Random access to highly compressed strings -- represented by straight-line programs or Lempel-Ziv parses, for example -- is a well-studied topic. Random access to such strings in s…
BWT for string collections
Davide Cenzato, Zsuzsanna Lipták, Nadia Pisanti +2
We survey the different methods used for extending the BWT to collections of strings, following largely [Cenzato and Lipták, CPM 2022, Bioinformatics 2024]. We analyze the specific…
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…
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…
Maintaining the cycle structure of dynamic permutations
Zsuzsanna Lipták, Francesco Masillo, Gonzalo Navarro
We present a new data structure for maintaining dynamic permutations, which we call a . The FST allows one to efficiently maintain the cycle s…
Novel Results on the Number of Runs of the Burrows-Wheeler-Transform
Sara Giuliani, Shunsuke Inenaga, Zsuzsanna Lipták +3
The Burrows-Wheeler-Transform (BWT), a reversible string transformation, is one of the fundamental components of many current data structures in string processing. It is central in…