哈夫曼编码encode

1、【精品文档】如有侵权，请联系网站删除，仅供学习与交流哈夫曼编码encode.精品文档.哈夫曼编码(Huffman Coding)From May10 AlgorithmJump to: navigation, searchTemplate:Translation 哈夫曼编码(Huffman Coding)是一種編碼方式，以哈夫曼树即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在 计算机 信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表

2、的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由David.A.Huffman发展起来的。 例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准

3、确的估算，就可以大幅度提高无损压缩的比例。 In computer science, Huffman coding is an entropy encoding algorithm used for lossless data compression. The term refers to the use of a variable-length code table for encoding a source symbol (such as a character in a file) where the variable-length code table has been derived

4、 in a particular way based on the estimated probability of occurrence for each possible value of the source symbol. It was developed by David A. Huffman as a Ph.D. student at MIT in 1952, and published in A Method for the Construction of Minimum-Redundancy Codes. 哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径

5、长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+.+Wn*Ln)，N个权值Wi(i=1,2,.n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,.n)。可以证明哈夫曼树的WPL是最小的。 从树中一个结点到另一个结点之间的构成这两个结点之间的路径，路径上的分支数目称做路径长度。树的路径长度是从树根到每一结点的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和

6、，通常记作 。假设有n个权值1,2, , n，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为i，则其中带权路径长度WPL最小的二叉树称做最优二叉树或赫夫曼树。赫夫曼树构造的算法（圆圈表示叶结点，方块表示非终端结点）。 (关于哈夫曼编码的其他代码) /* 赫夫曼树和赫夫曼编码的存储表示 */typedef struct unsigned int weight; unsigned int parent,lchild,rchild;HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树 */typedef char *HuffmanCode; /* 动态分配数组存储赫夫曼编码

7、表 */* 求赫夫曼编码 */#include"c1.h"#include"c6-7.h"#include"func6-1.c"void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) /* 算法6.12 */ /* w存放n个字符的权值(均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC */ int m,i,s1,s2,start; unsigned c,f; HuffmanTree p; char *cd; if(n<=1) return

