math - 霍夫曼代码中字符的单位代码的条件？

Question

这是我在学校环境中遇到的一个问题，但它一直困扰着我，所以我决定在这里问它。

在霍夫曼压缩中，固定长度的序列（字符）用可变长度的序列编码。代码序列长度取决于源字符的频率（或概率）。

我的问题是：最低最高字符频率是多少，该字符将用一位编码？

Answer 1

事实证明，答案是 0.4，也就是说，如果最高频率p是p >= 0.4，则保证对应字符的 1 位代码。换句话说，这是一个充分条件。

p >= 1/3 也是必要条件。也就是说，可能有0.4 > p >= 1/3的例子，最短代码是 1 位，但如果p < 1/3则没有这样的情况。

对此进行推理的方法是查看代码树的构造方式，特别是最后 3 个幸存子树的频率。一个证明出现在约翰森，“关于二进制霍夫曼码的冗余”，1980 年（不幸的是，这是一个付费链接）。

Answer 2

一般来说，大约 50% 的输入符号流必须由给定符号组成，以便 Huffman 将其编码为单个位。这样做的原因是由于霍夫曼编码的工作方式（一个符号的编码不能是另一个符号的前缀），通过使用单个位对符号进行编码，您要求每个其他符号的第一位是相反的值（即，如果一个符号被编码为0，则其他所有内容都必须以1加上至少一位开头）。由于您正在消除任何给定位长度的一半可能的编码空间，因此您需要获得一种方法来编码至少一半的输入符号以达到收支平衡。

请注意，有一种特殊情况，符号空间仅包含 3 个符号。在这种情况下，具有最高频率的任何符号都将用 1 位编码（因为其他两个将是未选择的第一位值的第二位变体） - 如果 2 或更多具有同样更大的概率，任何一个都可以被编码。因此，在 3 个符号的情况下，具有 34% 概率的符号理论上可以编码为单个位（例如0），而其他两个可能具有 33% 或更低的概率并编码为10和11。

因此，如果您正在考虑所有可能性，那么从技术上讲，任何 1/3 或以上的内容都可能被编码为单个位（在 3 个符号的情况下）。