Entropy Lower Bounds for Dictionary Compression
Entropy Lower Bounds for Dictionary Compression
复制标题
字典压缩的熵下界
DOI：
10.4230/lipics.cpm.2019.11
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Michal Ganczorz
中科院分区：
文献类型：
--
作者：
Michal Ganczorz
我们表明，广泛的字典压缩方法（包括LZ 77，LZ 78，语法压缩器以及基于解析的结构）需要|S| 10 - 12 - 2000（|S| k log σ/ logσ| S|）位来编码其输出。这与已知的上界相匹配，并提高了|S|香港（南）为此，我们抽象出这些方法创建的解析的关键属性，构造一个特定的字符串家族，并分析这些字符串的解析。我们还表明，对于k = α logσ，|S|，其中0 < α < 1是常数，上述方法产生大小至少为1 1-α的输出|S| Hk（S）位。因此，我们的结果将字典压缩器与基于上下文的压缩器（如PPM）和基于BWT的压缩器分开，因为这些压缩器包括实现|S| Hk（S）+ O（σ log σ）位，即冗余度取决于k和σ，但不取决于|S|. 2012 ACM学科分类计算理论→数据压缩
We show that a wide class of dictionary compression methods (including LZ77, LZ78, grammar compressors as well as parsing-based structures) require |S|Hk(S) + Ω (|S|k log σ/ logσ |S|) bits to encode their output. This matches known upper bounds and improves the information-theoretic lower bound of |S|Hk(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 = α logσ |S|, where 0 < α < 1 is a constant, the aforementioned methods produce an output of size at least 1 1−α |S|Hk(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|Hk(S) + O(σ log σ) bits, i.e. the redundancy depends on k and σ but not on |S|. 2012 ACM Subject Classification Theory of computation → Data compression