Huffman编码
Huffman编码实验，原理弄懂了，源代码不是很懂，挖个坑，以后用到再细读。
实验原理
在众多无失真信道编码技术方案中，
哈夫曼（Huffman）算法作为一种高效获取最佳平均码长的技术方案，
它能够充分利用短长度的码字，
大幅降低了平均码长，
从而显著提升了数据压缩效率，
同时确保了可分离性的特性。
正是由于哈夫曼算法的优势所在，
目前在有关信源编码的各种领域中，
哈夫曼算法作为一项基础且关键的技术手段被广泛采用。
（一）Huffman编码方法
在当前的数字通信领域中，普遍采用二进制符号作为基础。基于此，在应用过程中发现，在这些条件下通过Huffman算法构建最优树能够达到最佳效果。基于上述分析与结论，在应用过程中发现，在这些条件下通过Huffman算法构建最优树能够达到最佳效果。详细步骤如下：
1、将信源符号按概率从大到小进行排列；
给两个概率最小的信源符号分别赋值"0"和"1"后将其合并为一个新的符号，并以这两个最小概率之和作为其概率。结果得到一个只有（n−1）个元素的新信息源（假设原来所需编码的元素数目为n），并称这个新信息源为第一次缩减后的信息源S₁。
对缩减信源S1中的符号按照其概率值由高至低排序，在完成此操作后依次执行步骤2，并最终获得只包含（n-2）个符号的新缩减信源S2
4、反复执行下述操作：持续缩减信源直至其仅剩下两个符号为止。此时这两只留下的符号的概率总和必定等于1。接着给它们分别赋予码字'0'与'1'。然后从缩减过程的最后一步开始依照编码路径逆向推导出各原始字符对应的哈夫曼编码。
（二）方差最小的Huffman码字
在缩减信息源的过程中, 当合并后的新符号的概率与原有其他符号的概率相等时, 从编码理论的角度来看, 这些符号可以以任意顺序进行排列, 所编成的码字均为正确无误的形式, 但采用不同的编码策略所得出的代码形式各不相同. 相应地产生的代码长度也存在差异, 由此导致代码长度的标准差也随之发生变化. 当代码长度的标准差较小时, 表明各个代码长度之间的波动幅度较小, 大部分代码长度与平均值较为接近. 这对于信息传输而言至关重要: 对于一般性的信息传递需求而言, 它能保证可靠性和有效性; 而对于具有实时性需求的情形而言, 其意义同样不容忽视.
为了获得具有最小方差的Huffman码字，在将缩减信源按照概率从高到低重新排列时
（三）递归算法实现Huffman编码
在Huffman编码的过程中，在每一次循环中都会对一个缩减的信息源执行相同的过程——即先对该信息源进行排序然后将其合并为新的节点，并且最终生成的方式是通过逆向追踪编码路径来确定各个码字的位置值进而完成整个码表的设计工作；基于这一规律的基础上设计出一套高效的Huffman编码算法方案
在信源编码中，在给定n个符号及其对应的概率pi的情况下，则其主要思想可具体体现为通过构建一棵二叉树来进行编码分配。
procedure Huffman(n,{pi})
if n= = 2 then
对两个符号各分配一个码元“0”和“1”；
else
降序排序；
合并符号，并得到新的概率分布pi′；
Huffman(n-1,{ pi′})；
对被合并的两个符号各分配一个码元“0”和“1”；
endprocedure
代码解读（四）动态分配内存
基于所接收的信息统计其概率分布进行Huffman编码，在编码前无法预先知道具体所需的字符数量及其频率，并且无法预估所需的二进制码长。对于这些字符及其对应的二进制码字来说，单纯依靠固定长度数组无法满足需求。而C语言通过动态内存管理使得资源可以按需调整。这种方法能够有效地解决这一问题。
程序代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#definedelta 1.0e-6
voidsort(float *,char * *,int *,int);
voidcode(float *,char * *,int *,int);
voidmain()
{
float *p,*p_i;
float sum;
char * * c;
int *idx;
int q;
int i,j;
int l1,l2;
char * s;
float t;
int idx_t;
printf("input the number of thesymbols:\n");
scanf("%d",&q);
idx=(int *)calloc(q,sizeof(int));
p=(float *)calloc(q,sizeof(float));
p_i=(float *)calloc(q,sizeof(float));
c=(char * *)calloc(q,sizeof(char *));
for(i=0;i<q;i++)
{
c[i]=(char *)calloc(1,sizeof(char));
c[i][0]='\0';
}
sum=0.0;
for(i=0;i<q;i++)
{
printf("input the probabilityof x[%d]:\n",i);
scanf("%f",&p[i]);
p_i[i]=p[i];
idx[i]=i;
sum+=p[i];
}
if((sum-1.0)>delta||(1.0-sum)>delta)
{
printf("the probabilities error!!\n");
exit(-1);
}
for (i=0;i<q;i++)
{
for (j=0;j<q-i;j++)
{
if(p[j]<p[j+1])
{
t=p[j];
p[j]=p[j+1];
p[j+1]=t;
idx_t=idx[j];
idx[j]=idx[j+1];
idx[j+1]=idx_t;
l1=strlen(c[j]);
l2=strlen(c[j+1]);
s=(char *)calloc(l1+1,sizeof(char));
strcpy(s,c[j]);
realloc(c[j],l2+1);
strcpy(c[j],c[j+1]);
realloc(c[j+1],l1+1);
strcpy(c[j+1],s);
free(s);
}
}
}
code(p,c,idx,q);
for(i=0;i<q;i++)
{
printf("x[%d]:probability=%.6f code=%s\n",idx[i],p_i[idx[i]],c[i]);
}
free(c);
free(p);
free(p_i);
free(idx);
}
voidsort(float * p,char * * c,int * idx,int q)
{
int i,j;
int l1,l2;
char * s;
float t;
t=p[q-1];
j=idx[q-1];
l1=strlen(c[q-1]);
s=(char *)calloc(l1+1,sizeof(char));
strcpy(s,c[q-1]);
i=q-2;
while((i>=0)&&(t>=p[i]))
{
p[i+1]=p[i];
idx[i+1]=idx[i];
l2=strlen(c[i]);
realloc(c[i+1],l2+1);
strcpy(c[i+1],c[i]);
i--;
}
p[i+1]=t;
idx[i+1]=j;
realloc(c[i+1],l1+1);
strcpy(c[i+1],s);
free(s);
}
voidcode(float * p,char * * c,int * idx, int q)
{
int l1,l2;
int idx1,idx2;
char * s;
if(q==2)
{
l1=strlen(c[0]);
l2=strlen(c[1]);
realloc(c[0],l1+2);
realloc(c[1],l2+2);
strcat(c[0],"0");
strcat(c[1],"1");
}
else
{
p[q-2]=p[q-1]+p[q-2];
idx1=idx[q-2];
idx2=idx[q-1];
sort(p,c,idx,q-1);
code(p,c,idx,q-1);
for (int i=0;i<q;i++)
{
if(idx[i]==idx1)
{
idx1=i;
break;
}
}
for (int j=0;j<q;j++)
{
if (idx[j]==idx2)
{
idx2=j;
break;
}
}
l1=strlen(c[idx1]);
l2=strlen(c[idx2]);
s=(char *)calloc(l1+2,sizeof(char*));
strcpy(s,c[idx1]);
realloc(c[idx1],l1+2);
strcpy(c[idx1],s);
strcat(c[idx1],"0");
realloc(c[idx2],l2+2);
strcpy(c[idx2],s);
strcat(c[idx2],"1");
free(s);
}
}
代码解读