信息来源与记忆的熵率

Question

我有一些英文书写文本并计算它的熵。然而我意识到基于LZ方法的压缩算法在熵给定的限制下压缩得非常少。

这是由于模拟英文文本的信息来源具有记忆。 所以压缩的边界由熵率给出，而不是由该熵的熵给出。

我看到了带有记忆的信息源熵率的定义，但想知道如何用英文写的文本的算法或伪代码计算熵率。

任何想法？

感谢您的帮助。

Answer 1

一般来说，用记忆来估计一个信息源的熵率是一个难题，而且当有很多长距离依赖性时（就像自然语言一样），这是特别困难的。本质上你需要做的是根据样本构建语言的语法，然后计算语法的熵率。您在提取语法时所做的特定假设将会对最终的熵率产生很大的影响，所以您能够做的最好的做法是估计实际熵率的一些相当薄弱的界限资源。

一个常见的做法是简单地通过使用像gzip这样的标准压缩程序压缩大样本来估计熵率，尽管Cosma Shalizi指出这是一个可怕的想法。如果您打算使用通用数据压缩算法，LZ76是更好的选择; FermínMoscoso del Prado有一个paper出来寻找一些替代品。

尽管压缩算法确实给了你一种语法，但它甚至会更好地使用能准确捕获语言中长距离依赖关系的语法。不幸的是，从原始文本样本中学习现实的自然语言语法是一个开放的研究问题。但是，在学习有限状态逼近自然语言方面有一些有前途的工作可用于产生良好的熵率估计。检查出CSSR是一种解决这些问题的方法。