Nicola Prezza

TCS Journal 2021 Journal Article

Adaptive learning of compressible strings

• Gabriele Fici
• Nicola Prezza
• Rossano Venturini

Suppose an oracle knows a string S that is unknown to us and that we want to determine. The oracle can answer queries of the form “Is s a substring of S? ”. In 1995, Skiena and Sundaram showed that, in the worst case, any algorithm needs to ask the oracle σ n / 4 − O ( n ) queries in order to be able to reconstruct the hidden string, where σ is the size of the alphabet of S and n its length, and gave an algorithm that spends ( σ − 1 ) n + O ( σ n ) queries to reconstruct S. The main contribution of our paper is to improve the above upper-bound in the context where the string is compressible. We first present a universal algorithm that, given a (computable) compressor that compresses the string to τ bits, performs q = O ( τ ) substring queries; this algorithm, however, runs in exponential time. For this reason, the second part of the paper focuses on more time-efficient algorithms whose number of queries is bounded by specific compressibility measures. We first show that any string of length n over an integer alphabet of size σ with rle runs can be reconstructed with q = O ( rle ( σ + log ⁡ n rle ) ) substring queries in linear time and space. We then present an algorithm that spends q ∈ O ( σ g log ⁡ n ) substring queries and runs in O ( n ( log ⁡ n + log ⁡ σ ) + q ) time using linear space, where g is the size of a smallest straight-line program generating the string.

SODA Conference 2021 Conference Paper

On Indexing and Compressing Finite Automata

