Huffman编码原理简介

    霍夫曼（Huffman）编码是1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部信息的总码长一定小于实际信息的符号长度。

    对于学多媒体的同学来说，需要知道Huffman编码过程的几个步骤：

    l）将信号源的符号按照出现概率递减的顺序排列。（注意，一定要递减）

    2）将最下面的两个最小出现概率进行合并相加，得到的结果作为新符号的出现概率。

    3）重复进行步骤1和2直到概率相加的结果等于1为止。

    4）在合并运算时，概率大的符号用编码0表示，概率小的符号用编码1表示。

    5）记录下概率为1处到当前信号源符号之间的0，l序列，从而得到每个符号的编码。

    下面我举个简单例子:

    一串信号源S＝{s1,s2,s3,s4,s5}对应概率为p＝{40，30，15，10，5}，（百分率）

    按照递减的格式排列概率后，根据第二步，会得到一个新的概率列表，依然按照递减排列，注意：如果遇到相同概率，合并后的概率放在下面！

    最后概率最大的编码为0，最小的编码为1。如图所示：

    所以，编码结果为

    s1=1

    s2=00

    s3=010

    s4=0110

    s5=0111

    霍夫曼编码具有如下特点：

1) 编出来的码都是异字头码，保证了码的唯一可译性。

2) 由于编码长度可变。因此译码时间较长，使得霍夫曼编码的压缩与还原相当费时。

3) 编码长度不统一，硬件实现有难度。

4) 对不同信号源的编码效率不同，当信号源的符号概率为2的负幂次方时，达到100％的编码效率；若信号源符号的概率相等，则编码效率最低。

5) 由于0与1的指定是任意的，故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能。

霍夫曼编码的C语言实现

#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=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\\weight\\parent\\lchild\\rchild\\n"); 

for(i=1;i<=m;i++)

printf("%d\\%d\\%d\\%d\\%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\\Weight\\Code\\n"); 

for(i=1;i<=n;i++)

printf("%d\\%d\\%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].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=HT[i].weight; 

s2=i; 

} 

if(s1>s2)

{ 

temp=s1; 

s1=s2; 

s2=temp; 

} 

code.s1=s1; 

code.s2=s2; 

return code; 

}