哈夫曼编码 百科内容来自于: 百度百科

哈夫曼编码(Huffman Coding)是一种编码方式,哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法,该方法完全依据字符出现概率来构造异字头的平均长度最短的码字,有时称之为最佳编码,一般就叫做Huffman编码(有时也称为霍夫曼编码)。

发展历史

1951年,哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。导师Robert M. Fano给他们的学期报告的题目是,寻找最有效的二进制编码。由于无法证明哪个已有编码是最有效的,哈夫曼放弃对已有编码的研究,转向新的探索,最终发现了基于有序频率二叉树编码的想法,并很快证明了这个方法是最有效的。由于这个算法,学生终于青出于蓝,超过了他那曾经和信息论创立者香农共同研究过类似编码的导师。哈夫曼使用自底向上的方法构建二叉树,避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。
1952年,David A. Huffman在麻省理工攻读博士时发表了《一种构建极小多余编码的方法》(A Method for the Construction of Minimum-Redundancy Codes)一文,它一般就叫做Huffman编码。

应用举例

哈夫曼树─即最优二叉树,带权路径长度最小的二叉树,经常应用于数据压缩。 在计算机信息处理中,
哈弗曼编码在信息论中应用举例

哈弗曼编码在信息论中应用举例

哈夫曼编码”是一种一致性编码法(又称“熵编码法”),用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符(例如某文件中的一个符号)进行编码。这张编码表的特殊之处在于,它是根据每一个源字符出现的估算概率而建立起来的(出现概率高的字符使用较短的编码,反之出现概率低的则使用较长的编码,这便使编码之后的字符串的平均期望长度降低,从而达到无损压缩数据的目的)。这种方法是由David.A.Huffman发展起来的。 例如,在英文中,e的出现概率很高,而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时,e极有可能用一个位
哈弗曼编码在信息论中应用举例

哈弗曼编码在信息论中应用举例

(bit)来表示,而z则可能花去25个位(不是26)。用普通的表示方法时,每个英文字母均占用一个字节(byte),即8个位。二者相比,e使用了一般编码的1/8的长度,z则使用了3倍多。若能实现对于英文中各个字母出现概率的较准确的估算,就可以大幅度提高无损压缩的比例。

压缩实现

速度要求

为了让它(huffman.cpp)快速运行,同时不使用任何动态库,比如STL或者MFC。它压缩1M数据少于100ms(P3处理器,主频1G)。

压缩过程

压缩代码非常简单,首先用ASCII值初始化511个哈夫曼节点:
CHuffmanNode nodes[511];
for(int nCount = 0; nCount < 256; nCount++)
nodes[nCount].byAscii = nCount;
其次,计算在输入缓冲区数据中,每个ASCII码出现的频率:
for(nCount = 0; nCount < nSrcLen; nCount++)
nodes[pSrc[nCount]].nFrequency++;
然后,根据频率进行排序:
qsort(nodes, 256, sizeof(CHuffmanNode), frequencyCompare);
哈夫曼树,获取每个ASCII码对应的位序列:
int nNodeCount = GetHuffmanTree(nodes);

构造哈夫曼树

构造哈夫曼树非常简单,将所有的节点放到一个队列中,用一个节点替换两个频率最低的节点,新节点的频率就是这两个节点的频率之和。这样,新节点就是两个被替换节点的父节点了。如此循环,直到队列中只剩一个节点(树根)。
// parent node
pNode = &nodes[nParentNode++];
// pop first child
pNode->pLeft = PopNode(pNodes, nBackNode--, false);
// pop second child
pNode->pRight = PopNode(pNodes, nBackNode--, true);
// adjust parent of the two poped nodes
pNode->pLeft->pParent = pNode->pRight->pParent = pNode;
// adjust parent frequency
pNode->nFrequency = pNode->pLeft->nFrequency + pNode->pRight->nFrequency;

注意事项

有一个好的诀窍来避免使用任何队列组件。ASCII码只有256个,但实际分配了511个(CHuffmanNode nodes[511]),前255个记录ASCII码,而用后255个记录哈夫曼树中的父节点。并且在构造树的时候只使用一个指针数组(ChuffmanNode *pNodes[256])来指向这些节点。同样使用两个变量来操作队列索引(int nParentNode = nNodeCount;nBackNode = nNodeCount –1)。
接着,压缩的最后一步是将每个ASCII编码写入输出缓冲区中:
int nDesIndex = 0;
// loop to write codes
for(nCount = 0; nCount < nSrcLen; nCount++)
{
*(DWORD*)(pDesPtr+(nDesIndex>>3)) |=
nodes[pSrc[nCount]].dwCode << (nDesIndex&7);
nDesIndex += nodes[pSrc[nCount]].nCodeLength;
}
(nDesIndex>>3): >>3 以8位为界限右移后到达右边字节的前面
(nDesIndex&7): &7 得到最高位.
此外,在压缩缓冲区中,必须保存哈夫曼树的节点以及位序列,这样才能在解压缩时重新构造哈夫曼树(只需保存ASCII值和对应的位序列)。

