霍夫曼编码(Huffman Coding)

哈夫曼编码是一种将字符编码为可变长度二进制数的压缩算法，由David A. Huffman在1952年提出。哈夫曼编码是一种可变长度编码，它能够将字符集中出现频率较高的字符用较短的编码表示，从而实现对数据的压缩。相对于固定长度编码（如 ASCII 编码），哈夫曼编码能够更好地适应数据的特点，从而实现更高效的压缩。哈夫曼编码的规则是通过构建哈夫曼树，将字符按照其出现频率或权重转换为二进制编码。它的主要步骤包括计算字符的频率或权重、构建哈夫曼树、赋值编码、最终得到的编码即为哈夫曼编码。其基本规则如下：1.对于给定的字符集，对每个字符计算其出现频率或权重。2.将字符集中的每个字符视为一个叶子节点，并将其频率或权重作为该节点的权重。3.构建一个哈夫曼树，通过将两个具有最小权重的节点合并来构建树。每次合并会创建一个新的节点，其权重为两个被合并节点的权重之和，并将这个新节点作为下一次合并的一个节点。4.重复第三步，直到所有节点都合并为树的根节点。5.对于每个字符，从根节点开始，若该字符对应的叶子节点在其路径上，则编码为 1，否则编码为 0。6.最终得到的编码即为哈夫曼编码。哈夫曼编码的优势在于对出现频率高的字符使用较短的编码，从而实现数据压缩。哈夫曼编码广泛应用于数据压缩、无损压缩、数据传输、编码解码等领域。它能够显著地减小数据传输的带宽需求和存储空间，提高数据传输和处理的效率，因此被广泛应用于多媒体数据压缩、通信传输、图像处理、声音处理等领域。

赫夫曼码的码字（各符号的代码）是异前置码字，即任一码字不会是另一码字的前面部分，这使各码字可以连在一起传送，中间不需另加隔离符号，只要传送时不出错，收端仍可分离各个码字，不致混淆。哈夫曼编码，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码。扩展资料赫夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的赫夫曼编码。例如a7从左至右，由U至U″″，其码字为1000；a6按路线将所遇到的“0”和“1”按最低位到最高位的顺序排好，其码字为1001…用赫夫曼编码所得的平均比特率为：Σ码长×出现概率上例为：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，二者已经是很接近了。参考资料来源：百度百科-哈夫曼编码

79位，解法如下：先统计一下每个字母的出现的次数：t：2、h：1、i：4、s：3、a：2、n：2、d：1、e：1、l：1、r：1、g：1。然后构造哈夫曼树：23/ 15 8/ / 7 8 i4 _4/ / s3 4 4 4/ / / 2 2 2 t2 a2 n2/ / / h1 d1 e1 l1 r1 g1所以对应的所有叶子结点的路径长度 * 出现次数 之和便是总编码长度。WPL = 3 * 3 + 5* （1+1+1+1+1+1） + 4*（2+2+2） + 2*（4 + 4） = 79。哈夫曼编码简介：哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。

二．霍夫曼编码 霍夫曼（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

霍夫曼(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）是码长可变的编码霍夫曼算法和香农范诺算法的编码都不需要额外的同步码（解释）霍夫曼树是最小二叉树，编码效率比香农范诺高霍夫曼编码对错误敏感，错一位，可能导致后面的解码都是错误的，而且计算机也无法纠错，我们称为错误传播霍夫曼编码是变长编码，整个编码结果是一个整体，无法随意解压缩其中的某一个部分

哈夫曼编码是我在得到app中吴军老师的《信息论40讲》中了解到的，虽然是一个关于信息论的编码方法， 但是对于我们的生活和工作也是很有帮助的，所以记了下来。 关于哈夫曼编码，是从摩尔斯电码说起的，这种电码是用点（嘀）和长线（嗒）对英文的26个字母进行编码的，按照对信息度量的方法，如果对26个字母采用等长度析编码，比如进行进制编码就需要log26（这里的log函数是以2为底的），也就是约5比特信息，而采用摩尔斯电码的方法，平均只需要3比特，这样效率就高了很多，发报时间也节省了大约1/3左右。 在战争时期，能够节省发电报的时间对情报人员的安全是很重要的，因为谍战片里情报人员没法完电报就被别人闯进来带走的情形在现实中是真的很常见的，尤其是在二战时期欧洲的德占区。另外就算是除去战争的因素，能够节省1/3的发报成本也是一个很大的改进。 但是，如果按照哈夫曼编码的方法来看摩尔斯电码，就会发现虽然摩尔斯电码不自觉的采用了哈夫曼编码的方法，但还不是最简洁的编码方法，依然有改进的空间。 事实证明，越长出现的信息采用较短的编码，不常出现的信息采用较长的编码相比于所有信息都采用相同长度编码的方法更合算的。我们可以按照这样一个推倒步骤来看一下： （对于我个人来讲，虽然数学学得不怎么样，但是这种推导过程我还是很喜欢的，因为通过自己动手来将一个结论推导出来时间很开心的事。) 哈夫曼编码从本质上讲就是讲最宝贵的资源（最短的编码）给出现概率最大的信息。而至于如何分配，其中的一个原则就是一条信息编码的长度和出现概率的对数成正比。 按我的理解就是出现的概率越大，投入的资源就越多。 那么哈夫曼编码的原则对于我们有什么用处呢？可以这样讲，只要是需要分配资源的工作，它都有指导意义。 课程中给我印象最深就是美国私立学校哈克学校的前校长尼科诺夫博士的一句话：在孩子小时候，要让他们尝试各种兴趣爱好，但是最终他们要在一个点上实现突破，就好比用圆规画圆，一方面有一个扎得很深的中心，另一方面有足够广的很浅的覆盖面。我觉得这是我能够听明白并且能够实践应用的最简单直接的方法。而且吴军老师就是用哈夫曼编码的方法来指导行动的，不排斥尝试新东西，但也对那些看样子不太能做成的事坚决停止投入，然后将更多的精力投入到成功率最高的事情上。 吴军老师有句话很好，“理论不在学得多，而在于学以致用”。而我们大多数人都是学得多，用得少，我也是一样。也许我可以从学着用哈夫曼编码开始，试着将学到的理论指导实践，踏踏实实的往前走。

设某信源产生有五种符号u1、u2、u3、u4和u5，对应概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。霍夫曼编码是变长编码，思路：对概率大的编的码字短，概率小的编的码字长，这样一来所编的总码长就小，这样编码效率就高。上面那样求是不对的，除非你这6个码字是等概率的，各占1/6。应该用对应的概率*其对应得码长，再求和。实际应用中除采用定时清洗以消除误差扩散和采用缓冲存储以解决速率匹配以外，主要问题是解决小符号集合的统计匹配，例如黑（1）、白（0）传真信源的统计匹配，采用0和1不同长度游程组成扩大的符号集合信源。游程，指相同码元的长度（如二进码中连续的一串0或一串1的长度或个数）。按照CCITT标准，需要统计2×1728种游程（长度），这样，实现时的存储量太大。事实上长游程的概率很小，故CCITT还规定：若l表示游程长度，则l=64q+r。

// 哈夫曼编码(算法)#include x0dx0a#include x0dx0a#include typedef char *HuffmanCode; //动态分配数组，存储哈夫曼编码typedef structx0dx0a{x0dx0a unsigned int weight; //用来存放各个结点的权值x0dx0a unsigned int parent,LChild,RChild; //指向双亲、孩子结点的指针x0dx0a} HTNode, *HuffmanTree; //动态分配数组，存储哈夫曼树//选择两个parent为0，且weight最小的结点s1和s2x0dx0avoid Select(HuffmanTree *ht,int n,int *s1,int *s2)x0dx0a{x0dx0a int i,min;x0dx0a for(i=1; i<=n; i++)x0dx0a {x0dx0a if((*ht)[i].parent==0)x0dx0a {x0dx0a min=i;x0dx0a break;x0dx0a }x0dx0a }x0dx0a for(i=1; i<=n; i++)x0dx0a {x0dx0a if((*ht)[i].parent==0)x0dx0a {x0dx0a if((*ht)[i].weight<(*ht)[min].weight)x0dx0a min=i;x0dx0a }x0dx0a }x0dx0a *s1=min;x0dx0a for(i=1; i<=n; i++)x0dx0a {x0dx0a if((*ht)[i].parent==0 && i!=(*s1))x0dx0a {x0dx0a min=i;x0dx0a break;x0dx0a }x0dx0a }x0dx0a for(i=1; i<=n; i++)x0dx0a {x0dx0a if((*ht)[i].parent==0 && i!=(*s1))x0dx0a {x0dx0a if((*ht)[i].weight<(*ht)[min].weight) x0dx0a min=i;x0dx0a }x0dx0a }x0dx0a *s2=min;x0dx0a}//构造哈夫曼树ht。w存放已知的n个权值x0dx0avoid CrtHuffmanTree(HuffmanTree *ht,int *w,int n)x0dx0a{x0dx0a int m,i,s1,s2;x0dx0a m=2*n-1;x0dx0a *ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode));x0dx0a for(i=1; i<=n; i++) //1--n号存放叶子结点，初始化x0dx0a {x0dx0a (*ht)[i].weight=w[i];x0dx0a (*ht)[i].LChild=0;x0dx0a (*ht)[i].parent=0;x0dx0a (*ht)[i].RChild=0;x0dx0a }x0dx0a for(i=n+1; i<=m; i++)x0dx0a {x0dx0a (*ht)[i].weight=0;x0dx0a (*ht)[i].LChild=0;x0dx0a (*ht)[i].parent=0;x0dx0a (*ht)[i].RChild=0;x0dx0a } //非叶子结点初始化x0dx0a printf(" HuffmanTree: ");x0dx0a for(i=n+1; i<=m; i++) //创建非叶子结点，建哈夫曼树x0dx0a { x0dx0a //在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0x0dx0a //且weight最小的结点，其序号分别赋值给s1、s2x0dx0a Select(ht,i-1,&s1,&s2);x0dx0a (*ht)[s1].parent=i;x0dx0a (*ht)[s2].parent=i;x0dx0a (*ht)[i].LChild=s1;x0dx0a (*ht)[i].RChild=s2;x0dx0a (*ht)[i].weight=(*ht)[s1].weight+(*ht)[s2].weight;x0dx0a printf("%d (%d, %d) ",(*ht)[i].weight,(*ht)[s1].weight,(*ht)[s2].weight);x0dx0a }x0dx0a printf(" ");x0dx0a} //哈夫曼树建立完毕//从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码x0dx0avoid CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n)x0dx0a{x0dx0a char *cd;x0dx0a int i,start,p;x0dx0a unsigned int c;x0dx0a hc=(HuffmanCode *)malloc((n+1)*sizeof(char *)); //分配n个编码的头指针x0dx0a cd=(char *)malloc(n*sizeof(char)); //分配求当前编码的工作空间x0dx0a cd[n-1]=""; //从右向左逐位存放编码，首先存放编码结束符x0dx0a for(i=1; i<=n; i++) //求n个叶子结点对应的哈夫曼编码x0dx0a {x0dx0a start=n-1; //初始化编码起始指针x0dx0a for(c=i,p=(*ht)[i].parent; p!=0; c=p,p=(*ht)[p].parent) //从叶子到根结点求编码x0dx0a if( (*ht)[p].LChild==c) x0dx0a cd[--start]="0"; //左分支标0x0dx0a else x0dx0a cd[--start]="1"; //右分支标1x0dx0a hc[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个编码分配空间x0dx0a strcpy(hc[i],&cd[start]);x0dx0a }x0dx0a free(cd);x0dx0a for(i=1; i<=n; i++)x0dx0a printf("HuffmanCode of %3d is %s ",(*ht)[i].weight,hc[i]);x0dx0a printf(" ");x0dx0a}void main()x0dx0a{x0dx0a HuffmanTree HT;x0dx0a HuffmanCode HC;x0dx0a int *w,i,n,wei,m;x0dx0a printf(" n = " );x0dx0a scanf("%d",&n);x0dx0a w=(int *)malloc((n+1)*sizeof(int)); x0dx0a printf(" input the %d element"s weight: ",n); x0dx0a for(i=1; i<=n; i++)x0dx0a { x0dx0a printf("%d: ",i); x0dx0a fflush(stdin);x0dx0a scanf("%d",&wei);x0dx0a w[i]=wei;x0dx0a }x0dx0a CrtHuffmanTree(&HT,w,n);x0dx0a CrtHuffmanCode(&HT,&HC,n);x0dx0a}

