huffman 压缩

一、huffman二叉树原理

1、将数组按每个数值的权重大小，最小两个权重的数值合并组成一个二叉树，新的二叉树节点值取代原有的两个数值，成为数组的新值，并具有新的权重（原权重相加）；

2、新的数组继续取最小权重形成新的二叉树，取代原两数，形成新数组，以此不断循环，直至数组合并成一个值，并形成一个二叉数"森林"——即以最后一个数为根，每层分叉形成两叉；

3、每个数值根据二叉树路径（0,1)形成二进制的huffman编码，并取代原数值。

二、huffman二叉树在文件压缩中的应用

1、文件的每个字节就是数组的每个数值，数值的权重由数值出现的次数取代；

2、每次分叉用1个bit表示，值为0或1。

3、每层一个bit，n层就n个bit，出现次数最多（权重最大的）最靠近根部，也就是用两个bit，出现次数越少，越远离根部，需要更多bits表示。

4、原理用8bits表示的字节，由于靠近根部，可能用2个bits表示，每个字节少6个bits，加上此类字节是文件出现次数最多的字节，节约的bits就会相当可观；虽然远离根部的字节需要较多的bits表示，甚至可能多过8bits，而其出现次数少，增加bits较前面出现频率高的字节减少的字节相比就少得可怜！

以“today,is,a,good,day”(为直观用‘，’代替空格)为例解释huffman压缩。

（1）形成字节数组及其权重

字节数组	t	o	d	a	y	,	i	s	g
权重（出现频率）	1	3	2	2	2	4	1	1	1

(2)生成二叉树

(3)形成huffman编码。

字节数组	t	o	d	a	y	,	i	s	g
huffman编码	0000	100	010	011	101	11	0001	0010	0011

（4）用编码代替原字符

t	o	d	a	y	,	i	s	,	a	,	g	o	o	d	,	d	a	y
1110100	1101111	1100100	1100001	1111001	101100	1101001	1110011	101100	1100001	101100	1100111	1101111	1101111	1100100	101100	1100100	1100001	1111001
0000	100	010	011	101	11	0001	0010	11	011	11	0011	100	100	010	11	010	011	101

压缩前152bits，压缩后51bits，压缩比33.5%。

三、huffman解压

huffman编码存在不包含“前缀”特性，即n个bits的编码的前（n-1)位绝对不存在编码表中！！！如上表中由于有编码‘0000’，故不会存在‘0’，‘00’，‘000’等编码。有‘100’，绝不存在‘10’。

解压利用这特性，先取两位bits，看是否匹配编码表，不匹配，就取3位，直至匹配；接着循环取，直到结束。