research
∙
08/07/2023
Collapsing the Hierarchy of Compressed Data Structures: Suffix Arrays in Optimal Compressed Space
In the last decades, the necessity to process massive amounts of textual...
share
research
∙
07/17/2023
Grammar Boosting: A New Technique for Proving Lower Bounds for Computation over Compressed Data
Grammar compression is a general compression framework in which a string...
research
∙
01/04/2022
Dynamic Suffix Array with Polylogarithmic Queries and Updates
The suffix array SA[1..n] of a text T of length n is a permutation of {1...
research
∙
06/24/2021
Breaking the O(n)-Barrier in the Construction of Compressed Suffix Arrays
The suffix array, describing the lexicographic order of suffixes of a gi...
research
∙
05/24/2021
Fast and Space-Efficient Construction of AVL Grammars from the LZ77 Parsing
Grammar compression is, next to Lempel-Ziv (LZ77) and run-length Burrows...
research
∙
10/23/2019
Resolution of the Burrows-Wheeler Transform Conjecture
Burrows-Wheeler Transform (BWT) is an invertible text transformation tha...
research
∙
04/08/2019
String Synchronizing Sets: Sublinear-Time BWT Construction and Optimal LCE Data Structure
Burrows-Wheeler transform (BWT) is an invertible text transformation tha...
research
∙
03/05/2018
String Attractors: Verification and Optimization
String attractors [STOC 2018] are combinatorial objects recently introdu...
research
∙
12/13/2017
Closing in on Time and Space Optimal Construction of Compressed Indexes
Fast and space-efficient construction of compressed indexes such as comp...
research
∙
10/30/2017