霍夫曼编码是一种被广泛应用而且非常有效的数据压缩技术，根据待压缩数据的特征，一个可压缩掉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++;}}

设某信源产生有五种符号u1、u2、u3、u4和u5，对应概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。首先，将符号按照概率由大到小排队，如图所示。编码时，从最小概率的两个符号开始，可选其中一个支路为0，另一支路为1。这里，我们选上支路为0，下支路为1。再将已编码的两支路的概率合并，并重新排队。多次重复使用上述方法直至合并概率归一时为止。从图（a）和（b）可以看出，两者虽平均码长相等，但同一符号可以有不同的码长，即编码方法并不唯一，其原因是两支路概率合并后重新排队时，可能出现几个支路概率相等，造成排队方法不唯一。一般，若将新合并后的支路排到等概率的最上支路，将有利于缩短码长方差，且编出的码更接近于等长码。这里图（a）的编码比（b）好。扩展资料发展历史哈夫曼编码(Huffman Coding)，又称霍夫曼编码。1951年，哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师Robert M. Fano给他们的学期报告的题目是，寻找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者香农共同研究过类似编码的导师。哈夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。1952年，David A. Huffman在麻省理工攻读博士时发表了《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文，它一般就叫做Huffman编码。参考资料来源：百度百科-哈夫曼编码

答案在这里 ^-^ Alpha Bravo Charlie Delta Echo Foxtrot Golf Hotel India Juliet Kilo Lima Mike November Oscar Papa Quebec Romeo Sierra Tango Uniform

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

频率是W=，你可以根据这个算出每个符号的使用概率。Huffman编码的基本思想就是：对于使用频率比较高的符号用较短的码字去编码，对于使用频率比较低的符号用较长的码字去编码，这样使得编码效率很高，即所编的码字的平均每个比特所携带的信息量较大。A的概率：10/27 （编码为：11）B的概率：2/27 （编码为：101）C的概率：5/27 （编码为：01）D的概率：6/27 （编码为：00）E的概率：4/27 （编码为：100）编码的具体规则是：每次找概率最小的两个符号合并，若同时出现多个最小的概率，那就随便合并（其实具体工程应用是不能随便合并的，因为这个涉及到最后编码完成后，码字长度的方差问题，工程上方差要尽可能小，初学者可不拘泥于此）具体看我给你做的PPT还有就是你问的：是不是只有一种可能。回答是无论如何都肯定不是只有一种可能的，构造好Huffman树后，在树枝上赋值0和1，这个是随便赋的，为了简便和一致，图中左侧树枝都赋值为1，右侧为0另外,团IDC网上有许多产品团购,便宜有口碑

Huffman 编码c1:01c2:10c3:11c4:000c5:001

霍夫曼（Huffman）编码属于码词长度可变的编码类，是霍夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率。赫夫曼码的码字（各符号的代码）是异前置码字，即任一码字不会是另一码字的前面部分，这使各码字可以连在一起传送，中间不需另加隔离符号，只要传送时不出错，收端仍可分离各个码字，不致混淆。赫夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好。哈夫曼编码是上个世纪五十年代由哈夫曼教授研制开发的,它借助了数据结构当中的树型结构,在哈夫曼算法的支持下构造出一棵最优二叉树,我们把这类树命名为哈夫曼树.因此,准确地说,哈夫曼编码是在哈夫曼树的基础之上构造出来的一种编码形式,它的本身有着非常广泛的应用。

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

