霍夫曼编码

以前写的，证明最优子结构，随便一本算法书上就有. #include<stdio.h>#include<stdlib.h>#define NIL -2#define Size_Max_bm 30#define left(i) (2*(i)+1)#define right(i) (2*(i)+2)#define swap(a,b) {cjys t;t=(a);(a)=(b);(b)=t;}#define parent(i) ((i)%2?((i)-1)/2:((i)-2)/2)typedef struct cjys{ char sj; int pl; struct cjys *left; struct cjys *right;}cjys;typedef struct cjdl{ int size; int leapsize; cjys *p;}cjdl; cjys *fpnn(void);void input(cjdl *p);cjys *fpnn(void);void zxdwh(cjys *p, int i, int leapsize);void rd(cjdl *p, cjys tp);cjys cd(cjdl *p);void hbs(cjdl *p);cjys *cjs(cjdl *p);void bls(cjys *p,int *jl, int i);void disp(char *tp, cjys *p);int main(){ cjdl p; char x[255]; cjys *re=NULL; int jl[Size_Max_bm]; input(&p); re=cjs(&p); printf("对照编码图为: "); bls(re,jl,0); freopen("CON","r",stdin); printf("输入Huffman码(VLC):"); scanf("%s",x); disp(x,re); system("pause");}void input(cjdl *p){ int i; cjys *tp; tp=fpnn(); printf("输入字母个数:"); scanf("%d", &p->size); p->p=malloc(sizeof(cjys)*p->size); p->leapsize=0; for(i = 0; i < p->size;i++) { printf("输入第%d字母:",i+1),scanf(" %c",&tp->sj); printf("输入出现次数(频率整数):"),scanf("%d",&tp->pl); rd(p,*tp); } free(tp);}cjys *fpnn(void){ cjys *p=NULL; p=malloc(sizeof(cjys)); p->left=NULL; p->right=NULL; return p;} void zxdwh(cjys *p, int i, int leapsize){ int l=left(i), r=right(i), mini=i; if(l<leapsize && p[l].pl<p[mini].pl) mini=l; if(r<leapsize && p[r].pl<p[mini].pl) mini=r; if(mini != i) { swap(p[i],p[mini]); zxdwh(p,mini,leapsize); }}void rd(cjdl *p, cjys tp){ if(p->leapsize == p->size) { printf("队列已满!"); exit(0); } p->p[p->leapsize]=tp; int j=p->leapsize,k=parent(j); while(k>=0 && p->p[j].pl < p->p[k].pl) { swap(p->p[j],p->p[k]); j=k; k=parent(j); } p->leapsize++;} cjys cd(cjdl *p){ if(p->leapsize == 0) { printf("队列已空!"); exit(0); } cjys tp=p->p[0]; p->leapsize--; p->p[0]=p->p[p->leapsize]; zxdwh(p->p,0,p->leapsize); return tp;}void hbs(cjdl *p){ cjys *p1=NULL, *p2=NULL; cjys tp; p1=fpnn(); p2=fpnn(); *p1=cd(p); *p2=cd(p); tp.left=p1; tp.right=p2; tp.pl=p1->pl+p2->pl; tp.sj=NIL; rd(p,tp); }cjys *cjs(cjdl *p){ int i, n=p->leapsize; cjys *tp=NULL; tp=fpnn(); for(i = 0; i < n-1; i++) hbs(p); *tp=p->p[0]; return tp;}void bls(cjys *p, int *jl, int i){ if(p == NULL) return; if(p->sj!=NIL) { int i2; printf("%c:",p->sj); for(i2 = 0; i2 < i; i2++) printf("%d",jl[i2]); printf(" "); } jl[i]=0; bls(p->left,jl,i+1); jl[i]=1; bls(p->right,jl,i+1); }void disp(char *tp, cjys *p){ cjys *ttp=NULL; int pd=0; while(1) { ttp=p; while(1) { if(ttp->sj != NIL) { printf("%c",ttp->sj); break; } if(*tp == "") { pd=1; break; } if(*tp++ == "0" ) ttp=ttp->left; else ttp=ttp->right; } if(pd) break; }}

