哈夫曼编码.doc

上传人:数据九部 文档编号:10170389 上传时间:2021-04-25 格式:DOC 页数:5 大小:483KB
返回 下载 相关 举报
哈夫曼编码.doc_第1页
第1页 / 共5页
哈夫曼编码.doc_第2页
第2页 / 共5页
哈夫曼编码.doc_第3页
第3页 / 共5页
哈夫曼编码.doc_第4页
第4页 / 共5页
哈夫曼编码.doc_第5页
第5页 / 共5页
亲,该文档总共5页,全部预览完了,如果喜欢就下载吧!
资源描述

《哈夫曼编码.doc》由会员分享,可在线阅读,更多相关《哈夫曼编码.doc(5页珍藏版)》请在三一文库上搜索。

1、哈夫曼编码一、概述哈夫曼编码(Huffman Coding)是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。 Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫作Huffman编码。 以哈夫曼树即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩。 在计算机信息处理中,“哈夫曼编码”是一种一致性编码法(又称熵编码法),用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符(例如某文件中的一个符号)进行编码。这张编码表的特殊之处在于,它是根据每一个源字符出现的估算概率而建立起来的(出现概率高

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

3、一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号(例如,文本文件中的字符)用一个特定长度的位序列替代。因此,在文件中出现频率高的符号,使用短的位序列,而那些很少出现的符号,则用较长的位序列。二、C语言程序实现文件的huffman编码#include #define MAX 1000#define MAXSYMBS 30#define MAXNODE 59typedef structint weight;int flag;int parent;int lchild;int rchild;huffnode;typedef struct int bitsMAXSYMBS

4、; int start;huffcode;void main() huffnode huff_nodeMAXNODE; huffcode huff_codeMAXSYMBS,cd; int i,j,m1,m2,x1,x2,n,c,p; /*char symbsMAXSYMBS,symb;*/ /*数组buff_node初始化*/ printf(please input the leaf num of tree:n); scanf(%d,&n); for(i=0;i2*n-1;i+) huff_nodei.weight=0;huff_nodei.parent=0;huff_nodei.flag=

5、0;huff_nodei.lchild=-1;huff_nodei.rchild=-1; printf(please input the weight of every leafn); for(i=0;in-1;i+) scanf(%d,&huff_nodei.weight); /*构造哈弗曼树*/ for(i=0;in-1;i+) m1=m2=MAX; x1=x2=0; for(j=0;jn+i;j+) if(huff_nodej.weight m1&huff_nodej.flag =0) m2=m1; x2=x1; m1=huff_nodej.weight ; x1=j; else if

6、(huff_nodej.weight m2&huff_nodej.flag =0) m2=huff_nodej.weight; x2=j; huff_nodex1.parent=n+i; huff_nodex2.parent=n+i; huff_nodex1.flag =1; huff_nodex2.flag =1; huff_noden+i.weight =huff_nodex1.weight +huff_nodex2.weight ; huff_noden+i.lchild =x1; huff_noden+i.rchild =x2; /*求字符的哈弗曼编码*/ for(i=0;in;i+)

7、 cd.start =n;c=i;p=huff_nodec.parent ;while(p!=0)if(huff_nodep.lchild =c)cd.bits cd.start =0;else cd.bits cd.start =1;cd.start=cd.start -1;c=p;p=huff_nodep.parent ;cd.start +;for(j=cd.start ;j=n;j+)huff_codei.bitsj=cd.bits j;huff_codei.start =cd.start ; /*输出字符的哈弗曼编码*/ puts(the hafman code are:); for(i=0;in;i+) for(j=huff_codei.start;j=n;j+)printf(%10d,huff_codei.bits j); printf(/n); puts(press any key to quit.); 三、运行界面please input the leaf num of tree:8please input the weight of every leaf1 2 3 4 5 6 7 1输出:110101100100101111000111011

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 科普知识


经营许可证编号:宁ICP备18001539号-1