8、; m=2*n-1; *HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /* 0号单元未用 */ for(p=*HT+1,i=1;i<=n;+i,+p,+w) (*p).weight=*w; (*p).parent=0; (*p).lchild=0; (*p).rchild=0; for(;i<=m;+i,+p) (*p).parent=0; for(i=n+1;i<=m;+i) /* 建赫夫曼树 */ /* 在HT1i-1中选择parent为0且weight最小的两个结点，其序号分别为s1和s2 */ select(*HT,i-1,&

9、amp;s1,&s2); (*HT)s1.parent=(*HT)s2.parent=i; (*HT)i.lchild=s1; (*HT)i.rchild=s2; (*HT)i.weight=(*HT)s1.weight+(*HT)s2.weight; /* 从叶子到根逆向求每个字符的赫夫曼编码 */ *HC=(HuffmanCode)malloc(n+1)*sizeof(char*); /* 分配n个字符编码的头指针向量(0不用) */ cd=(char*)malloc(n*sizeof(char); /* 分配求编码的工作空间 */ cdn-1='0' /* 编码结

10、束符 */ for(i=1;i<=n;i+) /* 逐个字符求赫夫曼编码 */ start=n-1; /* 编码结束符位置 */ for(c=i,f=(*HT)i.parent;f!=0;c=f,f=(*HT)f.parent) /* 从叶子到根逆向求编码 */ if(*HT)f.lchild=c) cd-start='0' else cd-start='1' (*HC)i=(char*)malloc(n-start)*sizeof(char); /* 为第i个字符编码分配空间 */ strcpy(*HC)i,&cdstart); /* 从cd复制

11、编码(串)到HC */ free(cd); /* 释放工作空间 */void main() HuffmanTree HT; HuffmanCode HC; int *w,n,i; printf("请输入权值的个数(>1): "); scanf("%d",&n); w=(int*)malloc(n*sizeof(int); printf("请依次输入%d个权值(整型):n",n); for(i=0;i<=n-1;i+) scanf("%d",w+i); HuffmanCoding(&HT,

12、&HC,w,n); for(i=1;i<=n;i+) puts(HCi);/*无栈非递归遍历赫夫曼树，求赫夫曼编码*/#include"c1.h"#include"c6-7.h"#include"func6-1.c"void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *w,int n) */ /* w存放n个字符的权值(均>0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC */ int m,i,s1,s2; /* 此句与algo6-1.c不同 */ u

13、nsigned c,cdlen; /* 此句与algo6-1.c不同 */ HuffmanTree p; char *cd; if(n<=1) return; m=2*n-1; *HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /* 0号单元未用 */ for(p=*HT+1,i=1;i<=n;+i,+p,+w) (*p).weight=*w; (*p).parent=0; (*p).lchild=0; (*p).rchild=0; for(;i<=m;+i,+p) (*p).parent=0; for(i=n+1;i<=m;+i

14、) /* 建赫夫曼树 */ /* 在HT1i-1中选择parent为0且weight最小的两个结点，其序号分别为s1和s2 */ select(*HT,i-1,&s1,&s2); (*HT)s1.parent=(*HT)s2.parent=i; (*HT)i.lchild=s1; (*HT)i.rchild=s2; (*HT)i.weight=(*HT)s1.weight+(*HT)s2.weight; /* 以下为算法6.13，无栈非递归遍历赫夫曼树，求赫夫曼编码，以上同算法6.12 */ *HC=(HuffmanCode)malloc(n+1)*sizeof(char*);

15、 /* 分配n个字符编码的头指针向量(0不用) */ cd=(char*)malloc(n*sizeof(char); /* 分配求编码的工作空间 */ c=m; cdlen=0; for(i=1;i<=m;+i) (*HT)i.weight=0; /* 遍历赫夫曼树时用作结点状态标志 */ while(c) if(*HT)c.weight=0) /* 向左 */ (*HT)c.weight=1; if(*HT)c.lchild!=0) c=(*HT)c.lchild; cdcdlen+='0' else if(*HT)c.rchild=0) /* 登记叶子结点的字符的编

16、码 */ (*HC)c=(char *)malloc(cdlen+1)*sizeof(char); cdcdlen='0' strcpy(*HC)c,cd); /* 复制编码(串) */ else if(*HT)c.weight=1) /* 向右 */ (*HT)c.weight=2; if(*HT)c.rchild!=0) c=(*HT)c.rchild; cdcdlen+='1' else /* HTc.weight=2，退回 */ (*HT)c.weight=0; c=(*HT)c.parent; -cdlen; /* 退到父结点，编码长度减1 */ fr

