信息论编码哈夫曼编码的实现

信息论编码哈夫曼编码的实现院系：信息工程院系专业：通信工程专业学号：信息论发展简史与信息科学信息论从诞生到今天，已有五十多年历史，现已成为一门独立的理论科学，回顾它的发展历史，我们可以知道理论是如何从实践中经过抽象、概括、提高而逐步形成的。1.信息论形成的背景与基础信息论是在人们长期的通信工程实践中，由通信技术和概率论、随机过程和数理统计相结合而逐步发展起来的一门学科。人们公认的信息论的奠基人是当代伟大的数学家、美国贝尔实验室杰出的科学家香农，他在1948年发表了著名的论文《通信的数学理论》，为信息论奠定了理论基础。近半个世纪以来，以通信理论为核心的经典信息论，正以信息技术为物化手段，向高精尖方向迅猛发展，并以神奇般的力量把人类社会推入了信息时代。随着信息理论的迅猛发展和信息概念的不断深化，信息论所涉及的内容早已超越了狭义的通信工程范畴，进入了信息科学领域。通信系统是人类社会的神经系统，即使在原始社会也存在着最简单的通信工具和通信系统，这方面的社会实践是悠久漫长的。电的通信系统(电信系统)已有100多年的历史了。在一百余年的发展过程中，一个很有意义的历史事实是：当物理学中的电磁理论以及后来的电子学理论一旦有某些进展，很快就会促进电信系统的创造发明或改进。这是因为通信系统对人类社会的发展，其关系实在是太密切了。日常生活、工农业生产、科学研究以及战争等等，一切都离不开消息传递和信息流动。例如，当法拉第(M．Faraday)于1820年--1830年期间发现电磁感应的基本规律后，不久莫尔斯(F．B．Morse)就建立起电报系统(1832—1835)。1876年，贝尔(A．G．BELL)又发明了电话系统。1864年麦克斯韦(Maxell)预言了电磁波的存在，1888年赫兹(H．Hertz)用实验证明了这一预言。接着1895年英国的马可尼(G.Marconi)和俄国的波波夫(A．C．ΠoΠoB)就发明了无线电通信。本世纪初(1907年)，根据电子运动的规律，福雷斯特(1，Forest)发明了能把电磁波进行放大的电子管。之后很快出现了远距离无线电通信系统。大功率超高频电子管发明以后，电视系统就建立起来了(1925—1927)。电子在电磁场运动过程中能量相互交换的规律被人们认识后，就出现了微波电子管(最初是磁控管，后来是速调管、行波管)，接着，在三十年代末和四十年代初的二次世界大战初期，微波通信系统、微波雷达系统等就迅速发展起来。五十年代后期发明了量子放大器，六十年代初发明的激光技术，使人类进入了光纤通信的时代。随着工程技术的发展，有关理论问题的研究也逐步深入。1832年莫尔斯电报系统中高效率编码方法对后来香农的编码理论是有启发的。1885年凯尔文(L.Kelvin)曾经研究过一条电缆的极限传信率问题。1922年卡逊(J．R．Carson)对调幅信号的频谱结构进行了研究，并建立了信号频谱概念。1924年奈奎斯特(H．Nyquist)指出，如果以一个确定的速度来传输电报信号，就需要一定的带宽。他把信息率与带宽联系起来了。1928年哈特莱(R．V．Hartley)发展了奈奎斯特的工作，并提出把消息考虑为代码或单语的序列。他的工作对后来香农的思想是有影响的。1936年阿姆斯特朗(E．H．Armstrong)认识到在传输过程中增加带宽的办法对抑制噪声干扰肯定有好处。根据这一思想他提出了宽偏移的频率调制方法，该方法是有划时代意义的。信息论作为一门严密的科学分支，主要归功于贝尔实验室的香农。他在1948年发表的论文《通信的数学理论》奠定了信息论的基础。控制论的创始人维纳也对信息论有不可忽视的贡献。香农和维纳的基本思想都是把通信作为统计过程来处理。他们采用的术语、方法也主要依靠统计理论。1.哈夫曼编码简介哈夫曼编码(HuffmanCoding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。2.哈夫曼编码原理哈夫曼编码(HuffmanCoding)是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称熵编码法），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。这种方法是由David.A.Huffman发展起来的。例如，在英文中，e的出现概率很高，而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。3哈夫曼编码步骤首先，哈夫曼编码是哈夫曼树的一个应用，哈夫曼书又称优二树，是一种带路径长度最短的二叉树，所谓树的带权路径长度，就是树中所有的叶节点的权值乘上其到根节点的路径长度（若根节点为0，叶节点到根节点的路径长度为叶节点的层数）。树的带全路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)，N个权值Wi(i=1,2,...n)构成一棵有N哥叶节点的二叉树，相应的叶节点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。哈夫曼编码步骤：1.对给点的n个权值｛W1,W2,W3,...,Wi,...,Wn｝构成n棵二叉树的初始集合F=｛T1,T2,T3,...,Ti,...,Tn｝，其中每棵二叉树Ti中只有一个权值为Wi的根节点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值的升序排列）。2.在F中选取两棵根节点权值最小的树作为新的构造的二叉树的左右子树，新二叉树的根节点的权值为其左右子树的根节点的权值之和。3.从F中删除这两棵树，并把这棵树新的二叉树同样一升序排列加入到集合F中。4.重复二和三两步，知道集合F中只有一棵二叉树为止。简易的理解就是，假如我有A,B,C,D,E五个字符，出现的频率（即权值）分别为5,4,3,2,1，那么我们第一步先取两个最小权值作为左右子树构造一个新树，即取1,2构成新树，其节点为1+2=3，如图所示：虚线为新生成的节点，第二步再把新生成的权值3的节点放到剩下的集合中，所以集合变成｛5,4,3,3｝，再根据第二步，取最小的两个权值构成新树，如图：再一次建立哈夫曼树，如下图：其中各个权值替换对应的字符即为下图：所以各字符对应的编码为：A-11,B-10,C-00,D-011,E-010哈夫曼编码是一种无前缀编码，解码时不会混淆。其主要应用在数据压缩，加密解密等场合。4.C语言编写代码及运行结果/*对文本文件进行huffman编码、解码读取文本文件，并统计文件中字母个数建立huffman树对文件进行huffman编码对文件进行huffman解码*/#includestdio.h#defineMAXBIT10/*定义哈夫曼编码的最大长度*/#defineMAXVALUE10000/*定义最大权值*/#defineMAXLEAF30/*定义哈夫曼树中最多叶子节点个数*/#defineMAXNODEMAXLEAF*2-1/*哈夫曼树最多结点数*/typedefstruct{/*哈夫曼编码信息的结构*/intbit[MAXBIT];intstart;}Hcodetype;typedefstruct{/*哈夫曼树结点的结构*/intweight;intparent;intlchild;intrchild;}Hnodetype;voidhuffmantree(Hnodetypehuffnode[MAXNODE],intn)/*构造哈夫曼树的函数*/{inti,j,m1,m2,x1,x2;for(i=0;i2*n-1;i++)/*存放哈夫曼树结点的数组huffnode[]初始化*/{huffnode[i].weight=0;huffnode[i].parent=-1;huffnode[i].lchild=-1;huffnode[i].rchild=-1;}for(i=0;in;i++)/*输入入N个叶子节点的权值*/{printf(pleaseinput%dcharacter'sweight\n,i);scanf(%d,&huffnode[i].weight);}for(i=0;in-1;i++)/*开始循环构造哈夫曼树*/{m1=m2=MAXVALUE;x1=x2=0;for(j=0;jn+i;j++){if(huffnode[j].weightm1&&huffnode[j].parent==-1){m2=m1;x2=x1;m1=huffnode[j].weight;x1=j;}elseif(huffnode[j].weightm2&&huffnode[j].parent==-1){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;}}voidmain(){Hnodetypehuffnode[MAXNODE];Hcodetypehuffcode[MAXLEAF],cd;inti,j,c,p,n;printf(pleaseinputn\n);scanf(%d,&n);/*输入叶子节点个数*/huffmantree(huffnode,n);/*建立哈夫曼树*/for(i=0;in;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;jn;j++)/*保存求出的每个叶节点的哈夫曼编码和编码的起始位*/huffcode[i].bit[j]=cd.bit[j];huffcode[i].start=cd.start;}for(i=0;in;i++)/*输出每个叶子节点的哈夫曼编码*/{printf(%dcharacteris:,i);for(j=huffcode[i].start+1;jn;j++)printf(%d,huffcode[i].bit[j]);printf(\n);}}