• Nicola Cotumaccio
• Nicola Prezza

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. The problem is hard in the general case: a recent conditional lower bound suggests that, in the worst case, deciding at query time whether a pattern of length m belongs to the substring closure of the language accepted by requires time. On the other hand, Gagie et al. [TCS 2017] introduced a subclass of automata that allow an optimal Õ ( m )-time solution based on prefix-sorting the states in a total order. In this paper, we solve the long-standing problem of indexing arbitrary finite automata, matching the above bounds. 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 [log σ ] + 2[log p ] + 2 bits per transition and a smaller encoding for DFAs using [log σ ] + [log p ] + 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 Õ(m · 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 power-set 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. Contribution (i) provides a new compression paradigm for labeled graphs. Contributions (ii)-(iii) solve the regular language indexing problem, notably with a polynomial-time solution for DFAs. Contribution (iv) implies a new FPT analysis for the complexity of classic algorithms on automata, including membership and equivalence (the latter being PSPACE-complete when input automata are NFAs).

SODA Conference 2021 Conference Paper

On Locating Paths in Compressed Tries

• Nicola Prezza

In this paper, we consider the problem of compressing a trie while supporting the powerful locate queries: to return the pre-order identifiers of all nodes reached by a path labeled with a given query pattern. Our result builds on top of the XBW tree transform of Ferragina et al. [FOCS 2005] and generalizes the r-index locate machinery of Gagie et al. [SODA 2018, JACM 2020] based on the run-length encoded Burrows-Wheeler transform (BWT). Our first contribution is to propose a suitable generalization of the run-length BWT to tries. We show that this natural generalization enjoys several of the useful properties of its counterpart on strings: in particular, the transform natively supports counting occurrences of a query pattern on the trie's paths and its size r captures the trie's repetitiveness and lower-bounds a natural notion of trie entropy. Our main contribution is a much deeper insight into the combinatorial structure of this object. In detail, we show that a data structure of O ( r log n ) + 2 n + o ( n ) bits, where n is the number of nodes, allows locating the occ occurrences of a pattern of length m in nearly-optimal O ( m log σ + occ ) time, where σ is the alphabet's size. Our solution consists in sampling O ( r ) nodes that can be used as “anchor points” during the locate process. Once obtained the pre-order identifier of the first pattern occurrence (in co-lexicographic order), we show that a constant number of constant-time jumps between those anchor points lead to the identifier of the next pattern occurrence, thus enabling locating in optimal O (1) time per occurrence.

TCS Journal 2021 Journal Article

Space-efficient construction of compressed suffix trees

• Nicola Prezza
• Giovanna Rosone

We show how to build several data structures of central importance to string processing by taking as input the Burrows-Wheeler transform (BWT) and using small extra working space. Let n be the text length and σ be the alphabet size. We first provide two algorithms that enumerate all LCP values and suffix tree intervals in O ( n log ⁡ σ ) time using just o ( n log ⁡ σ ) bits of working space on top of the input re-writable BWT. Using these algorithms as building blocks, for any parameter 0 < ϵ ≤ 1 we show how to build the PLCP bitvector and the balanced parentheses representation of the suffix tree topology in O ( n ( log ⁡ σ + ϵ − 1 ⋅ log ⁡ log ⁡ n ) ) time using at most n log ⁡ σ ⋅ ( ϵ + o ( 1 ) ) bits of working space on top of the input re-writable BWT and the output. For example, we can build a compressed suffix tree from the BWT using just succinct working space (i. e. o ( n log ⁡ σ ) bits) and Θ ( n log ⁡ σ + n ( log ⁡ log ⁡ n ) 1 + δ ) time, for any constant δ > 0. This improves the previous most space-efficient algorithms, which worked in O ( n ) bits and O ( n log ⁡ n ) time. We also consider the problem of merging BWTs of string collections, and provide a solution running in O ( n log ⁡ σ ) time and using just o ( n log ⁡ σ ) bits of working space. An efficient implementation of our LCP construction and BWT merge algorithms uses (in RAM) as few as n bits on top of a packed representation of the input/output and process data as fast as 2. 92 megabases per second.

I&C Journal 2021 Journal Article

Wheeler languages

• Jarno Alanko
• Giovanna D'Agostino
• Alberto Policriti
• Nicola Prezza

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 a single string to an entire language. In this paper we study the regular languages accepted by automata having a Wheeler graph as transition function and prove results on determinization, Myhill-Nerode characterization, decidability, and closure properties for this class of languages.

SODA Conference 2020 Conference Paper

Regular Languages meet Prefix Sorting

• Jarno Alanko
• Giovanna D'Agostino
• Alberto Policriti
• Nicola Prezza

Indexing strings via prefix (or suffix) sorting is, arguably, one of the most successful algorithmic techniques developed in the last decades. Can indexing be extended to languages? The main contribution of this paper is to initiate the study of the sub-class of regular languages accepted by an automaton whose states can be prefix-sorted. Starting from the recent notion of Wheeler graph [Gagie et al. , TCS 2017]— which extends naturally the concept of prefix sorting to labeled graphs—we investigate the properties of Wheeler languages, that is, regular languages admitting an accepting Wheeler finite automaton. We first characterize this family as the natural extension of regular languages endowed with the co-lexicographic ordering: the sorted prefixes of strings belonging to a Wheeler language are partitioned into a finite number of co-lexicographic intervals, each formed by elements from a single Myhill-Nerode equivalence class. We proceed by proving several results related to Wheeler automata: (i) We show that every Wheeler NFA (WNFA) with n states admits an equivalent Wheeler DFA (WDFA) with at most 2 n – 1 – |Σ| states (Σ being the alphabet) that can be computed in O (n 3 ) time. (ii) We describe a quadratic algorithm to prefix-sort a proper superset of the WDFAs, a O ( n log n )-time online algorithm to sort acyclic WDFAs, and an optimal linear-time offline algorithm to sort general WDFAs. (iii) We provide a minimization theorem that characterizes the smallest WDFA recognizing the same language of any input WDFA. The corresponding constructive algorithm runs in optimal linear time in the acyclic case, and in O ( n log n ) time in the general case. (iv) We show how to compute the smallest WDFA equivalent to any acyclic DFA in nearly-optimal time. Our contributions imply new results of independent interest. Contributions (i-iii) provide a new class of NFAs for which the minimization problem can be approximated within a constant factor in polynomial time. Contribution (iv) provides a provably minimum-size solution for the well-studied problem of indexing deterministicacyclic graphs for linear-time pattern matching queries.

TCS Journal 2019 Journal Article

Universal compressed text indexing

• Gonzalo Navarro
• Nicola Prezza

The rise of repetitive datasets has lately generated a lot of interest in compressed self-indexes based on dictionary compression, a rich and heterogeneous family of techniques that exploits text repetitions in different ways. For each such compression scheme, several different indexing solutions have been proposed in the last two decades. To date, the fastest indexes for repetitive texts are based on the run-length compressed Burrows–Wheeler transform (BWT) and on the Compact Directed Acyclic Word Graph (CDAWG). The most space-efficient indexes, on the other hand, are based on the Lempel–Ziv parsing and on grammar compression. Indexes for more universal schemes such as collage systems and macro schemes have not yet been proposed. Very recently, Kempa and Prezza [STOC 2018] showed that all dictionary compressors can be interpreted as approximation algorithms for the smallest string attractor, that is, a set of text positions capturing all distinct substrings. Starting from this observation, in this paper we develop the first universal compressed self-index, that is, the first indexing data structure based on string attractors, which can therefore be built on top of any dictionary-compressed text representation. Let γ be the size of a string attractor for a text of length n. From known reductions, γ can be chosen to be asymptotically equal to any repetitiveness measure: number of runs in the BWT, size of the CDAWG, number of Lempel–Ziv phrases, number of rules in a grammar or collage system, size of a macro scheme. Our index takes O ( γ lg ⁡ ( n / γ ) ) words of space and supports locating the occ occurrences of any pattern of length m in O ( m lg ⁡ n + o c c lg ϵ ⁡ n ) time, for any constant ϵ > 0. This is, in particular, the first index for general macro schemes and collage systems. Our result shows that the relation between indexing and compression is much deeper than what was previously thought: the simple property standing at the core of all dictionary compressors is sufficient to support fast indexed queries.

STOC Conference 2018 Conference Paper

At the roots of dictionary compression: string attractors

• Dominik Kempa
• Nicola Prezza

SODA Conference 2018 Conference Paper

In-Place Sparse Suffix Sorting

• Nicola Prezza

Suffix arrays encode the lexicographical order of all suffixes of a text and are often combined with the Longest Common Prefix array (LCP) to simulate navigational queries on the suffix tree in reduced space. In space-critical applications such as sparse and compressed text indexing, only information regarding the lexicographical order of a size- b subset of all n text suffixes is often needed. Such information can be stored space-efficiently (in b words) in the sparse suffix array (SSA). The SSA and its relative sparse LCP array (SLCP) can be used as a space-efficient substitute of the sparse suffix tree. Very recently, Gawrychowski and Kociumaka [11] showed that the sparse suffix tree (and therefore SSA and SLCP) can be built in asymptotically optimal space with a Monte Carlo algorithm running in time. The main reason for using the SSA and SLCP arrays in place of the sparse suffix tree is, however, their reduced space of b words each. This leads naturally to the quest for in-place algorithms building these arrays. Franceschini and Muthukrishnan [8] showed that the full suffix array can be built in-place and in optimal running time. On the other hand, finding sub-quadratic in-place algorithms for building the SSA and SLCP for general subsets of suffixes has been an elusive task for decades. In this paper, we give the first solution to this problem. We provide the first in-place algorithm building the full LCP array in expected time and the first Monte Carlo in-place algorithms building the SSA and SLCP in expected time. We moreover describe the first in-place solution for the suffix selection problem: to compute the i -th smallest text suffix. In order to achieve these results, we show that we can quickly overwrite the text with a reversible and implicit data structure supporting Longest Common Extension queries in polylogarithmic time and text extraction in optimal time: this structure is strictly more powerful than a plain text representation and is of independent interest.

SODA Conference 2018 Conference Paper

Optimal-Time Text Indexing in BWT-runs Bounded Space

• Travis Gagie
• Gonzalo Navarro 0001
• Nicola Prezza

Indexing highly repetitive texts — such as genomic databases, software repositories and versioned text collections — has become an important problem since the turn of the millennium. A relevant compressibility measure for repetitive texts is r, the number of runs in their Burrows-Wheeler Transform (BWT). One of the earliest indexes for repetitive collections, the Run-Length FM-index, used O ( r ) space and was able to efficiently count the number of occurrences of a pattern of length m in the text (in loglogarithmic time per pattern symbol, with current techniques). However, it was unable to locate the positions of those occurrences efficiently within a space bounded in terms of r. Since then, a number of other indexes with space bounded by other measures of repetitiveness — the number of phrases in the Lempel-Ziv parse, the size of the smallest grammar generating the text, the size of the smallest automaton recognizing the text factors — have been proposed for efficiently locating, but not directly counting, the occurrences of a pattern. In this paper we close this long-standing problem, showing how to extend the Run-Length FM-index so that it can locate the occ occurrences efficiently within O ( r ) space (in loglogarithmic time each), and reaching optimal time O ( m + occ ) within O ( r log( n/r )) space, on a RAM machine with words of w = Ω(log n ) bits. Raising the space to O ( rw log σ ( n/r )), we support locate in O ( m log( σ )/ w + occ ) time, which is optimal in the packed setting and had not been obtained before in compressed space. We also describe a structure using O ( r log( n/r )) space that replaces the text and efficiently extracts any text substring, with an O (log( n/r )) additive time penalty over the optimum. Preliminary experiments show that our new structure outperforms the alternatives by orders of magnitude in the space/time tradeoff map.