解压缩

解压缩比构造哈夫曼树要简单的多,将输入缓冲区中的每个编码用对应的ASCII码逐个替换就可以了。只要记住,这里的输入缓冲区是一个包含每个ASCII值的编码的位流。因此,为了用ASCII值替换编码,我们必须用位流搜索哈夫曼树,直到发现一个叶节点,然后将它的ASCII值添加到输出缓冲区中:
int nDesIndex = 0;
DWORD nCode;
while(nDesIndex < nDesLen)
{
nCode = (*(DWORD*)(pSrc+(nSrcIndex>>3)))>>(nSrcIndex&7);
pNode = pRoot;
while(pNode->pLeft)
{
pNode = (nCode&1) ? pNode->pRight : pNode->pLeft;
nCode >>= 1;
nSrcIndex++;
}
pDes[nDesIndex++] = pNode->byAscii;
}

程序实现

费诺编码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define M 100
typedef struct Fano_Node
{
char ch;
float weight;
}FanoNode[M];
typedef struct node
{
int start;
int end;
struct node *next;
}LinkQueueNode;
typedef struct
{
LinkQueueNode *front;
LinkQueueNode *rear;
}LinkQueue;
//建立队列
void EnterQueue(LinkQueue *q,int s,int e)
{
LinkQueueNode *NewNode;
//生成新节点
NewNode=(LinkQueueNode*)malloc(sizeof( LinkQueueNode ));
if(NewNode!=NULL)
{
NewNode->start=s;
NewNode->end=e;
NewNode->next=NULL;
q->rear->next=NewNode;
q->rear=NewNode;
}
else
{
printf("Error!");
exit(-1);
}
}
//按权分组
void Divide(FanoNode f,int s,int *m,int e)
{
int i;
float sum,sum1;
sum=0;
for(i=s;i<=e;i++)
sum+=f[i].weight;//
*m=s;
sum1=0;
for(i=s;i<e;i++)
{
sum1+=f[i].weight;
*m=fabs(sum-2*sum1)>fabs(sum-2*sum1-2*f[i+1].weight)?(i+1):*m;
if(*m==i) break;
}
}
void main()
{
int i,j,n,max,m,h[M];
int sta,end;
float w;
char c,fc[M][M];
FanoNode FN;
LinkQueueNode *p;
LinkQueue *Q;
//初始化队Q
Q=(LinkQueue *)malloc(sizeof(LinkQueue));
Q->front=(LinkQueueNode*)malloc(sizeof(LinkQueueNode));
Q->rear=Q->front;
Q->front->next=NULL;
printf("\t***FanoCoding***\n");
printf("Please input the number of node:");
//输入信息
scanf("%d",&n);
//超过定义M,退出
if(n>=M)
{
printf(">=%d",M);
exit(-1);
}
i=1; //从第二个元素开始录入
while(i<=n)
{
printf("%d weight and node:",i);
scanf("%f %c",&FN[i].weight,&FN[i].ch);
for(j=1;j<i;j++)
{
if(FN[i].ch==FN[j].ch)//查找重复
{
printf("Same node!!!\n"); break;
}
}
if(i==j)
i++;
}
//排序(降序)
for(i=1;i<=n;i++)
{
max=i+1;
for(j=max;j<=n;j++)
max=FN[max].weight<FN[j].weight?j:max;
if(FN[i].weight<FN[max].weight)
{
w=FN[i].weight;
FN[i].weight=FN[max].weight;
FN[max].weight=w;
c=FN[i].ch;
FN[i].ch=FN[max].ch;
FN[max].ch=c;
}
}
for(i=1;i<=n;i++) //初始化h
h[i]=0;
EnterQueue(Q,1,n); //1和n进队
while(Q->front->next!=NULL)
{
p=Q->front->next; //出队
Q->front->next=p->next;
if(p==Q->rear)
Q->rear=Q->front;
sta=p->start;
end=p->end;
free(p);
Divide(FN,sta,&m,end); /*按权分组*/
for(i=sta;i<=m;i++)
{
fc[i][h[i]]='0';
++h[i];
}
if(sta!=m)
EnterQueue(Q,sta,m);
else
fc[sta][h[sta]]='\0';
for(i=m+1;i<=end;i++)
{
fc[i][h[i]]='1';
++h[i];
}
if(m==sta&&(m+1)==end)
//如果分组后首元素的下标与中间元素的相等,
//并且和最后元素的下标相差为1,则编码码字字符串结束
{
fc[m][h[m]]='\0';
fc[end][h[end]]='\0';
}
else
EnterQueue(Q,m+1,end);
}
for(i=1;i<=n;i++) /*打印编码信息*/
{
printf("%c:",FN[i].ch);
printf("%s\n",fc[i]);
}
system("pause");
}