代码：function CODE = huffman(p)%HUFFMAN Builds a variable-length Huffman code for a symbol source.% CODE = HUFFMAN(P) returns a Huffman code as binary strings in% cell array CODE for input symbol probability vector P. Each word% in CODE corresponds to a symbol whose probability is at the% corresponding index of P. %% Based on huffman5 by Sean Danaher, University of Northumbria,% Newcastle UK. Available at the MATLAB Central File Exchange:% Category General DSP in Signal Processing and Communications. % Copyright 2002-2004 R. C. Gonzalez, R. E. Woods, & S. L. Eddins% Digital Image Processing Using MATLAB, Prentice-Hall, 2004% $Revision: 1.5 $ $Date: 2003/10/26 18:37:16 $% Check the input arguments for reasonableness.error(nargchk(1, 1, nargin));if (ndims(p) ~= 2) | (min(size(p)) > 1) | ~isreal(p) | ~isnumeric(p) error("P must be a real numeric vector."); end% Global variable surviving all recursions of function "makecode"global CODECODE = cell(length(p), 1); % Init the global cell arrayif length(p) > 1 % When more than one symbol ... p = p / sum(p); % Normalize the input probabilities s = reduce(p); % Do Huffman source symbol reductions makecode(s, []); % Recursively generate the codeelse CODE = {"1"}; % Else, trivial one symbol case!end; %-------------------------------------------------------------------%function s = reduce(p);% Create a Huffman source reduction tree in a MATLAB cell structure% by performing source symbol reductions until there are only two% reduced symbols remainings = cell(length(p), 1);% Generate a starting tree with symbol nodes 1, 2, 3, ... to % reference the symbol probabilities.for i = 1:length(p) s{i} = i; endwhile numel(s) > 2 [p, i] = sort(p); % Sort the symbol probabilities p(2) = p(1) + p(2); % Merge the 2 lowest probabilities p(1) = []; % and prune the lowest one s = s(i); % Reorder tree for new probabilities s{2} = {s{1}, s{2}}; % and merge & prune its nodes s(1) = []; % to match the probabilitiesend%-------------------------------------------------------------------%function makecode(sc, codeword)% Scan the nodes of a Huffman source reduction tree recursively to% generate the indicated variable length code words.% Global variable surviving all recursive callsglobal CODE if isa(sc, "cell") % For cell array nodes, makecode(sc{1}, [codeword 0]); % add a 0 if the 1st element makecode(sc{2}, [codeword 1]); % or a 1 if the 2ndelse % For leaf (numeric) nodes, CODE{sc} = char("0" + codeword); % create a char code stringend将上述代码保存为huffman.m，调用实例：>> p = [0.1875 0.5 0.125 0.1875];>> c = huffman(p)c = "011" "1" "010" "00"c就是霍夫曼编码结果。

#include<stdio.h>#include<conio.h>#include<iostream.h>#include<string.h>#include<stdlib.h>#defineMAXVALUE10000/*权值最大值*/#defineMAXLEAF30/*叶子最多个数*/#defineMAXNODEMAXLEAF*2-1/*结点数的个数*/#defineMAXBIT50/*编码的最大位数*/typedefstructnode/*结点类型定义*/{charletter;intweight;intparent;intlchild;intrchild;}HNodeType;typedefstruct/*编码类型定义*/{charletter;intbit[MAXBIT];intstart;}HCodeType;typedefstruct/*输入符号的类型*/{chars;intnum;}lable;voidHuffmanTree(HNodeTypeHuffNode[],intn,lablea[]){inti,j,m1,m2,x1,x2,temp1;chartemp2;for(i=0;i<2*n-1;i++)/*结点初始化*/{HuffNode[i].letter=0;HuffNode[i].weight=0;HuffNode[i].parent=-1;HuffNode[i].lchild=-1;HuffNode[i].rchild=-1;}for(i=0;i<n-1;i++)for(j=i+1;j<n-1;j++)/*对输入字符按权值大小进行排序*/if(a[j].num>a[i].num){temp1=a[i].num;a[i].num=a[j].num;a[j].num=temp1;temp2=a[i].s;a[i].s=a[j].s;a[j].s=temp2;}for(i=0;i<n;i++){HuffNode[i].weight=a[i].num;HuffNode[i].letter=a[i].s;}for(i=0;i<n-1;i++)/*构造huffman树*/{m1=m2=MAXVALUE;x1=x2=0;for(j=0;j<n+i;j++)/*寻找权值最小与次小的结点*/{if(HuffNode[j].parent==-1&&HuffNode[j].weight<m1){m2=m1;x2=x1;m1=HuffNode[j].weight;x1=j;}elseif(HuffNode[j].parent==-1&&HuffNode[j].weight<m2){m2=HuffNode[j].weight;x2=j;}}HuffNode[x1].parent=n+i;HuffNode[x2].parent=n+i;/*权值最小与次小的结点进行组合*/HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;HuffNode[n+i].lchild=x1;HuffNode[n+i].rchild=x2;}}voidHuffmanCode(intn,lablea[]){HNodeTypeHuffNode[MAXNODE];HCodeTypeHuffCode[MAXLEAF],cd;inti,j,c,p;HuffmanTree(HuffNode,n,a);for(i=0;i<n;i++)/*按结点位置进行编码*/{cd.start=n-1;c=i;p=HuffNode[c].parent;while(p!=-1){if(HuffNode[p].lchild==c)cd.bit[cd.start]=0;elsecd.bit[cd.start]=1;cd.start--;c=p;p=HuffNode[c].parent;}for(j=cd.start+1;j<n;j++)/*储存编码*/HuffCode[i].bit[j]=cd.bit[j];HuffCode[i].start=cd.start;}for(i=0;i<n;i++){HuffCode[i].letter=HuffNode[i].letter;printf("%c",HuffCode[i].letter);for(j=HuffCode[i].start+1;j<n;j++)printf("%d",HuffCode[i].bit[j]);printf(" ");}}intmain(){labledata[30];chars[100],*p;inti,count=0;for(;;){cout<<"/求哈夫曼编码,直到输入为end结束!/"<<endl;printf("Inputsomeletters:");scanf("%s",s);if(!strcmp(s,"end"))exit(0);for(i=0;i<30;i++){data[i].s=0;data[i].num=0;}p=s;while(*p)/*计算字符个数与出现次数(即权值)*/{for(i=0;i<=count+1;i++){if(data[i].s==0){data[i].s=*p;data[i].num++;count++;break;}elseif(data[i].s==*p){data[i].num++;break;}}p++;}printf(" ");printf("differentletters:%d ",count);for(i=0;i<count;i++){printf("%c",data[i].s);printf("weight:%d ",data[i].num);}HuffmanCode(count,data);count=0;}getch();}这是我们的软件实习答案，希望对你有帮助!

哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。 以哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由David.A.Huffman发展起来的。 例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。 　　本文描述在网上能够找到的最简单，最快速的哈夫曼编码。本方法不使用任何扩展动态库，比如STL或者组件。只使用简单的C函数，比如：memset，memmove，qsort，malloc，realloc和memcpy。

求效率首先要求得信号的熵，也就是最小的编码长度，比如是2.3，然后再求霍夫曼码的平均编码长度（各个概率和码位相乘再求和）比如是2.7，那么效率就是0.85。霍夫曼编码的编码效率，我想可以用压缩率来表示吧。随机选取一段字符，计算其编码长度为 n。再对其用霍夫曼编码，得到长度为 m。于是 m/n 就是压缩率。霍夫曼编码是变长编码，思路：对概率大的编的码字短，概率小的编的码字长，这样一来所编的总码长就小，这样编码效率就高。扩展资料：在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。参考资料来源：百度百科-霍夫曼编码

属于数字压缩编码技术： 霍夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。下面引证一个定理，该定 理保证了按字符出现概率分配码长，可使平均码长最短。 定理：在变字长编码中，如果码字长度严格按照对应符号出现的概率大小逆序排列，则其平 均码字长度为最小。 现在通过一个实例来说明上述定理的实现过程。设将信源符号按出现的概率大小顺序排列为 ： U： ( a1 a2 a3 a4 a5 a6 a7 ) 0.20 0.19 0.18 0.17 0.15 0.10 0.01 给概率最小的两个符号a6与a7分别指定为“1”与“0”，然后将它们的概率相加再与原来的 a1~a5组合并重新排序成新的原为：U′： ( a1 a2 a3 a4 a5 a6′ ) 0.20 0.19 0.18 0.17 0.15 0.11 对a5与a′6分别指定“1”与“0”后，再作概率相加并重新按概率排序得U〃：（0.26 0.20 0.19 0.18 0.17）… 直到最后得 U〃〃：（0.61 0.39） 分别给以“0”，“1”为止，如图4－4所示。} 霍夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的霍夫曼编码。 例如a7从左至右，由U至U〃〃，其码字为0000； a6按践线将所遇到的“0”和“1”按最低位到最高位的顺序排好，其码字为0001… 用霍夫曼编码所得的平均比特率为：∑码长×出现概率 上例为： 0.2×2+0.19×2+0.18×3+0.17×3+0.15×3+0.1×4+0.01×4=2.72 bit 可以算出本例的信源熵为2.61bit，二者已经是很接近了。