Matlab自带Huffman函数(ps:你拼写错了）huffmandeco Huffman decoderhuffmandict Generate Huffman code dictionary for a source with known probability modelhuffmanenco Huffman encoder密码生成：symbols = [1 2 3]; % Data symbolsp = [0.1 0.1 0.8]; % Probability of each data symboldict = huffmandict(symbols,p) % Create the dictionary.dict{1,:} % Show one row of the dictionary.加密解密：sig = repmat([3 3 1 3 3 3 3 3 2 3],1,50); % Data to encodesymbols = [1 2 3]; % Distinct data symbols appearing in sigp = [0.1 0.1 0.8]; % Probability of each data symboldict = huffmandict(symbols,p); % Create the dictionary.hcode = huffmanenco(sig,dict); % Encode the data.dhsig = huffmandeco(hcode,dict); % Decode the code.

编码如下： x1：0 x2:10 x3:110 x4:1110 x5:11110 x6:11111 平均码长为0.3*1+0.25*2+0.2*3+0.1*4+0.1*5+0.05*5=2.55 过程为用频数小的相加,得新的二叉数和剩下的数中最小的比较,然后组成新树,依次类推,可得huffmantree,就可写出编码

哈夫曼编码，左子树默认为0，右子树默认为1，得到的编码如下：A：100 B：01 C：1011 D：11 E：1010 F：00编码的码长是：8*3 + 12 * 2 + 5*4 + 20 * 2 + 4*4 + 11 * 2 = 146频率是W=，可以根据这个算出每个符号的使用概率。Huffman编码的基本思想就是：对于使用频率比较高的符号用较短的码字去编码，对于使用频率比较低的符号用较长的码字去编码，这样使得编码效率很高，即所编的码字的平均每个比特所携带的信息量较大。A的概率：10/27 （编码为：11）B的概率：2/27 （编码为：101）C的概率：5/27 （编码为：01）D的概率：6/27 （编码为：00）E的概率：4/27 （编码为：100）编码的具体规则是：每次找概率最小的两个符号合并，若同时出现多个最小的概率，那就随便合并（其实具体工程应用是不能随便合并的，因为这个涉及到最后编码完成后，码字长度的方差问题，工程上方差要尽可能小，初学者可不拘泥于此）扩展资料：赫夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的赫夫曼编码。例如a7从左至右，由U至U″″，其码字为1000；a6按路线将所遇到的“0”和“1”按最低位到最高位的顺序排好，其码字为1001…用赫夫曼编码所得的平均比特率为：Σ码长×出现概率上例为：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，二者已经是很接近了。参考资料来源：百度百科-哈夫曼编码

Huffman编码特点: 1编码长度可变；2单译可译码；3最佳编码

这个是一个简单的，没有文件导入，需要编码的是自己输入的数组，你将它换成文件读取基本就可以实现对文章中的字符进行Huffman编码，这是我自己曾经做的一个程序，是VC6.0的,没有解码部分，解码部分你反过来推一下算法然后编一下代码就可以了。我还有一个是文件是用matlab作的huffman编码，你要的话给我邮箱，我给你发过去。#include<iostream.h>#include<string.h>#define N 100typedef struct{ int wei; //权值 int prt; //父节点 int lch; //左子节点 int rch; // 右子节点 int tmp; //中间变量，tmp=0 还未进行遍历 tmp=1 已近进行过向左遍历 tmp=2 已经进行过左右遍历 向上找到节点 char code[N];}huffmantree;void input();void print(huffmantree );void select(huffmantree *HT,int n,int &i,int &j){ int k; i=1; while(HT[i].prt!=0) { i++; } for(k=i+1;k<=n;k++) { if((HT[k].prt=0)&&(HT[k].wei <HT[i].wei)) i=k; } j=1; while((j==i)||(HT[j].prt!=0)) { j++; } for(k=j+1;k<=n;k++) { if((HT[k].prt=0)&&k!=i&&HT[k].wei<HT[j].wei) j=k; }}void huffman(int w[],huffmantree *HT,int n) //w存放n个字符的权值{ int m=2*n-1; int i,k,j; huffmantree *p=0; for(p=HT+1,i=1;i<=m;i++,p++) { HT[i].prt=0; HT[i].lch=0; HT[i].rch=0; } for(p=HT+1,i=1;i<=n;i++,p++) { HT[i].wei=w[i-1]; } for(p=HT+n+1,i=n+1;i<=m;i++,p++) { HT[i].wei=0;} for(k=n+1;k<=m;k++) { select(HT,k-1,i,j); // 找最小值和次小值的位置 HT[i].prt=k,HT[j].prt=k; // 找到i j 的父节点付给k HT[k].lch=i,HT[k].rch=j; // 父节点的左右指针分别指向i, j HT[k].wei=HT[i].wei+HT[j].wei; }}void huffmancoding(huffmantree *HT,int n) //n个叶子结点的huffman编码 从根节点开始编码{ int BT=2*n-1; int m=BT; int l,r,p; char s1[100]="0",s2[100]="1"; for(int i=0;i<=m;i++) //中间变量赋初值 { HT[i].tmp=0; } strcpy(HT[m].code," "); while(1) { l=HT[BT].lch; r=HT[BT].rch; p=HT[BT].prt; if(p==0&&HT[BT].tmp==2) break; if(l==0||r==0) { HT[BT].tmp=2; //如果是叶子结点则给中间变量赋值2向上返回一节结点 } if(HT[BT].tmp==0) //未进行过遍历，开始向左遍历 { HT[BT].tmp=1; //已经进行过向左遍历 l=HT[BT].lch; strcpy(HT[l].code,HT[BT].code); strcat(HT[l].code,s1); BT=l; } else if(HT[BT].tmp==1) { HT[BT].tmp=2; r=HT[BT].rch; strcpy(HT[r].code,HT[BT].code); strcat(HT[r].code,s2); BT=r; } else if(HT[BT].tmp==2) { p=HT[BT].prt; BT=p; } }}void print(huffmantree HT[],int n) //总共n个叶子节点{ int i; cout<<"源码："<<endl; for(i=1;i<=n;i++) cout<<HT[i].wei<<endl; cout<<"Huffman编码："<<endl; for(i=1;i<=n;i++) { cout<<HT[i].code<<endl; }}void input(int w[],int n){ int t,*p; int i=0; cout<<"对应的输入源码出现权值：(以-1结束)"<<endl; cin>>t; while(t>=0) { p=new int; *p=t; w[i]=*p; i++; cin>>t; }}void main(){ int n,m; cout<<"输入源码个数："; cin>>n; int *w; w=new int[n+1]; input(w,n); m=2*n-1; huffmantree *HT; HT=new huffmantree[m+1]; huffman(w,HT,n); huffmancoding(HT,n); print(HT,n); delete w,HT;}

#include <stdio.h>#include <string.h>#include <stdlib.h>#define TRUE 1#define ERROR 0#define OK 1#define FALSE 0#define INFEASIBLE -1#define OVERFLOW -2#define Status int #define MAXLENGTH 128typedef struct HTnode{ long weight; int parent; int lchild; int rchild;}HTNode, *HuffmanTree;typedef struct CTnode{ long weight; char *coded_string;}CharacterTable;typedef char * *HuffmanCode;FILE *fp=NULL;void Analyse (CharacterTable * *character_table, long * *w, char * *chara, int &n)//分析所有不同的字符的权值{ long *tmpw; char ch, *tmpchara; int i; (*character_table)=(CharacterTable *)malloc(128*sizeof(CharacterTable));//定义存放字母的数组 for(i=0; i<128; i++) { (*character_table)[i].weight=0; //初始化 (*character_table)[i].coded_string=NULL; } ch=fgetc(fp); while(!feof(fp))//诺到文件末尾，函数值为真 { //m=ch; if(ch<128 && ch>=0) (*character_table)[ch].weight++;//获得各个字母在文件中出现的次数 ch=fgetc(fp); } for(i=0, n=0; i<128; i++) if((*character_table)[i].weight) n++; //统计有多少不同的字符数 (*w)=(long *)malloc(n*sizeof(long));//deliver the character and the weight to main (*chara)=(char *)malloc(n*sizeof(char)); tmpw=(*w); tmpchara=(*chara); for(i=0; i<128; i++) if((*character_table)[i].weight) {//将权值放入*w数组中 *(*w)=(*character_table)[i].weight; *(*chara)=i;//这里i是字符 (*w)++; (*chara)++; } (*w)=tmpw; (*chara)=tmpchara;//指针返回数组头}void Select (HuffmanTree *HT, int i, int *Min1, int *Min2) { int j, n, tmp1=-1, tmp2=-2; for(n=0; n<i; n++) { if(!(*HT)[n].parent) { if(tmp1 == -1) { tmp1=n; continue; } if(tmp2 == -2) { tmp2=n; if((*HT)[tmp1].weight > (*HT)[tmp2].weight) { j=tmp1; tmp1=tmp2; tmp2=j; } continue; } if((*HT)[n].weight < (*HT)[tmp2].weight) //scan and change if((*HT)[n].weight < (*HT)[tmp1].weight) tmp1=n; else tmp2=n; } } *Min1=tmp1; *Min2=tmp2; //tmp[Min2].weight >= tmp[Min1].weight}Status Huffman(HuffmanTree *HT, HuffmanCode *HC,long *w, int n) { int m, i, Min1, Min2, p1, p2, start, *M1, *M2; char *cd; HuffmanTree *HTp; if(n<1) return ERROR; m=2*n-1; (*HT)=(HTNode *)malloc(m*sizeof(HTNode)); //intialise Hc in main HTp=HT; for(i=0; i<n; i++, w++) { (*HTp)[i].weight=*w; (*HTp)[i].parent=0; (*HTp)[i].lchild=0; (*HTp)[i].rchild=0; } for(; i<m; i++) { (*HTp)[i].weight=0; (*HTp)[i].parent=0; (*HTp)[i].lchild=0; (*HTp)[i].rchild=0; } M1=&Min1; M2=&Min2; for(i=n; i<m; i++) { Select(HT, i, M1, M2); (*HTp)[Min1].parent=i; (*HTp)[Min2].parent=i; (*HTp)[i].lchild=Min1; //左孩子要小一些 (*HTp)[i].rchild=Min2; (*HTp)[i].weight=(*HTp)[Min1].weight + (*HTp)[Min2].weight; } //coded the weight below (*HC)=(HuffmanCode)malloc(n*sizeof(char *)); cd=(char *)malloc(n*sizeof(char)); cd[n-1]=""; for(i=0; i<n; i++) { start=n-1; for(p1=i, p2=(*HTp)[p1].parent; p2!=0; p1=p2, p2=(*HTp)[p1].parent) { if( (*HTp)[p2].lchild ==p1) //编码, 左孩子为0, 右孩子为1 cd[--start]="0"; else cd[--start]="1"; } (*HC)[i]=(char *)malloc((n-start)*sizeof(char)); strcpy((*HC)[i],&cd[start]); } //over return OK;}void Weinumber_to_stringnumber(char * *stringnumber, long *w, int leaves) {//将权值以字符数组形式存放在上米的数组中 char tmp[30]; long i, j, k; int start; for(i=0; i<leaves; i++) { start=29; tmp[start--]=""; for(k=w[i], j=k%10; k!=0; k=k/10, j=k%10) tmp[start--]=j+"0"; stringnumber[i]=(char *)malloc((29-start)*sizeof(char)); strcpy(stringnumber[i], &tmp[start+1]); }}void Save_huffman_weight_dictionary(long *w, char *character, int leaves, HuffmanCode *HC){ char * *stringnumber; int i; FILE *fp1; fp1=fopen("weight.txt", "w"); stringnumber=(char * *)malloc(leaves * sizeof(char *)); Weinumber_to_stringnumber(stringnumber, w, leaves); for(i=0; i<leaves; i++) { fputc(" ", fp1); // for unhuffman add " fputc(character[i], fp1); fputc(" ", fp1); fputs(stringnumber[i], fp1); fputc(" ", fp1); fputc(""", fp1); fputs((*HC)[i], fp1); fputc(""", fp1); fputc(" ", fp1); } fclose(fp1);}void Huffman_file_convert(HuffmanCode *HC, CharacterTable *character_table) //fp had opened{ int i; char ch; FILE *fp2=fopen("coded.txt","w"); for( i=0; i<128; i++) if(character_table[i].weight) { character_table[i].coded_string=*(*HC); (*HC)++; } ch=fgetc(fp); while(!feof(fp)) { if( (ch>=0 && ch<128) && (character_table[ch].weight) )//it is very importan to add (ch>=0 && ch<128) fputs(character_table[ch].coded_string,fp2); ch=fgetc(fp); } fclose(fp2); }void fileopen1() //通过指针fp传递信息{ char filename[100]; do{ printf(" 请输入要编码的文件:"); scanf("%s", filename); if ((fp=fopen(filename,"r"))==NULL) printf(" 不能打开此文件! 请重新输入! "); }while(!fp);}void main(){ HuffmanTree Ht, *ht;//three level pointer HuffmanCode Hc, *hc; CharacterTable *CT, * *character_table; long *weight, * *w; char * character, * *chara; int leave; //the all leaves number ht=&Ht; hc=&Hc; w=&weight; chara=&character; character_table=&CT; fileopen1(); Analyse(character_table, w, chara, leave); fseek(fp, 0, 0);//将文件指针还原 Huffman(ht, hc, weight, leave);//构建哈弗曼树！ Save_huffman_weight_dictionary(weight, character, leave, hc); Huffman_file_convert(hc, CT); fclose(fp);}

哈夫曼编码是前缀编码。 A.正确B.错误正确答案：正确

function [h,l]=huffman(p) if (length(find(p<0))~=0) error("Not a prob,negative component"); end if (abs(sum(p)-1)>10e-10) error("Not a prob.vector,component do not add to 1") end n=length(p); q=p; m=zeros(n-1,n); for i=1:n-1 [q,l]=sort(q); m(i,:)=[l(1:n-i+1),zeros(1,i-1)]; q=[q(1)+q(2),q(3:n),1]; end for i=1:n-1 c(i,:)=blanks(n*n); end c(n-1,n)="0"; c(n-1,2*n)="1"; for i=2:n-1 c(n-i,1:n-1)=c(n-i+1,n*(find(m(n-i+1,:)==1))... -(n-2):n*(find(m(n-i+1,:)==1))); c(n-i,n)="0"; c(n-i,n+1:2*n-1)=c(n-i,1:n-1); c(n-i,2*n)="1"; for j=1:i-1 c(n-i,(j+1)*n+1:(j+2)*n)=c(n-i+1,... n*(find(m(n-i+1,:)==j+1)-1)+1:n*find(m(n-i+1,:)==j+1)); end end for i=1:n h(i,1:n)=c(1,n*(find(m(1,:)==i)-1)+1:find(m(1,:)==i)*n); ll(i)=length(find(abs(h(i,:))~=32)); end l=sum(p.*ll); hl 参考资料：赵永强

频率是W={10，2，5，6，4}，你可以根据这个算出每个符号的使用概率。Huffman编码的基本思想就是：对于使用频率比较高的符号用较短的码字去编码，对于使用频率比较低的符号用较长的码字去编码，这样使得编码效率很高，即所编的码字的平均每个比特所携带的信息量较大。 A的概率：10/27 （编码为：11） B的概率：2/27 （编码为：101） C的概率：5/27 （编码为：01） D的概率：6/27 （编码为：00） E的概率：4/27 （编码为：100）编码的具体规则是：每次找概率最小的两个符号合并，若同时出现多个最小的概率，那就随便合并（其实具体工程应用是不能随便合并的，因为这个涉及到最后编码完成后，码字长度的方差问题，工程上方差要尽可能小，初学者可不拘泥于此）具体看我给你做的PPT 还有就是你问的：是不是只有一种可能。回答是无论如何都肯定不是只有一种可能的，构造好Huffman树后，在树枝上赋值0和1，这个是随便赋的，为了简便和一致，图中左侧树枝都赋值为1，右侧为0 ~

你讲的是实现时的语言注释，还是他的实现过程

哈弗曼树就是每回将2个最小的并1个。过程大约如下：8,2,5,3,2,17,42+2=43,4,4,5,8,173+4=74,5,7,8,174+5=97,8,9,177+8=159,15,179+15=2417,2417+24=41这个树大概是这样的，分号是某个点的两个子节点写完了的意思，意会下：4124 1715 9;7 8; 4 5;3 4; 2 2;哈弗曼树的形态是不一定唯一的因此这个也是可以的4124 1715 9;7 8; 4 5;3 4;2 2；她们的带权路径长度分别是3*4+4*4+8*3+2*4+2*4+5*3+17*1=1003*4+2*5+2*5+8*3+4*3+5*3+17*1=100都是带全路径长度最短的生成树扩展资料：简介在计算机数据处理中，哈夫曼编码使用变长编码表对源符号（比如文件中的1个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。哈夫曼编码的起源：哈夫曼编码是 1952 年由 David A. Huffman 提出的一种无损数据压缩的编码算法。哈夫曼编码先统计出每种字母在字符串里出现的频率，根据频率建立一棵路径带权的二叉树，也就是哈夫曼树，树上每个结点存储字母出现的频率，根结点到结点的路径即是字母的编码，频率高的字母使用较短的编码，频率低的字母使用较长的编码，使得编码后的字符串占用空间最小。参考资料来源：百度百科-哈夫曼树

哈夫曼编码是在哈夫曼树的基础上进行的，其编码步骤为：（1）利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树，并在叶子结点上注明对应的字符。（2）在树中从根结点到叶子结点都有一条路径，对路径上的各分支约定指向左子树根的分支表示“0”码，指向右子树的分支表示“1”码。（2）取从根到每个叶子上的“0”或“1”的序列作为各个叶子结点（字符）的编码。

一.JPEG压缩过程 JPEG压缩分四个步骤实现： 1.颜色模式转换及采样； 2.DCT变换； 3.量化； 4.编码。 二. 1．颜色模式转换及采样 RGB色彩系统是我们最常用的表示颜色的方式。JPEG采用的是YCbCr色彩系统。想要用JPEG基本压缩法处理全彩色图像，得先把RGB颜色模式图像数据，转换为YCbCr颜色模式的数据。Y代表亮度，Cb和Cr则代表色度、饱和度。通过下列计算公式可完成数据转换。 Y=0.2990R+0.5870G+0.1140B Cb=-0.1687R-0.3313G+0.5000B+128 Cr=0.5000R-0.4187G-0.0813B＋128 人类的眼晴对低频的数据比对高频的数据具有更高的敏感度，事实上，人类的眼睛对亮度的改变也比对色彩的改变要敏感得多，也就是说Y成份的数据是比较重要的。既然Cb成份和Cr成份的数据比较相对不重要，就可以只取部分数据来处理。以增加压缩的比例。JPEG通常有两种采样方式：YUV411和YUV422，它们所代表的意义是Y、Cb和Cr三个成份的数据取样比例。 2.DCT变换 DCT变换的全称是离散余弦变换(Discrete Cosine Transform)，是指将一组光强数据转换成频率数据，以便得知强度变化的情形。若对高频的数据做些修饰，再转回原来形式的数据时，显然与原始数据有些差异，但是人类的眼睛却是不容易辨认出来。 压缩时，将原始图像数据分成8*8数据单元矩阵，例如亮度值的第一个矩阵内容如下： JPEG将整个亮度矩阵与色度Cb矩阵，饱和度Cr矩阵，视为一个基本单元称作MCU。每个MCU所包含的矩阵数量不得超过10个。例如，行和列采样的比例皆为4:2:2，则每个MCU将包含四个亮度矩阵，一个色度矩阵及一个饱和度矩阵。 当图像数据分成一个8*8矩阵后，还必须将每个数值减去128，然后一一代入DCT变换公式中，即可达到DCT变换的目的。图像数据值必须减去128，是因为DCT转换公式所接受的数字范围是在-128到+127之间。 DCT变换公式：x,y代表图像数据矩阵内某个数值的坐标位置f(x,y)代表图像数据矩阵内的数个数值u,v代表DCT变换后矩阵内某个数值的坐标位置F(u,v)代表DCT变换后矩阵内的某个数值 u=0 且 v=0 c(u)c(v)=1/1.414 u>0 或 v>0 c(u)c(v)=1 经过DCT变换后的矩阵数据自然数为频率系数，这些系数以F（0，0）的值最大，称为DC，其余的63个频率系数则多半是一些接近于0的正负浮点数，一概称之为AC。 3、量化 图像数据转换为频率系数后，还得接受一项量化程序，才能进入编码阶段。量化阶段需要两个8*8矩阵数据，一个是专门处理亮度的频率系数，另一个则是针对色度的频率系数，将频率系数除以量化矩阵的值，取得与商数最近的整数，即完成量化。 当频率系数经过量化后，将频率系数由浮点数转变为整数，这才便于执行最后的编码。不过，经过量化阶段后，所有数据只保留整数近似值，也就再度损失了一些数据内容，JPEG提供的量化表如下： 4、编码 Huffman编码无专利权问题，成为JPEG最常用的编码方式，Huffman编码通常是以完整的MCU来进行的。 编码时，每个矩阵数据的DC值与63个AC值，将分别使用不同的Huffman编码表，而亮度与色度也需要不同的Huffman编码表，所以一共需要四个编码表，才能顺利地完成JPEG编码工作。 DC编码 DC是彩采用差值脉冲编码调制的差值编码法，也就是在同一个图像分量中取得每个DC值与前一个DC值的差值来编码。DC采用差值脉冲编码的主要原因是由于在连续色调的图像中，其差值多半比原值小，对差值进行编码所需的位数，会比对原值进行编码所需的位数少许多。例如差值为5，它的二进制表示值为101，如果差值为-5，则先改为正整数5，再将其二进制转换成1的补数即可。所谓1的补数，就是将每个Bit若值为0，便改成1；Bit为1，则变成0。差值5应保留的位数为3，下表即列出差值所应保留的Bit数与差值内容的对照。 在差值前端另外加入一些差值的霍夫曼码值，例如亮度差值为5（101）的位数为3，则霍夫曼码值应该是100，两者连接在一起即为100101。下列两份表格分别是亮度和色度DC差值的编码表。根据这两份表格内容，即可为DC差值加上霍夫曼码值，完成DC的编码工作。 AC编码 AC编码方式与DC略有不同，在AC编码之前，首先得将63个AC值按Zig-zag排序，即按照下图箭头所指示的顺序串联起来。 63个AC值排列好的，将AC系数转换成中间符号，中间符号表示为RRRR/SSSS，RRRR是指第非零的AC之前，其值为0的AC个数，SSSS是指AC值所需的位数，AC系数的范围与SSSS的对应关系与DC差值Bits数与差值内容对照表相似。 如果连续为0的AC个数大于15，则用15/0来表示连续的16个0，15/0称为ZRL（Zero Rum Length），而（0/0）称为EOB（Enel of Block）用来表示其后所剩余的AC系数皆等于0，以中间符号值作为索引值，从相应的AC编码表中找出适当的霍夫曼码值，再与AC值相连即可。 例如某一组亮度的中间符为5/3，AC值为4，首先以5/3为索引值，从亮度AC的Huffman编码表中找到1111111110011110霍夫曼码值，于是加上原来100（4）即是用来取[5，4]的Huffman编码1111111110011110100，[5，4]表示AC值为4的前面有5个零。 由于亮度AC，色度AC霍夫曼编码表比较长，在此省略去，有兴趣者可参阅相关书籍。 实现上述四个步骤，即完成一幅图像的JPEG压缩。 参考资料[1] 林福宗 《图像文件格式（上）——Windows 编程》，清华大学出版社， 1996年[2] 李振辉、李仁各编著，《探索图像文件的奥秘》，清华大学出版社，1996年[3] 黎洪松、成实译《JPEG静止数据压缩标准》，学苑出版社，1996年希望有点帮助

霍夫曼编码计算过程：无损数据压缩的熵编码。在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而达到无损压缩数据的目的。例如，在英文中，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）中发表了这个编码方法。

属于数字压缩编码技术： 霍夫曼编码是可变字长编码(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，二者已经是很接近了。

7(0010) 19(10) 2(00000) 6(0001) 32(01) 3(00001) 21(11) 10(0011)哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。赫夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就称Huffman编码。下面引证一个定理，该定理保证了按字符出现概率分配码长，可使平均码长最短。

1、码字不同。哈夫曼所构造的码字不是唯一的，对于同一个信息源，无论上述的前后顺序如何排列，它的平均码长是不会改变的，所以他的优点是编码效率唯一性。而二进制编码所构造的码字是唯一。2、长度不同哈夫曼编码是依据字符出现概率来构造异字头的平均长度最短的码字，比较精准，二进制编码是用预先规定的方法将文字、数字或其他对象编成二进制的数码，或将信息、数据转换成规定的二进制电脉冲信号。二进制是最基础的编码。赫夫曼编码方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率 和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成1。每次相 加时都将“0”和“1”赋与相加的两个概率，读出时由该符号开始一直走到最后的“1”， 将路线上所遇到的“0”和“1”按最低位到最高位的顺序排好，就是该符号的赫夫曼编码。以上内容参考：百度百科-哈夫曼编码

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

哈夫曼编码(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。

哈夫曼编码(Huffman Coding)是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由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。 因此，大家都会发现，理解甚至修改这个编码都是很容易的。 背景 哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。 编码使用 我用简单的C函数写这个编码是为了让它在任何地方使用都会比较方便。你可以将他们放到类中，或者直接使用这个函数。并且我使用了简单的格式，仅仅输入输出缓冲区，而不象其它文章中那样，输入输出文件。 bool CompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen); bool DecompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen); 要点说明 速度 为了让它(huffman.cpp)快速运行，我花了很长时间。同时，我没有使用任何动态库，比如STL或者MFC。它压缩1M数据少于100ms（P3处理器，主频1G）。 压缩 压缩代码非常简单，首先用ASCII值初始化511个哈夫曼节点： CHuffmanNode nodes[511]; for(int nCount = 0; nCount < 256; nCount++) nodes[nCount].byAscii = nCount; 然后，计算在输入缓冲区数据中，每个ASCII码出现的频率： for(nCount = 0; nCount < nSrcLen; nCount++) nodes[pSrc[nCount]].nFrequency++; 然后，根据频率进行排序： qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare); 现在，构造哈夫曼树，获取每个ASCII码对应的位序列： int nNodeCount = GetHuffmanTree(nodes); 构造哈夫曼树非常简单，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父节点了。如此循环，直到队列中只剩一个节点（树根）。 // parent node pNode = &nodes[nParentNode++]; // pop first child pNode->pLeft = PopNode(pNodes, nBackNode--, false); // pop second child pNode->pRight = PopNode(pNodes, nBackNode--, true); // adjust parent of the two poped nodes pNode->pLeft->pParent = pNode->pRight->pParent = pNode; // adjust parent frequency pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency; 这里我用了一个好的诀窍来避免使用任何队列组件。我先前就直到ASCII码只有256个，但我分配了511个(CHuffmanNode nodes[511])，前255个记录ASCII码，而用后255个记录哈夫曼树中的父节点。并且在构造树的时候只使用一个指针数组(ChuffmanNode *pNodes[256])来指向这些节点。同样使用两个变量来操作队列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount –1)。 接着，压缩的最后一步是将每个ASCII编码写入输出缓冲区中： int nDesIndex = 0; // loop to write codes for(nCount = 0; nCount < nSrcLen; nCount++) { *(DWORD*)(pDesPtr+(nDesIndex>>3)) |= nodes[pSrc[nCount]].dwCode << (nDesIndex&7); nDesIndex += nodes[pSrc[nCount]].nCodeLength; } (nDesIndex>>3): >>3 以8位为界限右移后到达右边字节的前面 (nDesIndex&7): &7 得到最高位. 注意：在压缩缓冲区中，我们必须保存哈夫曼树的节点以及位序列，这样我们才能在解压缩时重新构造哈夫曼树（只需保存ASCII值和对应的位序列）。 解压缩 解压缩比构造哈夫曼树要简单的多，将输入缓冲区中的每个编码用对应的ASCII码逐个替换就可以了。只要记住，这里的输入缓冲区是一个包含每个ASCII值的编码的位流。因此，为了用ASCII值替换编码，我们必须用位流搜索哈夫曼树，直到发现一个叶节点，然后将它的ASCII值添加到输出缓冲区中： int nDesIndex = 0; DWORD nCode; while(nDesIndex < nDesLen) { nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7); pNode = pRoot; while(pNode->pLeft) { pNode = (nCode&1) ? pNode->pRight : pNode->pLeft; nCode >>= 1; nSrcIndex++; } pDes[nDesIndex++] = pNode->byAscii; }