17、ee(cd);void main() /* 主程序同algo6-1.c */ HuffmanTree HT; HuffmanCode HC; int *w,n,i; printf("请输入权值的个数(>1): "); scanf("%d",&n); w=(int *)malloc(n*sizeof(int); printf("请依次输入%d个权值(整型):n",n); for(i=0;i<=n-1;i+) scanf("%d",w+i); HuffmanCoding(&HT,&H

18、C,w,n); for(i=1;i<=n;i+) puts(HCi);关于哈夫曼编码的其他代码From May10 AlgorithmJump to: navigation, search-Brianchon 08:22, 22 4月 2006 (CDT) 基本类型： typedef char label_t;typedef int weight_t;哈夫曼树结点： typedef struct _T_node node_t, *node_p;struct _T_node weight_t Weight; node_p Left; union label_t Label; node_p

19、Right; U;下面的代码接受N(N>0)个标签L和相应的权值W，以此构造哈夫曼树： node_p Huffman(label_p L, weight_p W, int N) node_p A = (node_p)malloc(2*N-1)*sizeof(*A); int i, j;将叶子结点初始化到前N个结点中去，我们通过堆来选出结点并甩到数组后面，它们的位置不再改变，保证了指向它们的指针有效。新生成的内结点取代最后被选出的结点放在A0，然后通过下筛入堆。堆总是在数组A的前端并规模递减，这样堆可以一直维护着而无需重建。最后生成的内结点是根结点，它正好是放置在A0，这样我们返回的根结点

20、指针也是分配出的内存块指针A，可以用于稍后的free()调用。 for ( i = 0, i < N; +i ) Ai.Left = 0; Ai.U.Label = Li; Ai.Weight = Wi;通过下筛过程建堆，下筛建堆可以在线性时间内完成。 for ( i = N/2-1; i >= 0; -i ) Sift(A, i, N); 建立树的过程是：不断从堆中提取权值最小的两个结点，并创建连接这两个结点的内结点，然后将其纳入堆中。Ai是堆中的最后一个结点，j指向上次被选出的结点，新选出的结点将紧接在它们前面放置。 i = N-1, j = 2*N-1; while ( i

21、> 0 ) A-j = A0; Sift_new(A, 0, i, A+i); A-j = A0; A0.Left = A+j; A0.U.Right = A+j+1; A0.Weight = Aj.Weight+Aj+1.Weight; Sift(A, 0, i-); return A;下筛例程如下，这样写的目的是为了尽量减少结构的赋值。Sift_new从Ai开始向下在堆中寻找合适的位置放置新结点Node，Ai开始时是空闲的。 void Sift_new(node_p A, int i, int N, node_p Node) for (   ) int j = (

22、i+1)*2; if ( j > N ) break; if ( j = N | Aj-1.Weight < Aj.Weight ) -j; if ( Node->Weight <= Aj.Weight ) break; Ai = Aj; i = j; Ai = *Node;void Sift(node_p A, int i, int N) int j = (i+1)*2; if ( j <= N ) if ( j = N | Aj-1.Weight < Aj.Weight ) -j; if ( Ai.Weight > Aj.Weight ) node

23、_t T = Ai; Ai = Aj; Sift_new(A, j, N, &T);RLE RLE又叫Run Length Encoding，是一个针对无损压缩的非常简单的算法。它用重复字节和重复的次数来简单描述来代替重复的字节。尽管简单并且对于通常的压缩非常低效，但它有的时候却非常有用（例如，JPEG就使用它）。1.1. 原理图2.1显示了一个如何使用RLE算法来对一个数据流编码的例子，其中出现六次的符号93已经用3个字节来代替：一个标记字节（0在本例中）重复的次数（6）和符号本身（93）。RLE解码器遇到符号0的时候，它表明后面的两个字节决定了需要输出哪个符号以及输出多少次。1.2

24、. 实现RLE可以使用很多不同的方法。基本压缩库中详细实现的方式是非常有效的一个。一个特殊的标记字节用来指示重复节的开始，而不是对于重复非重复节都coding run。因此非重复节可以有任意长度而不被控制字节打断，除非指定的标记字节出现在非重复节（顶多以两个字节来编码）的稀有情况下。为了最优化效率，标记字节应该是输入流中最少出现的符号（或许就不存在）。重复runs能够在32768字节的时候运转。少于129字节的要求3个字节编码（标记+次数+符号），而大雨128字节要求四个字节（标记+次数的高4位|0x80+次数的低4位）。这是通常所有采用的压缩的做法，并且也是相比较三个字节固定编码（允许使用3

25、个字节来编码256个字节）而言非常少见的有损压缩率的方法。在这种模式下，最坏的压缩结果是：输出大小=257/256*输入大小+12.   哈夫曼哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号，长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示，而不常见的符号需要很多为来表示。哈夫曼算法在改变任何符号二进制编码引起少量密集表现方面是最佳的。然而，它并不处理符号的顺序和重复或序号的序列。2.1. 原理我不打算探究哈夫曼编码的所有实际的细节，但基本的原理是为每个符号找到新的二进制表示，从而通常符号使用很少的位，不常见的符号使用较多的位。简短的说，这

26、个问题的解决方案是为了查找每个符号的通用程度，我们建立一个未压缩数据的柱状图；通过递归拆分这个柱状图为两部分来创建一个二叉树，每个递归的一半应该和另一半具有同样的权（权是NK =1符号数k, N是分之中符号的数量，符号数k是符号k出现的次数）这棵树有两个目的：1  编码器使用这棵树来找到每个符号最优的表示方法2  解码器使用这棵树唯一的标识在压缩流中每个编码的开始和结束，其通过在读压缩数据位的时候自顶向底的遍历树，选择基于数据流中的每个独立位的分支，一旦一个到达叶子节点，解码器知道一个完整的编码已经读出来了。我们来看一个例子会让我们更清楚。图2.2显示了一个10个字节的未压

27、缩的数据。根据符号频率，哈夫曼编码器生成哈夫曼树（图2.4）和相应的编码表示（图2.3）。 你可以看到，常见的符号接近根，因此只要少数位来表示。于是最终的压缩数据流如图2.5所示。压缩后的数据流是24位（三个字节），原来是80位（10个字节）。当然，我应该存储哈夫曼树，这样解码器就能够解码出对应的压缩流了，这就使得该例子中的真正数据流比输入的流数据量大。这是相对较短的数据上的副作用。对于大数据量来说，上面的哈夫曼树就不占太多比例了。解码的时候，从上到下遍历树，为压缩的流选择从左/右分支，每次碰到一个叶子节点的时候，就可以将对应的字节写到解压输出流中，然后再从根开始遍历。2.2. 实现哈夫曼编码

28、器可以在基本压缩库中找到，其是非常直接的实现。这个实现的基本缺陷是：1  慢位流实现2  相当慢的解码（比编码慢）3  最大的树深度是32（编码器在任何超过32位大小的时候退出）。如果我不是搞错的话，这是不可能的，除非输出的数据大于232字节。另一方面，这个实现有几个优点：1  哈夫曼树以一个紧密的形式每个符号要求12位（对于8位的符号）的方式存储，这意味着最大的头为384。2  编码相当容易理解哈夫曼编码在数据有噪音的情况（不是有规律的，例如RLE）下非常好，这中情况下大多数基于字典方式的编码器都有问题。3.   Rice

29、对于由大word（例如：16或32位）组成的数据和教低的数据值，Rice编码能够获得较好的压缩比。音频和高动态变化的图像都是这种类型的数据，它们被某种预言预处理过（例如delta相邻的采样）。尽管哈夫曼编码处理这种数据是最优的，却由于几个原因而不适合处理这种数据（例如：32位大小要求16GB的柱状图缓冲区来进行哈夫曼树编码）。因此一个比较动态的方式更适合由大word组成的数据。3.1. 原理Rice编码背后的基本思想是尽可能的用较少的位来存储多个字（正像使用哈夫曼编码一样）。实际上，有人可能想到Rice是静态的哈夫曼编码（例如，编码不是由实际数据内容的统计信息决定，而是由小的值比高的值常见的假

30、定决定）。编码非常简单：将值X用X个1位之后跟一个0位来表示。3.2. 实现在基本压缩库针对Rice做了许多优化：1  每个字最没有意义的位被存储为k和最有意义的N-k位用Rice编码。K作为先前流中少许采样的位平均数。这是通常最好使用Rice编码的方法，隐藏噪音且对于动态变化的范围并不导致非常长的Rice编码。2  如果rice编码比固定的开端长，T，一个可选的编码：输出T个1位，紧跟（log2(X-T)）个1和一个0位，接着是X-T（最没有意义的(log2(X-T)-1位）。这对于大值来说都是比较高效的代码并且阻止可笑的长Rice编码（最坏的情况，对于一个32位word

31、单个Rice编码可能变成232位或512MB）。如果开端是4，下面是结果编码表：X bin Rice Thresholded Rice 0 00000 0 0   1 00001 10 10   2 00010 110 110   3 00011 1110 1110   4 00100 11110 11110   5 00101 111110 111110   6 00110 1111110 11111100 +1 7 00111 11111110 11111101 

32、0; 8 01000 111111110 1111111000 +1 9 01001 1111111110 1111111001   10 01010 11111111110 1111111010 -1 11 01011 111111111110 1111111011 -2 12 01100 1111111111110 111111110000   13 01101 11111111111110 111111110001 -1 14 01110 111111111111110 111111110010 -2 15 01111 111111111

33、1111110 111111110011 -3 16 10000 11111111111111110 111111110100 -4 17 10001 111111111111111110 111111110101 -5 18 10010 1111111111111111110 111111110110 -6 19 10011 11111111111111111110 111111110111 -7 20 10100 111111111111111111110 11111111100000 -5 就像你看到的一样，在这个实现中使用threshold方法仅仅两个编码导致一个最坏的情况；剩下的编码

34、产生比标准Rice编码还要短的编码。3  最坏的情况，输出。4.   Lempel-Ziv (LZ77)Lempel-Ziv压缩模式有许多不同的变量。基本压缩库有清晰的LZ77算法的实现（Lempel-Ziv，1977），执行的很好，源代码也非常容易理解。LZ编码器能用来通用目标的压缩，特别对于文本执行的很好。它也在RLE和哈夫曼编码器（RLE，LZ，哈夫曼）中使用来大多数情况下获得更多的压缩。4.1. 原理在LZ压缩算法的背后是使用RLE算法用先前出现的相同字节序列的引用来替代。简单的讲，LZ算法被认为是字符串匹配的算法。例如：在一段文本中某字符串经常出现，并且

35、可以通过前面文本中出现的字符串指针来表示。当然这个想法的前提是指针应该比字符串本身要短。例如，在上一段短语“字符串”经常出现，可以将除第一个字符串之外的所有用第一个字符串引用来表示从而节省一些空间。一个字符串引用通过下面的方式来表示：1  唯一的标记2  偏移数量3  字符串长度由编码的模式决定引用是一个固定的或变动的长度。后面的情况经常是首选，因为它允许编码器用引用的大小来交换字符串的大小（例如，如果字符串相当长，增加引用的长度可能是值得的）。4.2. 实现使用LZ77的一个问题是由于算法需要字符串匹配，对于每个输入流的单个字节，每个流中此字节前面的哪个字节都必

36、须被作为字符串的开始从而尽可能的进行字符串匹配，这意味着算法非常慢。另一个问题是为了最优化压缩而调整字符串引用的表示形式并不容易。例如，必须决定是否所有的引用和非压缩字节应该在压缩流中的字节边界发生。基本压缩库使用一个清晰的实现来保证所有的符号和引用是字节对齐的，因此牺牲了压缩比率，并且字符串匹配程序并不是最优化的（没有缓存、历史缓冲区或提高速度的小技巧），这意味着程序非常慢。另一方面，解压缩程序非常简单。一个提高LZ77速度的试验已经进行了，这个试验中使用数组索引来加速字符串匹配的过程。然而，它还是比通常的压缩程序慢。哈夫曼编码原码#define INT_MAX 10000#define E

37、NCODING_LENGTH 1000#include "stdio.h"#include "string.h"#include "malloc.h"typedef enumnone,left_child,right_child Which;/标记是左孩子还是右孩子typedef char Elemtype;typedef struct TNode    Elemtype letter;     int weight;   &

38、#160;int parent;    Which sigh;    char *code;HTNode,*HuffmanTree;int n;char coding50;/储存代码char strENCODING_LENGTH;/保存要翻译的句子void InitTreeNode(HuffmanTree &HT)/初始前N个结点,后M-N个结点置空    int i;int w;char c;    int m=2*n-1;&

39、#160;   HuffmanTree p;    HT=(HuffmanTree)malloc(m)*sizeof(HTNode);    printf("input %d database letter and weight",n);    p=HT;    getchar();    for (i=1;i<=n;i+) 

40、60;      scanf("%c%d",&c,&w);        p->code='0'        p->letter=c;        p->parent=0;    

41、60;   p->sigh=none;        p->weight=w;        p+;        getchar();        for (;i<=m;i+,p+)    

42、;    p->code='0'        p->letter=' '        p->parent=0;        p->sigh=none;        p->

43、weight=0;    /INITTREENODEvoid Select(HuffmanTree HT,int end,int *s1,int *s2)/在0END之间,找出最小和次小的两个结点序号,返回S1,S2int i;int min1=INT_MAX;int min2;for (i=0;i<=end;i+)/找最小的结点序号     if (HTi.parent=0&&HTi.weight<min1)      

44、60;   *s1=i;         min1=HTi.weight;     min2=INT_MAX;      for(i=0;i<=end;i+)/找次小结点的序号          if (HTi.parent=0&&(*s1!=i)

45、&&min2>HTi.weight)              *s2=i;              min2=HTi.weight;             

46、60;  void HuffmanTreeCreat(HuffmanTree &HT)/建立HUFFMAN树    int i;int m=2*n-1;    int s1,s2;    for(i=n;i<m;i+)        Select(HT,i-1,&s1,&s2);      

47、;  HTs1.parent=i;        HTs2.parent=i;        HTs1.sigh=left_child;        HTs2.sigh=right_child;        HTi.weight=HTs1.weight+H

48、Ts2.weight;    void HuffmanTreeCode(HuffmanTree HT)/HUFFMAN译码int i;char *temp;temp=(char *)malloc(n*sizeof(char);tempn-1='0'int p;int s;for (i=0;i<n;i+)     p=i;     s=n-1;    while (HTp.parent!=0)/从

49、结点回溯,左孩子为0,右孩子为1        if (HTp.sigh=left_child)              temp-s='0'        else if (HTp.sigh=right_child)     &#

50、160;      temp-s='1'        p=HTp.parent;        HTi.code=(char *)malloc(n-s)*sizeof(char);/分配结点码长度的内存空间    strcpy(HTi.code,temp+s);    printf

51、("%sn",HTi.code);    void GetCodingSen(char *sentence)/输入要编码的句子    int l;    gets(sentence);    l=strlen(sentence);    sentencel='0'void HuffmanTreeEncoding(char sen,HuffmanTree HT)/

52、将句子进行编码int i=0;int j;while(seni!='0')    for(j=0;j<n;j+)        if (HTj.letter=seni) /字母吻合则用代码取代        strcat(coding,HTj.code);        break; &

53、#160;              i+;    if (seni=32) i+;printf("n%s",coding);void HuffmanTreeDecoding(HuffmanTree HT,char code)/HUFFMAN译码过程,将代码翻译为句子    char sen100;    char t

54、emp50;    char voidstr=" "    int i;int j;    int t=0;int s=0;    for(i=0;i<strlen(code);i+)        tempt+=codei;        for(j=

55、0;j<n;j+)            if (strcmp(HTj.code,temp)=0)/代码段吻合                sens=HTj.letter;s+;           &

56、#160;    strcpy(temp,voidstr);/将TEMP置空                t=0;                break;      

57、0;                     printf("n%s",sen);void main()     HTNode hnode;    HuffmanTree huff;    huff=&hnode;  &#

58、160; printf("input the letter for coding numbern");    scanf("%d",&n);    InitTreeNode(huff);    HuffmanTreeCreat(huff);    HuffmanTreeCode(huff);    GetCodingSen(str);

59、60;   HuffmanTreeEncoding(str,huff);    HuffmanTreeDecoding(huff,coding);第9章 图象的压缩编码，JPEG压缩编码标准在介绍图象的压缩编码之前，先考虑一个问题：为什么要压缩？其实这个问题不用我回答，你也能想得到。因为图象信息的数据量实在是太惊人了。举一个例子就明白：一张A4(210mm×297mm) 幅面的照片，若用中等分辨率(300dpi)的扫描仪按真彩色扫描，其数据量为多少？让我们来计算一下：共有(300×210/25.4) &#

60、215;(300×297/25.4)个象素，每个象素占3个字节，其数据量为26M字节，其数据量之大可见一斑了。如今在Internet上，传统基于字符界面的应用逐渐被能够浏览图象信息的WWW(World Wide Web)方式所取代。WWW尽管漂亮，但是也带来了一个问题：图象信息的数据量太大了，本来就已经非常紧张的网络带宽变得更加不堪重负，使得World Wide Web变成了World Wide Wait。总之，大数据量的图象信息会给存储器的存储容量，通信干线信道的带宽，以及计算机的处理速度增加极大的压力。单纯靠增加存储器容量，提高信道带宽以及计算机的处理速度等方法来解决这个问题是不

61、现实的，这时就要考虑压缩。压缩的理论基础是信息论。从信息论的角度来看，压缩就是去掉信息中的冗余，即保留不确定的信息，去掉确定的信息(可推知的)，也就是用一种更接近信息本质的描述来代替原有冗余的描述。这个本质的东西就是信息量(即不确定因素)。压缩可分为两大类：第一类压缩过程是可逆的，也就是说，从压缩后的图象能够完全恢复出原来的图象，信息没有任何丢失，称为无损压缩；第二类压缩过程是不可逆的，无法完全恢复出原图象，信息有一定的丢失，称为有损压缩。选择哪一类压缩，要折衷考虑，尽管我们希望能够无损压缩，但是通常有损压缩的压缩比(即原图象占的字节数与压缩后图象占的字节数之比，压缩比越大，说明压缩效率越高)

62、比无损压缩的高。图象压缩一般通过改变图象的表示方式来达到，因此压缩和编码是分不开的。图象压缩的主要应用是图象信息的传输和存储，可广泛地应用于广播电视、电视会议、计算机通讯、传真、多媒体系统、医学图象、卫星图象等领域。压缩编码的方法有很多，主要分成以下四大类：(1)象素编码；(2)预测编码；(3)变换编码；(4)其它方法。所谓象素编码是指，编码时对每个象素单独处理，不考虑象素之间的相关性。在象素编码中常用的几种方法有：(1)脉冲编码调制(Pulse Code Modulation，简称PCM)；(2)熵编码(Entropy Coding)；(3)行程编码(Run Length Coding)；(

63、4)位平面编码(Bit Plane Coding)。其中我们要介绍的是熵编码中的哈夫曼(Huffman)编码和行程编码(以读取.PCX文件为例)。所谓预测编码是指，去除相邻象素之间的相关性和冗余性，只对新的信息进行编码。举个简单的例子，因为象素的灰度是连续的，所以在一片区域中，相邻象素之间灰度值的差别可能很小。如果我们只记录第一个象素的灰度，其它象素的灰度都用它与前一个象素灰度之差来表示，就能起到压缩的目的。如248，2，1，0，1，3，实际上这6个象素的灰度是248，250，251，251，252，255。表示250需要8个比特，而表示2只需要两个比特，这样就实现了压缩。常用的预测编码有调制

64、(Delta Modulation，简称DM)；微分预测编码(Differential Pulse Code Modulation，DPCM)，具体的细节在此就不详述了。所谓变换编码是指，将给定的图象变换到另一个数据域(如频域)上，使得大量的信息能用较少的数据来表示，从而达到压缩的目的。变换编码有很多，如(1)离散傅立叶变换(Discrete Fourier Transform，简称DFT)；(2)离散余弦变换(Discrete Cosine Transform，简称DCT)；(3)离散哈达玛变换(Discrete Hadamard Transform，简称DHT)。其它的编码方法也有很多，如

65、混合编码(Hybird Coding)、矢量量化(Vector Quantize，VQ) 、LZW算法。在这里，我们只介绍LZW算法的大体思想。值得注意的是，近些年来出现了很多新的压缩编码方法，如使用人工神经元网络(Artificial Neural Network，简称ANN)的压缩编码算法、分形(Fractl)、小波(Wavelet) 、基于对象(Object Based)的压缩编码算法、基于模型(Model Based)的压缩编码算法(应用在MPEG4及未来的视频压缩编码标准中)。这些都超出了本书的范围。本章的最后，我们将以JPEG压缩编码标准为例，看看上面的几种编码方法在实际的压缩编码

66、中是怎样应用的。9.1 哈夫曼编码哈夫曼(Huffman)编码是一种常用的压缩编码方法，是Huffman于1952年为压缩文本文件建立的。它的基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不相同。这些代码都是二进制码，且码的长度是可变的。举个例子：假设一个文件中出现了8种符号S0,S1,S2,S3,S4,S5,S6,S7，那么每种符号要编码，至少需要3比特。假设编码成000,001,010,011,100,101,110,111(称做码字)。那么符号序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1编码后变成0000011110000011

67、10010010011100101000000001，共用了42比特。我们发现S0，S1，S2这三个符号出现的频率比较大，其它符号出现的频率比较小，如果我们采用一种编码方案使得S0，S1，S2的码字短，其它符号的码字长，这样就能够减少占用的比特数。例如，我们采用这样的编码方案：S0到S7的码字分别01,11,101,0000,0001,0010,0011,100，那么上述符号序列变成011110001110011101101000000010010010111，共用了39比特，尽管有些码字如S3，S4，S5，S6变长了(由3位变成4位)，但使用频繁的几个码字如S0，S1变短了，所以实现了压缩。

68、上述的编码是如何得到的呢？随意乱写是不行的。编码必须保证不能出现一个码字和另一个的前几位相同的情况，比如说，如果S0的码字为01，S2的码字为011，那么当序列中出现011时，你不知道是S0的码字后面跟了个1，还是完整的一个S2的码字。我们给出的编码能够保证这一点。下面给出具体的Huffman编码算法。(1)              首先统计出每个符号出现的频率，上例S0到S7的出现频率分别为4/14，3/14，2/14，1/14，1/14，1/14，1/14，1

69、/14。(2)              从左到右把上述频率按从小到大的顺序排列。(3)              每一次选出最小的两个值，作为二叉树的两个叶子节点，将和作为它们的根节点，这两个叶子节点不再参与比较，新的根节点参与比较。(4)              重复(3)，直到最后得到和为1的根节点。(5)              将形成的二叉树的左