哈夫曼编码的原理?

发布网友 发布时间：2022-04-23 22:28

我来回答

共5个回答

热心网友 时间：2022-04-23 04:14

霍夫曼编码的基本思想：输入一个待编码的串，首先统计串中各字符出现的次数，称之为频次，假设统计频次的数组为count[ ]，则霍夫曼编码每次找出count数组中的值最小的两个分别作为左右孩子，建立他们的父节点，循环这个操作2*n-1-n（n是不同的字符数）次，这样就把霍夫曼树建好了。建树的过程需要注意，首先把count数组里面的n个值初始化为霍夫曼树的n个叶子节点，他们的孩子节点的标号初始化为-1，父节点初始化为他本身的标号。接下来是编码，每次从霍夫曼树的叶子节点出发，依次向上找，假设当前的节点标号是i，那么他的父节点必然是myHuffmantree[i].parent，如果i是myHuffmantree[i].parent的左节点，则该节点的路径为0，如果是右节点，则该节点的路径为1。当向上找到一个节点，他的父节点标号就是他本身，就停止（说明该节点已经是根节点）。还有一个需要注意的地方：在查找当前权值最小的两个节点时，那些父节点不是他本身的节点不能考虑进去，因为这些节点已经被处理过了

热心网友 时间：2022-04-23 05:32

这个是我同学的哈夫曼编码程序

另外还有解码的程序，要的话再商量

#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);
}

热心网友 时间：2022-04-23 07:06

最简单的理解方式是：把最常用的词用最短的代码表示，可以理解为缩写
比如NBA就代表National Basketball Association这多字母了，这样如果把文章中的所有National Basketball Association都改成NBA是不是能省很多字，解说员都是这么做的，呵呵

热心网友 时间：2022-04-23 08:58

最小带权生成树

热心网友 时间：2022-04-23 11:22

霍夫曼（Huffman）编码属于码词长度可变的编码类，是霍夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率。生成霍夫曼编码算法基于一种称为“编码树”（coding tree）的技术。算法步骤如下：
（1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。
（2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。
（3）重复第2步，直到形成一个符号为止（树），其概率最后等于1。
（4）从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。
以下这个简单例子说明了这一过程。
1)．字母A,B,C,D,E已被编码，相应的出现概率如下：
p(A)=0.16, p(B)=0.51, p(C)=0.09, p(D)=0.13, p(E)=0.11
2)．C和E概率最小，被排在第一棵二叉树中作为树叶。它们的根节点CE的组合概率为0.20。从CE到C的一边被标记为1，从CE到E的一边被标记为0。这种标记是强制性的。所以，不同的哈夫曼编码可能由相同的数据产生。
3)．各节点相应的概率如下：
p(A)=0.16, p(B)=0.51, p(CE)=0.20, p(D)=0.13
D和A两个节点的概率最小。这两个节点作为叶子组合成一棵新的二叉树。根节点AD的组合概率为0.29。由AD到A的一边标记为1，由AD到D的一边标记为0。
如果不同的二叉树的根节点有相同的概率，那么具有从根到节点最短的最大路径的二叉树应先生成。这样能保持编码的长度基本稳定。
4)．剩下节点的概率如下：
p(AD)=0.29, p(B)=0.51, p(CE)=0.20
AD和CE两节点的概率最小。它们生成一棵二叉树。其根节点ADCE的组合概率为0.49。由ADCE到AD一边标记为0，由ADCE到CE的一边标记为1。
5)．剩下两个节点相应的概率如下：
p(ADCE)=0.49, p(B)=0.51
它们生成最后一棵根节点为ADCEB的二叉树。由ADCEB到B的一边记为1，由ADCEB到ADCE的一边记为0。
6)．图03-02-2为霍夫曼编码。编码结果被存放在一个表中：
w(A)=001, w(B)=1, w(C)=011, w(D)=000, w(E)=010

图03-02-2 霍夫曼编码例
霍夫曼编码器的编码过程可用例子演示和解释。
下面是另一个霍夫曼编码例子。假定要编码的文本是：
"EXAMPLE OF HUFFMAN CODE"
首先，计算文本中符号出现的概率（表03-02-2）。
表03-02-2 符号在文本中出现的概率
符号
概率

E
2/25

X
1/25

A
2/25

M
2/25

P
1/25

L
1/25

O
2/25

F
2/25

H
1/25

U
1/25

C
1/25

D
1/25

I
1/25

N
2/25

G
1/25

空格
3/25

最后得到图03-02-3所示的编码树。

图03-02-3 霍夫曼编码树
在霍夫曼编码理论的基础上发展了一些改进的编码算法。其中一种称为自适应霍夫曼编码（Adaptive Huffman code）。这种方案能够根据符号概率的变化动态地改变码词，产生的代码比原始霍夫曼编码更有效。另一种称为扩展的霍夫曼编码（Extended Huffman code）允许编码符号组而不是单个符号。
同香农-范诺编码一样，霍夫曼码的码长虽然是可变的，但却不需要另外附加同步代码。这是因为这两种方法都自含同步码，在编码之后的码串中都不需要另外添加标记符号，即在译码时分割符号的特殊代码。当然，霍夫曼编码方法的编码效率比香农-范诺编码效率高一些。
采用霍夫曼编码时有两个问题值得注意：①霍夫曼码没有错误保护功能，在译码时，如果码串中没有错误，那么就能一个接一个地正确译出代码。但如果码串中有错误，那怕仅仅是1位出现错误，也会引起一连串的错误，这种现象称为错误传播(error propagation)。计算机对这种错误也*为力，说不出错在哪里，更谈不上去纠正它。②霍夫曼码是可变长度码，因此很难随意查找或调用压缩文件中间的内容，然后再译码，这就需要在存储代码之前加以考虑。尽管如此，霍夫曼码还是得到广泛应用。