比较如下：1、码字不同。哈夫曼所构造的码字不是唯一的，对于同一个信息源，无论上述的前后顺序如何排列，它的平均码长是不会改变的，所以他的优点是编码效率唯一性。而二进制编码所构造的码字是唯一。2、长度不同哈夫曼编码是依据字符出现概率来构造异字头的平均长度最短的码字，比较精准，二进制编码是用预先规定的方法将文字、数字或其他对象编成二进制的数码，或将信息、数据转换成规定的二进制电脉冲信号。二进制是最基础的编码。3、稳定性不同哈夫曼编码的稳定性比较差。如果改变其中一位数据就会产生改变。二进制编码具有抗干扰能力强，可靠性高等优点。参考资料来源：百度百科-哈夫曼编码参考资料来源：百度百科-二进制编码

哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称“熵编码法”），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由David.A.Huffman发展起来的。 例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。若能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。

比较如下：1、码字不同。哈夫曼所构造的码字不是唯一的，对于同一个信息源，无论上述的前后顺序如何排列，它的平均码长是不会改变的，所以他的优点是编码效率唯一性。而二进制编码所构造的码字是唯一。2、长度不同哈夫曼编码是依据字符出现概率来构造异字头的平均长度最短的码字，比较精准，二进制编码是用预先规定的方法将文字、数字或其他对象编成二进制的数码，或将信息、数据转换成规定的二进制电脉冲信号。二进制是最基础的编码。3、稳定性不同哈夫曼编码的稳定性比较差。如果改变其中一位数据就会产生改变。二进制编码具有抗干扰能力强，可靠性高等优点。参考资料来源：百度百科-哈夫曼编码参考资料来源：百度百科-二进制编码

