algorithm - 为什么霍夫曼编码好？

Question

我不是询问霍夫曼编码是如何工作的，而是想知道它为什么好。

我有以下两个问题:

第一季度

我理解哈夫曼编码的最终目的是让某个字符的位数更少，从而节省空间。我不明白的是，为什么一个字符的位数决定可以与字符的频率有关？

Huffman Encoding Trees说

It is sometimes advantageous to use variable-length codes, in which different symbols may be represented by different numbers of bits. For example, Morse code does not use the same number of dots and dashes for each letter of the alphabet. In particular, E, the most frequent letter, is represented by a single dot.

所以在摩尔斯电码中，E可以用一个点来表示，因为它是出现频率最高的字母。但为什么？为什么它出现频率最高就可以是点？

第二季度

为什么字符的概率/统计对霍夫曼编码如此重要？

统计表出错了怎么办？

Answer 1

如果您为最常使用的符号分配更少的数字或位或更短的代码单词，您将节省大量存储空间。

假设您要为英文字母分配 26 个唯一代码，并希望根据这些代码存储一本英文小说(仅字母)，如果您为最常出现的字符分配短长度代码，则需要的内存更少。

您可能已经注意到，重要城市的邮政编码和 STD 代码通常较短(因为它们经常使用)。这是信息论中非常基本的概念。

霍夫曼编码给出前缀码。

哈夫曼树的构造:

为n个字符构造霍夫曼树的贪心方法如下:

在 n 个子树中放置 n 个字符。首先将两个权重最小的节点组合成一棵树，该树被分配两个叶节点权重的总和作为其根节点的权重。这样做直到你得到一棵树。

例如考虑下面的二叉树，其中 E 和 T 具有高权重(出现频率很高)

它是一个前缀树。要得到任何字符的哈夫曼编码，从字符对应的节点开始，回溯到根节点。