压缩性示例

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 和旋风 380 是正确的。

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

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