霍夫曼编码压缩率（霍夫曼编码的编码效率怎么求）

本文目录

• 霍夫曼编码的编码效率怎么求
• 利用huffman编码对文件进行压缩，不同文件类型压缩率有差别的原因
• Python算法之哈夫曼编码
• 为什么说哈夫曼编码是压缩率最高的编码
• 压缩算法进行字符串压缩
• 哈夫曼编码的平均码长是多少
• 哈夫曼树霍夫曼树平均码率是什么意思
• 哈夫曼编码/译码器
• 霍夫曼编码压缩率n1是什么
• 哈夫曼编码码长怎么算

霍夫曼编码的编码效率怎么求

求效率首先要求得信号的熵，也就是最小的编码长度，比如是2.3，然后再求霍夫曼码的平均编码长度（各个概率和码位相乘再求和）比如是2.7，那么效率就是0.85。

霍夫曼编码的编码效率，我想可以用压缩率来表示吧。随机选取一段字符，计算其编码长度为 n。再对其用霍夫曼编码，得到长度为 m。于是 m/n 就是压缩率。

霍夫曼编码是变长编码，思路：对概率大的编的码字短，概率小的编的码字长，这样一来所编的总码长就小，这样编码效率就高。

扩展资料：

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

利用huffman编码对文件进行压缩，不同文件类型压缩率有差别的原因

