[讲义] Huffman编码与lzw编码扩展

1、Huffman编码及LZW编码 Zero目录 1、编码与解码 2、Huffman编码 3、LZW编码 4、两者优劣 5、信息熵编码与解码编码：将原码转成ASCII码，然后按其二进制编码。 字符 ASCII码 2进制 A 65 01000001 B 66 01000010 C 67 01000011 . Z 90 01011010编码与解码ZERO0101101001000101010100100100111101011010010001010101001001001111编码与解码对应解码：将编码拆成8位一段，一次还原成ASCII码，然后还原出字符。相当于编码的逆过程。Huffman编码据统计

2、：英文字母出现概率如下： 空格 E T O A N I R S0.196 0.105 0.072 0.065 0.063 0.059 0.055 0.054 0.052 H D L C F U M P Y0.047 0.035 0.029 0.023 0.0225 0.0225 0.021 0.0175 0.012 W G B V K X J Q Z0.012 0.011 0.0105 0.008 0.003 0.002 0.001 0.001 0.001Huffman编码010101DWZEC非叶子节点编码导致歧义产生11CC？E？编码规则可以看做一颗二叉树：Huffman编码 假设有一棵树

3、。 编码：把每个字符对应路径上的01输出。 解码：按给定01串走，每次走到叶子节点，把节点上的字符输出，然后回到根。Huffman编码 令w(i)表示字符i在文章中的出现次数，l(i)表示字符i在树中的路径长度。 压缩后总长度实际上就是树的带权路径长度WPL=w(i)*l(i) (其中，i是所有出现的字符。) 我们不加证明的给出以下事实：Huffman编码在叶子权值集合不变的情况下，WPL最小的二叉树叫最优二叉树。而Huffman树是一种最优二叉树。Huffman树的构造方法如下：1、每个叶子节点都放入集合S中。2、当S只有1个节点时退出，此时树根就是这个节点。3、否则，从S中选出两个权值最小

4、的节点u,v，建立一个新的节点p，p的两个儿子分别是u,v。权值w(p)=w(u)+w(v)，并将节点p放入集合S中。4、重复第二步直到退出。Huffman编码/TIESR222211IT/IS/TREE1R2E2I2T1S/20001100101110111401401201601100110001001001100001111101101WPL=2*2+2*2+2*3+2*3+1*3+1*3=26基于Huffman树的编码叫做Huffman编码，由于Huffman树是一颗最有二叉树，所以Huffman编码是同类编码中最短的。LZW编码 Huffman编码尽管已经是同类编码中最优的，但仍有许

5、多局限，首先他是与字符出现顺序无关的，仅仅和频率有关，这就浪费巨大的压缩空间。 另一方面，他所依赖的Huffman树要作为额外信息附加在文件中，这对于小文件的压缩影响是很大的。 LZW编码就很好的弥补了这两个缺陷。LZW编码LZW编码步骤如下：1、初始化字典，读入一个字符放入W中。2、读入一个字符K：1不存在字符K可读：输出W对应的字码。结束编码。2WK在字典中：将K加入到W末尾。3WK不在字典中：将字码W输出，然后将WK加入字典，并令W为K。LZW编码编码模拟：ababcbababaaaaaaa0,1,3,2,4,7,0,9,10,0编码编码字符（串）字符（串）0a1b2c3ab4ba5ab

6、c6cb7bab8baba9aa10aaa11aaaaLZW编码LZW解码步骤如下：1、初始化字典，读入一个字码W。2、读入一个字码K：1不存在字码K可读：输出W对应的字符（串）。结束解码。2存在字码K可读：在W对应的字符（串）末尾加入字码K的第一个字符，形成的字符串加入字典。然后输出W对应的字符（串），把K的值给W。两者优劣 Huffman编码，依赖字符出现频率，与字符出现顺序无关，编码解码时占用空间较小，压缩效果略差，压缩出的文件存在额外附加信息，改进空间较小。 LZW编码，依赖字符出现顺序，与字符出现频率无关，编码解码时要占用一定量的空间，压缩效果略好，无附加信息，有较大改进空间。信息熵

7、 信息熵表示数据的不确定性，同时也是确定这个数据之后所得到的信息。 信息熵的公式为H=-pi log pi（log x的底数为2） 如果一个2进制位为1的概率为x，熵为y那么图像为：信息熵 而往往储存1bit的数据，却没有储存1bit的信息。这也就使压缩成为了可能。 在无损压缩算法中，数据量是可变的，而数据所蕴含的信息量是不变的。压缩算法实际上是对信息熵的提炼。信息熵 比如，在一篇文章的一个字符，是e的概率大于其他的字符，尤其是远大于一些偏僻字符。所以在这个位置上写上e，表达的信息量不足数据量，而压缩则是让这个位置的信息熵更大。而lzw也是利用了字典和书写规律，在一篇文章中，I后面往往是接的空格或者是其他