霍夫曼编码计算过程：无损数据压缩的熵编码。在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节，即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。霍夫曼编码历史：1951年，霍夫曼在麻省理工学院（MIT）攻读博士学位，他和修读信息论课程的同学得选择是完成学期报告还是期末考试。导师罗伯特·法诺（Robert Fano）出的学期报告题目是：查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，霍夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。霍夫曼使用自底向上的方法构建二叉树，避免了次优算法香农-范诺编码（Shannon–Fano coding）的最大弊端──自顶向下构建树。1952年，于论文《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）中发表了这个编码方法。

如果一个码的任何一个码字都不是其他码字的前缀，称为前缀码, 也称即时码. 即时码的特点: 1. 唯一可译 2. 译码时没有延时. 二进制霍夫曼编码步骤: References : <信息论与编码> 陈运主编 第二版 http://baike.baidu.com/link?url=_1Ns4TTbQI-iCCK18Gog5DGdvbFG9tnh_a1hgaqJ2sgU3-zAm29XtjZIuwiJPnKdSurwx055cwYgv4ueFhiKFK

霍夫曼编码是变长编码，思路：对概率大的编的码字短，概率小的编的码字长，这样一来所编的总码长就小，这样编码效率就高。上面那样求是不对的，除非你这6个码字是等概率的，各占1/6。应该用对应的概率*其对应得码长，再求和。扩展资料：在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码。这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节，即8个比特。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。参考资料来源：百度百科-霍夫曼编码

霍夫曼编码（Huffman Coding）是一种编码方式，是一种用于无损数据压缩的熵编码（权编码）算法。

