Two decades ago, a breakthrough in indexing string collections made it possible to
represent them within their compressed space while at the same time offering indexed …

Automatic sequences are sequences over a finite alphabet generated by a finite-state
machine. This book presents a novel viewpoint on automatic sequences, and more …

Abstract The Burrows-Wheeler Transform (BWT) is an invertible text transformation that
permutes symbols of a text according to the lexicographical order of its suffixes. BWT is the …

The last two decades have witnessed a dramatic increase in the amount of highly repetitive
datasets consisting of sequential data (strings, texts). Processing these massive amounts of …

We describe the first self-indexes able to count and locate pattern occurrences in optimal
time within a space bounded by the size of the most popular dictionary compressors. To …

We consider several types of internal queries, that is, questions about fragments of a given
text specified in constant space by their locations in. Our main result is an optimal data …

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 …

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”) …

Improvements in nanopore sequencing necessitate efficient classification methods,
including pre-filtering and adaptive sampling algorithms that enrich for reads of interest …