可压缩性示例

Question

从我的算法教科书:

一年一度的县赛马比赛将引进三羽从未参加过比赛的纯种马.很兴奋,你研究他们过去的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位,对于Whirlwind来说是380位,对于Phantasm来说是420位(检查它!).Aurora具有最短的编码,因此在强烈意义上是最可预测的.

他们是如何为Phantasm获得420的？我一直得到400字节,如下所示:

首先结合,其他= 0.4,结合第二,第三= 0.6.最终以2位编码每个位置.

有没有我对霍夫曼编码算法误解的东西？

教科书可在此处获得:http://www.cs.berkeley.edu/~vazirani/algorithms.html(第156页).

Answer 1

我认为你是对的：Phantasm 的 200 个结果可以用 400 位（不是字节）表示。290 为 Aurora 和 380 为 Whirlwind 是正确的。

正确的霍夫曼代码是通过以下方式生成的：

1. 结合两个最不可能的结果：0.2 和 0.2。得到 0.4。
2. 结合接下来的两个最不可能的结果：0.3 和 0.3。得到 0.6。
3. 结合 0.4 和 0.6。获得 1.0。

如果你这样做，你会得到 420 位：

1. 结合两个最不可能的结果：0.2 和 0.2。得到 0.4。
2. 结合 0.4 和 0.3。（错！）得到 0.7。
3. 结合 0.7 和 0.3。获得 1.0