2026-07-21T20:02:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23250 2025-10-27T10:36:15Z ddc:004 open_access

Bit Packed Encodings for Grammar-Compressed Strings Supporting Fast Random Access Cleary, Alan M. Winjum, Joseph Dood, Jordan Shibata, Hiroki Inenaga, Shunsuke String algorithms data compression random access grammar-based compression Grammar-based compression is a powerful compression technique that allows for computation over the compressed data. While there has been extensive theoretical work on grammar and encoding size, there has been little work on practical grammar encodings. In this work, we consider the canonical array-of-arrays grammar representation and present a general bit packing approach for reducing its space requirements in practice. We then present three bit packing strategies based on this approach - one online and two offline - with different space-time trade-offs. This technique can be used to encode any grammar-compressed string while preserving the virtues of the array-of-arrays representation. We show that our encodings are Nlog₂ N away from the information-theoretic bound, where N is the number of symbols in the grammar, and that they are much smaller than methods that meet the information-theoretic bound in practice. Moreover, our experiments show that by using bit packed encodings we can achieve state-of-the-art performance both in grammar encoding size and run-time performance of random-access queries. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alan M. Cleary and Joseph Winjum and Jordan Dood and Hiroki Shibata and Shunsuke Inenaga 2025 Is Part Of LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2025.12 urn:nbn:de:0030-drops-232506 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.12 eng https://creativecommons.org/licenses/by/4.0/legalcode