有关的熵到损压缩率

Question

从 香的来源编码原理 我们知道，熵的一个压缩串受熵的原串像这样：

H(X) <= L < H(X) + 1/N 

其中H(X)熵源字符串中，N为长的源串，我是预期的长度压缩串。

这必然意味着有一个限制无损的压缩。

我想知道的是：

• 我们可以直接涉及熵到一些预期压缩比?

• 我们可以使用的熵找到一些上限，用于压缩比?

Answer 1

你不能直接涉及熵压缩比不知道的长度源string,但是你可以看到这理论上的限制到最大压缩比通过解决对于可能的最小值。你可以用这种限制作为标准的效率的压缩算法，尽管一个糟糕的指标并不意味着一个更好的算法已经发现了或甚至存在。

所以，是的。你可以使用熵找到理论上的最大损压缩比率，但是没有，你不能用它来确定预期压缩比率对于任何给定的压缩算法。

Answer 2

香农定理定义而言的随机数据和概率。同样地， 熵 一串是唯一定义为随机的字符串--熵是一个属性的分布，不符自己。因此，我们可以重申了香农定理非正式方式为：

如果你随机选择一串的自给率分布，那么最好的平均压缩比我们可以得到的串通过熵率的概率分布。

给任何随机的字符串，我可以很容易地编写压缩算法，将压缩，串下降到1位，但是我的算法将一定长度的增加一些其他的琴弦。我压缩算法的工作如下：

1. 如果输入等于字符串 一些预先选择的随机的字符串, 输出是1-bit string"0"
2. 否则，输出是N+1位字符串的"1"随后通过输入字符串

相应的解压缩算法是：

1. 如果输入"0"，其输出是 我们之前预先选择的随机的字符串
2. 否则，出的一切除了第输入点

这里的关键是，我们不能写下来 一个 算法，对于所有串从一个赋予分发，压缩了他们 所有 在高利率的平均水平。这里还有太多的弦。

如果我们有一个给出的概率分布的串，我们可以计算出的熵率的分配，然后如果随机挑一串 根据分布 并且尝试使用压缩 任何 算法，相对大小压缩string会，平均而言，永远不得少于熵率。这是什么香农定理说。

Answer 3

是的。的 熵率 英语是经常被援引作为1.5位的每个字符的(或).典型的编码使用的8位的每个字符。所以最大限度地压缩的文本应是1.5/8(~19%)的尺寸原来的。实际结果的纯文本版本的简*奥斯汀的傲慢与偏见：orig=701K,bzip2=178K，~25%以上。

Answer 4

是的！我认为 这纸 将你指出正确的方向。

ETA 看起来你需要一个IEEE件的读取实际的纸张。如果有人能找到一个公开提供的资源(或解释的数学这里的)，那会好得多，当然！