哈夫曼编码

相关概念

• 前缀编码：任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。
• 等长编码：各个字符的编码长度都相等。
• 不等长编码：各个字符的编码长度不等（不全相等）。

不等长编码的好处：可以使传送电文的字符串的总长度尽可能地短。

对出现频率高的字符采用尽可能短的编码，则传送电文的总长便可减少。

哈夫曼编码构造

利用二叉树设计前缀编码：向左为 0，向右为 1，每个叶子结点的路径可组成编码。

这是一个不等长的前缀编码，不会混淆同时可以保证传输效率。

总编码长度等于 Huffman 树的带权路径长度 WPL。

Huffman 编码是一种前缀编码，解码时不会混淆。

链接到

• 上一个知识点：6.12 哈夫曼树的构造
• 下一个知识点：无（本章最后一个知识点）