Huffman 压缩.ppt

Huffman 压缩 原理 Huffman编码是一种可变长编码方式，是由美国数学家David Huffman创立的，是二叉树的一种特殊转化形式。 编码的原理：将使用次数多的代码转换成长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。 算法原则 Huffman算法的最根本的原则：累计的(字符的统计数字*字符的编码长度)为最小，也就是权值(字符的统计数字*字符的编码长度)的和最小。 1. Huffman树（1） Huffman树是二叉树的一种特殊转化形式。以下是构件Huffman树的例子： 比如有以下数据， ABFACGCAHGBBAACECDFGFAAEABBB 先进行统计A(8) B(6) C(4) D(1) E(2) F(3) G(3) H(1) 括号里面的是统计次数 1. Huffman树（2） 生成Huffman树：每次取最小的那两个节点(node)合并成一个节点(node)，并且将累计数值相加作为新的接点的累计数值，最顶层的是根节点(root) 注：列表中最小节点的是指包括合并了的节点在内的所有节点，已经合并的节点不在列表中 1. Huffman树（3） A(8) B(6) C(4) D(1) E(2) F(3) G(3) H(1) 运算的过程如下： 1:D+H(2) 2:DE+H(4) 3:F+G(6) 4:C+DEH(8) 5:B+FG(12) 6:A+CDEH(16) 7:ACDEH+BFG(28) 那么转化为Huffman树就是 Huffman树 层数 Root ┌┴┐ ACDEH BFG 1 ┌┴┐┌┴┐ CDEH A B FG 2 ┌┴┐ ┌┴┐ DEH C F G 3 ┌┴┐ DH E 4 ┌┴┐ D H 5 如果不使用Huffman算法，而使用普通的编码，结果是什么呢？ Huffman树 层数 Root ┌┴┐ ABCD EFGH 1 ┌┴┐ ┌┴┐ AB CD EF GH 2 ┌┴┐┌┴┐┌┴┐ ┌┴┐ A B C D E F G H 3 2.编码和解码（1） 编码：将ABCDEFGH用Huffman树产生的编码对应着写到文件中，并且保留原始的Huffman树，主要是编码段的信息。 一般要编码256个元素的话需要511个单位来储存Huffman树，每个Huffman树都必须有以下的结构：code,char,left,right,probability(出现次数)，通常情况是利用一个数组结构。 2.编码和解码（2） 因为在解码的时候只需要用到code，所以只需要记录每个元素的编码就可以了。 解码：利用文件中保存的Huffman编码，一一对应，解读编码，把可变长编码转换为定长编码。 3.发展 由于Huffman编码需要扫描两次，第一次是统计数字，第二次是编码写文件，大大影响了速度，因此有人发明了enhanced Huffman aglorithm。这种算法只扫描一遍文件，动态产生Huffman树，即每读n个字节就重新编码一次Huffman树，以达到提高速度的目的。在解码的过程中使用动态还原技术。 * A(8) B(6) C(4) D(1) E(2) F(3) G(3) H(1) 取左面是1 右面是0 则有。 注：层数就是位数或者说是代码长度，权值=代码长度*该字的统计次数。 Huffman树 层数 Root ┌┴┐ ACDEH BFG 1 ┌┴┐┌┴┐ CDEH A B FG 2 ┌┴┐ ┌┴┐ DEH C F G 3 ┌┴┐ DH E 4 ┌┴┐ D H 5 代码 位数 权值 A = 10 2 16 B = 01 2 12 C = 1