Source author record

Nicola Prezza

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Formal Languages and Automata Theory

Catalog footprint

Research overview

11works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Computing matching statistics on Wheeler DFAs

Matching statistics were introduced to solve the approximate string matching problem, which is a recurrent subroutine in bioinformatics applications. In 2010, Ohlebusch et al. [SPIRE 2010] proposed a time and space efficient algorithm for computing matching statistics which relies on some components of a compressed suffix tree - notably, the longest common prefix (LCP) array. In this paper, we show how their algorithm can be generalized from strings to Wheeler deterministic finite automata. Most importantly, we introduce a notion of LCP array for Wheeler automata, thus establishing a first clear step towards extending (compressed) suffix tree functionalities to labeled graphs.

preprint2021arXiv

Towards a Definitive Compressibility Measure for Repetitive Sequences

Unlike in statistical compression, where Shannon's entropy is a definitive lower bound, no such clear measure exists for the compressibility of repetitive sequences. Since statistical entropy does not capture repetitiveness, ad-hoc measures like the size $z$ of the Lempel--Ziv parse are frequently used to estimate it. The size $b \le z$ of the smallest bidirectional macro scheme captures better what can be achieved via copy-paste processes, though it is NP-complete to compute and it is not monotonic upon symbol appends. Recently, a more principled measure, the size $γ$ of the smallest string \emph{attractor}, was introduced. The measure $γ\le b$ lower bounds all the previous relevant ones, yet length- $n$ strings can be represented and efficiently indexed within space $O(γ\log\frac{n}γ)$ , which also upper bounds most measures. While $γ$ is certainly a better measure of repetitiveness than $b$ , it is also NP-complete to compute and not monotonic, and it is unknown if one can always represent a string in $o(γ\log n)$ space. In this paper, we study an even smaller measure, $δ\le γ$ , which can be computed in linear time, is monotonic, and allows encoding every string in $O(δ\log\frac{n}δ)$ space because $z = O(δ\log\frac{n}δ)$ . We show that $δ$ better captures the compressibility of repetitive strings. Concretely, we show that (1) $δ$ can be strictly smaller than $γ$ , by up to a logarithmic factor; (2) there are string families needing $Ω(δ\log\frac{n}δ)$ space to be encoded, so this space is optimal for every $n$ and $δ$ ; (3) one can build run-length context-free grammars of size $O(δ\log\frac{n}δ)$ , whereas the smallest (non-run-length) grammar can be up to $Θ(\log n/\log\log n)$ times larger; and (4) within $O(δ\log\frac{n}δ)$ space we can not only...

preprint2020arXiv

On Indexing and Compressing Finite Automata

An index for a finite automaton is a powerful data structure that supports locating paths labeled with a query pattern, thus solving pattern matching on the underlying regular language. In this paper, we solve the long-standing problem of indexing arbitrary finite automata. Our solution consists in finding a partial co-lexicographic order of the states and proving, as in the total order case, that states reached by a given string form one interval on the partial order, thus enabling indexing. We provide a lower bound stating that such an interval requires $O(p)$ words to be represented, $p$ being the order's width (i.e. the size of its largest antichain). Indeed, we show that $p$ determines the complexity of several fundamental problems on finite automata: (i) Letting $σ$ be the alphabet size, we provide an encoding for NFAs using $\lceil\log σ\rceil + 2\lceil\log p\rceil + 2$ bits per transition and a smaller encoding for DFAs using $\lceil\log σ\rceil + \lceil\log p\rceil + 2$ bits per transition. This is achieved by generalizing the Burrows-Wheeler transform to arbitrary automata. (ii) We show that indexed pattern matching can be solved in $\tilde O(m\cdot p^2)$ query time on NFAs. (iii) We provide a polynomial-time algorithm to index DFAs, while matching the optimal value for $p$ . On the other hand, we prove that the problem is NP-hard on NFAs. (iv) We show that, in the worst case, the classic powerset construction algorithm for NFA determinization generates an equivalent DFA of size $2^p(n-p+1)-1$ , where $n$ is the number of NFA's states.

preprint2020arXiv

Optimal Substring-Equality Queries with Applications to Sparse Text Indexing

