霍夫曼编码的C语言实现
默认分类 2009-06-04 18:40:33 阅读1001 评论2 字号：大中小
霍夫曼编码的C语言实现
1.霍夫曼编码
霍夫曼编码是1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。霍夫曼编码同香农、费诺编码一样是一种通信编码，但是他们是按不同思路设计了各自的编码实现方法。
通信的根本问题是如何将信源输出的信息在接收端的信息精确或近似的复制出来。若接收端要求无失真地精确复制信源输出的消息，此信源编是无失真编码。只有对离散信源可以实现无失真编码，由于连续信源输出信息量可为无限大，故不可能实现无失真编码。霍夫曼编码就是一种无损压缩编码，在通信领域中应用非常广泛，因此我们用C语言的方式为让大家更好的认识和理解霍夫曼编码。
2.编码原理
霍夫曼码由霍夫曼树构造，平均码长是霍夫曼树的带权路径长度，由于霍夫曼树是权最小的树，故其压缩效果最好。霍夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。 在计算机信息处理中，“霍夫曼编码”是一种一致性编码法（又称"熵编码法"），用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的。
霍夫曼码是用概率匹配方法进行信源编码。有两个明显特点：一是保证了概率大的符号对应于短码，概率小的对应于长码，充分利用了短码；二是缩减信源的最后二个码字总是最后一位不同，从而保证了霍夫曼码是即时码。
霍夫曼变长码的效率很高，它可以单个信源符号编码或用L较小的信源序列编码，对编码器的设计来说也易实现，但要注意，更高效率的编码仍须按长序列来计算，这样才能使平均码字降低。
3.霍夫曼编码的步骤
（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｝
。
根据字符出现的概率来构造平均长度最短的异字头码字。霍未曼编码通常采用两次扫描的办法，第一次扫描得到统计结果，第二次扫描进行编码。
4.编码的特点
（1）哈夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，直到树根结束，最后得到一个横放的码树，因此，编出的码是即时码。
（2）哈夫曼编码采用概率匹配方法来决定各码字的码长，概率大的符号对应于短码，概率小的符号对
应于长码，从而使平均码长最小。
（3）每次对概率最小的两个符号求概率之和形成缩减信源时，就构造出两个树枝，由于给两个树枝赋码元时是任意的，因此编出的码字并不惟一。
5.C语言的实现
#include <stdio.h>
#include <malloc.h>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
#define HuffmanTree HF
#define HuffmanCode HMC
typedef struct
{unsigned int weight;
unsigned int parent,lchild,rchild;
} HTNode,*HF;
typedef char **HMC;
typedef struct {
unsigned int s1;
unsigned int s2;
} MinCode;
void Error(char *message);
HMC HuffmanCoding(HF HT,HMC HC,unsigned int *w,unsigned int n);
MinCode Select(HF HT,unsigned int n);
void Error(char *message)
{
fprintf(stderr,"Error:%s\n",message);
exit(1);
}
HMC HuffmanCoding(HF HT,HMC HC,unsigned int *w,unsigned int n)
{
unsigned int i,s1=0,s2=0;
HF p;
char *cd;
unsigned int f,c,start,m;
MinCode min;
if(n<=1) Error("Code too small!");
m=2*n-1;
HT=(HF)malloc((m+1)*sizeof(HTNode));
for(p=HT,i=0;i<=n;i++,p++,w++)
{
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;i++,p++)
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(i=n+1;i<=m;i++)
{
min=Select(HT,i-1);
s1=min.s1;
s2=min.s2;
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
printf("HT List:\n");
printf("Number\t\tweight\t\tparent\t\tlchild\t\trchild\n");
for(i=1;i<=m;i++)
printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n",
i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
HC=(HMC)malloc((n+1)*sizeof(char *));
cd=(char *)malloc(n*sizeof(char *));
cd[n-1]='\0';
for(i=1;i<=n;i++)
{
start=n-1;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
if(HT[f].lchild==c) cd[--start]='0';
else cd[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char *));
strcpy(HC[i],&cd[start]);
}
free(cd);
return HC;
}
哈夫曼编码树的带权路径长度void main()
{
MinCode Select(HF HT,unsigned int n);
HF HT=NULL;
HuffmanCode HC=NULL;
unsigned int *w=NULL;
unsigned int i,n;
printf("请输入节点数n:");
scanf("%d",&n);
w=(unsigned int *)malloc((n+1)*sizeof(unsigned int *));
w[0]=0;
printf("请输入权重:\n");
for(i=1;i<=n;i++)
{
printf("w[%d]=",i);
scanf("%d",&w[i]);
}
HC=HuffmanCoding(HT,HC,w,n);
printf("HMC:\n");
printf("Number\t\tWeight\t\tCode\n");
for(i=1;i<=n;i++)
printf("%d\t\t%d\t\t%s\n",i,w[i],HC[i]);
}
MinCode Select(HF HT,unsigned int n)
{
unsigned int min,secmin;
unsigned int temp;
unsigned int i,s1,s2,tempi;
MinCode code;
s1=1;s2=1;
for(i=1;i<=n;i++)
if(HT[i].parent==0)
{
min=HT[i].weight;
s1=i;
break;
}
tempi=i++;
for(;i<=n;i++)
if(HT[i].weight<min&&HT[i].parent==0)
{
min=HT[i].weight;
s1=i;
}
for(i=tempi;i<=n;i++)
if(HT[i].parent==0&&i!=s1)
{
secmin=HT[i].weight;
s2=i;
break;
}
for(i=1;i<=n;i++)
if(HT[i].weight<secmin&&i!=s1&&HT[i].parent==0)
{
secmin=HT[i].weight;
s2=i;
}
if(s1>s2)
{
temp=s1;
s1=s2;
s2=temp;
}
code.s1=s1;
code.s2=s2;
return code;
}
执行程序后显示如图1：
图1
改变节点数n的值后显示如图2：
图2
6. 霍夫曼编码的优、缺点：
优点：
(1)有效的信源编码可取得较好的冗余压缩效果。
(2)有效的信源编码可使输出码元概率均匀化。
在哈夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。
缺点：
（1）由于编码长度可变。因此译码时间较长，使得霍夫曼编码的压缩与还原相当费时。
（2）编码长度不统一，硬件实现有难度。
（3） 对不同信号源的编码效率不同，当信号源的符号概率为2的负幂次方时，达到100％的编码效率；若信号源符号的概率相等，则编码效率最低。
（4） 由于"0"与"1"的指定是任意的，故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。