java数据结构和算法——赫夫曼编码的介绍

通信领域中信息的处理方式1——定长编码

定长编码原理如下：

通信领域中信息的处理方式2——变长编码

变长编码原理如下：

通信领域中信息的处理方式3-赫夫曼编码

赫夫曼编码原理如下：

1)、传输的字符串

i like like like java do you like a java    

2)、 各个字符对应的个数

d:1 y:1 u:1 j:2  v:2  o:2  l:4  k:4  e:4 i:5  a:5   :9

3）、按照上面字符出现的次数构建一颗赫夫曼树, 次数作为权值

构成赫夫曼树的步骤：
1) 从小到大进行排序, 将每一个数据，每个数据都是一个节点，每个节点可以看成
   是一颗最简单的二叉树
2) 取出根节点权值最小的两颗二叉树 
3) 组成一颗新的二叉树, 该新的二叉树的根节点的权值是前面两颗二叉树
   根节点权值的和  
4) 再将这颗新的二叉树，以根节点的权值大小再次排序，不断重复  1-2-3-4 
   的步骤，直到数列中，所有的数据都被处理，就得到一颗赫夫曼树

4）、根据赫夫曼树，给各个字符,规定编码 (前缀编码)， 向左的路径为0 向右的路径为1 ， 编码如下:

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

5)、 按照上面的赫夫曼编码，我们的"i like like like java do you like a java" 字符串对应的编码为 (注意这里我们使用的无损压缩)

101010011011110111101001101111011110100110111101111010000 110000111001100111100001100111100010010010011011110111101 1100100001100001110

6)、通过赫夫曼编码处理 长度为 133，原来长度是 359 , 压缩了 (359-133) / 359 = 62.9% 。此编码满足前缀编码, 即字符的编码都不能是其他字符编码的前缀。不会造成匹配的多义性，赫夫曼编码是无损处理方案。