gzipped 文件小于 Shannon 限制？
gzipped file is smaller than Shannon limit?
我有一个大小为 664KB 的文本文件（使用 ls -l）。据我了解，如果不产生信息 loss，则不能将文件压缩成小于 Shannon Source Coding limit 的任何内容。
我在这里使用了一个程序来计算文本文件 (4.36) 的平均香农熵，并将它乘以它的字符数。我得到 371KB。
然后，我使用了 bzip2，据我所知是 lossless，发现它将文件压缩到 171K。据我了解，没有 losing 信息，没有任何东西可以压缩小于香农限制，那么 bzip 如何压缩比它小的文件 losslessless 呢？我是否遗漏了一些关于 os 如何编码文件的信息？
The text file I used for this experiment is MIT Classic's The Republic by Plato.
The program I used to calculate shannon entropy is this one。它给了我与我用来 cross-check 它的另一个程序相同的结果。
的确，通常我们不能比香农熵压缩得更好（假设没有损失），而且所有 zip 编码都是无损的。
但是，必须考虑几点。
对于香农熵（与某种对数熵相反），假定了一个统计模型来提供信息。
在某些特定情况下（不是完全随机的，遵守某些规则..），可能会发生没有统计模型可以完美处理我们可以拥有的所有先验知识的情况。
然而，这不是这里最重要的问题。通过查看您使用的代码，似乎唯一考虑的统计信息是每个字符的频率。这隐含地假设字符之间没有相关性。
很明显，这是一个非常严格的假设，对于文本文件肯定无效。
很明显，您的压缩算法能够从相邻字符之间的相关性中获益。
这完全取决于模型。
您计算中使用的模型是每个字节值都有一些独立的概率。这称为“0 阶”，因为每个字节位置的概率取决于前零字节。
更复杂的模型会使用前面字节的信息来生成当前字节的概率分布。 bzip2 利用其他字节的上下文，所有通用无损压缩器（如 gzip 和 xz）也是如此。
顺便说一下，pigz 有一个 -H 或 --huffman 选项，它执行 0 阶压缩（仅限霍夫曼编码），并且会接近 0 阶香农限制你正在计算。
我有一个大小为 664KB 的文本文件（使用 ls -l）。据我了解，如果不产生信息 loss，则不能将文件压缩成小于 Shannon Source Coding limit 的任何内容。 我在这里使用了一个程序来计算文本文件 (4.36) 的平均香农熵，并将它乘以它的字符数。我得到 371KB。
然后，我使用了 bzip2，据我所知是 lossless，发现它将文件压缩到 171K。据我了解，没有 losing 信息，没有任何东西可以压缩小于香农限制，那么 bzip 如何压缩比它小的文件 losslessless 呢？我是否遗漏了一些关于 os 如何编码文件的信息？
The text file I used for this experiment is MIT Classic's The Republic by Plato.
The program I used to calculate shannon entropy is this one。它给了我与我用来 cross-check 它的另一个程序相同的结果。
的确，通常我们不能比香农熵压缩得更好（假设没有损失），而且所有 zip 编码都是无损的。
但是，必须考虑几点。
对于香农熵（与某种对数熵相反），假定了一个统计模型来提供信息。
在某些特定情况下（不是完全随机的，遵守某些规则..），可能会发生没有统计模型可以完美处理我们可以拥有的所有先验知识的情况。
然而，这不是这里最重要的问题。通过查看您使用的代码，似乎唯一考虑的统计信息是每个字符的频率。这隐含地假设字符之间没有相关性。
很明显，这是一个非常严格的假设，对于文本文件肯定无效。
很明显，您的压缩算法能够从相邻字符之间的相关性中获益。
这完全取决于模型。
您计算中使用的模型是每个字节值都有一些独立的概率。这称为“0 阶”，因为每个字节位置的概率取决于前零字节。
更复杂的模型会使用前面字节的信息来生成当前字节的概率分布。 bzip2 利用其他字节的上下文，所有通用无损压缩器（如 gzip 和 xz）也是如此。
顺便说一下，pigz 有一个 -H 或 --huffman 选项，它执行 0 阶压缩（仅限霍夫曼编码），并且会接近 0 阶香农限制你正在计算。