Huffman编码及LZW编码 ——Zero 目录 1、编码与解码 2、Huffman编码.ppt

Huffman编码及LZW编码 ——Zero 目录 1、编码与解码 2、Huffman编码 3、LZW编码 4、两者优劣 5、信息熵 编码与解码 编码：将原码转成ASCII码，然后按其二进制编码。 字符 ASCII码 2进制 A 65 B 66 C 67 .... Z 90 编码与解码 ZERO0100010101001111 01011010010001010101001001001111 编码与解码 对应解码： 将编码拆成8位一段，一次还原成ASCII码，然后还原出字符。相当于编码的逆过程。 Huffman编码 据统计：英文字母出现概率如下： 空格 E T O A N I R S 0.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 Y 0.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 Z 0.012 0.011 0.0105 0.008 0.003 0.002 0.001 0.001 0.001 Huffman编码 0 1 0 1 0 1 D W Z E C 非叶子节点编码 导致歧义产生 11 CC？ E？ 编码规则可以看做一颗二叉树： Huffman编码 假设有一棵树。 编码：把每个字符对应路径上的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中选出两个权值最小的节点u,v，建立一个新的节点p，p的两个儿子分别是u,v。权值w(p)=w(u)+w(v)，并将节点p放入集合S中。 4、重复第二步直到退出。 Huffman编码 / T I E S R 2 2 2 2 1 1 IT/IS/TREE 00 01 100 101 110 111 10001001001100001111101101 WPL=2*2+2*2+2*3+2*3 +1*3+1*3=26 基于Huffman树的编码叫做Huffman编码，由于Huffman树是一颗最有二叉树，所以Huffman编码是同类编码中最短的。 LZW编码 Huffman编码尽管已经是同类编码中最优的，但仍有许多局限，首先他是与字符出现顺序无关的，仅仅和频率有关，这就浪费巨大的压缩空间。 另一方面，他所依赖的Huffman树要作为额外信息附加在文件中，这对于小文件的压缩影响是很大的。 LZW编码就很好的弥补了这两个缺陷。 LZW编码 LZW编码步骤如下： 1、初始化字典，读入一个字符放入W中。 2、读入一个字符K： 1不存在字符K可读：输出W对应的字 码。结束编码。 2WK在字典中：将K加入到W末尾。 3WK不在字典中：将字码W输出，然 后将WK加入字典，并令W为K。 LZW编码 编码模拟： ababcbababaaaaaaa 0,1,3,2,4,7,0,9,10,0 编码 字符（串） 0 a 1 b 2 c 3 ab 4 ba 5 abc 6 cb 7 bab 8 baba 9 aa 10 aaa 11 aaaa L