We consider the problem of encoding a string of length $n$ from an integer alphabet of size $σ$ so that access and substring equality queries (that is, determining the equality of any two substrings) can be answered efficiently. Any uniquely-decodable encoding supporting access must take $n\logσ+ Θ(\log (n\logσ))$ bits. We describe a new data structure matching this lower bound when $σ\leq n^{O(1)}$ while supporting both queries in optimal $O(1)$ time. Furthermore, we show that the string can be overwritten in-place with this structure. The redundancy of $Θ(\log n)$ bits and the constant query time break exponentially a lower bound that is known to hold in the read-only model. Using our new string representation, we obtain the first in-place subquadratic (indeed, even sublinear in some cases) algorithms for several string-processing problems in the restore model: the input string is rewritable and must be restored before the computation terminates. In particular, we describe the first in-place subquadratic Monte Carlo solutions to the sparse suffix sorting, sparse LCP array construction, and suffix selection problems. With the sole exception of suffix selection, our algorithms are also the first running in sublinear time for small enough sets of input suffixes. Combining these solutions, we obtain the first sublinear-time Monte Carlo algorithm for building the sparse suffix tree in compact space. We also show how to derandomize our algorithms using small space. This leads to the first Las Vegas in-place algorithm computing the full LCP array in $O(n\log n)$ time and to the first Las Vegas in-place algorithms solving the sparse suffix sorting and sparse LCP array construction problems in $O(n^{1.5}\sqrt{\log σ})$ time. Running times of these Las Vegas algorithms hold in the worst case with high probability.

preprint2020arXiv

Wheeler Languages

The recently introduced class of Wheeler graphs, inspired by the Burrows-Wheeler Transform (BWT) of a given string, admits an efficient index data structure for searching for subpaths with a given path label, and lifts the applicability of the Burrows-Wheeler transform from strings to languages. In this paper we study the regular languages accepted by automata having a Wheeler graph as transition function, and prove results on determination, Myhill_Nerode characterization, decidability, and closure properties for this class of languages.

preprint2016arXiv

Fast Longest Common Extensions in Small Space

In this paper we address the longest common extension (LCE) problem: to compute the length $\ell$ of the longest common prefix between any two suffixes of $T\in Σ^n$ with $Σ= \{0, \ldots σ-1\}$ . We present two fast and space-efficient solutions based on (Karp-Rabin) \textit{fingerprinting} and \textit{sampling}. Our first data structure exploits properties of Mersenne prime numbers when used as moduli of the Karp-Rabin hash function and takes $n\lceil \log_2σ\rceil$ bits of space. Our second structure works with any prime modulus and takes $n\lceil \log_2σ\rceil + n/w + w\log_2 n$ bits of space ( $w$ memory-word size). Both structures support $\mathcal O\left(m\logσ/w \right)$ -time extraction of any length- $m$ text substring, $\mathcal O(\log\ell)$ -time LCE queries with high probability, and can be built in optimal $\mathcal O(n)$ time. In the first case, ours is the first result showing that it is possible to answer LCE queries in $o(n)$ time while using only $\mathcal O(1)$ words on top of the space required to store the text. Our results improve the state of the art in space usage, query times, and preprocessing times and are extremely practical: we present a C++ implementation that is very fast and space-efficient in practice.

preprint2016arXiv

Practical combinations of repetition-aware data structures

Highly-repetitive collections of strings are increasingly being amassed by genome sequencing and genetic variation experiments, as well as by storing all versions of human-generated files, like webpages and source code. Existing indexes for locating all the exact occurrences of a pattern in a highly-repetitive string take advantage of a single measure of repetition. However, multiple, distinct measures of repetition all grow sublinearly in the length of a highly-repetitive string. In this paper we explore the practical advantages of combining data structures whose size depends on distinct measures of repetition. The main ingredient of our structures is the run-length encoded BWT (RLBWT), which takes space proportional to the number of runs in the Burrows-Wheeler transform of a string. We describe a range of practical variants that combine RLBWT with the set of boundaries of the Lempel-Ziv 77 factors of a string, which take space proportional to the number of factors. Such variants use, respectively, the RLBWT of a string and the RLBWT of its reverse, or just one RLBWT inside a bidirectional index, or just one RLBWT with support for unidirectional extraction. We also study the practical advantages of combining RLBWT with the compact directed acyclic word graph of a string, a data structure that takes space proportional to the number of one-character extensions of maximal repeats. Our approaches are easy to implement, and provide competitive tradeoffs on significant datasets.

