Title :
Queries on LZ-Bounded Encodings
Author :
Belazzougui, Djamal ; Gagie, Travis ; Gawrychowski, Pawel ; Karkkainen, Juha ; Ordonez, Alberto ; Puglisi, Simon J. ; Tabei, Yasuo
Author_Institution :
Helsinki Inst. for Inf. Technol. (HIIT), Helsinki, Finland
Abstract :
We describe a data structure that stores a strings 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.
Keywords :
data compression; LZ-bounded encoding; Lempel-Ziv encoding; data compression; Data compression; Data structures; Encoding; Information technology; Silicon; Vegetation; Zirconium;
Conference_Titel :
Data Compression Conference (DCC), 2015
Conference_Location :
Snowbird, UT
DOI :
10.1109/DCC.2015.69