#include <stdio.h>#include <stdlib.h>#include <string.h>///////////////////////////////////////////////////////////////////////////////*定义赫夫曼树结点的结构体变量，存放结点的权值、字符、双亲、坐孩子和右孩子*/typedef struct{ int weight; char ch; //增加一个域用于存放该节点的字符 int parent,lchild,rchild;}HTNode,*HuffmanTree;typedef char **HuffmanCode; //指向赫夫曼编码的指针///////////////////////////////////////////////////////////////////////////////*本程序用到的函数原型*/void welcome(); //打印操作选择界面void HuffmanCoding(HuffmanTree &,char *,int *,int);//建立赫夫曼树的算法void select(HuffmanTree HT,int j,int *s1,int *s2); //从目前已建好的赫夫曼树中选择parent为0且weight最小的两个结点void Init(); //输入n个字符及其对应的权值，根据权值建立哈夫曼树void Coding(); //编码void Decoding(); //译码void Print_code(); //打印译码好的代码文件void Print_tree(); //以凹凸表形式打印哈夫曼树int Read_tree(HuffmanTree &); //从文件中读入赫夫曼树void find(HuffmanTree &HT,char *code,char *text,int i,int m);//译码时根据01字符串寻找相应叶子节点的递归算法void Convert_tree(unsigned char T[100][100],int s,int *i,int j);//将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树HuffmanTree HT; //全局变量，指向存放赫夫曼树的存储空间int n=0; //全局变量，存放赫夫曼树叶子结点的数目int main(){char select;while(1){ welcome(); scanf("%c",&select); switch(select) { case "i": case "I":Init();break; case "c": case "C":Coding();break; case "d": case "D":Decoding();break; case "p": case "P":Print_code();break; case "t": case "T":Print_tree();break; case "e": case "E":exit(1); default :printf("Input error! "); } getchar();}return 0;}void welcome() //打印操作选择界面{printf("*-----------------------------------------------------* ");printf("| What do you want to do? | ");printf("|-----------------------------------------------------| "); printf("| | ");printf("| I--------------------------Init the Huffman tree. | ");printf("| C--------------------------Code your file. | ");printf("| D--------------------------Decode the code. | ");printf("| P--------------------------Print the codefile. | ");printf("| T--------------------------Print the Huffman tree. | "); printf("| | "); printf("*-----------------------------------------------------* ");}///////////////////////////////////////////////////////////////////////////////////////*初始化函数，输入n个字符及其对应的权值，根据权值建立哈夫曼树，并将其存于文件hfmtree中*/void Init() {FILE *fp;int i,n,w[52]; //w数组存放n个字符的权值char character[52]; //存放n个字符printf(" 输入字符个数 n:");scanf("%d",&n); //输入字符集大小printf("输入%d个字符及其对应的权值: ",n);for (i=0;i<n;i++){ char b=getchar(); scanf("%c",&character[i]); scanf("%d",&w[i]); //输入n个字符和对应的权值} HuffmanCoding(HT,character,w,n); //建立赫夫曼树if((fp=fopen("hfmtree.txt","w"))==NULL) printf("Open file hfmtree.txt error! ");for (i=1;i<=2*n-1;i++){ if(fwrite(&HT[i],sizeof(HTNode),1,fp)!=1) //将建立的赫夫曼树存入文件hfmtree.txt中 printf("File write error! ");}printf(" 建立赫夫曼树成功，已将其存于文件hfmtree.txt中 ");fclose(fp);}/////////////////////////////////////////////////////////////////////////////////////////建立赫夫曼树的算法///////////////////////////////////////////////////////////void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n){int m,i,s1,s2;HuffmanTree p;if(n<=1) return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(p=HT+1,i=1;i<=n;++i,++p,++character,++w){p->ch=*character;p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;}for(;i<=m;++i,++p) {p->ch=0;p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;}for(i=n+1;i<=m;++i){ 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;}}////////////////////////////////////////////////////////////////////////////////*从HT[1]到HT[j]中选择parent为0且weight最小的两个结点，用s1和s2返回其序号*/void select(HuffmanTree HT,int j,int *s1,int *s2){int i;//找weight最小的结点for (i=1;i<=j;i++) if (HT[i].parent==0) {*s1=i;break;}for (;i<=j;i++) if ((HT[i].parent==0)&&(HT[i].weight<HT[*s1].weight)) *s1=i; HT[*s1].parent=1;//找weight次小的结点for (i=1;i<=j;i++) if (HT[i].parent==0) {*s2=i;break;}for (;i<=j;i++) if ((HT[i].parent==0)&&(i!=*s1)&&(HT[i].weight<HT[*s2].weight)) *s2=i;}////////////////////////////////////////////////////////////////////////////////*对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中*/void Coding() {FILE *fp,*fw;int i,f,c,start;char *cd;HuffmanCode HC;if(n==0) n=Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数 /////以下程序段求赫夫曼树中各叶子节点的字符对应的的编码，并存于HC指向的空间中{HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char *)malloc(n*sizeof(char));cd[n-1]="";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)); strcpy(HC[i],&cd[start]);}free(cd);}/////////////////////////////////////////////////////////////////////////////////////if((fp=fopen("tobetrans.txt","rb"))==NULL) printf("Open file tobetrans.txt error! ");if((fw=fopen("codefile.txt","wb+"))==NULL) printf("Open file codefile.txt error! ");char temp;fscanf(fp,"%c",&temp); //从文件读入第一个字符while(!feof(fp)){ for(i=1;i<=n;i++) if(HT[i].ch==temp) break; //在赫夫曼树中查找字符所在的位置 for(int r=0;HC[i][r]!="";r++) //将字符对应的编码存入文件 fputc(HC[i][r],fw); fscanf(fp,"%c",&temp); //从文件读入下一个字符}fclose(fw);fclose(fp);printf(" 对文件hfmtree.txt编码成功,结果已存入codefile.txt中。 ");}//////////////////////////////////////////////////////////////////////////*将文件codefile中的代码进行译码，结果存入文件textfile中*/void Decoding() {FILE *fp,*fw;int m,i;char *code,*text,*p; if(n==0) n=Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数if((fp=fopen("codefile.txt","rb"))==NULL) printf("Open file codefile.txt error! "); if((fw=fopen("textfile.txt","wb+"))==NULL) printf("Open file textfile.txt error! ");code=(char *)malloc(sizeof(char));fscanf(fp,"%c",code); //从文件读入一个字符for(i=1;!feof(fp);i++){ code=(char *)realloc(code,(i+1)*sizeof(char)); //增加空间 fscanf(fp,"%c",&code[i]); //从文件读入下一个字符 }code[i-1]="";/////////到此codefile.txt文件中的字符已全部读入，存放在code数组中 text=(char *)malloc(100*sizeof(char));p=text; m=2*n-1;if(*code=="0") find(HT,code,text,HT[m].lchild,m); //从根节点的左子树去找else find(HT,code,text,HT[m].rchild,m); //从根节点的右子树去找 for(i=0;p[i]!="";i++) //把译码好的字符存入文件textfile.txt中 fputc(p[i],fw);fclose(fp);fclose(fw);printf(" 对codefile.txt文件译码成功，结果已存入textfile.txt文件。 ");}///////////////////////////////////////////////////////////////////////////////////////////////////////*将文件codefi1e以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。*/void Print_code(){FILE *fp,*fw;char temp;int i; if((fp=fopen("codefile.txt","rb"))==NULL) printf("Open file codefile.txt error! ");if((fw=fopen("codeprint.txt","wb+"))==NULL) printf("Open file codeprint.txt error! ");printf(" 文件codefi1e以紧凑格式显示如下: ");fscanf(fp,"%c",&temp); //从文件读入一个字符for (i=1;!feof(fp);i++){ printf("%c",temp); if(i%50==0) printf(" "); fputc(temp,fw); //将该字符存入文件codeprint.txt中 fscanf(fp,"%c",&temp); //从文件读入一个字符}printf(" 此字符形式的编码已写入文件codeprint.txt中. ");fclose(fp);fclose(fw);}///////////////////////////////////////////////////////////////////////////////////////////////////*将已在内存中的哈夫曼树以凹凸表形式显示在屏幕上，同时将此字符形式的哈夫曼树写入文件treeprint中。*/void Print_tree(){unsigned char T[100][100];int i,j,m=0;FILE *fp;if(n==0) n=Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数Convert_tree(T,0,&m,2*n-1); //将内存中的赫夫曼树转换成凹凸表形式的树，存于数组T中if((fp=fopen("treeprint.txt","wb+"))==NULL) printf("Open file treeprint.txt error! "); printf(" 以凹凸表形式打印已建好的赫夫曼树： ");for(i=1;i<=2*n-1;i++){ for (j=0;T[i][j]!=0;j++) { if(T[i][j]==" ") {printf(" ");fputc(T[i][j],fp);} else {printf("%d",T[i][j]);fprintf(fp,"%d ",T[i][j]);} } printf(" ");}fclose(fp);printf(" 此字符形式的哈夫曼树已写入文件treeprint.txt中. ");}///////////////////////////////////////////////////////////////////////////////////*从文件hfmtree.txt中读入赫夫曼树，返回叶子节点数*/int Read_tree(HuffmanTree &HT) {FILE *fp;int i,n;HT=(HuffmanTree)malloc(sizeof(HTNode)); if((fp=fopen("hfmtree.txt","r"))==NULL) printf("Open file hfmtree.txt error! ");for (i=1;!feof(fp);i++){ HT=(HuffmanTree)realloc(HT,(i+1)*sizeof(HTNode)); //增加空间 fread(&HT[i],sizeof(HTNode),1,fp); //读入一个节点信息}fclose(fp);n=(i-1)/2;return n;}/////////////////////////////////////////////////////////////////*译码时根据01字符串寻找相应叶子节点的递归算法*/void find(HuffmanTree &HT,char *code,char *text,int i,int m){if(*code!="") //若译码未结束{ code++; if(HT[i].lchild==0&&HT[i].rchild==0) //若找到叶子节点 { *text=HT[i].ch; //将叶子节点的字符存入text中 text++; if((*code=="0")) find(HT,code,text,HT[m].lchild,m); //继续从根节点的左子树找 else find(HT,code,text,HT[m].rchild,m); //继续从根节点的右子树找 } else //如果不是叶子节点 if(*code=="0") find(HT,code,text,HT[i].lchild,m); //从该节点的左子树去找 else find(HT,code,text,HT[i].rchild,m); //从该节点的右子树去找}else *text=""; //译码结束}/////////////////////////////////////////////////////////////////////////*将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树*/void Convert_tree(unsigned char T[100][100],int s,int *i,int j){int k,l;l=++(*i);for(k=0;k<s;k++) T[l][k]=" ";T[l][k]=HT[j].weight;if(HT[j].lchild) Convert_tree(T,s+1,i,HT[j].lchild);if(HT[j].rchild) Convert_tree(T,s+1,i,HT[j].rchild); T[l][++k]="";}为了您的安全，请只打开来源可靠的网址打开网站 取消来自: http://hi.baidu.com/laizhij/blog/item/4f3edefb6008321e6c22eb34.html

应该是美国的David Huffman戴维 哈夫曼对于学过数据结构的人来说，Huffman这个名字应该不会陌生吧。David Huffman教授1999年10月7日逝世。在他的一生中，他对于有限状态自动机，开关电路，异步过程和信号设计有杰出的贡献。但是我们只是通过数据结构中的Huffman编码才了解这位杰出的科学家的。他发明的Huffman编码能够使我们通常的数据传输数量减少到最小。这个编码的发明和这个算法一样十分引人入胜。1950年，Huffman在MIT(麻省理工)的信息理论与编码研究生班学习。Robert Fano教授让学生们自己决定是参加期未考试还是做一个大作业。而Huffman选择了后者，原因很简单，因为解决一个大作业可能比期未考试更容易通过。这个大作业促使了Huffman以后算法的诞生。离开MIT后，Huffman来到University of California的计算机系任教，并为此系的学术做出了许多杰出的工作。而他的算法也广泛应用于传真机，图象压缩和计算机安全领域。但是Huffman却从未为此算法申请过专利或其它相关能够为他带来经济利益的东西，他将他全部的精力放在教学上，以他自己的话来说，“我所要带来的就是我的学生。”