preprint2016arXiv

Space-Efficient Re-Pair Compression

Re-Pair is an effective grammar-based compression scheme achieving strong compression rates in practice. Let $n$ , $σ$ , and $d$ be the text length, alphabet size, and dictionary size of the final grammar, respectively. In their original paper, the authors show how to compute the Re-Pair grammar in expected linear time and $5n + 4σ^2 + 4d + \sqrt{n}$ words of working space on top of the text. In this work, we propose two algorithms improving on the space of their original solution. Our model assumes a memory word of $\lceil\log_2 n\rceil$ bits and a re-writable input text composed by $n$ such words. Our first algorithm runs in expected $\mathcal O(n/ε)$ time and uses $(1+ε)n +\sqrt n$ words of space on top of the text for any parameter $0<ε\leq 1$ chosen in advance. Our second algorithm runs in expected $\mathcal O(n\log n)$ time and improves the space to $n +\sqrt n$ words.

preprint2015arXiv

A Compressed-Gap Data-Aware Measure

In this paper, we consider the problem of efficiently representing a set $S$ of $n$ items out of a universe $U=\{0,...,u-1\}$ while supporting a number of operations on it. Let $G=g_1...g_n$ be the gap stream associated with $S$ , $gap$ its bit-size when encoded with \emph{gap-encoding}, and $H_0(G)$ its empirical zero-order entropy. We prove that (1) $nH_0(G)\in o(gap)$ if $G$ is highly compressible, and (2) $nH_0(G) \leq n\log(u/n) + n \leq uH_0(S)$ . Let $d$ be the number of \emph{distinct} gap lengths between elements in $S$ . We firstly propose a new space-efficient zero-order compressed representation of $S$ taking $n(H_0(G)+1)+\mathcal O(d\log u)$ bits of space. Then, we describe a fully-indexable dictionary that supports \emph{rank} and \emph{select} queries in $\mathcal O(\log(u/n)+\log\log u)$ time while requiring asymptotically the same space as the proposed compressed representation of $S$ .

preprint2015arXiv

Composite repetition-aware data structures

In highly repetitive strings, like collections of genomes from the same species, distinct measures of repetition all grow sublinearly in the length of the text, and indexes targeted to such strings typically depend only on one of these measures. We describe two data structures whose size depends on multiple measures of repetition at once, and that provide competitive tradeoffs between the time for counting and reporting all the exact occurrences of a pattern, and the space taken by the structure. The key component of our constructions is the run-length encoded BWT (RLBWT), which takes space proportional to the number of BWT runs: rather than augmenting RLBWT with suffix array samples, we combine it with data structures from LZ77 indexes, which take space proportional to the number of LZ77 factors, and with the compact directed acyclic word graph (CDAWG), which takes space proportional to the number of extensions of maximal repeats. The combination of CDAWG and RLBWT enables also a new representation of the suffix tree, whose size depends again on the number of extensions of maximal repeats, and that is powerful enough to support matching statistics and constant-space traversal.

preprint2015arXiv

Computing LZ77 in Run-Compressed Space

In this paper, we show that the LZ77 factorization of a text T {\inΣ^n} can be computed in O(R log n) bits of working space and O(n log R) time, R being the number of runs in the Burrows-Wheeler transform of T reversed. For extremely repetitive inputs, the working space can be as low as O(log n) bits: exponentially smaller than the text itself. As a direct consequence of our result, we show that a class of repetition-aware self-indexes based on a combination of run-length encoded BWT and LZ77 can be built in asymptotically optimal O(R + z) words of working space, z being the size of the LZ77 parsing.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Nicola Prezza

Research overview

Is this your work?

11 publications

Computing matching statistics on Wheeler DFAs

Towards a Definitive Compressibility Measure for Repetitive Sequences

On Indexing and Compressing Finite Automata

Optimal Substring-Equality Queries with Applications to Sparse Text Indexing

Wheeler Languages

Fast Longest Common Extensions in Small Space

Practical combinations of repetition-aware data structures

Space-Efficient Re-Pair Compression

A Compressed-Gap Data-Aware Measure

Composite repetition-aware data structures

Computing LZ77 in Run-Compressed Space

See the researcher in context

Building this map preview