2024年10月霍夫曼树编码压缩方法（Huffman编码）

　　⑴霍夫曼树编码压缩方法（Huffman编码

　　⑵这个是一个简单的，没有文件导入，需要编码的是自己输入的数组，你将它换成文件读取基本就可以实现对文章中的字符进行Huffman编码，这是我自己曾经做的一个程序，是VC.的,没有解码部分，解码部分你反过来推一下算法然后编一下代码就可以了。我还有一个是文件是用matlab作的huffman编码，你要的话给我邮箱，我给你发过去。#include《iostream.h》#include《string.h》#defineNtypedefstruct{intwei;//权值intprt;//父节点intlch;//左子节点intrch;//右子节点inttmp;//中间变量，tmp=还未进行遍历tmp=已近进行过向左遍历tmp=已经进行过左右遍历向上找到节点charcode;}huffmantree;voidinput();voidprint(huffmantree);voidselect(huffmantree*HT,intn,int&i,int&j){intk;i=;while(HT.prt!=){i++;}for(k=i+;k《=n;k++){if((HT.wei))i=k;}j=;while((j==i)||(HT.prt!=)){j++;}for(k=j+;k《=n;k++){if((HT.wei)j=k;}}voidhuffman(intw,huffmantree*HT,intn)//w存放n个字符的权值{intm=*n-;inti,k,j;huffmantree*p=;for(p=HT+,i=;i《=m;i++,p++){HT.prt=;HT.lch=;HT.rch=;}for(p=HT+,i=;i《=n;i++,p++){HT;}for(p=HT+n+,i=n+;i《=m;i++,p++){HT.wei=;}for(k=n+;k《=m;k++){select(HT,k-,i,j);//找最小值和次小值的位置HT.prt=k;//找到ij的父节点付给kHT.rch=j;//父节点的左右指针分别指向i,jHT.wei;}}voidhuffmancoding(huffmantree*HT,intn)//n个叶子结点的huffman编码从根节点开始编码{intBT=*n-;intm=BT;intl,r,p;chars=““;for(inti=;i《=m;i++)//中间变量赋初值{HT.tmp=;}strcpy(HT.code,““);while(){l=HT.lch;r=HT.rch;p=HT.prt;if(p==&&HT.tmp==)break;if(l==||r==){HT.tmp=;//如果是叶子结点则给中间变量赋值向上返回一节结点}if(HT.tmp==)//未进行过遍历，开始向左遍历{HT.tmp=;//已经进行过向左遍历l=HT.lch;strcpy(HT.code);strcat(HT.code,s);BT=l;}elseif(HT.tmp==){HT.tmp=;r=HT.rch;strcpy(HT.code);strcat(HT.code,s);BT=r;}elseif(HT.tmp==){p=HT.prt;BT=p;}}}voidprint(huffmantreeHT,intn)//总共n个叶子节点{inti;cout《《“源码：“《《endl;for(i=;i《=n;i++)cout《《HT.wei《《endl;cout《《“Huffman编码：“《《endl;for(i=;i《=n;i++){cout《《HT.code《《endl;}}voidinput(intw,intn){intt,*p;inti=;cout《《“对应的输入源码出现权值：(以-结束)“《《endl;cin》》t;while(t》=){p=newint;*p=t;w=*p;i++;cin》》t;}}voidmain(){intn,m;cout《《“输入源码个数：“;cin》》n;int*w;w=newint;input(w,n);m=*n-;huffmantree*HT;HT=newhuffmantree;huffman(w,HT,n);huffmancoding(HT,n);print(HT,n);deletew,HT;}

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

　　⑷基于霍夫曼编码的文本压缩实验难吗

