哈夫曼编码的原理?
这个是我同学的哈夫曼编码程序
另外还有解码的程序,要的话再商量
#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 128
typedef 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)[i].weight=0; //初始化
(*character_table)[i].coded_string=NULL;
}
ch=fgetc(fp);
while(!feof(fp))//诺到文件末尾,函数值为真
{
//m=ch;
if(ch<128 && ch>=0)
(*character_table)[ch].weight++;//获得各个字母在文件中出现的次数
ch=fgetc(fp);
}
for(i=0, n=0; i<128; i++)
if((*character_table)[i].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)[i].weight)
{//将权值放入*w数组中
*(*w)=(*character_table)[i].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)[n].parent)
{
if(tmp1 == -1)
{
tmp1=n;
continue;
}
if(tmp2 == -2)
{
tmp2=n;
if((*HT)[tmp1].weight > (*HT)[tmp2].weight)
{
j=tmp1;
tmp1=tmp2;
tmp2=j;
}
continue;
}
if((*HT)[n].weight < (*HT)[tmp2].weight) //scan and change
if((*HT)[n].weight < (*HT)[tmp1].weight)
tmp1=n;
else
tmp2=n;
}
}
*Min1=tmp1;
*Min2=tmp2; //tmp[Min2].weight >= tmp[Min1].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)[i].weight=*w;
(*HTp)[i].parent=0;
(*HTp)[i].lchild=0;
(*HTp)[i].rchild=0;
}
for(; i<m; i++)
{
(*HTp)[i].weight=0;
(*HTp)[i].parent=0;
(*HTp)[i].lchild=0;
(*HTp)[i].rchild=0;
}
M1=&Min1;
M2=&Min2;
for(i=n; i<m; i++)
{
Select(HT, i, M1, M2);
(*HTp)[Min1].parent=i;
(*HTp)[Min2].parent=i;
(*HTp)[i].lchild=Min1; //左孩子要小一些
(*HTp)[i].rchild=Min2;
(*HTp)[i].weight=(*HTp)[Min1].weight + (*HTp)[Min2].weight;
}
//coded the weight below
(*HC)=(HuffmanCode)malloc(n*sizeof(char *));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=0; i<n; i++)
{
start=n-1;
for(p1=i, p2=(*HTp)[p1].parent; p2!=0; p1=p2, p2=(*HTp)[p1].parent)
{
if( (*HTp)[p2].lchild ==p1) //编码, 左孩子为0, 右孩子为1
cd[--start]='0';
else
cd[--start]='1';
}
(*HC)[i]=(char *)malloc((n-start)*sizeof(char));
strcpy((*HC)[i],&cd[start]);
} //over
return OK;
}
void Weinumber_to_stringnumber(char * *stringnumber, long *w, int leaves)
{//将权值以字符数组形式存放在上米的数组中
char tmp[30];
long i, j, k;
int start;
for(i=0; i<leaves; i++)
{
start=29;
tmp[start--]='\0';
for(k=w[i], j=k%10; k!=0; k=k/10, j=k%10)
tmp[start--]=j+'0';
stringnumber[i]=(char *)malloc((29-start)*sizeof(char));
strcpy(stringnumber[i], &tmp[start+1]);
}
}
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[i], fp1);
fputc('\t', fp1);
fputs(stringnumber[i], fp1);
fputc('\t', fp1);
fputc('\'', fp1);
fputs((*HC)[i], 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[i].weight)
{
character_table[i].coded_string=*(*HC);
(*HC)++;
}
ch=fgetc(fp);
while(!feof(fp))
{
if( (ch>=0 && ch<128) && (character_table[ch].weight) )//it is very importan to add (ch>=0 && ch<128)
fputs(character_table[ch].coded_string,fp2);
ch=fgetc(fp);
}
fclose(fp2);
}
void fileopen1() //通过指针fp传递信息
{
char filename[100];
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);
}
最简单的理解方式是:把最常用的词用最短的代码表示,可以理解为缩写
比如NBA就代表National Basketball Association这多字母了,这样如果把文章中的所有National Basketball Association都改成NBA是不是能省很多字,解说员都是这么做的,呵呵
最小带权生成树
霍夫曼编码的原理是什么?
霍夫曼编码是变长编码,思路:对概率大的编的码字短,概率小的编的码字长,这样一来所编的总码长就小,这样编码效率就高。上面那样求是不对的,除非你这6个码字是等概率的,各占1\/6。应该用对应的概率*其对应得码长,再求和。
哈夫曼编码原理
赫夫曼码的码字(各符号的代码)是异前置码字,即任一码字不会是另一码字的前面部分,这使各码字可以连在一起传送,中间不需另加隔离符号,只要传送时不出错,收端仍可分离各个码字,不致混淆。哈夫曼编码,又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提...
哈夫曼编码的基本原理是什么?
哈夫曼编码是一种可变长度编码,它能够将字符集中出现频率较高的字符用较短的编码表示,从而实现对数据的压缩。相对于固定长度编码(如 ASCII 编码),哈夫曼编码能够更好地适应数据的特点,从而实现更高效的压缩。
霍夫曼解码原理是什么
霍夫曼编码(Huffmancoding)是一种编码方式,它能够有效地压缩符号序列。它基于一种叫做霍夫曼树的数据结构。霍夫曼树是一种二叉树,每个叶子结点代表一个符号,它的权值是该符号在符号序列中出现的概率。每个非叶子结点的权值是它的左右儿子的权值之和。霍夫曼树的构建方式是:对所有符号的权值进行排序,每...
霍夫曼编码
霍夫曼编码是一种基于权重的编码方法。在数据通信和数据处理中,针对数据的不同频率进行不同长度的编码,对于出现频率较高的数据赋予较短的编码,而对于出现频率较低的数据赋予较长的编码。这样可以实现数据的压缩,同时保证解压缩后的数据完整性和原始性。二、霍夫曼编码的工作原理 霍夫曼编码基于概率统计...
哈夫曼编码的原理
这里图(a)的编码比(b)好。赫夫曼码的码字(各符号的代码是异前置码字,即任一码字不会是另一码宇的前面部分,这使各码字可以连在一起传送,中间不需另加隔离符号,只要传送时不出错,收端仍可分离各个码字,不致混淆。实际应用中,除采用定时清洗以消除误差扩散和采用缓冲存储以解决速率匹配以外...
哈夫曼编码的原理是什么?
哈夫曼编码:哈夫曼静态编码:它对需要编码的数据进行两遍扫描:第一遍统计原数据中各字符出现的频率,利用得到的频率值创建哈夫曼树,并必须把树的信息保存起来,即把字符0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来,(用4Bytes的长度存储频率值,频率值的表示范围为0--2^32-1,这已...
哈夫曼编码的原理是什么?
两者虽平均码长相等,但同一符号可以有不同的码长,即编码方法并不唯一,其原因是两支路概率合并后重新排队时,可能出现几个支路概率相等,造成排队方法不唯一。一般,若将新合并后的支路排到等概率的最上支路,将有利于缩短码长方差,且编出的码更接近于等长码。这里图(a)的编码比(b)好。
霍夫曼编码详解
总结来说,霍夫曼编码是信源编码领域的瑰宝,它巧妙地平衡了复杂性和效率,为信息传输中的高效编码提供了可能。通过理解和应用霍夫曼编码,我们可以更深入地探索和优化通信系统的性能。进一步了解这些编码技术的详细原理和应用,可参考经典的通信学教材如Proakis的《Communication Systems Engineering》或周炯槃、...
什么是霍夫曼编码?
详情请查看视频回答
谭知协美: 霍夫曼(Huffman)编码属于码词长度可变的编码类,是霍夫曼在1952年提出的一种编码方法,即从下到上的编码方法.同其他码词长度可变的编码一样,可区别的不同码词的生成是基于不同符号出现的不同概率.生成霍夫曼编码算法基于一种称...
宿松县17390531319: Huffman编码的基本原理是什么? - ?
谭知协美: 构造最优二叉树就是其原理.最优二叉树:假设有n个权值{w1,w2,...,wn},试构造一颗又n个叶子结点的二叉树,每个叶子结点带权为wi,则其中带权路径长度WPL最小的二叉树称作最优二叉树,也叫赫夫曼树.具体请看数据结构相关书籍.希望这个解释对你有用,祝你学习进步~!
宿松县17390531319: 什么赫夫曼编码,我想知道下它的原理 - ?
谭知协美: 赫夫曼编码赫夫曼(Huffman)在1952年提出了另一种编码方法,即从下到上的编码方法.现仍以一个具体的例子说明它的编码步骤:(1) 初始化,根据符号概率的大小按由大到小顺序对符号进行排序,如表4-03和图4-02所示.(2) 把概率...
宿松县17390531319: 哈夫曼编码的工作原理,性能,应用 - ?
谭知协美: 哈夫曼编码(Huffman Coding)是一种编码方式,以哈夫曼树—即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩. 在计算机信息处理中,“哈夫曼编码”是一种一致性编码法(又称"熵编码法"),用于数据的无损耗压缩....
宿松县17390531319: 如何叙述哈夫曼编码 - ?
谭知协美: 哈夫曼编码 哈夫曼树可用于构造最短的不等长编码方案,具体做法如下:设需要编码的字符集合为{d1,d2,…,d¬n},它们在字符串中出现的频率为{w1, w2,…, wn},以d1,d2,…,d¬n作为叶子结点, w1, w2,…, wn¬作为叶子结点的权值,构造一颗...
宿松县17390531319: Huffman编码的基本原理? - ?
谭知协美: 编码的基本原理
宿松县17390531319: 什么是变字长最佳编码原理 - ?
谭知协美: 哈夫曼编码(Huffman Coding),又称霍夫曼编码最佳编码定理:在变字长码中,对于出现概率大的信息符号编以短字长的码;对于出现概率小的信息符号编以长字长的码,如果码字长度严格按照符号概率的大小的相反顺序排列,则平均码字长度一定小于按任何其他符号顺序排列方式得到的码字长度.Huffman编码步骤:概率统计,得到n个不同概率的信号;将n个信源信息符号的n个概率,按概率大小排序;将最后两个小概率相加,概率个数减为n-1;将n-1个概率重新排序;再将最后两个小概率相加,概率个数减为n-2;如此反复n-2次,得到只剩两个概率序列;以二进制码元(0,1)赋值,构成Huffman码字.
宿松县17390531319: huffman编码算法 - ?
谭知协美: 哈夫曼是一种编码手段.也就是说保证将来的编码是最小长度的,最终生成最小的哈夫曼编码树,又称哈夫曼最小树.它的原理是将一段文本中出现的字符按出现的频率决定其编码.然后按其最终的编码生成一段明文.知道了这个原理,编码...
宿松县17390531319: 哈夫曼编码是一种可变长,信源中某符号发生概率越低,其码长越 - --怎么? - ?
谭知协美: 哈夫曼编码的原理是:一个符号发生频率越高,其码长越短,反之则越长.很好理解:要使总长最短,出现越多次的符号的编码就要越短.打个不恰当的比方,现在用的最多的几个汉字“个”“的”“们”“什”“么”什么的笔画不是都很少吗?这就是文字演变的规律,也就是哈夫曼编码的原理.
宿松县17390531319: 什么是哈夫曼编码? - ?
谭知协美: 哈夫曼编码(Huffman Coding)是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种. Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字,有时称之为最佳编码,一般就叫作...