编码解码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100
#define M 2*N-1
typedef char * HuffmanCode[2*M];//haffman编码
typedef struct
{
int weight;//权值
int parent;//父节节点
int LChild;//左子节点
int RChild;//右子节点
}HTNode,Huffman[M+1];//huffman树
typedef struct Node
{
int weight; //叶子结点的权值
char c; //叶子结点
int num; //叶子结点的二进制码的长度
}WNode,WeightNode[N];
/***产生叶子结点的字符和权值***/
void CreateWeight(char ch[],int *s,WeightNode CW,int *p)
{
int i,j,k;
int tag;
*p=0;//叶子节点个数
//统计字符出现个数,放入CW
for(i=0;ch[i]!='\0';i++)
{
tag=1;
for(j=0;j<i;j++)
if(ch[j]==ch[i])
{
tag=0;
break;
}
if(tag)
{
CW[++*p].c=ch[i];
CW[*p].weight=1;
for(k=i+1;ch[k]!='\0';k++)
if(ch[i]==ch[k])
CW[*p].weight++;//权值累加
}
}
*s=i;//字符串长度
}
/********创建HuffmanTree********/
void CreateHuffmanTree(Huffman ht,WeightNode w,int n)
{
int i,j;
int s1,s2;
//初始化哈夫曼树
for(i=1;i<=n;i++)
{
ht[i].weight =w[i].weight;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}
for(i=n+1;i<=2*n-1;i++)
{
ht[i].weight=0;
ht[i].parent=0;
ht[i].LChild=0;
ht[i].RChild=0;
}
for(i=n+1;i<=2*n-1;i++)
{
for(j=1;j<=i-1;j++)
if(!ht[j].parent)
break;
s1=j; //找到第一个双亲为零的结点
for(;j<=i-1;j++)
if(!ht[j].parent)
s1=ht[s1].weight>ht[j].weight?j:s1;
ht[s1].parent=i;
ht[i].LChild=s1;
for(j=1;j<=i-1;j++)
if(!ht[j].parent)
break;
s2=j; //找到第二个双亲为零的结点
for(;j<=i-1;j++)
if(!ht[j].parent)
s2=ht[s2].weight>ht[j].weight?j:s2;
ht[s2].parent=i;
ht[i].RChild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;//权值累加
}
}
/***********叶子结点的编码***********/
void CrtHuffmanNodeCode(Huffman ht,char ch[],HuffmanCode h,WeightNode weight,int m,int n)
{
int i,c,p,start;
char *cd;
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';//末尾置0
for(i=1;i<=n;i++)
{
start=n-1; //cd串每次从末尾开始
c=i;
p=ht[i].parent;//p在n+1至2n-1
while(p) //沿父亲方向遍历,直到为0
{
start--;//依次向前置值
if(ht[p].LChild==c)//与左子相同,置0
cd[start]='0';
else //否则置1
cd[start]='1';
c=p;
p=ht[p].parent;
}
weight[i].num=n-start; //二进制码的长度(包含末尾0)
h[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(h[i],&cd[start]);//将二进制字符串拷贝到指针数组h中
}
free(cd);//释放cd内存
system("pause");
}
/*********所有字符的编码*********/
void CrtHuffmanCode(char ch[],HuffmanCode h,HuffmanCode hc,WeightNode weight,int n,int m)
{
int i,k;
for(i=0;i<m;i++)
{
for(k=1;k<=n;k++) /*从weight[k].c中查找与ch[i]相等的下标K*/
if(ch[i]==weight[k].c)
break;
hc[i]=(char *)malloc((weight[k].num)*sizeof(char));
strcpy(hc[i],h[k]); //拷贝二进制编码
}
}
/*****解码*****/
void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m)
{
int i=0,j,p;
printf("***StringInformation***\n");
while(i<m)
{
p=2*n-1;//从父亲节点向下遍历直到叶子节点
for(j=0;hc[i][j]!='\0';j++)
{
if(hc[i][j]=='0')
p=ht[p].LChild;
else
p=ht[p].RChild;
}
printf("%c",w[p].c); /*打印原信息*/
i++;
}
}
/*****释放huffman编码内存*****/
void FreeHuffmanCode(HuffmanCode h,HuffmanCode hc,int n,int m)
{
int i;
for(i=1;i<=n;i++)//释放叶子结点的编码
free(h[i]);
for(i=0;i<m;i++) //释放所有结点的编码
free(hc[i]);
}
void main()
{
int i,n=0; /*n为叶子结点的个数*/
int m=0; /*m为字符串ch[]的长度*/
char ch[N]; /*ch[N]存放输入的字符串*/
Huffman ht; /*Huffman二叉数*/
HuffmanCode h,hc; /*h存放叶子结点的编码,hc 存放所有结点的编码*/
WeightNode weight; /*存放叶子结点的信息*/
printf("\t***HuffmanCoding***\n");
printf("please input information :");
gets(ch); /*输入字符串*/
CreateWeight(ch,&m,weight,&n); /*产生叶子结点信息,m为字符串ch[]的长度*/
printf("***WeightInformation***\n Node ");
for(i=1;i<=n;i++) /*输出叶子结点的字符与权值*/
printf("%c ",weight[i].c);
printf("\nWeight ");
for(i=1;i<=n;i++)
printf("%d ",weight[i].weight);
CreateHuffmanTree(ht,weight,n); /*产生Huffman树*/
printf("\n***HuffamnTreeInformation***\n");
printf("\ti\tweight\tparent\tLChild\tRChild\n");
for(i=1;i<=2*n-1;i++) /*打印Huffman树的信息*/
printf("\t%d\t%d\t%d\t%d\t%d\n",i,ht[i].weight,ht[i].parent,ht[i].LChild,ht[i].RChild);
CrtHuffmanNodeCode(ht,ch,h,weight,m,n); /*叶子结点的编码*/
printf(" ***NodeCode***\n"); /*打印叶子结点的编码*/
for(i=1;i<=n;i++)
{
printf("\t%c:",weight[i].c);
printf("%s\n",h[i]);
}
CrtHuffmanCode(ch,h,hc,weight,n,m); /*所有字符的编码*/
printf("***StringCode***\n"); /*打印字符串的编码*/
for(i=0;i<m;i++)
printf("%s",hc[i]);
system("pause");
TrsHuffmanTree(ht,weight,hc,n,m); /*解码*/
FreeHuffmanCode(h,hc,n,m);
system("pause");
}

