1 citations · 1 across the 6 of their papers we have counts for
7 papers · 1 filter
Compressing Suffix Trees by Path Decompositions
Ruben Becker, Davide Cenzato, Travis Gagie +4
The suffix tree is arguably the most fundamental data structure on strings: introduced by Weiner (SWAT 1973) and McCreight (JACM 1976), it allows solving a myriad of computational…
The Trie Measure, Revisited
Jarno N. Alanko, Ruben Becker, Davide Cenzato +4
In this paper, we study the following problem: given subsets of an integer universe , having total cardinality ,…
Encoding Co-Lex Orders of Finite-State Automata in Linear Space
Ruben Becker, Nicola Cotumaccio, Sung-Hwan Kim +2
The Burrows-Wheeler transform (BWT) is a string transformation that enhances string indexing and compressibility. Cotumaccio and Prezza [SODA '21] extended this transformation to n…
Suffixient Arrays: a New Efficient Suffix Array Compression Technique
Davide Cenzato, Lore Depuydt, Travis Gagie +4
The Suffix Array is a classic text index enabling on-line pattern matching queries via simple binary search. The main drawback of the Suffix Array is that it takes linear space in…
Algorithms for Galois Words: Detection, Factorization, and Rotation
Diptarama Hendrian, Dominik Köppl, Ryo Yoshinaka +1
Lyndon words are extensively studied in combinatorics on words -- they play a crucial role on upper bounding the number of runs a word can have [Bannai+, SIAM J. Comput.'17]. We ca…
Computing the LCP Array of a Labeled Graph
Jarno Alanko, Davide Cenzato, Nicola Cotumaccio +3
The LCP array is an important tool in stringology, allowing to speed up pattern matching algorithms and enabling compact representations of the suffix tree. Recently, Conte et al.…
Sketching and Streaming for Dictionary Compression
Ruben Becker, Matteo Canton, Davide Cenzato +3
We initiate the study of sub-linear sketching and streaming techniques for estimating the output size of common dictionary compressors such as Lempel-Ziv '77, the run-length Burrow…