#include <stdio.h>#include <stdlib.h>#include <string.h>///////////////////////////////////////////////////////////////////////////////*定义赫夫曼树结点的结构体变量，存放结点的权值、字符、双亲、坐孩子和右孩子*/typedef struct{ int weight; char ch; //增加一个域用于存放该节点的字符 int parent,lchild,rchild;}HTNode,*HuffmanTree;typedef char **HuffmanCode; //指向赫夫曼编码的指针///////////////////////////////////////////////////////////////////////////////*本程序用到的函数原型*/void welcome(); //打印操作选择界面void HuffmanCoding(HuffmanTree &,char *,int *,int);//建立赫夫曼树的算法void select(HuffmanTree HT,int j,int *s1,int *s2); //从目前已建好的赫夫曼树中选择parent为0且weight最小的两个结点void Init(); //输入n个字符及其对应的权值，根据权值建立哈夫曼树void Coding(); //编码void Decoding(); //译码void Print_code(); //打印译码好的代码文件void Print_tree(); //以凹凸表形式打印哈夫曼树int Read_tree(HuffmanTree &); //从文件中读入赫夫曼树void find(HuffmanTree &HT,char *code,char *text,int i,int m);//译码时根据01字符串寻找相应叶子节点的递归算法void Convert_tree(unsigned char T[100][100],int s,int *i,int j);//将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树HuffmanTree HT; //全局变量，指向存放赫夫曼树的存储空间int n=0; //全局变量，存放赫夫曼树叶子结点的数目int main(){char select;while(1){ welcome(); scanf("%c",&select); switch(select) { case "i": case "I":Init();break; case "c": case "C":Coding();break; case "d": case "D":Decoding();break; case "p": case "P":Print_code();break; case "t": case "T":Print_tree();break; case "e": case "E":exit(1); default :printf("Input error! "); } getchar();}return 0;}void welcome() //打印操作选择界面{printf("*-----------------------------------------------------* ");printf("| What do you want to do? | ");printf("|-----------------------------------------------------| "); printf("| | ");printf("| I--------------------------Init the Huffman tree. | ");printf("| C--------------------------Code your file. | ");printf("| D--------------------------Decode the code. | ");printf("| P--------------------------Print the codefile. | ");printf("| T--------------------------Print the Huffman tree. | "); printf("| | "); printf("*-----------------------------------------------------* ");}///////////////////////////////////////////////////////////////////////////////////////*初始化函数，输入n个字符及其对应的权值，根据权值建立哈夫曼树，并将其存于文件hfmtree中*/void Init() {FILE *fp;int i,n,w[52]; //w数组存放n个字符的权值char character[52]; //存放n个字符printf(" 输入字符个数 n:");scanf("%d",&n); //输入字符集大小printf("输入%d个字符及其对应的权值: ",n);for (i=0;i<n;i++){ char b=getchar(); scanf("%c",&character[i]); scanf("%d",&w[i]); //输入n个字符和对应的权值} HuffmanCoding(HT,character,w,n); //建立赫夫曼树if((fp=fopen("hfmtree.txt","w"))==NULL) printf("Open file hfmtree.txt error! ");for (i=1;i<=2*n-1;i++){ if(fwrite(&HT[i],sizeof(HTNode),1,fp)!=1) //将建立的赫夫曼树存入文件hfmtree.txt中 printf("File write error! ");}printf(" 建立赫夫曼树成功，已将其存于文件hfmtree.txt中 ");fclose(fp);}/////////////////////////////////////////////////////////////////////////////////////////建立赫夫曼树的算法///////////////////////////////////////////////////////////void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n){int m,i,s1,s2;HuffmanTree p;if(n<=1) return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(p=HT+1,i=1;i<=n;++i,++p,++character,++w){p->ch=*character;p->weight=*w;p->parent=0;p->lchild=0;p->rchild=0;}for(;i<=m;++i,++p) {p->ch=0;p->weight=0;p->parent=0;p->lchild=0;p->rchild=0;}for(i=n+1;i<=m;++i){ 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;}}////////////////////////////////////////////////////////////////////////////////*从HT[1]到HT[j]中选择parent为0且weight最小的两个结点，用s1和s2返回其序号*/void select(HuffmanTree HT,int j,int *s1,int *s2){int i;//找weight最小的结点for (i=1;i<=j;i++) if (HT[i].parent==0) {*s1=i;break;}for (;i<=j;i++) if ((HT[i].parent==0)&&(HT[i].weight<HT[*s1].weight)) *s1=i; HT[*s1].parent=1;//找weight次小的结点for (i=1;i<=j;i++) if (HT[i].parent==0) {*s2=i;break;}for (;i<=j;i++) if ((HT[i].parent==0)&&(i!=*s1)&&(HT[i].weight<HT[*s2].weight)) *s2=i;}////////////////////////////////////////////////////////////////////////////////*对文件tobetrans中的正文进行编码，然后将结果存入文件codefile中*/void Coding() {FILE *fp,*fw;int i,f,c,start;char *cd;HuffmanCode HC;if(n==0) n=Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数 /////以下程序段求赫夫曼树中各叶子节点的字符对应的的编码，并存于HC指向的空间中{HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char *)malloc(n*sizeof(char));cd[n-1]="";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)); strcpy(HC[i],&cd[start]);}free(cd);}/////////////////////////////////////////////////////////////////////////////////////if((fp=fopen("tobetrans.txt","rb"))==NULL) printf("Open file tobetrans.txt error! ");if((fw=fopen("codefile.txt","wb+"))==NULL) printf("Open file codefile.txt error! ");char temp;fscanf(fp,"%c",&temp); //从文件读入第一个字符while(!feof(fp)){ for(i=1;i<=n;i++) if(HT[i].ch==temp) break; //在赫夫曼树中查找字符所在的位置 for(int r=0;HC[i][r]!="";r++) //将字符对应的编码存入文件 fputc(HC[i][r],fw); fscanf(fp,"%c",&temp); //从文件读入下一个字符}fclose(fw);fclose(fp);printf(" 对文件hfmtree.txt编码成功,结果已存入codefile.txt中。 ");}//////////////////////////////////////////////////////////////////////////*将文件codefile中的代码进行译码，结果存入文件textfile中*/void Decoding() {FILE *fp,*fw;int m,i;char *code,*text,*p; if(n==0) n=Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数if((fp=fopen("codefile.txt","rb"))==NULL) printf("Open file codefile.txt error! "); if((fw=fopen("textfile.txt","wb+"))==NULL) printf("Open file textfile.txt error! ");code=(char *)malloc(sizeof(char));fscanf(fp,"%c",code); //从文件读入一个字符for(i=1;!feof(fp);i++){ code=(char *)realloc(code,(i+1)*sizeof(char)); //增加空间 fscanf(fp,"%c",&code[i]); //从文件读入下一个字符 }code[i-1]="";/////////到此codefile.txt文件中的字符已全部读入，存放在code数组中 text=(char *)malloc(100*sizeof(char));p=text; m=2*n-1;if(*code=="0") find(HT,code,text,HT[m].lchild,m); //从根节点的左子树去找else find(HT,code,text,HT[m].rchild,m); //从根节点的右子树去找 for(i=0;p[i]!="";i++) //把译码好的字符存入文件textfile.txt中 fputc(p[i],fw);fclose(fp);fclose(fw);printf(" 对codefile.txt文件译码成功，结果已存入textfile.txt文件。 ");}///////////////////////////////////////////////////////////////////////////////////////////////////////*将文件codefi1e以紧凑格式显示在终端上,每行50个代码。同时将此字符形式的编码文件写入文件codeprint中。*/void Print_code(){FILE *fp,*fw;char temp;int i; if((fp=fopen("codefile.txt","rb"))==NULL) printf("Open file codefile.txt error! ");if((fw=fopen("codeprint.txt","wb+"))==NULL) printf("Open file codeprint.txt error! ");printf(" 文件codefi1e以紧凑格式显示如下: ");fscanf(fp,"%c",&temp); //从文件读入一个字符for (i=1;!feof(fp);i++){ printf("%c",temp); if(i%50==0) printf(" "); fputc(temp,fw); //将该字符存入文件codeprint.txt中 fscanf(fp,"%c",&temp); //从文件读入一个字符}printf(" 此字符形式的编码已写入文件codeprint.txt中. ");fclose(fp);fclose(fw);}///////////////////////////////////////////////////////////////////////////////////////////////////*将已在内存中的哈夫曼树以凹凸表形式显示在屏幕上，同时将此字符形式的哈夫曼树写入文件treeprint中。*/void Print_tree(){unsigned char T[100][100];int i,j,m=0;FILE *fp;if(n==0) n=Read_tree(HT);//从文件hfmtree.txt中读入赫夫曼树,返回叶子结点数Convert_tree(T,0,&m,2*n-1); //将内存中的赫夫曼树转换成凹凸表形式的树，存于数组T中if((fp=fopen("treeprint.txt","wb+"))==NULL) printf("Open file treeprint.txt error! "); printf(" 以凹凸表形式打印已建好的赫夫曼树： ");for(i=1;i<=2*n-1;i++){ for (j=0;T[i][j]!=0;j++) { if(T[i][j]==" ") {printf(" ");fputc(T[i][j],fp);} else {printf("%d",T[i][j]);fprintf(fp,"%d ",T[i][j]);} } printf(" ");}fclose(fp);printf(" 此字符形式的哈夫曼树已写入文件treeprint.txt中. ");}///////////////////////////////////////////////////////////////////////////////////*从文件hfmtree.txt中读入赫夫曼树，返回叶子节点数*/int Read_tree(HuffmanTree &HT) {FILE *fp;int i,n;HT=(HuffmanTree)malloc(sizeof(HTNode)); if((fp=fopen("hfmtree.txt","r"))==NULL) printf("Open file hfmtree.txt error! ");for (i=1;!feof(fp);i++){ HT=(HuffmanTree)realloc(HT,(i+1)*sizeof(HTNode)); //增加空间 fread(&HT[i],sizeof(HTNode),1,fp); //读入一个节点信息}fclose(fp);n=(i-1)/2;return n;}/////////////////////////////////////////////////////////////////*译码时根据01字符串寻找相应叶子节点的递归算法*/void find(HuffmanTree &HT,char *code,char *text,int i,int m){if(*code!="") //若译码未结束{ code++; if(HT[i].lchild==0&&HT[i].rchild==0) //若找到叶子节点 { *text=HT[i].ch; //将叶子节点的字符存入text中 text++; if((*code=="0")) find(HT,code,text,HT[m].lchild,m); //继续从根节点的左子树找 else find(HT,code,text,HT[m].rchild,m); //继续从根节点的右子树找 } else //如果不是叶子节点 if(*code=="0") find(HT,code,text,HT[i].lchild,m); //从该节点的左子树去找 else find(HT,code,text,HT[i].rchild,m); //从该节点的右子树去找}else *text=""; //译码结束}/////////////////////////////////////////////////////////////////////////*将内存中的赫夫曼树转换成凹凸表形式的赫夫曼树*/void Convert_tree(unsigned char T[100][100],int s,int *i,int j){int k,l;l=++(*i);for(k=0;k<s;k++) T[l][k]=" ";T[l][k]=HT[j].weight;if(HT[j].lchild) Convert_tree(T,s+1,i,HT[j].lchild);if(HT[j].rchild) Convert_tree(T,s+1,i,HT[j].rchild); T[l][++k]="";}自己改改吧！

说明：本程序是依据严蔚敏的数据结构（C语言版）上的代码实现的。#pragmaonce#include<stdio.h>#include<tchar.h>#include<stdlib.h>#define MAX 100 typedefstruct{ //节点 int weight; int parent, lchild, rchild;}HTNode, *HuffmanTree; typedefchar **HuffmanCode; //字符串数组，用于存储叶子节点的编码 void SelectMinNode(HuffmanTree &HT, int m, int &i1, int &i2) //找出权值最小的两个节点对应的数组下标{ HuffmanTree p = HT; int s1, s2; s1 = s2 = MAX; i1 = i2 = 1; for(int i=1; i<=m; i++) { if(!(p+i)->parent) { if((p+i)->weight < s1) { i2 = i; s1 = (p+i)->weight ; } } } for(int i=1; i<=m; i++) { if(!(p+i)->parent && i!=i2) { if((p+i)->weight < s2) { i1 = i; s2 = (p+i)->weight ; } } }}void StrCopy(char *p, char *q, int start) //从字符数组中第start个字符开始复制{ char *c1, *c2; c1 = p; while(q[start] != "") { *c1 = q[start]; c1++; start++; } *c1 = q[start];//别忘了将‘ "复制过来}void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n){ //HT赫夫曼树节点数组，HC存储赫夫曼编码，*w 节点权值数组的首地址，n节点个数 int i, i1, i2, m; HuffmanTree p; if(n<=1) return; m = 2 * n -1; //n个叶子节点的赫夫曼树的节点总数为2n-1，可以结合树的度为n-1自己证明。 HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); //数组首元素不使用，故多分配一个空间 p = HT + 1; for(i=1;i<=n;++i,++p,++w) //n个叶子节点初始化 { p->weight = *w; p->lchild = 0; p->rchild = 0; p->parent = 0; } for(;i<=m;++i,++p) //非叶子节点初始化 { p->weight = 0; p->lchild = 0; p->rchild = 0; p->parent = 0; } for(i=n+1;i<=m;++i) //对非叶子节点重新计算 { SelectMinNode(HT, i-1, i1, i2); HT[i1].parent = i; HT[i2].parent = i; HT[i].lchild = i1; HT[i].rchild = i2; HT[i].weight = HT[i1].weight + HT[i2].weight ; } ///从叶子节点到根节点求赫夫曼编码 char* cd; int start, c, f; HC = (HuffmanCode)malloc((n+1)*sizeof(char*));//分配字符指针数组，同样多分配一个 cd = (char*)malloc(n*sizeof(char)); //零时变量，用于存储当前叶子节点的赫夫曼编码 cd[n-1] = ""; for(int 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)); StrCopy(HC[i], cd, start); //将存储的编码copy给HC的第i个数组 } free(cd);}void PrintHuffmanCode(HuffmanTree HT, HuffmanCode HC, int n) //打印各节点的赫夫曼编码{ HuffmanCode p; for(int i=1; i<=n; i++) { p = HC; printf("The weight %d HuffmanCode is: ", HT[i]); while(*p[i]!="") { printf("%c",*p[i]); p[i]++; } printf(" "); }}void main(){ int n = 8; HuffmanTree HT; HuffmanCode HC; int a[8] = {5, 29, 7, 8, 14, 23, 3, 11};//信号源的概率分布，即P={p0, p1,…, pK-1} HuffmanCoding(HT, HC, a, n); PrintHuffmanCode(HT, HC, n); system("pause");}

哈夫曼编码的扩展操作码是怎么算的？假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}。哈夫曼编码 根据上面可得编码表： a:1001 b:01 c:10111 d:1010 e:11 f:10110 g:00 h:1000用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为：4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61/3=0.87=87%其平均码长是等长码的87%，所以平均压缩率为13%。因为定长编码已经用相同的位数这个条件保证了任一个字符的编码都不会成为其它编码的前缀,所以这种情况只会出现在变长编码当中，要想避免这种情况，就必须用一个条件来制约定长编码，这个条件就是要想成为压缩编码，变长编码就必须是前缀编码，所谓的前缀编码就是任何一个字符的编码都不能是另一个字符编码的前缀。

