2026-07-22T16:01:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15497 2024-03-06T10:55:26Z ddc:004 open_access

Repetition- and Linearity-Aware Rank/Select Dictionaries Ferragina, Paolo Manzini, Giovanni Vinciguerra, Giorgio Data compression Compressed data structures Entropy We revisit the fundamental problem of compressing an integer dictionary that supports efficient rank and select operations by exploiting two kinds of regularities arising in real data: repetitiveness and approximate linearity. Our first contribution is a Lempel-Ziv parsing properly enriched to also capture approximate linearity in the data and still be compressed to the kth order entropy. Our second contribution is a variant of the block tree structure whose space complexity takes advantage of both repetitiveness and approximate linearity, and results highly competitive in time too. Our third and final contribution is an implementation and experimentation of this last data structure, which achieves new space-time trade-offs compared to known data structures that exploit only one of the two regularities. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paolo Ferragina and Giovanni Manzini and Giorgio Vinciguerra 2021 Is Part Of LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2021.64 urn:nbn:de:0030-drops-154974 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.64 eng https://creativecommons.org/licenses/by/4.0/legalcode