4 papers
Faster Cache-Efficient Pattern Matching for Deterministic Wheeler Pangenome Graphs
Riccardo Maso, Nicola Prezza, Carlo Tosoni
Pattern matching on strings is regarded as one of the core operations in computer science. Although researchers proposed several solutions to this problem, some of the most elegant…
New Entropy Measures for Tries with Applications to the XBWT
Lorenzo Carfagna, Carlo Tosoni
Entropy quantifies the number of bits required to store objects under certain given assumptions. While this is a well established concept for strings, in the context of tries the s…
Indexing Tries within Entropy-Bounded Space
Lorenzo Carfagna, Carlo Tosoni
We study the problem of indexing and compressing tries using a BWT-based approach. Specifically, we consider a succinct and compressed representation of the XBWT of Ferragina et al…
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…