Queries on LZ-Bounded Encodings
Belazzougui, Djamal · Gagie, Travis · Gawrychowski, Paweł · Kärkkäinen, Juha · Ordóñez, Alberto · Puglisi, Simon J. · Tabei, Yasuo
Original · EN
We describe a data structure that stores a string S in space similar to that of its Lempel-Ziv encoding and efficiently supports access, rank and select queries. These queries are fundamental for implementing succinct and compressed data structures, such as compressed trees and graphs. We show that our data structure can be built in a scalable manner and is both small and fast in practice compared to other data structures supporting such queries.
English translation
This paper has no Arabic translation yet. Be the first: it takes a few seconds, and the result is stored for every future reader.