《哈夫曼编码encode67页.doc》由会员分享，可在线阅读，更多相关《哈夫曼编码encode67页.doc（67页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、如有侵权，请联系网站删除，仅供学习与交流哈夫曼编码encode【精品文档】第 67 页哈夫曼编码(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 in a partic
4、ular 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是最小的。 从树中一个结点到另一个结点之间的构成这两个结点之间的路径，路径上的分支数目称做路径长度。树的路径长度是从树根到每一结点的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和，通常记作 。假设有n个
6、权值1,2, , n，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为i，则其中带权路径长度WPL最小的二叉树称做最优二叉树或赫夫曼树。赫夫曼树构造的算法（圆圈表示叶结点，方块表示非终端结点）。 (关于哈夫曼编码的其他代码) /* 赫夫曼树和赫夫曼编码的存储表示 */typedef struct unsigned int weight; unsigned int parent,lchild,rchild;HTNode,*HuffmanTree; /* 动态分配数组存储赫夫曼树 */typedef char *HuffmanCode; /* 动态分配数组存储赫夫曼编码表 */* 求赫夫曼编码
7、 */#includec1.h#includec6-7.h#includefunc6-1.cvoid 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; m=2*n-1; *HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);
8、/* 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,&s1,&s2); (*HT)s1.parent=(*HT)s2.parent=i; (*HT)i.lchild=s1; (*HT)i.r
9、child=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; /* 编码结束符 */ for(i=1;i1): ); scanf(%d,&n); w=(int*)malloc(n*sizeof(int); printf(请依次输入%d个权值(整
10、型):n,n); for(i=0;i=n-1;i+) scanf(%d,w+i); HuffmanCoding(&HT,&HC,w,n); for(i=1;i0)，构造赫夫曼树HT，并求出n个字符的赫夫曼编码HC */ int m,i,s1,s2; /* 此句与algo6-1.c不同 */ unsigned 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=*
11、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,&s1,&s2); (*HT)s1.parent=(*HT)s2.parent=i; (*HT)i.lchild=s1; (*HT)i.rchild=s2; (*HT)i.wei
12、ght=(*HT)s1.weight+(*HT)s2.weight; /* 以下为算法6.13，无栈非递归遍历赫夫曼树，求赫夫曼编码，以上同算法6.12 */ *HC=(HuffmanCode)malloc(n+1)*sizeof(char*); /* 分配n个字符编码的头指针向量(0不用) */ cd=(char*)malloc(n*sizeof(char); /* 分配求编码的工作空间 */ c=m; cdlen=0; for(i=1;i1): ); scanf(%d,&n); w=(int *)malloc(n*sizeof(int); printf(请依次输入%d个权值(整型):n,n
13、); for(i=0;i=n-1;i+) scanf(%d,w+i); HuffmanCoding(&HT,&HC,w,n); for(i=1;i0)个标签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的前端并规模递减
14、，这样堆可以一直维护着而无需重建。最后生成的内结点是根结点，它正好是放置在A0，这样我们返回的根结点指针也是分配出的内存块指针A，可以用于稍后的free()调用。 for ( i = 0, i = 0; -i ) Sift(A, i, N); 建立树的过程是：不断从堆中提取权值最小的两个结点，并创建连接这两个结点的内结点，然后将其纳入堆中。Ai是堆中的最后一个结点，j指向上次被选出的结点，新选出的结点将紧接在它们前面放置。 i = N-1, j = 2*N-1; while ( i 0 ) A-j = A0; Sift_new(A, 0, i, A+i); A-j = A0; A0.Left
15、= 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 = (i+1)*2; if ( j N ) break; if ( j = N | Aj-1.Weight Weight = Aj.Weight )
16、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 ) node_t T = Ai; Ai = Aj; Sift_new(A, j, N, &T);RLE RLE又叫Run Length Encoding，是一个针对无损压缩的非常简单的算法。它用重复字节和重复的次数来简单描述来代替重复的字节。尽管简单并且对于通常的压缩非常低效，但它有的时候却非常有用（例如，JPEG就使用它）。1.1
17、. 原理图2.1显示了一个如何使用RLE算法来对一个数据流编码的例子，其中出现六次的符号93已经用3个字节来代替：一个标记字节（0在本例中）重复的次数（6）和符号本身（93）。RLE解码器遇到符号0的时候，它表明后面的两个字节决定了需要输出哪个符号以及输出多少次。1.2. 实现RLE可以使用很多不同的方法。基本压缩库中详细实现的方式是非常有效的一个。一个特殊的标记字节用来指示重复节的开始，而不是对于重复非重复节都coding run。因此非重复节可以有任意长度而不被控制字节打断，除非指定的标记字节出现在非重复节（顶多以两个字节来编码）的稀有情况下。为了最优化效率，标记字节应该是输入流中最少出现
18、的符号（或许就不存在）。重复runs能够在32768字节的时候运转。少于129字节的要求3个字节编码（标记+次数+符号），而大雨128字节要求四个字节（标记+次数的高4位|0x80+次数的低4位）。这是通常所有采用的压缩的做法，并且也是相比较三个字节固定编码（允许使用3个字节来编码256个字节）而言非常少见的有损压缩率的方法。在这种模式下，最坏的压缩结果是：输出大小=257/256*输入大小+12. 哈夫曼哈夫曼编码是无损压缩当中最好的方法。它使用预先二进制描述来替换每个符号，长度由特殊符号出现的频率决定。常见的符号需要很少的位来表示，而不常见的符号需要很多为来表示。哈夫曼算法在改变任何符号二
19、进制编码引起少量密集表现方面是最佳的。然而，它并不处理符号的顺序和重复或序号的序列。2.1. 原理我不打算探究哈夫曼编码的所有实际的细节，但基本的原理是为每个符号找到新的二进制表示，从而通常符号使用很少的位，不常见的符号使用较多的位。简短的说，这个问题的解决方案是为了查找每个符号的通用程度，我们建立一个未压缩数据的柱状图；通过递归拆分这个柱状图为两部分来创建一个二叉树，每个递归的一半应该和另一半具有同样的权（权是NK =1符号数k, N是分之中符号的数量，符号数k是符号k出现的次数）这棵树有两个目的：1 编码器使用这棵树来找到每个符号最优的表示方法2 解码器使用这棵树唯一的标识在压缩流中每个编
20、码的开始和结束，其通过在读压缩数据位的时候自顶向底的遍历树，选择基于数据流中的每个独立位的分支，一旦一个到达叶子节点，解码器知道一个完整的编码已经读出来了。我们来看一个例子会让我们更清楚。图2.2显示了一个10个字节的未压缩的数据。根据符号频率，哈夫曼编码器生成哈夫曼树（图2.4）和相应的编码表示（图2.3）。 你可以看到，常见的符号接近根，因此只要少数位来表示。于是最终的压缩数据流如图2.5所示。压缩后的数据流是24位（三个字节），原来是80位（10个字节）。当然，我应该存储哈夫曼树，这样解码器就能够解码出对应的压缩流了，这就使得该例子中的真正数据流比输入的流数据量大。这是相对较短的数据上的
21、副作用。对于大数据量来说，上面的哈夫曼树就不占太多比例了。解码的时候，从上到下遍历树，为压缩的流选择从左/右分支，每次碰到一个叶子节点的时候，就可以将对应的字节写到解压输出流中，然后再从根开始遍历。2.2. 实现哈夫曼编码器可以在基本压缩库中找到，其是非常直接的实现。这个实现的基本缺陷是：1 慢位流实现2 相当慢的解码（比编码慢）3 最大的树深度是32（编码器在任何超过32位大小的时候退出）。如果我不是搞错的话，这是不可能的，除非输出的数据大于232字节。另一方面，这个实现有几个优点：1 哈夫曼树以一个紧密的形式每个符号要求12位（对于8位的符号）的方式存储，这意味着最大的头为384。2 编码
22、相当容易理解哈夫曼编码在数据有噪音的情况（不是有规律的，例如RLE）下非常好，这中情况下大多数基于字典方式的编码器都有问题。3. Rice对于由大word（例如：16或32位）组成的数据和教低的数据值，Rice编码能够获得较好的压缩比。音频和高动态变化的图像都是这种类型的数据，它们被某种预言预处理过（例如delta相邻的采样）。尽管哈夫曼编码处理这种数据是最优的，却由于几个原因而不适合处理这种数据（例如：32位大小要求16GB的柱状图缓冲区来进行哈夫曼树编码）。因此一个比较动态的方式更适合由大word组成的数据。3.1. 原理Rice编码背后的基本思想是尽可能的用较少的位来存储多个字（正像使用
23、哈夫曼编码一样）。实际上，有人可能想到Rice是静态的哈夫曼编码（例如，编码不是由实际数据内容的统计信息决定，而是由小的值比高的值常见的假定决定）。编码非常简单：将值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(
24、X-T)-1位）。这对于大值来说都是比较高效的代码并且阻止可笑的长Rice编码（最坏的情况，对于一个32位word单个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 8 01000 111111110 1
25、111111000 +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 1111111111111110 111111110011 -3 16 10000 11111111111111110
26、111111110100 -4 17 10001 111111111111111110 111111110101 -5 18 10010 1111111111111111110 111111110110 -6 19 10011 11111111111111111110 111111110111 -7 20 10100 111111111111111111110 11111111100000 -5 就像你看到的一样，在这个实现中使用threshold方法仅仅两个编码导致一个最坏的情况；剩下的编码产生比标准Rice编码还要短的编码。3 最坏的情况，输出。4. Lempel-Ziv (LZ77)Le
27、mpel-Ziv压缩模式有许多不同的变量。基本压缩库有清晰的LZ77算法的实现（Lempel-Ziv，1977），执行的很好，源代码也非常容易理解。LZ编码器能用来通用目标的压缩，特别对于文本执行的很好。它也在RLE和哈夫曼编码器（RLE，LZ，哈夫曼）中使用来大多数情况下获得更多的压缩。4.1. 原理在LZ压缩算法的背后是使用RLE算法用先前出现的相同字节序列的引用来替代。简单的讲，LZ算法被认为是字符串匹配的算法。例如：在一段文本中某字符串经常出现，并且可以通过前面文本中出现的字符串指针来表示。当然这个想法的前提是指针应该比字符串本身要短。例如，在上一段短语“字符串”经常出现，可以将除第一
28、个字符串之外的所有用第一个字符串引用来表示从而节省一些空间。一个字符串引用通过下面的方式来表示：1 唯一的标记2 偏移数量3 字符串长度由编码的模式决定引用是一个固定的或变动的长度。后面的情况经常是首选，因为它允许编码器用引用的大小来交换字符串的大小（例如，如果字符串相当长，增加引用的长度可能是值得的）。4.2. 实现使用LZ77的一个问题是由于算法需要字符串匹配，对于每个输入流的单个字节，每个流中此字节前面的哪个字节都必须被作为字符串的开始从而尽可能的进行字符串匹配，这意味着算法非常慢。另一个问题是为了最优化压缩而调整字符串引用的表示形式并不容易。例如，必须决定是否所有的引用和非压缩字节应该
29、在压缩流中的字节边界发生。基本压缩库使用一个清晰的实现来保证所有的符号和引用是字节对齐的，因此牺牲了压缩比率，并且字符串匹配程序并不是最优化的（没有缓存、历史缓冲区或提高速度的小技巧），这意味着程序非常慢。另一方面，解压缩程序非常简单。一个提高LZ77速度的试验已经进行了，这个试验中使用数组索引来加速字符串匹配的过程。然而，它还是比通常的压缩程序慢。哈夫曼编码原码#define INT_MAX 10000#define ENCODING_LENGTH 1000#include stdio.h#include string.h#include malloc.htypedef enumnone,l
30、eft_child,right_child Which;/标记是左孩子还是右孩子typedef char Elemtype;typedef struct TNodeElemtype letter; int weight;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*
31、n-1;HuffmanTree p;HT=(HuffmanTree)malloc(m)*sizeof(HTNode);printf(input %d database letter and weight,n);p=HT;getchar();for (i=1;icode=0;p-letter=c;p-parent=0;p-sigh=none;p-weight=w;p+;getchar();for (;icode=0;p-letter= ;p-parent=0;p-sigh=none;p-weight=0;/INITTREENODEvoid Select(HuffmanTree HT,int en
32、d,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.weightmin1) *s1=i;min1=HTi.weight;min2=INT_MAX;for(i=0;iHTi.weight)*s2=i;min2=HTi.weight;void HuffmanTreeCreat(HuffmanTree &HT)/建立HUFFMAN树int i;int m=2*n-1;int s1,s2;for(i
33、=n;im;i+)Select(HT,i-1,&s1,&s2);HTs1.parent=i;HTs2.parent=i;HTs1.sigh=left_child;HTs2.sigh=right_child;HTi.weight=HTs1.weight+HTs2.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;in;i+)p=i;s=n-1;while (HTp.parent
34、!=0)/从结点回溯,左孩子为0,右孩子为1if (HTp.sigh=left_child)temp-s=0;else if (HTp.sigh=right_child)temp-s=1;p=HTp.parent;HTi.code=(char *)malloc(n-s)*sizeof(char);/分配结点码长度的内存空间strcpy(HTi.code,temp+s);printf(%sn,HTi.code);void GetCodingSen(char *sentence)/输入要编码的句子int l;gets(sentence);l=strlen(sentence);sentencel=0
35、;void HuffmanTreeEncoding(char sen,HuffmanTree HT)/将句子进行编码int i=0;int j;while(seni!=0)for(j=0;jn;j+)if (HTj.letter=seni) /字母吻合则用代码取代strcat(coding,HTj.code);break;i+;if (seni=32) i+;printf(n%s,coding);void HuffmanTreeDecoding(HuffmanTree HT,char code)/HUFFMAN译码过程,将代码翻译为句子char sen100;char temp50;char voidstr= ;int i;int j;int t=0;int s=0;for(i=0;istrlen(code);i+)tempt+=codei;