哈夫曼编码(Huffman Coding),又称霍夫曼编码,是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫Huffman编码(有时也称为霍夫曼编码)。
下面是用C语言实现的简单的哈夫曼编码实现,要实现编码,首先得创建哈夫曼树(也叫最优二叉树)。
哈夫曼树就是带权路径长度(WPL)最小的二叉树,而权路径长度(WPL)指的是出现频率*其到根节点的长度。最后使出现平率高的越靠近根节点。
哈夫曼编码的优点便是降低重复的码值,实现无损压缩。
#include <stdio.h>
#include <stdlib.h>
//结构体创建节点
typedef struct{
char word;
int weight,left,right,parent;
int *code;
}HuffNode;
//初始化森林(对节点与权值进行初始化)
int n;
void StartHuffTree(HuffNode * F){
int i,w;
char ch;
printf("请输入字符与权重(空格间隔,回车结束):\n");
for(i=0;i<n;i++){
printf("第%d个节点:",i+1);
scanf("%s",&ch);
scanf("%d",&w);
F[i].word=ch;
F[i].weight=w;
F[i].left=F[i].right=F[i].parent=-1;
F[i].code=NULL;
}
printf("----------------------------------------------------\n");
}
//创建哈夫曼树 (创建哈夫曼树,最优二叉树)
void CreatHuffTree(HuffNode * F){
printf("创建哈弗曼树:\n");
int i,j,k1,k2;
//循环n-1次创建树的双亲
for(i=0;i<n-1;i++){
//k1,k2找到可以作为子树的树
for(k1=0;k1<n+i&&F[k1].parent!=-1;k1++);
for(k2=k1+1;k2<n+i&&F[k2].parent!=-1;k2++);
//循环 整个森林,使得k1,k2为最小的次小的2颗树
for(j=k2;j<n+i;j++){
if(F[j].parent==-1){
if(F[j].weight<F[k1].weight){
k2=k1;
k1=j;
}
else if(F[j].weight<F[k2].weight){
k2=j;
}
}
}
//在第n+i节点 上创建k1,k2的双亲
F[n+i].word='x';
F[n+i].weight=(F[k1]).weight+(F[k2]).weight;
F[n+i].left=k1;
F[n+i].right=k2;
F[n+i].parent=-1;
F[n+i].code=NULL;
F[k1].parent=n+i;
F[k2].parent=n+i;
// printf("%d",F[n+i].parent);
// getchar();
//
}
//判断创建的树是否正确
for(j=0;j<7;j++){
printf("%4c",F[j].word);
printf("%4d",F[j].weight);
printf("%4d",F[j].left);
printf("%4d",F[j].right);
printf("%4d\n",F[j].parent);
}
printf("-----------------------------------------------------\n");
}
//对哈弗曼树进行编码
void CreatCode(HuffNode * F){
printf("哈弗曼树编码:............\n");
int i,pa,c;
int *p;
for(i=0;i<n;i++){
F[i].code=p=(int *)malloc(n*sizeof(int));
p[0]=0;
c=i;
while(F[c].parent!=-1){
pa=F[c].parent;
if(F[pa].left==c){
p[++p[0]]=0;
}else{
p[++p[0]]=1;
}
c=pa;
}
}
}
void PrintHuffTree(HuffNode * F){
printf("输出哈夫曼编码:\n");
for(int i=0;i<n;i++){
printf("%4c",F[i].word);
printf(" ");
for(int j=F[i].code[0];j>0;j--){
printf("%d",F[i].code[j]);
}
printf("\n");
}
}
int main(void)
{
printf("输入叶子节点个数:");
scanf("%d",&n);
//初始化
HuffNode * F=(HuffNode *)malloc((2*n-1)*sizeof(HuffNode));
StartHuffTree(F);
//创建哈夫曼树
CreatHuffTree(F);
//编码
CreatCode(F);
//输出
PrintHuffTree(F);
return 0;
}