怎么没人回答呢 我来回答吧 我想从压缩文件的原理能得到你这个问题的答案（有点长，请耐心看，绝对长知识）： 压缩文件的运行原理 　　如果您从互联网上下载了许多程序和文件，可能会遇到很多ZIP文件。这种压缩机制是一种很方便的发明，尤其是对网络用户，因为它可以减小文件中的比特和字节总数，使文件能够通过较慢的互联网连接实现更快传输，此外还可以减少文件的磁盘占用空间。在下载了文件后，计算机可使用WinZip或Stuffit这样的程序来展开文件，将其复原到原始大小。如果一切正常，展开的文件与压缩前的原始文件将完全相同。　　乍一听好像很神秘：您是怎样减少比特和字节的数量并将它们原封不动地还原回去的呢？等一切水落石出之后，您会发现这个过程背后的基本理念其实非常简单明了。在本文中，我们将讨论这种通过简单压缩来明显减小文件的方法。　　大多数计算机文件类型都包含相当多的冗余内容——它们会反复列出一些相同的信息。文件压缩程序就是要消除这种冗余现象。与反复列出某一块信息不同，文件压缩程序只列出该信息一次，然后当它在原始程序中出现时再重新引用它。　　以我们熟悉的信息类型——单词——为例子。　　肯尼迪（John F. Kennedy）在1961年的就职演说中曾说过下面这段著名的话：　　Ask not what your country can do for you——ask what you can do for your country.（不要问国家能为你做些什么，而应该问自己能为国家做些什么。）　　这段话有17个单词，包含61个字母、16个空格、1个破折号和1个句点。如果每个字母、空格或标点都占用1个内存单元，那么文件的总大小为79个单元。为了减小文件的大小，我们需要找出冗余的部分。　　我们立刻发现：　　如果忽略大小写字母间的区别，这个句子几乎有一半是冗余的。九个单词（ask、not、what、your、country、can、do、for、you）几乎提供了组成整句话所需的所有东西。为了构造出另一半句子，我们只需要拿出前半段句子中的单词，然后加上空格和标点就行了。　　大多数压缩程序使用基于自适应字典的LZ算法来缩小文件。“LZ”指的是此算法的发明者Lempel和Ziv，“字典”指的是对数据块进行归类的方法。　　排列字典的机制有很多种，它也可以像编号列表那样简单。在我们检查肯尼迪这句著名讲话时，可以挑出重复的单词，并将它们放到编号索引中。然后，我们直接写入编号而不是写入整个单词。　　因此，如果我们的字典是：　　ask 　　what 　　your 　　country 　　can 　　do 　　for 　　you 　　我们的句子现在就应该是这样的：　　1 not 2 3 4 5 6 7 8-- 1 2 8 5 6 7 3 4 　　如果您了解这种机制，那么只需使用该字典和编号模式即可轻松重新构造出原始句子。这就是在展开某个下载文件时，计算机中的解压缩程序所做的工作。你可能还遇到过能够自行解压缩的压缩文件。若要创建这种文件，编程人员需要在被压缩的文件中设置一个简单的解压缩程序。在下载完毕后，它可以自动重新构造出原始文件。　　但是使用这种机制究竟能够节省多少空间呢？“1 not 2 3 4 5 6 7 8——1 2 8 5 6 7 3 4”当然短于“Ask not what your country can do for you-- ask what you can do for your country.”，但应注意的是，我们需要随文件一起保存这个字典。　　在实际压缩方案中，计算出各种文件需求是一个相当复杂的过程。让我们回过头考虑一下上面的例子。每个字符和空格都占用1个内存单元，整个原句要占用79个单元。压缩后的句子（包括空格）占用了37个单元，而字典（单词和编号）也占用了37个单元。也就是说，文件的大小为74个单元，因此我们并没有把文件大小减少很多。　　但这只是一个句子的情况！可以想象的是，如果用该压缩程序处理完肯尼迪讲话的其余部分，我们会发现这些单词以及其他单词重复了更多次。而且，正如下一节所言，为了得到尽可能高的组织效率，可以对字典进行重写。　　在上一个的例子中，我们挑出了所有重复的单词并将它们放在一个字典中。对于我们来说，这是最显而易见的字典编写方法。但是压缩程序却不这样认为：它对单词没有概念——它只会寻找各个模式。为了尽可能减小文件的大小，它会仔细挑选出最优模式。　　如果从这个角度处理该句子，我们最终会得到一个完全不同的字典。　　如果压缩程序扫描肯尼迪的这句话，它遇到的第一个冗余部分只有几个字母长。在ask not what your中，出现了一个重复的模式，即字母t后面跟一个空格——在not和what中。如果压缩程序将此模式写入字典，则每次出现“t”后面跟一个空格的情况时，它会写入一个“1”。但是在这个短句中，此模式的出现次数不够多，不足以将其保留为字典中的一个条目，因此程序最终会覆盖它。　　程序接下来注意到的内容是ou，在your和country中都出现了它。如果这是一篇较长的文档，将此模式写入字典会节省大量空间——在英语中ou是一个十分常见的字母组合。但是在压缩程序看完整个句子后，它立即发现了一个更好的字典条目选择：不仅ou发生了重复，而且your和country整个单词都发生了重复，并且它们实际上是作为一个短语your country一起发生重复的。在本例中，程序会用your country条目覆盖掉字典中的ou条目。　　短语can do for也发生了重复，一次后面跟着your，另一次跟着you，因此我们又发现can do for you也是一种重复模式。这样，我们可以用一个数字来代替15个字符（包含空格），而your country只允许我们用一个数字代替13个字符（包含空格），所以程序会用r country条目覆盖your country条目，然后再写入一个单独的can do for you条目。程序通过这种方式继续工作，挑出所有重复的信息，然后计算应该将哪一种模式写入字典。基于自适应字典的LZ算法中的“自适应”部分指的就是这种重写字典的能力。程序执行此工作的过程实际上非常复杂。　　无论使用什么方法，这种深入搜索机制都能比仅仅挑出单词这种方法更有效率地对文件进行压缩。如果使用我们上面提取出的模式，然后用“__”代替空格，最终将得到下面这个更大的字典：　　ask__ 　　what__­ 　　you 　　r__country 　　__can__do__for__you 　　而句子则较短：　　“1not__2345__--__12354” 　　句子现在占用18个内存单元，字典占用41个单元。所以，我们将文件总大小从79个单元压缩到了59个单元！这仅仅是压缩句子的一种方法，而且不一定是最高效的方法。（看看您能找到更好的方法吗！）　　那么这种机制到底有多好呢？文件压缩率取决于多种因素，包括文件类型、文件大小和压缩方案。　　在世界上的大多数语言中，某些字母和单词经常以相同的模式一起出现。正是由于这种高冗余性，而导致文本文件的压缩率会很高。通常大小合适的文本文件的压缩率可以达到50%或更高。大多数编程语言的冗余度也很高，因为它们的命令相对较少，并且命令经常采用一种设定的模式。对于包含大量不重复信息的文件（例如图像或MP3文件），则不能使用这种机制来获得很高的压缩率，因为它们不包含重复多次的模式。　　如果文件有大量重复模式，那么压缩率通常会随着文件大小的增加而增加。从我们的例子中就可以看出这一点——如果我们摘录的肯尼迪讲话再长一些，您会发现又多次出现了我们字典中的模式，因此能够通过每个字典条目节省更多的文件空间。此外，对于更大的文件，还可能出现具有更大普遍性的模式，从而能够创建出效率更高的字典。　　此外，文件压缩效率还取决于压缩程序使用的具体算法。有些程序能够在某些类型的文件中更好地寻找到模式，因此能更有效地压缩这些类型的文件。其他一些压缩程序在字典中又使用了字典，这使它们在压缩大文件时表现很好，但是在压缩较小的文件时效率不高。尽管这一类的所有压缩程序都基于同一个基本理念，但是它们的执行方式却各不相同。程序开发人员始终在尝试建立更好的压缩机制。　　有损压缩和无损压缩　　我们在上文中讨论的压缩类型称为无损压缩，因为您重新创建的文件与原始文件完全相同。所有无损压缩都基于这样一种理念：将文件变为“较小”的形式以利于传输或存储，并在另一方收到它后复原以便重新使用它。　　有损压缩则与此大不相同。这些程序直接去除“不必要”的信息，对文件进行剪裁以使它变得更小。这种类型的压缩大量应用于减小位图图像的文件大小，因为位图图像的体积通常非常庞大。为了了解有损压缩的工作原理，让我们看看你的计算机如何对一张扫描的照片进行压缩。　　对于此类文件，无损压缩程序的压缩率通常不高。尽管图片的大部分看起来都是相同的——例如，整个天空都是蓝色的——但是大部分像素之间都存在微小的差异。为了使图片变得更小同时不降低其分辨率，您必须更改某些像素的颜色值。如果图片中包含大量的蓝色天空，程序会挑选一种能够用于所有像素的蓝色。然后，程序重写该文件，所有天空像素的值都使用此信息。如果压缩方案选择得当，您不会注意到任何变化，但是文件大小会显著减小。　　当然，对于有损压缩，在文件压缩后您无法将其复原成原始文件的样子。您必须接受压缩程序对原始文件的重新解释。因此，如果需要完全重现原来的内容（例如软件应用程序、数据库和总统就职演说），则不应该使用这种压缩形式。

