2026-07-23T05:29:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10482 2024-03-06T10:45:50Z ddc:004 open_access

Entropy Lower Bounds for Dictionary Compression Gańczorz, Michał compression empirical entropy parsing lower bounds We show that a wide class of dictionary compression methods (including LZ77, LZ78, grammar compressors as well as parsing-based structures) require |S|H_k(S) + Omega (|S|k log sigma/log_sigma |S|) bits to encode their output. This matches known upper bounds and improves the information-theoretic lower bound of |S|H_k(S). To this end, we abstract the crucial properties of parsings created by those methods, construct a certain family of strings and analyze the parsings of those strings. We also show that for k = alpha log_sigma |S|, where 0 < alpha < 1 is a constant, the aforementioned methods produce an output of size at least 1/(1-alpha)|S|H_k(S) bits. Thus our results separate dictionary compressors from context-based one (such as PPM) and BWT-based ones, as the those include methods achieving |S|H_k(S) + O(sigma^k log sigma) bits, i.e. the redundancy depends on k and sigma but not on |S|. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michał Gańczorz 2019 Is Part Of LIPIcs, Volume 128, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2019.11 urn:nbn:de:0030-drops-104822 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2019.11 eng https://creativecommons.org/licenses/by/3.0/legalcode