Dynamic entropy-compressed sequences and full-text indexes

DOI10.1145/1367064.1367072zbMath1446.68043MaRDI QIDQ4962737

Veli Mäkinen, Gonzalo Navarro

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1367064.1367072

zbMATH Keywords

entropy; sequences; partial sums; compressed text databases; compressed dynamic data structures

Mathematics Subject Classification ID

68P15: Database theory

68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)

68P05: Data structures

Related Items

Unnamed Item, Extra Space during Initialization of Succinct Data Structures and Dynamical Initializable Arrays., Faster Practical Block Compression for Rank/Select Dictionaries, Fast construction of wavelet trees, Compressed property suffix trees, Space efficient data structures for dynamic orthogonal range counting, Space-efficient data-analysis queries on grids, Efficient fully-compressed sequence representations, Space-efficient construction of Lempel-Ziv compressed text indexes, A four-stage algorithm for updating a Burrows-Wheeler transform, Dynamic rank/select structures with applications to run-length encoded texts, Rank/select on dynamic compressed sequences and applications, Dynamic extended suffix arrays, Approximate string matching with compressed indexes, Grammar compressed sequences with rank/select support, Stronger Lempel-Ziv based compressed text indexing, Fully Functional Static and Dynamic Succinct Trees