Python算法之哈夫曼编码

问题: 哈夫曼编码,英文名称 Huffman Coding，有时也翻译为霍夫曼编码，在1952年提出的，是最好的编码方式。哈夫曼编码在电子通讯方面有着重要的应用，同时也广泛应用于数据压缩，其压缩率通常在20% 90%之间 赫夫曼码是可变字长编码(VLC)的一种。哈夫曼树是最优二叉树， 带权路径长度最小的二叉树。

原理:

假设有几个数字40,10,20,16,14。

首先将这五个数字按照从小到大的顺序排列：10, 14，16，20, 40。

构建哈夫曼树：

1.首先选取10,14

2.重新排序：16,20,24,40

3.重新排序24,36,40,60

4.按照二叉树左0右1，构建哈夫曼树

所以最终得到数字10的编码为100，数字14的编码为101，数字16的编码为110，数字20的编码为111，数字40的编码为0。

代码：

运行结果:

为什么说哈夫曼编码是压缩率最高的编码

假设用于通信的电文由字符集{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%。

因为定长编码已经用相同的位数这个条件保证了任一个字符的编码都不会成为其它编码的前缀,所以这种情况只会出现在变长编码当中，要想避免这种情况，

就必须用一个条件来制约定长编码，这个条件就是要想成为压缩编码，变长编码就必须是前缀编码，所谓的前缀编码就是任何一个字符的编码都不能是另一个字符编码的前缀。

扩展资料：

实际应用中，除采用定时清洗以消除误差扩散和采用缓冲存储以解决速率匹配以外，主要问题是解决小符号集合的统计匹配，

例如黑（1）、白（0）传真信源的统计匹配，采用0和1不同长度游程组成扩大的符号集合信源。游程，指相同码元的长度（如二进码中连续的一串0或一串1的长度或个数）。按照CCITT标准，需要统计2×1728种游程（长度），

这样，实现时的存储量太大。事实上长游程的概率很小，故CCITT还规定：若l表示游程长度，则l=64q+r。其中q称主码，r为基码。编码时，不小于64的游程长度由主码和基码组成。而当l为64的整数倍时，只用主码的代码，已不存在基码的代码。

压缩算法进行字符串压缩

Deflater 是同时使用了LZ77算法与哈夫曼编码的一个无损数据压缩算法。 我们可以使用 java 提供的 Deflater 和 Inflater 类对 json 进行压缩和解压缩，下面是工具类 压缩前的字节长度为：1825 压缩后的字节长度为：284 压缩率为63.73%，压缩后体积为原来的36.27% 压缩前的字节长度为：1825 压缩后的字节长度为：307 压缩率为62.04%，压缩后体积为原来的37.95%，也是不错的！

哈夫曼编码的平均码长是多少

假设用于通信的电文由字符集{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%。

参考资料

哈夫曼编码码长怎么算？.新浪博客

哈夫曼树霍夫曼树平均码率是什么意思

指将原始数据用哈夫曼编码压缩后，每个字符平均对应的编码长度。哈夫曼树或者霍夫曼树是一种被用于数据压缩的树形结构，其中字符的出现频率越高，其在哈夫曼树中对应的编码越短，从而使得整个数据压缩后的码率更低。哈夫曼编码是无损压缩算法，所以编码后的数据可以完美还原为原始数据，而不会有任何丢失和失真。同时，哈夫曼编码也是一种熵编码，具有最小熵的特性，即可以最大程度地减小数据的冗余度。哈夫曼树平均码率越低，说明数据压缩的效果越好，压缩后的数据占用的空间更小，并且可以在不损失数据的情况下实现数据压缩。

哈夫曼编码/译码器

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

霍夫曼编码压缩率n1是什么

压缩前的数据量。在霍夫曼编码中，n1和n2代表两个表示相同信息的数据集合中所携载信息单元的数量，n1表示压缩前的数据量，n2表示压缩后的数据量。霍夫曼编码，又译为哈夫曼编码、赫夫曼编码，是一种用于无损数据压缩的熵编码算法。

哈夫曼编码码长怎么算

设某信源产生有五种符号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。