|
之前说到了如何构建赫夫曼树，那么赫夫曼树有什么用呢？赫夫曼树经典的应用之一就是赫夫曼编码。 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等，压缩率不会很高 赫夫曼编码是按字节来处理的，因此可以处理所有的文件
|
