【开卷数据结构 】哈夫曼编码
在上文中，我们了解了哈夫曼树的基本概念和构造算法，那么哈夫曼树究竟有什么用呢？接下来讲的哈夫曼编码就是哈夫曼树的应用。
目录
🌺哈夫曼编码
如果有一段文字【ABCDEF】要网络传输给别人，在进行数据压缩时，最简单的编码方法就是固定长度编码。
🍁固定长度编码
Q：什么是固定长度编码
A：在数据通信中，若对每个字符用相同的二进制位表示，称这种编码方式为固定长度编码。
有一段文字【BADCADFEED 】，我们可以用相应的二进制的数据表示，如图所示
字母 A B C D E F 二进制字符 000 001 010 011 100 101 这样真正传输的数据就是编码后的 【001000011010000011101100100011】 （三十个字符），对方接收时可以按照3位一分来译码。如果一篇文章很长，这样的二进制串也将长的非常的可怕，那么有没有什么方法可以对其进行压缩的吗？
🍁哈夫曼编码
我们假设各字母出现的频率如下
假设六个字母的频率为 A:27 B:8 C:15 D:15 E:30 F:5 ，合起来正好是 100 ,那就意味着，我们完全可以重新按照赫夫曼树来规划它们。
我们将左分支权值改为0，右分支权值改为1，那么该哈夫曼树就变成了
这时，我们对着六个字母用其从树根到叶所经过路径的 0 与 1 来编码，按照新的字母对应的二进制字符对【BADCADFEED 】进行编码，通过对比可以很明显的发现，字符数量减少了。
- 固定长度编码：001000011010000011101100100011（共30个字符）
- 哈夫曼编码： 1001010010101001000111100 （共25个字符）
哈夫曼编码的特点：
- 对频率高的字符赋以短编码。
- 对频率较低的字符则赋予较长一些的代码。
- 从而使得字符的平均编码长度减短，起到压缩数据的效果。
- 哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。
🍁前缀编码
Q：什么是前缀编码
A：前缀编码是指对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀。
仔细观察，哈夫曼编码其实就是一种前缀编码
Q：前缀编码有什么优点
A：通过观察前缀编码（哈夫曼编码）【1001010010101001000111100】，以及其对应的哈夫曼树，我们发现不会出现容易混淆的编码，比如不会出现与1000，1001混淆的10，100编码。
对前缀编码的解析很简单，因为没有一个编码是其他编码的前缀。所以识别出第一个编码，将它翻译成原码，再对余下的编码文件重复同样的解码操作即可。例如，码串 00101100 可被唯一的翻译成 0，0，101，100 .
🌺文件的编码与译码
🍁编码
有了字符集的哈夫曼编码表之后，对数据文件的编码过程是：依次读人文件中的字符c，在哈夫曼编码表HC中找到此字符，将字符c转换为编码表中存放的编码串。
🍁译码
对编码后的文件进行译码的过程必须借助于哈夫曼树。具体过程是：依次读入文件的二码，从哈夫曼树的根结点(即HT[m])出发，若当前读入0，则走向左孩子，否则走向右孩子。一旦到达某一叶子HT[i]时便译出相应的字符编码HT[i]。然后重新从根出发继续译码，直至文件结束。