Nicola Prezza

Practical and Effective Re-Pair Compression

2017 · arXiv (Cornell University)

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 algorithm computing Re-Pair uses $(1+ε)n+\sqrt n$ words on top of the re-writable text …

gsufsort: constructing suffix arrays, LCP arrays and BWTs for string collections

2020 · Algorithms for Molecular Biology

BACKGROUND: The construction of a suffix array for a collection of strings is a fundamental task in Bioinformatics and in many other applications that process strings. Related data structures, as the Longest Common Prefix array, …

On Locating Paths in Compressed Tries

2021 · Society for Industrial and Applied Mathematics eBooks

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. …