　　⑸难，实验任务与目的（简单介绍实验内容，说明实验任务和目的.实验内容根据ascii码文件中各ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈夫曼编码写入文件中，实现文件压缩。对于给定的一组字符，可以根据其权值进行哈夫曼编码，并能输出对应的哈夫曼树和哈夫曼编码；实现哈夫曼解码。能够分析文件，统计文件中出现的字符，再对文件进行编码，实现文件的压缩和解压缩，能够对于文件的压缩，比例进行统计，能够打印文件。分析与设计哈夫曼树的存储结构，实现哈夫曼算法以及编码与译码基本功能，并对任意文本文件利用哈夫曼编码进行压缩得到压缩文件，然后进行解压缩得到解压文件。首先运行的时候，用户主界面上有菜单提示该如何使用软件，根据菜单提示选择所要执行的项，依次进行，因为各个环节之间有先后顺序。第一步为输入压缩软件的名称，由键盘输入文件路径和文件名称，读入字符数组中，打开该文件，按照提示进行压缩。若打不开，则继续输入。..读文件并计算字符频率文件将信息存放在字符数组中；计算每个字符出现的次数，申请一个结构体数组空间，用读取的字符减去字符结束符作为下标记录字符的频率。..根据字符的频率，利用Huffman编码思想创建Huffman树将所记录的字符的频率作为权值来创建Huffman树，依次选择权值最小的两个字符作为左右孩子，其和作为父结点的权值，依次进行下去，直到所有的字符结点都成为叶子结点。..由创建的Huffman树来决定字符对应的编码，进行文件的压缩根据创建的Huffman树来确定个字符的编码，左孩子为，右孩子为。读取文件，依次将每个字符用他们的编码表示，即完成一次编码。..解码压缩即根据Huffman树进行译码读取编码文件，依据创建的Huffman树，定义一个指针指向根结点。从根结点开始，每读一个字符，指针变化一次（当读取的字符是‘’时，指针指向当前所指结点的右孩子，当读取的字符是‘’时，指针指向当前所指结点的左孩子，直至该指针所指结点为叶子结点时结束（即当结点的左右孩子均为空时。将当前叶子结点所代表的字符值输出到译码文件中，依次读取编码文件中的字符，按照上述方法依次进行下去直至文件..Huffman算法（根据给定的n个权值{}构成n棵二叉树的集合F={}，其中每棵二叉树中只有一个带权为的根结点，其左右子树为空。（在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。（在F中删除这两棵树，同时将新达到的二叉树加入F中。（重复（和（，直到F只含一棵树为止。..Huffman编码假设每种字符在电文中出现的次数为，其编码长度为，电文中只有n种字符，则电文总长为。对应到二叉树上，若置为叶子结点的权，恰为从根到叶子结点的路径长度，则恰为二叉树上的带权路径长度。由此可见，设计电文总长最短的二进制前缀编码即为以n种字符出现的频率做权，设计一棵Huffman树的问题题，由此得到的二进制前缀编码即为Huffman编码。第页

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

　　⑺哈夫曼编码的编码方法怎样

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

　　⑼什么赫夫曼编码,我想知道下它的原理

　　⑽是一种利用二叉树实现的编码原理霍夫曼（Huffman编码原理霍夫曼（Huffman编码是年为文本文件而建立，是一种统计编码。属于无损压缩编码。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。步骤进行：l将信号源的符号按照出现概率递减的顺序排列。将两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率。重复进行步骤和直到概率相加的结果等于为止。在合并运算时，概率大的符号用编码表示，概率小的符号用编码表示。记录下概率为处到当前信号源符号之间的，l序列，从而得到每个符号的编码。例：设信号源为s＝｛s,s,s,s,s｝对应的概率为p＝｛.，.，.,.，.｝。根据字符出现的概率来构造平均长度最短的异字头码字。霍未曼编码通常采用两次扫描的办法，第一次扫描得到统计结果，第二次扫描进行编码。霍夫曼编码具有一些明显的特点：)编出来的码都是异字头码，保证了码的唯一可译性。)由于编码长度可变。因此译码时间较长，使得霍夫曼编码的压缩与还原相当费时。)编码长度不统一，硬件实现有难度。)对不同信号源的编码效率不同，当信号源的符号概率为的负幂次方时，达到％的编码效率；若信号源符号的概率相等，则编码效率最低。)由于““与““的指定是任意的，故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能、都差不多，个人感觉c++更好学

　　⑾二叉树在计算机科学与技术中的应用有哪些

　　⑿霍夫曼编码：这是一种数据压缩方法，利用一棵霍夫曼树（本质为二叉树来压缩一组数据。优先级队列：它使用一棵二叉树来记录集合中元素的优先级，并将其排序，为解决问题提供更好的方案。事件调度：主要使用二叉搜索树，这能够使得查找信息更加高效。数据库系统：主要使用B树，这能够使插入和删除操作更加高效。用户界面：在图形用户界面中，窗口按树形结构组织，如windows系统。文件系统：文件按树形结构组织，如windows系统。人工智能：比如棋类这种逻辑类的游戏，可以把步骤生成决策树。以上如果需要详细了解，可直接百度相关名词。

　　⒀huffman树怎么样保存文件编码，把已经文件的huffman编码存进一个txt文件，怎么压缩储存

　　⒁新建一个文件荚然后把你的编码放进去再用解压器解压成TXT文件就可以拉

　　⒂利用哈夫曼编码进行压缩压缩率一般达到多少

　　⒃哈夫曼编码进行压缩的压缩率是根据平均码长来计算的，压缩率比较低。

　　⒄例如：用三位二进行数进行的等长编码平均长度为，而根据哈夫曼树编码的平均码长为：

　　⒅*.+*.+*.+*.+*.+*.+*.+*.=.

