可压缩性示例
从我的算法教科书：
一年一度的县级赛马会带来三匹从未相互竞争过的纯种马。 兴奋的是，你研究了他们过去的200场比赛，并将这些比赛概括为四个结果的概率分布：第一个（“第一名”），第二名，第三名和其他。
Outcome Aurora Whirlwind Phantasm
first 0.15 0.30 0.20
second 0.10 0.05 0.30
third 0.70 0.25 0.30
other 0.05 0.40 0.20
哪匹马是最可预测的？ 对这个问题的一种量化方法是考虑可压缩性。 将每匹马的历史记录为一串200个值（第一，第二，第三，其他）。 然后可以使用霍夫曼算法计算编码这些记录字符串所需的位总数。 这对于Aurora来说是290比特，对于旋风来说是380比特，对于Phantasm来说则是420（检查它！）。 Aurora具有最短的编码，因此在最强烈的意义上是最可预测的。
他们是如何得到Phantasm 420的？ 我一直得到400字节，如下所示：
先结合，其他= 0.4，结合第二，第三= 0.6。 最终以2位编码每个位置。
有什么我误解了霍夫曼编码算法吗？
教科书可在此访问：http://www.cs.berkeley.edu/~vazirani/algorithms.html（第156页）。
我认为你是对的：Phantasm的200个结果可以用400位（而不是字节）表示。 奥罗拉的290和旋风的380是正确的。
以下列方式生成正确的霍夫曼码：
如果你这样做，你会得到420位：