Lempel–Ziv (LZ77) compression is the most commonly used lossless compression
algorithm. The basic idea is to greedily break the input string into blocks (called “phrases”) …

The sensitivity of a string compression algorithm C asks how much the output size C (T) for
an input string T can increase when a single character edit operation is performed on T. This …

While the th order empirical entropy is an accepted measure of the compressibility of
individual sequences on classical text collections, it is useful only for small values of and …

Measuring sequence similarity and compressing texts are among the most fundamental
tasks in string algorithms. In this work, we develop near-optimal quantum algorithms for the …

Abstract The extended Burrows-Wheeler Transform (eBWT) was introduced by Mantaci et
al.[TCS 2007] to extend the definition of the BWT to a collection of strings. As opposed to …

Until recently, most experts would probably have agreed we cannot backwards-step in
constant time with a run-length compressed Burrows-Wheeler Transform (RLBWT), since …

Motivated by challenges in pangenomic read alignment, we propose a generalization of
Wheeler graphs that we call Wheeler maps. A Wheeler map stores a text T [1.. n] and an …

Computation over compressed data is a new paradigm in the design of algorithms and data
structures that can reduce space usage and speed up computation by orders of magnitude …

Abstract The extended Burrows Wheeler Transform (eBWT eBWT) was introduced by
Mantaci et al. TCS 2007 to extend the definition of the BWT BWT to a collection of strings. In …

Indexing highly repetitive texts is important in fields such as bioinformatics and versioned
repositories. The run-length compression of the Burrows-Wheeler transform (BWT) provides …