Entropy bounds for grammar compression
Entropy bounds for grammar compression
复制标题
语法压缩的熵界限
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Michal Ganczorz
中科院分区：
文献类型：
--
作者：
Michal Ganczorz
在语法压缩中，我们将字符串表示为与上下文无关的语法。该模型具有简单、压缩率高、适合压缩表示处理等特点，在理论和实际应用中都很受欢迎。在实践中，实现压缩需要将这样的语法编码为二进制字符串，这里有几种常用的。我们为几种压缩方法绑定了这种编码的大小，以及众所周知的RePair算法。对于RePair，我们证明了它的标准编码，即熵编码和语法的特殊编码的组合，达到$1.5|S|H_k(S)$。我们还表明，通过在一些迭代后停止，我们可以得到$|S|H_k(S)$。后者尤其重要，因为它解释了在实践中观察到的现象，即引入太多的非终结符会导致位大小增长。我们将我们的方法推广到其他压缩方法，如贪心或不可约语法的宽类，以及其他位编码（包括使用固定长度代码的naive）。我们的方法不仅证明了边界，而且部分地解释了为什么Greedy和RePair在实践中比其他基于语法的方法要好得多。最后，我们表明，对于一个广泛的字典压缩方法（包括语法压缩器）$ omegalleft (nk log sigma/log_sigma n
ight)$位的冗余是必需的。这显示了基于上下文/BWT方法和字典压缩算法之间的分离，因为对于前者，存在冗余不依赖于$n$，而只依赖于$k$~和~$sigma$的方法。
In grammar compression we represent a string as a context free grammar. This model is popular both in theoretical and practical applications due to its simplicity, good compression rate and suitability for processing of the compressed representations. In practice, achieving compression requires encoding such grammar as a binary string, there are a few commonly used. We bound the size of such encodings for several compression methods, along with well-known RePair algorithm. For RePair we prove that its standard encoding, which is a combination of entropy coding and special encoding of a grammar, achieves $1.5|S|H_k(S)$. We also show that by stopping after some iteration we can achieve $|S|H_k(S)$. The latter is particularly important, as it explains the phenomenon observed in practice, that introducing too many nonterminals causes the bit-size to grow. We generalize our approach to other compressions methods like Greedy or wide class of irreducible grammars, and other bit encodings (including naive, which uses fixed-length codes). Our approach not only proves the bounds but also partially explains why Greedy and RePair are much better in practice than the other grammar based methods. At last, we show that for a wide family of dictionary compression methods (including grammar compressors) $Omegaleft(nk log sigma/log_sigma n
ight)$ bits of redundancy are required. This shows a separation between context-based/BWT methods and dictionary compression algorithms, as for the former there exists methods where redundancy does not depend on $n$, but only on $k$~and~$sigma$.