霍夫曼编码是一种被广泛应用而且非常有效的数据压缩技术，根据待压缩数据的特征，一个可压缩掉20%~90%。这里考虑的数据指的是字符串序列。要理解霍夫曼编码，先要理解霍夫曼树，即最优二叉树，是一类带权路径长度最短的树。路径是指从树中一个结点到另一个结点之间的通路，路径上的分支数目称为路径长度。树的路径长度是从树根到每一个叶子之间的路径长度之和。结点的带权路径长度为从该结点到树根之间的路径长度与该结点权的乘积，树的带权路径长度为树中所有叶子结点的带权路径长度之和.霍夫曼树是指所有叶子结点的二叉树中带权路径长度最小的二叉树.当给定了n个叶子结点的权值后，构造出的最优二叉树的结点数目m就确定了，即m=2n-1,所以可用一维结构树组来存储最优二叉树#define MAXLEAFNUM 50 /*最优二叉树中最大叶子树目*/struct node{ char ch; /*当前结点表示的字符，对于非叶子结点，此域不用*/ int weight; /*当前结点的权值*/ int parent; /*当前结点的父结点的下标，为0时表示无父结点*/ int lchild,rchild; /*当前结点的左，右孩子结点的下标，为0时表示无孩子结点*/}HuffmanTree[2 * MAXLEAFNUM];typedef char *HuffmanCode[MAXLEAFNUM + 1]；创建最优二叉树void createHTree(HuffmanTree HT, char *c, int *w, int n){ /*数组c[0..n-1]和w[0..n-1]存放了n个字符及其概率，构造霍夫树HT*/ int i, s1, s2; if (n <= 1) return;/*根据n个权值构造n棵只有根结点的二叉树*/ for (i=1; i<=n; i++) { HT[i].ch = c[i-1]; HT[i].weight = w[i-1]; HT[i].parent = HT[i].lchild = HT[i].rchild = 0; }for (; i<2*n; ++i) { HT[i].parent = 0; HT[i].lchild = 0; HT[i].rchild = 0; }/*构造霍夫曼树*/ for (i=n+1; i<2*n; i++) { /*从HT[1..i-1]中选择parent为0且weight最小的两棵树，其序号为s1和s2*/ select(HT,i-1,s1,s2); HT[s1].parent = i; HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; }}应用霍夫曼编码假设有一个包含100 000个字符的数据文件要压缩存储。各字符在该文件中的出现频度见表1。仅有6种不同字符出现过，字符a出现了45000次。 a b c d e f 频度（千字） 45 13 12 16 9 5固定代码字 000 001 010 011 100 101变长代码字 0 101 100 111 1101 1100表1 一个字符编码问题。大小为100 000个字符的一个数据文件仅包含字符a~f，每个字符出现的频度如表中所示。如果对每个字符赋予一个三位的编码，则该文件可被编码为300000位。如果利用表中的可变长度编码，该文件可被编码为224000位。可以用很多种方式来表示这样一个文件。采用固定长度编码，则需要三位二进制数字来表示六个字符：a=000，b=001，…，f=101。这种方法需要300 000来对整个原文件编码。 而可变长度编码是对频度高的字符赋以短编码，而对频度低的字符赋以较长一些的编码。表1显示了这种编码，其中一位串0表示a，四位串1100表示f。这种编码方式需要 （45*1+13*3+12*3+16*3+9*4+5*4）*1000 = 224 000 位来表示整个文件，即可压缩掉约25%。这其实就是最优字符编码（霍夫曼编码）前缀编码我们这里考虑的编码方案中，没有一个编码是另一个编码的前缀。这样的编码称为前缀编码（或许“无前缀编码“是个更好的名字，但是前缀编码是标准的书面语）。 对任何一种二进制字符编码来说编码总是简单的，这只要将文件中表示每个字符的编码并置起来即可。利用表1的可变长度编码，把包含三个字符的文件abc编成0 . 101 . 100 = 0 101 100,其中“.“表示并置。 在前缀编码中解码也是很方便的。因为没有一个码是其他码的前缀，故被编码文件的开始处的编码是确定的。我们只要识别出第一个编码，将它翻译成原文字符，再对余下的编码文件重复这个解码过程即可。在我们的例子中，可将串001 011 101唯一地分析为0.0.101.1101，因此可解码为aabe。 解码过程需要有一种关于前缀编码的方便表示，使得初始编码可以很容易地被识别出来。有一种表示方法就是叶子为给定字符的二叉树。在这种树中，我们将一个字符的编码解释为从根至该字符的路径，其中0表示“转向左子结点”，1表示“转向右子结点“。如下给出最优二叉树，如图1。图1以下给出查找最优二叉树叶子结点编码的算法typedef char *HuffmanCode[MAXLEAFNUM + 1]；(本文开头也有说明)void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int n){ /* n个叶子结点在霍夫曼树HT中的下标为1~n,*/ /*第i（1<= i <= n）个叶子的编码存放HC[i]中*/ char *cd; int i,start,c,f; if (n<=1) return;/*分配n个字节的内存，用来存放当前得到的编码*/ /*n个叶子结点最大的编码长度为n所以分配n个字节*/ cd = (char*)malloc(n) cd[n-1] = ‘/0";for (i=1; i<=n; i++) { start = n -1; for (c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent) /*从叶子结点开始查找编码*/ /*叶子结点的父结点的左子树为叶子结点，则编码为0*/ /*否则就为父结点的右子树，则编码为1*/ if (HT[f].lchild = = c) cd[--start] = ‘0"; else cd[--start] = ‘1"; /*分配内存，分配内存的字节数为当前得到的字符编码数*/ HC[i] = (char*)malloc(n-start); strcpy(HC[i], &cd[start]);}free(cd);}译码算法为：从根结点出发，按二进制位串中的0和1确定是进入左分支还是右分支，当到达叶子结点时译出该叶子对应的字符。数据文件（包含编码）未结束，则回到根结点继续进行上述过程。给出如下函数：void Decoding(HuffmanTree HT, int n, char *buff){ /*利用具有n个叶子结点的最优二叉树（存储在数组HT中）进行译码，叶子的下标*//*为1~n，buff指向数据文件的编码序列*/int p = 2*n -1; /*指向根结点*/while (*buff){ if ((*buff) = = ‘0") p = HT[p].lchild; /*进入左分支*/ else p = HT[p].rchild; /*进入右分支*//*到达一个叶子结点*/ if（HT[p].lchild = = 0 && HT[p].rchild = = 0） { printf(“%c”, HT[p].ch); p = 2*n – 1; /*回到根结点*/ }buff++;}}