哈夫曼编码规则：哈夫曼编码是一种可变长度的编码方式，其特点是给予出现频率较高的字符更短的编码，以此达到压缩的目的。拓展：哈夫曼编码可以用于文件压缩，以有效减少文件大小。它也可以用来加速网络传输，以便更快地传输数据。此外，哈夫曼编码还可以用于错误检测和纠正，因为编码的模式可以帮助检测和纠正错误。

哈夫曼编码(Huffman Coding)是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由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。 因此，大家都会发现，理解甚至修改这个编码都是很容易的。 背景 哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。 编码使用 我用简单的C函数写这个编码是为了让它在任何地方使用都会比较方便。你可以将他们放到类中，或者直接使用这个函数。并且我使用了简单的格式，仅仅输入输出缓冲区，而不象其它文章中那样，输入输出文件。 bool CompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen); bool DecompressHuffman(BYTE *pSrc, int nSrcLen, BYTE *&pDes, int &nDesLen); 要点说明 速度 为了让它(huffman.cpp)快速运行，我花了很长时间。同时，我没有使用任何动态库，比如STL或者MFC。它压缩1M数据少于100ms（P3处理器，主频1G）。 压缩 压缩代码非常简单，首先用ASCII值初始化511个哈夫曼节点： CHuffmanNode nodes[511]; for(int nCount = 0; nCount < 256; nCount++) nodes[nCount].byAscii = nCount; 然后，计算在输入缓冲区数据中，每个ASCII码出现的频率： for(nCount = 0; nCount < nSrcLen; nCount++) nodes[pSrc[nCount]].nFrequency++; 然后，根据频率进行排序： qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare); 现在，构造哈夫曼树，获取每个ASCII码对应的位序列： int nNodeCount = GetHuffmanTree(nodes); 构造哈夫曼树非常简单，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。这样，新节点就是两个被替换节点的父节点了。如此循环，直到队列中只剩一个节点（树根）。 // parent node pNode = &nodes[nParentNode++]; // pop first child pNode->pLeft = PopNode(pNodes, nBackNode--, false); // pop second child pNode->pRight = PopNode(pNodes, nBackNode--, true); // adjust parent of the two poped nodes pNode->pLeft->pParent = pNode->pRight->pParent = pNode; // adjust parent frequency pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency; 这里我用了一个好的诀窍来避免使用任何队列组件。我先前就直到ASCII码只有256个，但我分配了511个(CHuffmanNode nodes[511])，前255个记录ASCII码，而用后255个记录哈夫曼树中的父节点。并且在构造树的时候只使用一个指针数组(ChuffmanNode *pNodes[256])来指向这些节点。同样使用两个变量来操作队列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount –1)。 接着，压缩的最后一步是将每个ASCII编码写入输出缓冲区中： int nDesIndex = 0; // loop to write codes for(nCount = 0; nCount < nSrcLen; nCount++) { *(DWORD*)(pDesPtr+(nDesIndex>>3)) |= nodes[pSrc[nCount]].dwCode << (nDesIndex&7); nDesIndex += nodes[pSrc[nCount]].nCodeLength; } (nDesIndex>>3): >>3 以8位为界限右移后到达右边字节的前面 (nDesIndex&7): &7 得到最高位. 注意：在压缩缓冲区中，我们必须保存哈夫曼树的节点以及位序列，这样我们才能在解压缩时重新构造哈夫曼树（只需保存ASCII值和对应的位序列）。 解压缩 解压缩比构造哈夫曼树要简单的多，将输入缓冲区中的每个编码用对应的ASCII码逐个替换就可以了。只要记住，这里的输入缓冲区是一个包含每个ASCII值的编码的位流。因此，为了用ASCII值替换编码，我们必须用位流搜索哈夫曼树，直到发现一个叶节点，然后将它的ASCII值添加到输出缓冲区中： int nDesIndex = 0; DWORD nCode; while(nDesIndex < nDesLen) { nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7); pNode = pRoot; while(pNode->pLeft) { pNode = (nCode&1) ? pNode->pRight : pNode->pLeft; nCode >>= 1; nSrcIndex++; } pDes[nDesIndex++] = pNode->byAscii; }

昨天电话面试的过程中被问到了可变长编码，被问的有点懵逼。。特地来记录一下。 由于度娘上面没有搜到相关的文章，所以只能自己总结一下，搜到的可变长编码好像有 赫夫曼编码 和 UTF 编码。UTF编码又有 UTF-8 和 UTF-16 ，本文仅对更为常见的 UTF-8 编码进行简单的分析介绍。 赫夫曼编码（Huffman Coding），又称哈夫曼编码、霍夫曼编码，是可变字长编码（VLC）的一种。在说赫夫曼编码前，需要先引入另一个概念： 赫夫曼 。赫夫曼树又称最优树，是一类带权路径长度最短的树，有着广泛的应用。 赫夫曼树的定义：假设有 n 个权值{w1 ,w2 ,... ,w n }，试构造一颗有 n 个叶子结点的二叉树，每个叶子结点带权为w i ，则其中带权路径长度WPL最小的二叉树称为 最优二叉树 或 霍夫曼树 。 举个例子：假如现在有A ,B ,C ,D ,E这五个字符，它们分别出现的频率（即权值）为5,4,3,2,1，下图为赫夫曼树的构建过程（每次取两个权值最小的节点生成一个树）： 赫夫曼编码是一种 无前缀 编码。解码时不会混淆。其 主要应用在数据压缩，加密解密 等场合。 UTF-8（8-bit Unicode Transformation Format）是一种 针对Unicode的可变长度字符编码，又称万国码 。 UTF-8 编码规则 ：如果只有一个字节则其最高二进制位为0；如果是多字节，其第一个字节从最高位开始，连续的二进制位值为 1 的个数决定了其编码的字节数，其余各字节均以 10 开头。 UTF-8转换表 表示如下： 实际表示 ASCII 字符的 UNICODE 字符，将会编码成1个字节，并且 UTF-8 表示与 ASCII 字符表示是一样的。所有其他的 UNICODE 字符转化成 UTF-8 将需要至少2个字节。每个字节由一个换码序列开始。第一个字节由唯一的换码序列，由 n 位连续的1加一位0组成, 首字节连续的1的个数表示字符编码所需的字节数。 Unicode 转换为 UTF-8 时，可以将 Unicode 二进制从低位往高位取出二进制数字，每次取6位，如上述的二进制就可以分别取出为如下示例所示的格式，前面按格式填补，不足8位用0填补。 注 ： Unicode 转换为 UTF-8 需要的字节数可以根据这个规则计算：如果 Unicode 小于0X80（Ascii字符），则转换后为1个字节。否则转换后的字节数为 Unicode 二进制位数+3再除以5。