　　⒆其平均码长是等长码的%，所以平均压缩率为%。

　　⒇哈夫曼编码，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。

　　⒈Huffman于年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码。

　　⒉压缩率，描述压缩文件的效果名，是文件压缩后的大小与压缩前的大小之比，例如：把m的文件压缩后是m，压缩率为/*%=%，压缩率一般是越小越好，但是压得越小，解压时间越长。

　　⒊哈夫曼编码的具体方法：先按出现的概率大小排队，把两个最小的概率相加，作为新的概率和剩余的概率重新排队，再把最小的两个概率相加，再重新排队，直到最后变成。

　　⒋每次相加时都将“”和“”赋与相加的两个概率，读出时由该符号开始一直走到最后的“”，将路线上所遇到的“”和“”按最低位到最高位的顺序排好，就是该符号的哈夫曼编码。

　　⒌霍夫曼算法的步骤是这样的：·从各个节点中找出最小的两个节点，给它们建一个父节点，值为这两个节点之和。·然后从节点序列中去除这两个节点，加入它们的父节点到序列中。重复上面两个步骤，直到节点序列中只剩下唯一一个节点。这时一棵最优二叉树就已经建成了，它的根就是剩下的这个节点。仍以上面的例子来看霍夫曼树的建立过程。最初的节点序列是这样的：a()b()c()d()e()把最小的c和e结合起来|()a()b()d()+------+------+||ce不断重复，最终得到的树是这样的：根|+----------+||+--------+||+-----------+||+----+||这时各个字符的编码长度和前面我们说过的方法得到的编码长度是相同的，因而文件的总长度也是相同的：*+*+*+*+*=考察霍夫曼树的建立过程中的每一步的节点序列的变化：下面我们用逆推法来证明对于各种不同的节点序列，用霍夫曼算法建立起来的树总是一棵最优二叉树：对霍夫曼树的建立过程运用逆推法：当这个过程中的节点序列只有两个节点时（比如前例中的和，肯定是一棵最优二叉树，一个编码为，另一个编码为，无法再进一步优化。然后往前步进，节点序列中不断地减少一个节点，增加两个节点，在步进过程中将始终保持是一棵最优二叉树，这是因为：.按照霍夫曼树的建立过程，新增的两个节点是当前节点序列中最小的两个，其他的任何两个节点的父节点都大于（或等于这两个节点的父节点，只要前一步是最优二叉树，其他的任何两个节点的父节点就一定都处在它们的父节点的上层或同层，所以这两个节点一定处在当前二叉树的最低一层。.这两个新增的节点是最小的，所以无法和其他上层节点对换。符合我们前面说的最优二叉树的第一个条件。.只要前一步是最优二叉树，由于这两个新增的节点是最小的，即使同层有其他节点，也无法和同层其他节点重新结合，产生比它们的父节点更小的上层节点来和同层的其他节点对换。它们的父节点小于其他节点的父节点，它们又小于其他所有节点，只要前一步符合最优二叉树的第二个条件，到这一步仍将符合。这样一步步逆推下去，在这个过程中霍夫曼树每一步都始终保持着是一棵最优二叉树。由于每一步都从节点序列中删除两个节点，新增一个节点，霍夫曼树的建立过程共需(原始节点数-)步，所以霍夫曼算法不失为一种精巧的编码式压缩算法。附：对于huffman树，《计算机程序设计艺术》中有完全不同的证明，大意是这样的：．二叉编码树的内部节点（非叶子节点数等于外部节点（叶子节点数减。．二叉编码树的外部节点的加权路径长度（值乘以路径长度之和，等于所有内部节点值之和。（这两条都可以通过对节点数运用数学归纳法来证明，留给大家做练习。．对huffman树的建立过程运用逆推，当只有一个内部节点时，肯定是一棵最优二叉树。．往前步进，新增两个最小的外部节点，它们结合在一起产生一个新的内部节点，当且仅当原先的内部节点集合是极小化的，加入这个新的内部节点后仍是极小化的。（因为最小的两个节点结合在一起，并处于最低层，相对于它们分别和其他同层或上层节点结合在一起，至少不会增加加权路径长度。．随着内部节点数逐个增加，内部节点集合总维持极小化。．实现部分如果世界上从没有一个压缩程序，我们看了前面的压缩原理，将有信心一定能作出一个可以压缩大多数格式、内容的数据的程序，当我们着手要做这样一个程序的时候，会发现有很多的难题需要我们去一个个解决，下面将逐个描述这些难题，并详细分析zip算法是如何解决这些难题的，其中很多问题带有普遍意义，比如查找匹配，比如数组排序等等，这些都是说不尽的话题，让我们深入其中，做一番思考。