哈夫曼编码.docx
《哈夫曼编码.docx》由会员分享，可在线阅读，更多相关《哈夫曼编码.docx（25页珍藏版）》请在冰点文库上搜索。
哈夫曼编码
哈夫曼编码
求助编辑百科名片
哈夫曼编码（HuffmanCoding）是一种编码方式，哈夫曼编码是可变字长编码（VLC）的一种。
uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。
目录
历史
哈夫曼编码举例
背景
编码使用
要点说明
速度
压缩
构造哈夫曼树
构造哈夫曼树注意事项
注意：
解压缩
程序实现
c语言实现:
费诺编码
c语言实现:
huffman编码解码
Matlab实现
历史
哈夫曼编码举例
背景
编码使用
要点说明
速度
压缩
构造哈夫曼树
构造哈夫曼树注意事项
注意：
解压缩
程序实现
c语言实现:
费诺编码
c语言实现:
huffman编码解码
Matlab实现
展开
基本简介
编辑本段历史
1951年，哈夫曼和他在MIT信息论的同学需要选择是完成学期报告还是期末考试。
导师RobertM.Fano给他们的学期报告的题目是，寻找最有效的二进制编码。
由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。
由于这个算法，学生终于青出于蓝，超过了他那曾经和信息论创立者香农共同研究过类似编码的导师。
哈夫曼使用自底向上的方法构建二叉树，避免了次优算法Shannon-Fano编码的最大弊端──自顶向下构建树。
哈夫曼编码举例
以哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。
在计算机信息处理中，“哈夫曼编码”是一种一致性编码法（又称“熵编码法”），用于数据的无损耗压缩。
这一术语是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。
这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。
这种方法是由David.A.Huffman发展起来的。
例如，在英文中，e的出现概率很高，而z的出现概率则最低。
当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位（bit）来表示，而z则可能花去25个位（不是26）。
用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。
二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。
倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。
本文描述在网上能够找到的最简单，最快速的哈夫曼编码。
本方法不使用任何扩展动态库，比如STL或者组件。
只使用简单的C函数，比如：
memset，memmove，qsort，malloc，realloc和memcpy。
因此，大家都会发现，理解甚至修改这个编码都是很容易的。
哈弗曼编码在信息论中应用举例
[1]
哈弗曼编码在信息论中应用举例
编辑本段背景
哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。
哈夫曼压缩属于可变代码长度算法一族。
意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。
因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。
编辑本段编码使用
我用简单的C函数写这个编码是为了让它在任何地方使用都会比较方便。
你可以将他们放到类中，或者直接使用这个函数。
并且我使用了简单的格式，仅仅输入输出缓冲区，而不象其它文章中那样，输入输出文件。
boolCompressHuffman（BYTE*pSrc,intnSrcLen,BYTE*&pDes,int&nDesLen）;
boolDecompressHuffman（BYTE*pSrc,intnSrcLen,BYTE*&pDes,int&nDesLen）;
编辑本段要点说明
速度
为了让它（huffman.cpp）快速运行，同时不使用任何动态库，比如STL或者MFC。
它压缩1M数据少于100ms（P3处理器，主频1G）。
压缩
压缩代码非常简单，首先用ASCII值初始化511个哈夫曼节点：
CHuffmanNodenodes[511];
for（intnCount=0;nCount<256;nCount++）
nodes[nCount].byAscii=nCount;
其次，计算在输入缓冲区数据中，每个ASCII码出现的频率：
for（nCount=0;nCount nodes[pSrc[nCount]].nFrequency++;
然后，根据频率进行排序：
qsort（nodes,256,sizeof（CHuffmanNode）,frequencyCompare）;
现在，构造哈夫曼树，获取每个ASCII码对应的位序列：
intnNodeCount=GetHuffmanTree（nodes）;
构造哈夫曼树
构造哈夫曼树非常简单，将所有的节点放到一个队列中，用一个节点替换两个频率最低的节点，新节点的频率就是这两个节点的频率之和。
这样，新节点就是两个被替换节点的父节点了。
如此循环，直到队列中只剩一个节点（树根）。
//parentnode
pNode=&nodes[nParentNode++];
//popfirstchild
pNode->pLeft=PopNode（pNodes,nBackNode--,false）;
//popsecondchild
pNode->pRight=PopNode（pNodes,nBackNode--,true）;
//adjustparentofthetwopopednodes
pNode->pLeft->pParent=pNode->pRight->pParent=pNode;
//adjustparentfrequency
pNode->nFrequency=pNode->pLeft->nFrequency+pNode->pRight->nFrequency;
构造哈夫曼树注意事项
这里我用了一个好的诀窍来避免使用任何队列组件。
我先前就知道ASCII码只有256个，但我分配了511个（CHuffmanNodenodes[511]），前255个记录ASCII码，而用后255个记录哈夫曼树中的父节点。
并且在构造树的时候只使用一个指针数组（ChuffmanNode*pNodes[256]）来指向这些节点。
同样使用两个变量来操作队列索引（intnParentNode=nNodeCount;nBackNode=nNodeCount–1）。
接着，压缩的最后一步是将每个ASCII编码写入输出缓冲区中：
intnDesIndex=0;
//looptowritecodes
for（nCount=0;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值添加到输出缓冲区中：
intnDesIndex=0;
DWORDnCode;
while（nDesIndex {
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;
}
编辑本段程序实现
c语言实现:
费诺编码
#include
#include
#include
#include
#defineM100
typedefstructFano_Node
{
charch;
floatweight;
}FanoNode[M];
typedefstructnode
{
intstart;
intend;
structnode*next;
}LinkQueueNode;
typedefstruct
{
LinkQueueNode*front;
LinkQueueNode*rear;
}LinkQueue;
//建立队列
voidEnterQueue（LinkQueue*q,ints,inte）
{
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）;
}
}
//按权分组
voidDivide（FanoNodef,ints,int*m,inte）
{
inti;
floatsum,sum1;
sum=0;
for（i=s;i<=e;i++）
sum+=f[i].weight;//
*m=s;
sum1=0;
for（i=s;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;
}
}
voidmain（）
{
inti,j,n,max,m,h[M];
intsta,end;
floatw;
charc,fc[M][M];
FanoNodeFN;
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（"Pleaseinputthenumberofnode:
"）;
//输入信息
scanf（"%d",&n）;
//超过定义M,退出
if（n>=M）
{
printf（">=%d",M）;
exit（-1）;
}
i=1;//从第二个元素开始录入
while（i<=n）
{
printf（"%dweightandnode:
",i）;
scanf（"%f%c",&FN[i].weight,&FN[i].ch）;
for（j=1;j {
if（FN[i].ch==FN[j].ch）//查找重复
{
printf（"Samenode!
!
!
\n"）;break;
}
}
if（i==j）
i++;
}
//排序（降序）
for（i=1;i<=n;i++）
{
max=i+1;
for（j=max;j<=n;j++）
max=FN[max].weightj:
max;
if（FN[i].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"）;
}
c语言实现:
huffman编码解码
#include
#include
#include
#defineN100
#defineM2*N-1
typedefchar*HuffmanCode[2*M];//haffman编码
typedefstruct
{
intweight;//权值
intparent;//父节节点
intLChild;//左子节点
intRChild;//右子节点
}HTNode,Huffman[M+1];//huffman树
typedefstructNode
{
intweight;//叶子结点的权值
charc;//叶子结点
intnum;//叶子结点的二进制码的长度
}WNode,WeightNode[N];
/***产生叶子结点的字符和权值***/
voidCreateWeight（charch[],int*s,WeightNodeCW,int*p）
{
inti,j,k;
inttag;
*p=0;//叶子节点个数
//统计字符出现个数,放入CW
for（i=0;ch[i]!
='\0';i++）
{
tag=1;
for（j=0;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********/
voidCreateHuffmanTree（Huffmanht,WeightNodew,intn）
{
inti,j;
ints1,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;//权值累加
}
}
/***********叶子结点的编码***********/
voidCrtHuffmanNodeCode（Huffmanht,charch[],HuffmanCodeh,WeightNodeweight,intm,intn）
{
inti,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"）;
}
/*********所有字符的编码*********/
voidCrtHuffmanCode（charch[],HuffmanCodeh,HuffmanCodehc,WeightNodeweight,intn,intm）
{
inti,k;
for（i=0;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]）;//拷贝二进制编码
}
}
/*****解码*****/
voidTrsHuffmanTree（Huffmanht,WeightNodew,HuffmanCodehc,intn,intm）
{
inti=0,j,p;
print
升级会员 