霍夫曼(Huffman)在1952年提出 是一种从下到上的编码方法，即从叶子逐步往上生成编码树编码算法实际上是一个构造霍夫曼树的过程（根据资料出现频率的多寡来建造的树，霍夫曼树的树叶节点用以储存资料元素 ( Data Element ) ，若该元素出现的频率越高，则由该元素至树根所经过的节点数越少）(1) 对资料中出现过的每一元素各自产生一外部节点，并赋予外部节点该元素之出现频率。(2) 令 L 是所有外部节点所成之集合。(3) 产生一个新节点 N 。令 N 为 L1 和 L2 的父节点，L1 和 L2 是 L 中出现频率最低的两个节点。令 N 节点的出现频率等於 L1 和 L2 的出现频率总和。由 L 中删除 L1 和 L2 ，并将 N 加入 L 中。(4) 重复步骤 (3) 的动作，直到 | L | = 1 。(5) 标示树中各节点的左子树链结为 0 ，右子树链结为 1 。（不一定，只要一枝为0一枝为1）是码长可变的编码霍夫曼算法和香农范诺算法的编码都不需要额外的同步码（解释）霍夫曼树是最小二叉树，编码效率比香农范诺高霍夫曼编码对错误敏感，错一位，可能导致后面的解码都是错误的，而且计算机也无法纠错，我们称为错误传播霍夫曼编码是变长编码，整个编码结果是一个整体，无法随意解压缩其中的某一个部分

二．霍夫曼编码 霍夫曼（Huffman）编码属于码词长度可变的编码类，是霍夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率。生成霍夫曼编码算法基于一种称为“编码树”（coding tree）的技术。算法步骤如下： （1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。 （2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。 （3）重复第2步，直到形成一个符号为止（树），其概率最后等于1。 （4）从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。 以下这个简单例子说明了这一过程。1)．字母A,B,C,D,E已被编码，相应的出现概率如下： p(A)=0.16, p(B)=0.51, p(C)=0.09, p(D)=0.13, p(E)=0.11 2)．C和E概率最小，被排在第一棵二叉树中作为树叶。它们的根节点CE的组合概率为0.20。从CE到C的一边被标记为1，从CE到E的一边被标记为0。这种标记是强制性的。所以，不同的哈夫曼编码可能由相同的数据产生。 3)．各节点相应的概率如下： p(A)=0.16, p(B)=0.51, p(CE)=0.20, p(D)=0.13 D和A两个节点的概率最小。这两个节点作为叶子组合成一棵新的二叉树。根节点AD的组合概率为0.29。由AD到A的一边标记为1，由AD到D的一边标记为0。 如果不同的二叉树的根节点有相同的概率，那么具有从根到节点最短的最大路径的二叉树应先生成。这样能保持编码的长度基本稳定。 4)．剩下节点的概率如下： p(AD)=0.29, p(B)=0.51, p(CE)=0.20 AD和CE两节点的概率最小。它们生成一棵二叉树。其根节点ADCE的组合概率为0.49。由ADCE到AD一边标记为0，由ADCE到CE的一边标记为1。 5)．剩下两个节点相应的概率如下： p(ADCE)=0.49, p(B)=0.51 它们生成最后一棵根节点为ADCEB的二叉树。由ADCEB到B的一边记为1，由ADCEB到ADCE的一边记为0。 6)．图03-02-2为霍夫曼编码。编码结果被存放在一个表中： w(A)=001, w(B)=1, w(C)=011, w(D)=000, w(E)=010 图03-02-2 霍夫曼编码例霍夫曼编码器的编码过程可用例子演示和解释。 下面是另一个霍夫曼编码例子。假定要编码的文本是： "EXAMPLE OF HUFFMAN CODE" 首先，计算文本中符号出现的概率（表03-02-2）。 表03-02-2 符号在文本中出现的概率 符号 概率 E 2/25 X 1/25 A 2/25 M 2/25 P 1/25 L 1/25 O 2/25 F 2/25 H 1/25 U 1/25 C 1/25 D 1/25 I 1/25 N 2/25 G 1/25 空格 3/25 最后得到图03-02-3所示的编码树。 图03-02-3 霍夫曼编码树 在霍夫曼编码理论的基础上发展了一些改进的编码算法。其中一种称为自适应霍夫曼编码（Adaptive Huffman code）。这种方案能够根据符号概率的变化动态地改变码词，产生的代码比原始霍夫曼编码更有效。另一种称为扩展的霍夫曼编码（Extended Huffman code）允许编码符号组而不是单个符号。 同香农-范诺编码一样，霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。这是因为这两种方法都自含同步码，在编码之后的码串中都不需要另外添加标记符号，即在译码时分割符号的特殊代码。当然，霍夫曼编码方法的编码效率比香农-范诺编码效率高一些。 采用霍夫曼编码时有两个问题值得注意：①霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，那怕仅仅是1位出现错误，也会引起一连串的错误，这种现象称为错误传播(error propagation)。计算机对这种错误也无能为力，说不出错在哪里，更谈不上去纠正它。②霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。尽管如此，霍夫曼码还是得到广泛应用。 http://210.41.4.20/course/58/58/MMT/Mmt03_02_2.htm