Matlab实现

Matlab 中简易实现Huffman编译码:
n=input('Please input the total number: ');
hf=zeros(2*n-1,5);
hq=[];
for ki=1:n
hf(ki,1)=ki;
hf(ki,2)=input('Please input the frequency: ');
hq=[hq,hf(ki,2)];
end
for ki=n+1:2*n-1
hf(ki,1)=ki;
mhq1=min(hq);
m=size(hq);
m=m(:,2);
k=1;
while k<=m%del min1
if hq(:,k)==mhq1
hq=[hq(:,1:(k-1)) hq(:,(k+1):m)];
m=m-1;
break
else
k=k+1;
end
end
k=1;
while hf(k,2)~=mhq1|hf(k,5)==1%find min1 location
k=k+1;
end
hf(k,5)=1;
k1=k;
mhq2=min(hq);
k=1;
while k<=m%del min2
if hq(:,k)==mhq2
hq=[hq(:,1:(k-1)) hq(:,(k+1):m)];
m=m-1;
break
else
k=k+1;
end
end
k=1;
while hf(k,2)~=mhq2|hf(k,5)==1%find min2 location
k=k+1;
end
hf(k,5)=1;
k2=k;
hf(ki,2)=mhq1+mhq2;
hf(ki,3)=k1;
hf(ki,4)=k2;
hq=[hq hf(ki,2)];
end
clc
choose=input('Please choose what you want:\n1: Encoding\n2: Decoding\n3:.Exit\n');
while choose==1|choose==2
if choose==1
a=input('Please input the letter you want to Encoding: ');
k=1;
while hf(k,2)~=a
k=k+1;
if k>=n
display('Error! You did not input this number.');
break
end
end
if k>=n
break
end
r=[];
while hf(k,5)==1
kc=n+1;
while hf(kc,3)~=k&hf(kc,4)~=k
kc=kc+1;
end
if hf(kc,3)==k
r=[0 r];
else
r=[1 r];
end
k=kc;
end
r
else
a=input('Please input the metrix you want to Decoding: ');
sa=size(a);
sa=sa(:,2);
k=2*n-1;
while sa~=0
if a(:,1)==0
k=hf(k,3);
else
k=hf(k,4);
end
a=a(:,2:sa);
sa=sa-1;
if k==0
display('Error! The metrix you entered is a wrong one.');
break
end
end
if k==0
break
end
r=hf(k,2);
end
choose=input('Choose what you want:\n1: Encoding\n2: Decoding\n3:.Exit\n');
clc;
end
if choose~=1&choose~=2
clc;
end
$firstVoiceSent
- 来自原声例句
小调查
请问您想要如何调整此模块?

感谢您的反馈,我们会尽快进行适当修改!
进来说说原因吧 确定
小调查
请问您想要如何调整此模块?

感谢您的反馈,我们会尽快进行适当修改!
进来说说原因吧 确定