霍夫曼编码计算过程：无损数据压缩的熵编码。
在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而改凯腊达到无损压缩数据的目的。
例如，在英文中，e的出现机率最高，而z的出现概率则最低。当利用霍夫曼编码对一篇英文进行压缩时，e极有可能用一个比特来表示，而z则可能花去25个比特（不是26）。用普通的表示方法时，每个英文字母均占用一个字节，即8个比核滑特。
二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。
霍夫曼编码历史：
1951年，霍夫曼在麻省理工学院（MIT）攻读博士学位，他和修读信息论课程的同学得选择是完成学期报告还是期末考试。导师罗伯特·法诺（Robert Fano）出的学期报孙敏告题目是：查找最有效的二进制编码。
由于无法证明哪个已有编码是最有效的，霍夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。霍夫曼使用自底向上的方法构建二叉树，避免了次优算法香农-范诺编码（Shannon–Fano coding）的最大弊端──自顶向下构建树。
1952年，于论文《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Redundancy Codes）中发表了这个编码方法。
以前写的，证明最优子结构，随便一本算法书上就有.#include<stdio.h>
#include<stdlib.h>
#define
NIL
-2
#define
Size_Max_bm
30
#define
left(i)
(2*(i)+1)
#define
right(i)
(2*(i)+2)
#define
swap(a,b)
{cjys
tt=(a)(a)=(b)(b)=t}
#define
parent(i)
((i)%2?((i)-1)/2:((i)-2)/2)typedef
struct
cjys
{
char
sj
int
pl
struct
cjys
*left
struct
cjys
*right
}cjystypedef
struct
cjdl
{
int
size
int
leapsize
cjys
*p
}cjdl
cjys
*fpnn(void)
void
input(cjdl
*p)
cjys
*fpnn(void)
void
zxdwh(cjys
*p,
int
i,
int
leapsize)
void
rd(cjdl
*p,
cjys
tp)
cjys
cd(cjdl
*p)
void
hbs(cjdl
*p)
cjys
*cjs(cjdl
*p)
void
bls(cjys
*p,int
*jl,
int
i)
void
disp(char
*tp,
cjys
*p)int
main()
{
cjdl
p
char
x[255]
cjys
*re=NULL
int
jl[Size_Max_bm]
input(&p)
re=cjs(&p)
printf("对照编码图为:\n")
bls(re,jl,0)
freopen("CON","r",stdin)
printf("输入Huffman码(VLC):")
scanf("%s",x)
disp(x,re)
system("pause")
}
void
input(cjdl
*p)
{
int
i
cjys
*tp
tp=fpnn()
printf("输入字母个数:")
scanf("%d",
&p->size)
p->p=malloc(sizeof(cjys)*p->size)
p->leapsize=0
for(i
=
0
i
<
p->sizei++)
{
printf("输入第%d字母:",i+1),scanf("
%c",&tp->sj)
printf("输入出现次数(频率整数):"),scanf("%d",&tp->pl)
rd(p,*tp)
}
free(tp)
}
cjys
*fpnn(void)
{
cjys
*p=NULL
p=malloc(sizeof(cjys))
p->left=NULL
p->right=NULL
return
p
}
void
zxdwh(cjys
*p,
int
i,
int
leapsize)
{
int
l=left(i),
r=right(i),
mini=i
if(l<leapsize
&&
p[l].pl<p[mini].pl)
mini=l
if(r<leapsize
&&
p[r].pl<p[mini].pl)
mini=r
if(mini
!=
i)
{
swap(p[i],p[mini])
zxdwh(p,mini,leapsize)
}
}
void
rd(cjdl
*p,
cjys
tp)
{
if(p->leapsize
==
p->size)
{
printf("队列已满!")
exit(0)
}
p->p[p->基枣leapsize]=tp
int
j=p->leapsize,k=parent(j)
while(k>=0
&&
p->p[j].pl
<
p->p[k].pl)
{
swap(p->p[j],p->p[k])
j=k
k=parent(j)
}
p->御裤leapsize++
}
cjys
cd(cjdl
*p)
{
if(p->leapsize
==
0)
{
printf("队列搏拆拆已空!")
exit(0)
}
cjys
tp=p->p[0]
p->leapsize--
p->p[0]=p->p[p->leapsize]
zxdwh(p->p,0,p->leapsize)
return
tp
}
void
hbs(cjdl
*p)
{
cjys
*p1=NULL,
*p2=NULL
cjys
tp
p1=fpnn()
p2=fpnn()
*p1=cd(p)
*p2=cd(p)
tp.left=p1
tp.right=p2
tp.pl=p1->pl+p2->pl
tp.sj=NIL
rd(p,tp)
}cjys
*cjs(cjdl
*p)
{
int
i,
n=p->leapsize
cjys
*tp=NULL
tp=fpnn()
for(i
=
0
i
<
n-1
i++)
hbs(p)
*tp=p->p[0]
return
tp
}
void
bls(cjys
*p,
int
*jl,
int
i)
{
if(p
==
NULL)
return
if(p->sj!=NIL)
{
int
i2
printf("%c:",p->sj)
for(i2
=
0
i2
<
i
i2++)
printf("%d",jl[i2])
printf("\n")
}
jl[i]=0
bls(p->left,jl,i+1)
jl[i]=1
bls(p->right,jl,i+1)
}
void
disp(char
*tp,
cjys
*p)
{
cjys
*ttp=NULL
int
pd=0
while(1)
{
ttp=p
while(1)
{
if(ttp->sj
!=
NIL)
{
printf("%c",ttp->sj)
break
}
if(*tp
==
'\0')
{
pd=1
break
}
if(*tp++
==
'0'
)
ttp=ttp->left
else
ttp=ttp->right
}
if(pd)
break
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）