霍夫曼编码的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＝｛，，, ，｝。哈夫曼编码树的带权路径长度
按照字符出现的概率来构造平均长度最短的异字头码字。霍未曼编码通常采用两次扫描的办法，第一次扫描取得统计结果，第二次扫描进行编码。
4.编码的特点
（1）哈夫曼编码实际上构造了一个码树，码树从最上层的端点开始构造，直到树根结束，
最后取得一个横放的码树，因此，编出的码是即时码。
（2）哈夫曼编码采用概率匹配方式来决定各码字的码长，概率大的符号对应于短码，概率小的符号对应于长码，从而使平均码长最小。
（3）每次对概率最小的两个符号求概率之和形成缩减信源时，就构造出两个树枝，由于给两个树枝赋码元时是任意的，因此编出的码字并非惟一。
语言的实现
#include <>
#include <>
#include <>
#include <>
#include <>
#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=;
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 *));
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论