搜索
Huffman编码及LZW编码——Zero目录•1、编码与解码•2、Huffman编码•3、LZW编码•4、两者优劣•5、信息熵编码与解码编码：将原码转成ASCII码，然后按其二进制编码。字符ASCII码2进制'A'6501000001'B'6601000010'C'6701000011....'Z'9001011010编码与解码ZERO0101101001000101010100100100111101011010010001010101001001001111编码与解码对应解码：将编码拆成8位一段，一次还原成ASCII码，然后还原出字符。相当于编码的逆过程。Huffman编码据统计：英文字母出现概率如下：空格ETOANIRS0.1960.1050.0720.0650.0630.0590.0550.0540.052HDLCFUMPY0.0470.0350.0290.0230.02250.02250.0210.01750.012WGBVKXJQZ0.0120.0110.01050.0080.0030.0020.0010.0010.001Huffman编码010101DWZEC非叶子节点编码导致歧义产生11CC？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编码/TIESR222211IT/IS/TREE1R2E2I2T1S/20001100101110111401401201601100110001001001100001111101101WPL=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编码编码模拟：ababcbababaaaaaaa0,1,3,2,4,7,0,9,10,0编码字符（串）0a1b2c3ab4ba5abc6cb7bab8baba9aa10aaa11aaaaLZW编码LZW解码步骤如下：1、初始化字典，读入一个字码W。2、读入一个字码K：1不存在字码K可读：输出W对应的字符（串）。结束解码。2存在字码K可读：在W对应的字符（串）末尾加入字码K的第一个字符，形成的字符串加入字典。然后输出W对应的字符（串），把K的值给W。两者优劣•Huffman编码，依赖字符出现频率，与字符出现顺序无关，编码解码时占用空间较小，压缩效果略差，压缩出的文件存在额外附加信息，改进空间较小。•LZW编码，依赖字符出现顺序，与字符出现频率无关，编码解码时要占用一定量的空间，压缩效果略好，无附加信息，有较大改进空间。信息熵•信息熵表示数据的不确定性，同时也是确定这个数据之后所得到的信息。•信息熵的公式为H=∑-pilogpi（logx的底数为2）•如果一个2进制位为1的概率为x，熵为y那么图像为：信息熵•而往往储存1bit的数据，却没有储存1bit的信息。这也就使压缩成为了可能。•在无损压缩算法中，数据量是可变的，而数据所蕴含的信息量是不变的。压缩算法实际上是对信息熵的提炼。信息熵•比如，在一篇文章的一个字符，是e的概率大于其他的字符，尤其是远大于一些偏僻字符。所以在这个位置上写上e，表达的信息量不足数据量，而压缩则是让这个位置的信息熵更大。而lzw也是利用了字典和书写规律，在一篇文章中，I后面往往是接的空格或者是其他分隔符，这样后面那个字符的信息熵就不足1bit。所以lzw和Huffman是从两种不同的方面上进行压缩，所以对应的优缺点也会不同。最完美的压缩可以说是编码后的数据完全无序，任何位置都有平等概率是字符集中的每一个字符。谢谢