13 citations · 26 across the 11 of their papers we have counts for
5 papers · 1 filter
A Separation Between Run-Length SLPs and LZ77
Philip Bille, Travis Gagie, Inge Li Gørtz +1
In this paper we give an infinite family of strings for which the length of the Lempel-Ziv'77 parse is a factor smaller than the smallest run-length grammar.
String Attractors
Nicola Prezza
Let be a string of length . In this paper we introduce the notion of \emph{string attractor}: a subset of the string's positions such that every distinct substring o…
Succinct Partial Sums and Fenwick Trees
Philip Bille, Anders Roy Christiansen, Nicola Prezza +1
We consider the well-studied partial sums problem in succint space where one is to maintain an array of n k-bit integers subject to updates such that partial sums queries can be ef…
From LZ77 to the Run-Length Encoded Burrows-Wheeler Transform, and Back
Alberto Policriti, Nicola Prezza
The Lempel-Ziv factorization (LZ77) and the Run-Length encoded Burrows-Wheeler Transform (RLBWT) are two important tools in text compression and indexing, being their sizes and…
A Framework of Dynamic Data Structures for String Processing
Nicola Prezza
In this paper we present DYNAMIC, an open-source C++ library implementing dynamic compressed data structures for string manipulation. Our framework includes useful tools such as se…