algorithm - 可压缩性示例

Question

来 self 的算法教科书:

The annual county horse race is bringing in three thoroughbreds who have never competed against one another. Excited, you study their past 200 races and summarize these as probability distributions over four outcomes: first (“first place”), second, third, and other.

                       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

Which horse is the most predictable? One quantitative approach to this question is to look at compressibility. Write down the history of each horse as a string of 200 values (first, second, third, other). The total number of bits needed to encode these track-record strings can then be computed using Huffman’s algorithm. This works out to 290 bits for Aurora, 380 for Whirlwind, and 420 for Phantasm (check it!). Aurora has the shortest encoding and is therefore in a strong sense the most predictable.

Phantasm 是怎么得到 420 的？我一直收到 400 字节，如下所示:

首先结合，其他 = 0.4，结合第二，第三 = 0.6。以 2 位编码每个位置结束。

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

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

Answer 1

我认为您是对的:Phantasm 的 200 个结果可以用 400 位(不是字节)来表示。 Aurora 的 290 和 Whirlwind 的 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