注释非常详细，希望对你有所帮助！#ifndef Huffman_Tree_h#define Huffman_Tree_h#endif#include <stdio.h>typedef struct { unsigned int weight; unsigned int parent,lchild,rchild;}HTNode, * HuffmanTree; //存储赫夫曼树的结点类型typedef char * * HuffmanCode; //用于存储字符集中各个字符相应的赫夫曼编码void strcpy(char *S1,char *S2){ //将字符串S2复制到S1 int i = 0; while( S2[i] != "" ){ S1[i] = S2[i]; i++; } S1[i] = "";}void Select(HuffmanTree HT,int t,int &s1,int &s2){ //在HT[1]到HT[t-1]中找出权值最小的两个S1和S2 int i = 1; s1 = s2 = 0; HT[0].weight = 65535; while( i <= t ){ //遍历查找权值最小的结点S1 if( HT[i].parent == 0 && HT[i].weight < HT[s1].weight ) s1 = i; i++; } i = 1; while( i <= t ){ //遍历查找除S1外权值最小的结点S2 if( i != s1 && HT[i].parent == 0 && HT[i].weight < HT[s2].weight ) s2 = i; i++; }}int HuffmanCoding( HuffmanTree &HT,HuffmanCode &HC,int *w,int n){ //根据各个字符的权值构造赫夫曼树HT，将对应的赫夫曼编码存储在HC中 int s1,s2,m,i,start; unsigned int c,f; HTNode * p; char *cd; if( n <= 1 ) return 0; m = 2 * n - 1; //赫夫曼树的总结点树为m HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); //申请存储赫夫曼树的空间 for(p = HT + 1, i = 1; i <= n; ++i, ++p, ++w){ //将各个叶子结点的weight赋以相应的权值，parent,lchild,rchild均赋为0 p->weight = *(w+1); p->parent = p->lchild = p->rchild = 0; } for( ; i <= m; ++i, ++p ){ //将各个非叶子结点的weight,parent,lchild,rchild均赋为0 p->weight = p->parent = p->lchild = p->rchild = 0; } for( i = n + 1; i <= m; ++i ){ //构造赫夫曼树，给各个非叶子结点赋值 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; } HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); //申请空间，用于存储指向存储各个字符相应赫夫曼编码的字符数组的指针 cd = (char *)malloc(n * sizeof(char)); //申请用于求赫夫曼编码 cd[n - 1] = ""; //编码结束符 for( i = 1; i <= n; ++i){ //逐个字符求赫夫曼编码 start = n -1; //编码在数组cd[]中的最前位置 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], &cd[start]); //将cd[]数组的start位置到n-1位置复制给HC[i] } free(cd); //释放空间 return 1;}以上为第一部分#include <stdio.h>#include <stdlib.h>#include "Huffman_Tree.h"#define Yes 1 //当程序已经调用过初始化赫夫曼树的InitHuff_T()函数，或已从htfTree文件读取过，则将Init_Mode置为Yes，否则为No#define No 0void InitHuff_T( HuffmanTree &HT, HuffmanCode &HC, char ch[],int &n ){ //初始化赫夫曼数，要求用户输入字符和相应权值 int i = 1,w[100],tem,j; char a[20]; FILE *save; printf("请输入编码字符集的大小n:"); scanf("%d",&n); //获取用户输入的字符集个数 while( i <= n ){ //获取用户输入的字符和相应权值，分别存储在ch[]和w[]数组中 printf("请输入第%d个字符和该字符的权值w:",i); fflush(stdin); scanf("%c%d",&ch[i],&w[i]); i++; } ch[i] = ""; HuffmanCoding(HT,HC,w,n); //根据用户的输入，生成赫夫曼数及各个字符相应的赫夫曼编码，分别存在HT树和HC中 if(( save = fopen("htfTree","w")) == NULL ){ //打开用于存储赫夫曼树的文件 printf("Open file fail...... "); exit(0); } tem = n; //接下来的14行是将字符集大小转换成字符形式写入到文件中 j = 0; while( tem != 0 ){ tem = tem / 10; j++; } tem = n; a[j] = ""; while( tem != 0 ){ a[j - 1] = (char)(tem % 10 + 48); tem = tem / 10; j--; } fputs(a,save); printf("%d ",n); //向屏幕输出字符集大小n fputc(" ",save); for( i = 1; i <= n; i++ ){ //分别向文件和屏幕输出各个字符和相应的赫夫曼编码 fputc(ch[i],save); printf("%c ",ch[i]); fputc(" ",save); fputs(HC[i],save); printf("%s ",HC[i]); fputc(" ",save); } for(i = 1; i <= 2 * n - 1; i++ ){ //将赫夫曼树各个结点的parent,lchild,rchild分别写入到文件中 tem = HT[i].parent; //将i结点的parent转换成字符并写入到文件中 if(tem == 0){ fputc(tem + 48,save); fputc(" ",save); } else{ j = 0; while( tem != 0 ){ tem = tem / 10; j++; } tem = HT[i].parent; a[j] = ""; while( tem != 0 ){ a[j - 1] = (char)(tem % 10 + 48); tem = tem / 10; j--; } fputs(a,save); fputc(" ",save); }tem = HT[i].lchild; //将i结点的lchild转换成字符并写入到文件中 if(tem == 0){ fputc(tem + 48,save); fputc(" ",save); } else{ j = 0; while( tem != 0 ){ tem = tem / 10; j++; } tem = HT[i].lchild; a[j] = ""; while( tem != 0 ){ a[j - 1] = (char)(tem % 10 + 48); tem = tem / 10; j--; } fputs(a,save); fputc(" ",save); }tem = HT[i].rchild; //将i结点的rchild转换成字符并写入到文件中 if(tem == 0){ fputc(tem + 48,save); fputc(" ",save); } else{ j = 0; while( tem != 0 ){ tem = tem / 10; j++; } tem = HT[i].rchild; a[j] = ""; while( tem != 0 ){ a[j - 1] = (char)(tem % 10 + 48); tem = tem / 10; j--; } fputs(a,save); fputc(" ",save); } } fclose(save);}void Encoding(HuffmanTree &HT, HuffmanCode &HC, char ch[]){ //根据赫夫曼编码将用户指定的文件中的字符编成相应的编码,并将所得编码存储到用户指定文件 FILE *ToBeTran,*CodeFile; char ToBeTran_Name[100],CodeFile_Name[100]; //存储用户指定文件的文件名 int i; char c; printf("请输入所要进行编码的文件的文件名:"); scanf("%s",ToBeTran_Name); //获得所要进行编码的文件的文件名 if(( ToBeTran = fopen(ToBeTran_Name,"r")) == NULL ){ //打开文件 printf("Open file fail...... "); exit(0); } printf("请输入编码后编码表示的信息所存储到的文件的文件名:"); scanf("%s",CodeFile_Name); //获得编码后编码表示的信息所存储到的文件的文件名 if(( CodeFile = fopen(CodeFile_Name,"w")) == NULL ){ //打开文件 printf("Open file fail...... "); exit(0); } c = fgetc(ToBeTran); //从文件读取一个字符 while( c != EOF ){ //对文件中的各个字符进行编码，直至文件结尾 i = 1; while( c != ch[i] && ch[i] != "" ) //在ch[]数组中查找从文件读取的字符 i++; if(ch[i] == ""){ //未找到，c不在ch[]数组中，c无法被识别，程序出错，退出 printf("字符%c无法识别，程序将退出。 ",c); exit(0); } fputs(HC[i],CodeFile); //若找到，则将c相应的赫夫曼编码写入到文件中 printf("%s",HC[i]); //将c相应的赫夫曼编码输出到屏幕 c = fgetc(ToBeTran); //读入文件中的下一个字符 } printf(" "); fclose(ToBeTran); fclose(CodeFile);}void Decoding(HuffmanTree HT, char ch[] , int n){ //对指定的存储由赫夫曼编码表示的信息的文件进行译码，翻译成相应的字符表示，并存储到指定文件 int p,i = 1; char code[1000],c; char CodeFile_Name[100],TextFile_Name[100]; //存储用户指定文件的文件名 p = 2 * n - 1; FILE *CodeFile,*TextFile; printf("请输入所要译的文件名:"); scanf("%s",CodeFile_Name); //获得所要译的文件的文件名 if(( CodeFile = fopen("CodeFile","r")) == NULL ){ //打开文件 printf("Open file fail...... "); exit(0); } printf("请输入译后的字符存储到的文件的文件名:"); scanf("%s",TextFile_Name); //获得译后的字符存储到的文件的文件名 if(( TextFile = fopen(TextFile_Name,"w")) == NULL ){ //打开文件 printf("Open file fail...... "); exit(0); } c = fgetc(CodeFile); while( c != EOF ){ code[i] = c; i++; c = fgetc(CodeFile); } code[i] = ""; //从文件读取字符，存储在code[]数组中 i = 1; while ( code[i] != "" && p != 0 ){ //对数组code[]中的赫夫曼编码进行译码 if ( code[i] == "0" ) p=HT[p].lchild; //进入左分支 else p = HT[p].rchild; //进入右分支 if (!HT[p].lchild&& !HT[p].rchild){ //进入叶子结点 fputc(ch[p], TextFile); //将相应的字符写入到文件中 printf("%c",ch[p]); //将相应的字符输出到屏幕 p = 2 * n - 1; //重新从树根出发进行译码 } i++; } printf(" ");}void ReadHuff_T( HuffmanTree &HT, HuffmanCode &HC, char ch[], int &n){ //从文件读取赫夫曼树 FILE *htfTree; char c[100],ch1; int i,j,t; if(( htfTree = fopen("htfTree","r")) == NULL ){ //打开存有赫夫曼树信息的文件 printf("Open file fail...... "); exit(0); } fgets(c,10,htfTree); //获取赫夫曼树叶子结点个数的字符串表示形式 i = 0; //以下6行将字符串形式转换成整数形式 while( c[i] != " " ) i++; n = 0; for( j = 0; j < i; j++ ) n = 10 * n + c[j] - "0"; //求出叶子结点数n HC = (HuffmanCode)malloc((n + 1) * sizeof(char *)); //申请HC空间 HT = (HuffmanTree)malloc((2 * n) * sizeof(HTNode)); //申请赫夫曼树存储空间 i = 1; while( i <= n ){ ch[i] = fgetc(htfTree); //读取字符集中的一个字符 HC[i] = (char *)malloc((10)*sizeof(char)); //申请用于存储读取到的字符集中的字符的赫夫曼编码的空间 fgetc(htfTree); //将‘ "输出 ch1 = fgetc(htfTree); //读取赫夫曼编码，存储在相应的HC[i][]数组里 int j = 0; while( ch1 != " " ){ HC[i][j] = ch1; j++; ch1 = fgetc(htfTree); } HC[i][j] = ""; i++; } ch[i] = ""; i = 0; while( i < 2 * n - 1 ){ //读取赫夫曼树的各个结点的parent,lchild,rchild.并赋值到赫夫曼树HT中 ch1 = fgetc(htfTree); //读取parent的字符串形式,存储在c[]中，并将其转换成整数形式，赋给HT[i].parent j = 0; while( ch1 != " " ){ c[j] = ch1; j++; ch1 = fgetc(htfTree); } HT[i+1].parent = 0; for( t = 0; t < j; t++ ) HT[i+1].parent = 10 * HT[i+1].parent + c[t] - "0"; ch1 = fgetc(htfTree); //读取lchild的字符串形式，并将其转换成整数形式，赋给HT[i].lchild j = 0; while( ch1 != " " ){ c[j] = ch1; j++; ch1 = fgetc(htfTree); } HT[i+1].lchild = 0; for( t = 0; t < j; t++ ) HT[i+1].lchild = 10 * HT[i+1].lchild + c[t] - "0"; ch1 = fgetc(htfTree); //读取rchild的字符串形式，并将其转换成整数形式，赋给HT[i].rchild j = 0; while( ch1 != " " ){ c[j] = ch1; j++; ch1 = fgetc(htfTree); } HT[i+1].rchild = 0; for( t = 0; t < j; t++ ) HT[i+1].rchild = 10 * HT[i+1].rchild + c[t] - "0"; i++; }}int main(){ HuffmanTree HT; HuffmanCode HC; char ch[100]; //用于存储字符集 int n,Init_Mode = No; //n为字符集的大小，Init_Mode = No 表示内存中没有赫夫曼树的信息 char mode; //让用户选择不同的操作 printf("请输入你要选择的功能 "); printf(" I -- 初始化 E -- 编码 "); printf(" D -- 译码 Q -- 退出程序 "); scanf("%c",&mode); //获得用户选择的操作 while( mode != "Q" && mode != "q" ){ //当用户输入不为Q或q时，执行相应操作 switch(mode){ case "I" : InitHuff_T(HT,HC,ch,n); Init_Mode = Yes; break; case "i" : InitHuff_T(HT,HC,ch,n); Init_Mode = Yes; break; case "E" : if( No == Init_Mode ) ReadHuff_T(HT,HC,ch,n); Encoding(HT,HC,ch); Init_Mode = Yes; break; case "e" : if( No == Init_Mode ) ReadHuff_T(HT,HC,ch,n); Encoding(HT,HC,ch); Init_Mode = Yes; break; case "D" : if( No == Init_Mode ) ReadHuff_T(HT,HC,ch,n); Decoding(HT,ch,n); Init_Mode = Yes; break; case "d" : if( No == Init_Mode ) ReadHuff_T(HT,HC,ch,n); Decoding(HT,ch,n); Init_Mode = Yes; default : printf("您的输入有错，请重新选择. "); } printf("请输入你要选择的功能 "); printf(" I -- 初始化 E -- 编码 "); printf(" D -- 译码 Q -- 退出程序 "); fflush(stdin); scanf("%c",&mode); //让用户继续选择相应的操作，直至用户选择退出 } return 0;}

/*文件名:exp7-6.cpp*/#include <stdio.h>#include <string.h>#define N 50 /*叶子结点数*/#define M 2*N-1 /*树中结点总数*/typedef struct{ char data[5]; /*结点值*/ int weight; /*权重*/ int parent; /*双亲结点*/ int lchild; /*左孩子结点*/ int rchild; /*右孩子结点*/} HTNode;typedef struct{ char cd[N]; /*存放哈夫曼码*/ int start;} HCode;void CreateHT(HTNode ht[],int n){ int i,k,lnode,rnode; int min1,min2; for (i=0;i<2*n-1;i++) /*所有结点的相关域置初值-1*/ ht[i].parent=ht[i].lchild=ht[i].rchild=-1; for (i=n;i<2*n-1;i++) /*构造哈夫曼树*/ { min1=min2=32767; /*lnode和rnode为最小权重的两个结点位置*/ lnode=rnode=-1; for (k=0;k<=i-1;k++) if (ht[k].parent==-1) /*只在尚未构造二叉树的结点中查找*/ { if (ht[k].weight<min1) { min2=min1;rnode=lnode; min1=ht[k].weight;lnode=k; } else if (ht[k].weight<min2) { min2=ht[k].weight;rnode=k; } } ht[lnode].parent=i;ht[rnode].parent=i; ht[i].weight=ht[lnode].weight+ht[rnode].weight; ht[i].lchild=lnode;ht[i].rchild=rnode; }}void CreateHCode(HTNode ht[],HCode hcd[],int n){ int i,f,c; HCode hc; for (i=0;i<n;i++) /*根据哈夫曼树求哈夫曼编码*/ { hc.start=n;c=i; f=ht[i].parent; while (f!=-1) /*循序直到树根结点*/ { if (ht[f].lchild==c) /*处理左孩子结点*/ hc.cd[hc.start--]="0"; else /*处理右孩子结点*/ hc.cd[hc.start--]="1"; c=f;f=ht[f].parent; } hc.start++; /*start指向哈夫曼编码最开始字符*/ hcd[i]=hc; }}void DispHCode(HTNode ht[],HCode hcd[],int n){ int i,k; int sum=0,m=0,j; printf(" 输出哈夫曼编码: "); /*输出哈夫曼编码*/ for (i=0;i<n;i++) { j=0; printf(" %s: ",ht[i].data); for (k=hcd[i].start;k<=n;k++) { printf("%c",hcd[i].cd[k]); j++; } m+=ht[i].weight; sum+=ht[i].weight*j; printf(" "); } printf(" 平均长度=%g ",1.0*sum/m);}void main(){ int n=15,i; char *str[]={"The","of","a","to","and","in","that","he","is","at","on","for","His","are","be"}; int fnum[]={1192,677,541,518,462,450,242,195,190,181,174,157,138,124,123}; HTNode ht[M]; HCode hcd[N]; for (i=0;i<n;i++) { strcpy(ht[i].data,str[i]); ht[i].weight=fnum[i]; } printf(" "); CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); printf(" ");}以前写的，你照着改下就行的.

设某信源产生有五种符号u1、u2、u3、u4和u5，对应概率P1=0.4，P2=0.1，P3=P4=0.2，P5=0.1。首先，将符号按照概率由大到小排队，如图所示。编码时，从最小概率的两个符号开始，可选其中一个支路为0，另一支路为1。这里，我们选上支路为0，下支路为1。再将已编码的两支路的概率合并，并重新排队。多次重复使用上述方法直至合并概率归一时为止。从图（a）和（b）可以看出，两者虽平均码长相等，但同一符号可以有不同的码长，即编码方法并不唯一，其原因是两支路概率合并后重新排队时，可能出现几个支路概率相等，造成排队方法不唯一。一般，若将新合并后的支路排到等概率的最上支路，将有利于缩短码长方差，且编出的码更接近于等长码。这里图（a）的编码比（b）好。扩展资料发展历史哈夫曼编码(Huffman Coding)，又称霍夫曼编码。1951年，哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师Robert M. Fano给他们的学期报告的题目是，寻找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者香农共同研究过类似编码的导师。哈夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。1952年，David A. Huffman在麻省理工攻读博士时发表了《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）一文，它一般就叫做Huffman编码。参考资料来源：百度百科-哈夫曼编码