霍夫曼编码计算过程

霍夫曼编码计算过程：无损数据压缩的熵编码。

在计算机数据处理中，霍夫曼编码使用变长编码表对源符号（如文件中的一个字母）进行编码，其中变长编码表是通过一种评估来源符号出现机率的方法得到的，出现机率高的字母使用较短的编码，反之出现机率低的则使用较长的编码，这便使编码之后的字符串的平均长度、期望值降低，从而改凯腊达到无损压缩数据的目的。

例如，在英文中，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）中发表了这个编码方法。

这梁租弊个是一个简单的，没有文件导入，需要编码的是自己输入的数组，你将它换成文件读取基本就可以实现对文章中的字符进行Huffman编码，这是我自己曾经做的一个程序，是VC6.0的,没有解码部分，解码部分你反过来推一下算法然后编一下代码就可以了。我还型局有一个是文件是用matlab作的huffman编码，你要的话给我邮箱，我给你发过去。

#include<iostream.h>

#include<string.h>

#define N 100

typedef struct

{

int wei //权值

int prt //父节点

int lch //左子节点

int rch// 右子节点

int tmp //中间变量，tmp=0 还未进行遍历 tmp=1 已近进行过向左遍历 tmp=2 已经进行过左右遍历 向上找到节点

char code[N]

}huffmantree

void input()

void print(huffmantree )

void select(huffmantree *HT,int n,int &i,int &j)

{

int k

i=1

while(HT[i].prt!=0)

{

i++

}

for(k=i+1k<=nk++)

{

if((HT[k].prt=0)&&(HT[k].wei <HT[i].wei))

i=k

}

j=1

while((j==i)||(HT[j].prt!=0))

{

j++

}

for(k=j+1k<=nk++)

{

if((HT[k].prt=0)&&k!=i&&HT[k].wei<HT[j].wei)

j=k

}

}

void huffman(int w[],huffmantree *HT,int n) //w存放n个字符的权值

{

int m=2*n-1

int i,k,j

huffmantree *p=0

for(p=HT+1,i=1i<=mi++,p++)

{

HT[i].prt=0

HT[i].lch=0

HT[i].rch=0

}

for(p=HT+1,i=1i<=ni++,p++)

{

HT[i].wei=w[i-1]

}

for(p=HT+n+1,i=n+1i<=mi++,p++)

{ HT[i].wei=0}

for(k=n+1k<=mk++)

{

select(HT,k-1,i,j) // 找最小值和次小值的位置

HT[i].prt=k,HT[j].prt=k // 找到i j 的父节点付给k

HT[k].lch=i,HT[k].rch=j // 父节点的左右指针分别指向i, j

HT[k].wei=HT[i].wei+HT[j].wei

}

}

void huffmancoding(huffmantree *HT,int n) //n个叶子结点的huffman编码 从根节点开始编码橡族

{

int BT=2*n-1

int m=BT

int l,r,p

char s1[100]="0",s2[100]="1"

for(int i=0i<=mi++)//中间变量赋初值

{ HT[i].tmp=0 }

strcpy(HT[m].code," ")

while(1)

{

l=HT[BT].lch

r=HT[BT].rch

p=HT[BT].prt

if(p==0&&HT[BT].tmp==2)

break

if(l==0||r==0)

{

HT[BT].tmp=2//如果是叶子结点则给中间变量赋值2向上返回一节结点

}

if(HT[BT].tmp==0) //未进行过遍历，开始向左遍历

{

HT[BT].tmp=1 //已经进行过向左遍历

l=HT[BT].lch

strcpy(HT[l].code,HT[BT].code)

strcat(HT[l].code,s1)

BT=l

}

else

if(HT[BT].tmp==1)

{

HT[BT].tmp=2

r=HT[BT].rch

strcpy(HT[r].code,HT[BT].code)

strcat(HT[r].code,s2)

BT=r

}

else if(HT[BT].tmp==2)

{

p=HT[BT].prt

BT=p

}

}

}

void print(huffmantree HT[],int n) //总共n个叶子节点

{

int i

cout<<"源码："<<endl

for(i=1i<=ni++)

cout<<HT[i].wei<<endl

cout<<"Huffman编码："<<endl

for(i=1i<=ni++)

{

cout<<HT[i].code<<endl

}

}

void input(int w[],int n)

{

int t,*p

int i=0

cout<<"对应的输入源码出现权值：(以-1结束)"<<endl

cin>>t

while(t>=0)

{

p=new int

*p=t

w[i]=*p

i++

cin>>t

}

}

void main()

{

int n,m

cout<<"输入源码个数："

cin>>n

int *w

w=new int[n+1]

input(w,n)

m=2*n-1

huffmantree *HT

HT=new huffmantree[m+1]

huffman(w,HT,n)

huffmancoding(HT,n)

print(HT,n)

delete w,HT

}

以前写的，证明最优子结构，随便一本算法书上就有.

#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

}

}

---