34 citations · 112 across the 32 of their papers we have counts for
4 papers · 1 filter
Queries on LZ-Bounded Encodings
Djamal Belazzougui, Travis Gagie, Paweł Gawrychowski +4
We describe a data structure that stores a string in space similar to that of its Lempel-Ziv encoding and efficiently supports access, rank and select queries. These queries ar…
Faster construction of asymptotically good unit-cost error correcting codes in the RAM model
Djamal Belazzougui
Assuming we are in a Word-RAM model with word size , we show that we can construct in time an error correcting code with a constant relative positive distance that maps n…
Rank, select and access in grammar-compressed strings
Djamal Belazzougui, Simon J. Puglisi, Yasuo Tabei
Given a string of length on a fixed alphabet of symbols, a grammar compressor produces a context-free grammar of size that generates and only . In this p…
Linear time construction of compressed text indices in compact space
Djamal Belazzougui
We show that the compressed suffix array and the compressed suffix tree for a string of length over an integer alphabet of size can both be built in (randomize…