赫夫曼编码&解码

之前说到了如何构建赫夫曼树，那么赫夫曼树有什么用呢？赫夫曼树经典的应用之一就是赫夫曼编码。

1. 赫夫曼编码是什么？

它是一种编码方式，可以用在电讯通信中，或者用于对数据文件进行压缩，压缩率一般在20%到90%。

2. 为什么要有赫夫曼编码？

我们要在网络中传输一句话，首先要将这句话的所有内容转成对应的Ascii码，然后再将Ascii转成二进制，这样一来，可能这句话原本长度是40，经过转换后会变得很长。这种编码方式叫定长编码，效率很低。其实我们可以统计这句话中各个字符出现的次数，然后用二进制数字记录这些字符出现的次数，对这句话进行编码时，将字符替换成对应的二进制就行了，这叫变长编码。但是这种编码方式也会有问题，就是最后传输的二进制串，对方在解码的时候，不知道哪些是要组合起来的，比如最后二进制串是101101……，到底第一位的1是单独解码呢还是要和第二位的0组合起来10才表示一个字符呢？这就造成了解码的多异性。赫夫曼编码就可以解决这个问题。

3. 赫夫曼编码原理：

假如现在要对i like like like java do you like a java这句话(长度是40)进行编码，过程如下：

• 统计各个字符出现的次数：d:1次 y:1次 u:1次 j:2次 v:2次 o:2次 i:4次 k:4次 e:4次 i:5次 a:5次 空格:9次

• 按照上面的字符出现的次数构建赫夫曼树，构建方法和之前讲的构建赫夫曼树一样。

• 根据赫夫曼树，给各个字符编码。规定向左的路径为0，向右路径为1，然后路径数字组合起来就是该字符的编码。比如到a字符的路径是先向右，再向左，再向左，那么a的编码就是100。

• 最终各个字符的编码如下：

o:1000   u:10010   d:100110   y:100111  i:101
a:100   k:1110   e:1111   j:0000   v:0001   l:001   空格:01

• 可以发现，每个字符的编码，都不会是另一个字符编码的前缀，比如空格的编码是01，其他字符，没有是以01开头的，因为到二叉树两个不同的节点路径不可能一样，这样解决了解码多异性的问题。

• 根据各个字符的编码，就可以得到要发送内容编码后的字符串，i是101，空格是01，l是001……要发送内容编码后就是10101001……，长度为133。

• 可以发现，编码后的二进制字符串长度(133)远远超过了原始内容长度(40)，所以还要压缩一下。压缩的方法就是将二进制字符串每8位转成一个数字再转成字节，最终得到的字节数组就是：

-88，-65，-56，-65，-56，-65，-55，77，-57，6，-24，-14，-117，-4，-60，-90，28

长度为17，原始长度是40，压缩率为57.5%。

4. 赫夫曼解码：

本来是要发送i like like like java do you like a java这句话的，最终发送的是-88，-65，-56，-65，-56，-65，-55，77，-57，6，-24，-14，-117，-4，-60，-90，28，对方接收到后怎么还原成原始的那句话呢？其实这就是一个逆向操作了。

• 编码的时候最后一步是压缩，那么这里就先要将接收到的字节数组解压成133位的字符串。即还原成10101001……这个字符串。

• 然后再根据各个字符的编码，还原成原始发送的内容，即用10101001……对照下表，将内容还原即可。

o:1000   u:10010   d:100110   y:100111  i:101
a:100   k:1110   e:1111   j:0000   v:0001   l:001   空格:01

5. 赫夫曼编码解码注意事项：

• 如果文件本身就是经过压缩处理的，比如视频文件、ppt等，压缩率不会很高

• 赫夫曼编码是按字节来处理的，因此可以处理所有的文件

• 如果文件重复的内容不多，压缩率也不高