9

从我的算法教科书：

一年一度的县赛马将带来三匹从未相互竞争过的纯种马。兴奋地，你研究了他们过去的 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 具有最短的编码，因此在强烈的意义上是最可预测的。

他们是如何获得 420 的 Phantasm 的？我不断收到 400 个字节，如下所示：

结合第一，其他 = 0.4，结合第二，第三 = 0.6。最终以 2 位编码每个位置。

我对霍夫曼编码算法有什么误解吗？

此处提供教科书：http ://www.cs.berkeley.edu/~vazirani/algorithms.html （第 156 页）。

4

1 回答 1

5

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

正确的 Huffman 码是通过以下方式生成的：

  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
于 2010-06-10T16:18:11.303 回答