有没有一种算法可以计算文本的香农熵？

Question

我知道英文的香农熵是每个字母1.0到1.5比特，有些人说低至每个字母0.6到1.3比特，但我想知道是否有一种算法可以分析大量文本并确定集体文本的期望值是每个字母0.08比特？

- Polo Montana

---

由于熵的定义是概率性的度量，因此很难以一种完全有意义的方式来衡量它。我可以使用压缩方案将任何给定的文本压缩为一个比特，并将其映射回原始文本，如果我只需要表示两个不同的文本，那么这是绝对没有问题的。因此，在这种情况下，您文本的信息内容为1个比特。 - Oliver Charlesworth

谢谢您的回复。有没有一种方法可以衡量不同文本的冗余性？比如说，如果你有两组1000个单词的文本，你能否衡量其中一个文本比另一个文本更或更少冗余？ - Polo Montana

不带一些上下文的话，这可能是由伪随机数生成器生成的其中之一，如果是这样的话，那就完全没有意义了（除了用于种子生成器的值）。你能说的只是，在某些规则的情况下（例如从前两个字母预测当前字母），你可以按一定比例压缩文本。但选择不同的规则，结果也会不同。 - Oliver Charlesworth

基本问题在于，您必须弄清楚在给定之前的内容的情况下，位流中的下一个位是多么“可预测”。虽然有许多不同的压缩算法利用已知的可预测特征，但没有办法量化某些东西可能是可预测的所有方式。想一想——有些朋友你可以预测他们在特定情况下会逐字逐句地说什么，有些朋友会反复使用相同的短语但顺序不同，而其他朋友则完全不可预测。 - Hot Licks

通过压缩文本（例如：gzip），您可以得到一个合理的估计，并查看压缩比。一个“标准”的文本可能会被压缩到其原始大小的10...20％。 - wildplasser

Answer 1

数学上，一个语言的熵率 的定义是：如果有一个能够生成该语言字符串的源，当假定该源是平稳的时，n-1 个先前符号的条件下第 n 个符号的熵的极限。

一个足够好的近似源是大型英文文本语料库，美国国家开放语料库 是一个很好的选择（100M 字符，涵盖所有文本类别）。然后，用于近似上述极限的基本算法是对于给定的 n，查找在文本中出现的所有 n 元组，并建立在计量熵率计算中涉及到的条件熵的各种概率的统计估计。

完整源代码非常简短而简单，只需大约40行Python代码。我最近写了一篇关于估算英语熵率的博客文章，更详细地介绍了数学定义和完整实现。它还包括对各种相关论文的引用，包括香农的原始文章。

- Clément

---

N-grams并不像通用数据压缩那样强大。因此，N-grams会高估香农熵。像PAQ这样的压缩器保持了压缩记录，并且是目前人类已知的最佳香农估计器。 - usr

@usr：压缩算法高度依赖于数据类型；我不确定世界纪录的主张可能有多少有效性。但确实，评估可压缩性是估计熵的另一种方式。 - Clément

Answer 2

对于文本的香农熵值是估计出来的，准确求得超出人类能力范围。你可以通过运行高效的压缩算法（PAQ）或使用人类来预测给定字符串的下一个字母来估计它。人类会做得很好，因为他们应用语义知识，不仅仅是统计知识或句法知识。

简短回答：尽可能地压缩您拥有的数据/文本，并计算您实际需要的位数。

具体算法取决于您可以将数字降低到多少。这将始终只是香农熵的上限（请记住，永远无法知道确切的价值）。

- usr

---

谢谢您的回复。您知道有哪些软件可以压缩数据/文本并提供数据压缩比吗？ - Polo Montana

“bits/character” 中的压缩比率为（压缩后大小 / 原始大小 * 8）。 - usr

@PoloMontana：只需使用您喜欢的压缩工具，比较文件在压缩前后的大小即可。 - Oliver Charlesworth

@usr 我不确定你提出的建议是否是一个好的度量标准（尽管我认为它是正确的方向）。首先 - 我们应该强调这是香农熵（SE）的_上限_。其次，我们应该将压缩后的大小与相同文本但随机排列的文本进行比较。可以想象有一些编码特定的压缩，这不应计入SE的一部分。假设排列后的文本不能像原始文本那样被压缩，而这种差异是关键的度量标准。 - Hooked

我强调这只是一个上限。随机排列输入很可能会增加它的真实熵，因为它添加了信息。想象一下像ABABABAB...这样几乎没有熵的文本。排列它会添加真正的、真实的、不可压缩的熵。如果你排列文本，你只能使用字符概率来压缩它，这非常有限。 - usr

@usr 我想表达的是，更好的SE估计值应该是将压缩的“ABABABA…”与其压缩排列形式“ABABBAAABABA…”进行比较，而不是将其与未压缩的“ABABABABA”进行比较。此外，“永远无法准确找出。”这句话在考虑到一个模糊的语料库时是正确的，例如每个可能被说出的句子的频率。对于固定的语料库或静态语言，可以精确计算。仍然是一个很好的答案，可以通过给OP举一个简单的例子来进一步完善。 - Hooked

Answer 3

Oli Charlesworth 是正确的，熵是定义在概率上的，而不是文本。

唯一真正能够生成数据无序度量的方法是使用 Kolmogorov 复杂性。尽管这也存在问题，特别是它是不可计算的，而且还没有严格地定义，因为人们必须任意选择一个基础语言—就像 Oli 所说的“上下文”。如果被测量的混乱与要处理的数据相关，则可以解决这种定义问题。因此，在考虑对特定计算机进行压缩时，基础语言将是该计算机的汇编语言。

因此，可以如下定义文本的无序度：

用汇编语言编写的最短程序的长度，该程序输出该文本。

- samthebest

---

“最短程序…”只是另一种谈论可压缩性的方式。程序的大小将由文本的可压缩性（在特定的压缩算法下）以及所需解压缩的代码大小来确定。 - Hot Licks