35 citations · 99 across the 47 of their papers we have counts for
4 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.
Fast Dynamic Arrays
Philip Bille, Anders Roy Christiansen, Mikko Berggren Ettienne +1
We present a highly optimized implementation of tiered vectors, a data structure for maintaining a sequence of elements supporting access in time and insertion and delet…
Time-Space Trade-Offs for Lempel-Ziv Compressed Indexing
Philip Bille, Mikko Berggren Ettienne, Inge Li Gørtz +1
Given a string , the \emph{compressed indexing problem} is to preprocess into a compressed representation that supports fast \emph{substring queries}. The goal is to use lit…
Practical and Effective Re-Pair Compression
Philip Bille, Inge Li Gørtz, Nicola Prezza
Re-Pair is an efficient grammar compressor that operates by recursively replacing high-frequency character pairs with new grammar symbols. The most space-efficient linear-time algo…