霍夫曼编码的原理（什么是哈夫曼编码）

本文目录

• 什么是哈夫曼编码
• 什么赫夫曼编码,我想知道下它的原理
• 根据哈夫曼编码原理，编写一个在用户输入结点权值的基础上建立的哈夫曼编码的程序
• 请问一下截取霍夫曼编码的原理
• 什么是变字长最佳编码原理
• 哈夫曼编码的原理
• 哈夫曼编码原理
• 霍夫曼编码
• 哈夫曼编码的原理是什么

什么是哈夫曼编码

哈夫曼编码是一种编码方式，它是一种线性的前缀编码方式，它利用了信源符号的统计特性，将出现概率高的符号用短码编码，出现概率低的符号用长码编码。这样可以使得编码后的平均码长最短，可以最大化压缩效果。 哈夫曼编码是1952年由David A. Huffman提出的，通常使用哈夫曼树来实现。哈夫曼树是一种带权赋值树形结构，它满足哈夫曼编码的要求，并且能够在编码过程中计算出最优编码方案。

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

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

根据哈夫曼编码原理，编写一个在用户输入结点权值的基础上建立的哈夫曼编码的程序

#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).weight=0; //初始化 (*character_table).coded_string=NULL; } ch=fgetc(fp); while(!feof(fp))//诺到文件末尾，函数值为真 { //m=ch; if(ch《128 && ch》=0) (*character_table).weight++;//获得各个字母在文件中出现的次数 ch=fgetc(fp); } for(i=0, n=0; i《128; i++) if((*character_table).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).weight) {//将权值放入*w数组中 *(*w)=(*character_table).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).parent) { if(tmp1 == -1) { tmp1=n; continue; } if(tmp2 == -2) { tmp2=n; if((*HT).weight) { j=tmp1; tmp1=tmp2; tmp2=j; } continue; } if((*HT).weight) //scan and change if((*HT).weight) tmp1=n; else tmp2=n; } } *Min1=tmp1; *Min2=tmp2; //tmp.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).weight=*w; (*HTp).parent=0; (*HTp).lchild=0; (*HTp).rchild=0; } for(; i《m; i++) { (*HTp).weight=0; (*HTp).parent=0; (*HTp).lchild=0; (*HTp).rchild=0; } M1=&Min1 M2=&Min2 for(i=n; i《m; i++) { Select(HT, i, M1, M2); (*HTp).parent=i; (*HTp).parent=i; (*HTp).lchild=Min1; //左孩子要小一些 (*HTp).rchild=Min2; (*HTp).weight; } //coded the weight below (*HC)=(HuffmanCode)malloc(n*sizeof(char *)); cd=(char *)malloc(n*sizeof(char)); cd=’\0’; for(i=0; i《n; i++) { start=n-1; for(p1=i, p2=(*HTp).parent) { if( (*HTp).lchild ==p1) //编码, 左孩子为0, 右孩子为1 cd=’0’; else cd=’1’; } (*HC)=(char *)malloc((n-start)*sizeof(char)); strcpy((*HC)); } //over return OK;}void Weinumber_to_stringnumber(char * *stringnumber, long *w, int leaves) {//将权值以字符数组形式存放在上米的数组中 char tmp; long i, j, k; int start; for(i=0; i《leaves; i++) { start=29; tmp=’\0’; for(k=w, j=k%10; k!=0; k=k/10, j=k%10) tmp=j+’0’; stringnumber=(char *)malloc((29-start)*sizeof(char)); strcpy(stringnumber); }}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, fp1); fputc(’\t’, fp1); fputs(stringnumber, fp1); fputc(’\t’, fp1); fputc(’\’’, fp1); fputs((*HC), fp1); fputc(’\’’, fp1); fputc(’\n’, 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.weight) { character_table.coded_string=*(*HC); (*HC)++; } ch=fgetc(fp); while(!feof(fp)) { if( (ch》=0 && ch《128) && (character_table.weight) )//it is very importan to add (ch》=0 && ch《128) fputs(character_table.coded_string,fp2); ch=fgetc(fp); } fclose(fp2); }void fileopen1() //通过指针fp传递信息{ char filename; do{ printf("\n\n\t请输入要编码的文件:"); scanf("%s", filename); if ((fp=fopen(filename,"r"))==NULL) printf("\n\t不能打开此文件! 请重新输入!\n"); }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);}

请问一下截取霍夫曼编码的原理

• 四年过去了，不知道楼主找到没

• 我也不太清楚，但是我找到了一个网址，希望对你有帮助http://wenku.baidu.com/view/3b9fe265f5335a8102d220b1.html

什么是变字长最佳编码原理

　　哈夫曼编码(Huffman Coding)，又称霍夫曼编码　　最佳编码定理：在变字长码中，对于出现概率大的信息符号编以短字长的码;对于出现概率小的信息符号编以长字长的码，如果码字长度严格按照符号概率的大小的相反顺序排列，则平均码字长度一定小于按任何其他符号顺序排列方式得到的码字长度。　　Huffman编码步骤：　　概率统计，得到n个不同概率的信号;　　将n个信源信息符号的n个概率，按概率大小排序;　　将最后两个小概率相加，概率个数减为n-1;　　将n-1个概率重新排序;　　再将最后两个小概率相加，概率个数减为n-2;　　如此反复n-2次，得到只剩两个概率序列;　　以二进制码元(0，1)赋值，构成Huffman码字。

哈夫曼编码的原理

霍夫曼编码的基本思想：输入一个待编码的串，首先统计串中各字符出现的次数，称之为频次，假设统计频次的数组为count.parent的左节点，则该节点的路径为0，如果是右节点，则该节点的路径为1。当向上找到一个节点，他的父节点标号就是他本身，就停止（说明该节点已经是根节点）。还有一个需要注意的地方：在查找当前权值最小的两个节点时，那些父节点不是他本身的节点不能考虑进去，因为这些节点已经被处理过了

哈夫曼编码原理

赫夫曼码的码字（各符号的代码）是异前置码字，即任一码字不会是另一码字的前面部分，这使各码字可以连在一起传送，中间不需另加隔离符号，只要传送时不出错，收端仍可分离各个码字，不致混淆。

哈夫曼编码，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(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，二者已经是很接近了。

霍夫曼编码

　　霍夫曼编码是一种从下到上的编码方法，即从叶子逐步往上生成编码树，编码算法实际上是一个构造霍夫曼树的过程。 　　根据资料出现频率的多寡来建造的树，霍夫曼树的树叶节点用以储存资料元素，若该元素出现的频率越高，则由该元素至树根所经过的节点数越少。 　　霍夫曼树是最小二叉树，编码效率比香农范诺高霍夫曼编码对错误敏感，错一位，可能导致后面的解码都是错误的，而且计算机也无法纠错，我们称为错误传播霍夫曼编码是变长编码，整个编码结果是一个整体，无法随意解压缩其中的某一个部分。

哈夫曼编码的原理是什么

设某信源产生有五种符号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 C***truction of Minimum-Redundancy Codes）一文，它一般就叫做Huffman编码。