计算机科学与工程系
一、实验名称：霍夫曼编码
二、实验环境
软件环境：Windows 2000，Microsoft Visual C++6.0
硬件环境：P4，2.4GHz，256内存，IBM-PC及兼容机
三、实验目的
掌握霍夫曼编码、译码原理，并能够通过程序模拟其编码、译码功能。
四、实验原理
1、消息按其出现的概率由大到小地排成一个概率序列；
2、把概率最小两个消息分成一组，其中一个消息编为0，另一个编为1，然后求其概率和，并把这个新概率与其他尚未处理过的概率重新按概率由大到小排成一个新的概率序列；
3、重复步骤，直到所有概率都已联合处理完为止。
五、实验过程与实验结果
源程序：
#include<iostream>
#include<string>
using namespace std;
#include<math.h>
typedef struct{//霍夫曼树的结构体
char ch;
double weight; //权值，此处为概率
int parent,lchild,rchild;
}htnode,*hfmtree;
typedef char **hfmcode;
/*****************************全局变量*****************************/ hfmtree HT;
hfmcode HC;
int n=0;//霍夫曼树叶节点个数
int m=0;//霍夫曼树所有节点个数
int *code_length;//用于记录每个消息字符的码长
/*****************************霍夫曼编码模块*****************************/
//对输入的字符进行检验
int Input_Char_Check()
{
int flag=1;
int j;
for(int i=1;i<n&&flag;i++)
{
for(j=i+1;j<=n;j++)
if(HT[j].ch==HT[i].ch)
{
flag=0;
break;
计算机科学与工程系
}
}
return flag;
}
//对输入的概率进行检测
int Input_Weight_Check(){
int flag=0;
double sum=0.0;
for(int i=1;i<=n;i++)
{
if(!(HT[i].weight>0&&HT[i].weight<1))//概率越界
{
flag=1;
return flag;
}
else{
sum+=HT[i].weight;
continue;
}
}
if(sum>1)//概率之和超过1
{
flag=2;
}
return flag;
}
void Select(int a,int *p1,int *p2)
/*Select函数，选出HT树到a为止，权值最小和次小且parent为0的2个节点*/
{
int i,j,x,y;
for(j=1;j<=a;++j){
if(HT[j].parent==0){
x=j;
break;
}
}
for(i=j+1;i<=a;++i){
if(HT[i].weight<HT[x].weight&&HT[i].parent==0){
x=i; //选出权值最小的节点
}
}
for(j=1;j<=a;++j) {
if(HT[j].parent==0&&x!=j)
2
计算机科学与工程系
{
y=j;
break;
}
}
for(i=j+1;i<=a;++i)
{
if(HT[i].weight<HT[y].weight&&HT[i].parent==0&&x!=i) {
y=i; //选出权值次小的节点 }
}
if(x>y){
*p1=y;
*p2=x;
}
else
{
*p1=x;
*p2=y;
}
}
/*初始化n个叶子节点及其余节点*/
void Init_htnode()
{
int i;
char temp_ch;
double temp_w;
I: cout<<"请输入信源发出的消息字符个数：";
cin>>n;
if(sizeof(n)!=sizeof(int)||n<=1)//若输入的不是整数，则报错 {
cout<<"您输入的数据有误，程序终止!"<<endl; exit(0);
}
code_length=new int[n+1];
for(i=1;i<=n;i++){
code_length[i]=0;//初始化码长为0
}
m=2*n-1;
HT=(hfmtree)malloc((m+1)*sizeof(htnode));
for(i=1;i<=n;++i) //初始化n个叶子结点 {
printf("请输入第%d个字符信息：",i);
3
计算机科学与工程系
cin>>temp_ch;
printf("请输入第%d个字符对应的概率：",i);
cin>>temp_w;
HT[i].ch=temp_ch;
HT[i].weight=temp_w;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
int flag1=Input_Char_Check();//检测输入的字符是否重复 int flag2=Input_Weight_Check();//检测输入的概率是否越界 if(!flag1)
{
cout<<"出现相同字符，输入错误，请重新输入!"<<endl; goto I;
}
if(flag2==1)
{
cout<<"概率越界，输入错误，请重新输入!"<<endl; goto I;
}
if(flag2==2)
{
cout<<"概率之和超过1，输入错误，请重新输入!"<<endl; goto I;
}
for(;i<=m;++i) //初始化其余的结点
{
HT[i].ch='*';//用*表示新生成根节点的字符域
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
}
//建立霍夫曼树
void Create_hfmtree()
{
int i;
int p1,p2;//用于记录权值最小及次小节点的下标
for(i=n+1;i<=m;++i) //建立霍夫曼树
{
Select(i-1,&p1,&p2);
HT[p1].parent=i;HT[p2].parent=i;
4
计算机科学与工程系
HT[i].lchild=p1;HT[i].rchild=p2;
HT[i].weight=HT[p1].weight+HT[p2].weight;
}
}
void Hfm_coding() //求出n个字符的霍夫曼编码HC及码长
{
int i,start;
int c;//当前字符下标
int f;//当前字符的父节点下标
char *cd;
HC=(hfmcode)malloc((n+1)*sizeof(char *));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i<=n;++i) //给n个字符编码
{
start=n-1;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
{
if(HT[f].lchild==c)
{
cd[--start]='0';
}
else
{
cd[--start]='1';
}
code_length[i]+=1;
}
HC[i]=(char*)malloc((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
}
free(cd);
}
//初始化
/*功能：从终端读入字符集大小n，以及n个字符和n个权值，建立霍夫曼树，并将它存于文件hfmTree中。*/
int Initialization()
{
Init_htnode();
Create_hfmtree();
Hfm_coding();
return 0;
}
5
计算机科学与工程系
/*****************************编码效率分析模块*****************************/
//求平均编码长度
double Ave_Code_Length()
{
double Ave_L=0.0;
for(int i=1;i<=n;i++)
Ave_L+=code_length[i]*HT[i].weight;
return Ave_L;
}
//求信源熵
double To_Get_H()
{
double H=0.0;
for(int i=1;i<=n;i++)
H+=-1*HT[i].weight*log(HT[i].weight)/log(2);
return H;
}
//求编码效率
double To_Get_Code_Efficiency()
{
double H2,H,Ave_L;
H=To_Get_H();
Ave_L=Ave_Code_Length();
H2=H/Ave_L;
return H2;
}
//分析结果输出
void Output()
{
double H2,H,Ave_L;
H=To_Get_H();
Ave_L=Ave_Code_Length();
H2=To_Get_Code_Efficiency();
cout<<"霍夫曼编码结果如下:（消息字符——码长——码字）"<<endl; for(int i=1;i<=n;i++)
cout<<HT[i].ch<<"——>"<<code_length[i]<<"——>"<<HC[i]<<endl;
cout<<"平均编码长度Ave_L=L1*p1+L2*p2+...+Ln*pn="<<Ave_L<<"（码元/消息）"<<endl;
cout<<"信源熵H=-（p1*log(p1)+p2*log(p2)+...+pn*log(pn)）/log(2)="<<H<<"（bit/消息）"<<endl;
cout<<"码元熵H2=H/Ave_L="<<H2<<"（bit/码元）"<<endl;
cout<<"编码效率E=（H2/H2max）*100%="<<H2*100<<"%"<<endl; }
6
计算机科学与工程系
/*****************************编码模块*****************************/ //字符串合理性检测
int Message_Str_Check(string temp)
{
int flag=1;//先假设输入的消息串不含非法字符
int j;
for(int i=0;temp[i]!='\0';i++){
for(j=1;j<=n;j++)
{
if(temp[i]==HT[j].ch)
break;
}
if(j>n)//表示出现非法字符
{
flag=0;
break;
}
}
return flag;
}
//获取待编码消息串
string Get_Message_Str()
{
string temp;
int flag;
A: cout<<"输入待编码的消息串:\n";
cin>>temp;
flag=Message_Str_Check(temp);
if(flag==0)//输入的消息串含非法字符
{
cout<<"输入的消息串含非法字符,请重新输入!"<<endl;
goto A;
}
return temp;
}
//对输入的消息串进行编码
string Get_All_Code_Str(string Message_Str)
{
string All_Code_Str="";
int j;
for(int i=0;Message_Str[i]!='\0';i++)
for(j=1;j<=n;j++)
{
if(Message_Str[i]==HT[j].ch)
7
计算机科学与工程系
{
All_Code_Str+=HC[j];
break;
}
}
return All_Code_Str;
}
//输出得到的二进制序列
void Output_All_Code_Str(string All_Code_Str)
{
cout<<"该消息串对应的编码序列如下:"<<endl;
cout<<All_Code_Str<<endl;
}
//编码
void Encoding()
{
string Message_Str,All_Code_Str;
Message_Str=Get_Message_Str();
All_Code_Str=Get_All_Code_Str(Message_Str);
Output_All_Code_Str(All_Code_Str);
}
/**********************译码模块**********************/ //检测输入的二进制序列是否含有非法字符
int Binary_Str_Check(string temp)
{
int flag=1;//假设不含非法字符
for(int i=0;temp[i]!='\0';i++)
{
if(!(temp[i]=='0'||temp[i]=='1'))
{
flag=0;
break;
}
}
return flag;
}
//获取待译的二进制序列
string Get_Binary_Str()
{
string temp;
int flag;
B: cout<<"输入待译的二进制序列:\n";
cin>>temp;
flag=Binary_Str_Check(temp);
8
计算机科学与工程系
if(flag==0)//输入的二进制序列含非法字符
{
cout<<"输入的二进制序列含非法字符,请重新输入!"<<endl; goto B;
}
return temp;
}
//获取源码
string Get_Original_Message_Str(string Binary_Str,int *flag) {
string temp="";
*flag=1;
string Original_Message_Str="";
int j;
for(int i=0;Binary_Str[i]!='\0';i++){
temp+=Binary_Str[i];
for(j=1;j<=n;j++)
{
if(HC[j]==temp)
{
Original_Message_Str+=HT[j].ch;
temp="";//重置temp
break;
}
}
}
if(temp!=""){
cout<<"您输入的二进制序列不可译，请重新输入!"<<endl; *flag=0;
}
return Original_Message_Str;
}
//输出得到的源码
void Output_Original_Message_Str(string Original_Message_Str) {
cout<<"该二进制序列对应的源码如下:"<<endl;
cout<<Original_Message_Str<<endl;
}
//译码
void Decoding()
{
int flag;
string Binary_Str,Original_Message_Str;
D: Binary_Str=Get_Binary_Str();
9
计算机科学与工程系
Original_Message_Str=Get_Original_Message_Str(Binary_Str,&flag);
if(!flag)
goto D;
Output_Original_Message_Str(Original_Message_Str);
}
/*****************************主函数*****************************/
int main(){
char choice=' ';
/*用于记录初始化情况*/
int flag=0;
cout<<"\n";
while(choice!='Q'&&choice!='q')//当choice的值不为q且不为Q时循环
{
C: cout<<" "<<"*************************霍夫曼编码/译码器*************************\n";
cout<<" "<<"I.输入建立"<<" "<<"E.编码"<<" "<<"D.译码"<<" "<<"Q.退出\n";
cout<<"请输入您要操作的步骤：";
cin>>choice;
if(choice=='I'||choice=='i')//初始化霍夫曼树
{
if(!flag){//初次执行初始化操作
flag=1;
}
Initialization();
Output();
}
else if(choice=='E'||choice=='e')//进行编码
{
if(!flag)
{
cout<<"操作错误!请执行输入建立操作后再进行本操作!"<<endl; goto C;
}
Encoding();
}
else if(choice=='D'||choice=='d')//译码
{
if(!flag)
{
cout<<"操作错误!请执行输入建立操作后再进行本操作!"<<endl; goto C;
}
10
计算机科学与工程系
Decoding();
}
else if(choice=='Q'||choice=='q')//退出程序
{
exit(0);
}
else//如果选了选项之外的就让用户重新选择
{
cout<<"您没有输入正确的步骤，请重新输入！"<<endl;
goto C;
}
cout<<endl;
}
return 0;
}
运行结果：
1、输入消息及其相应概率，建立霍夫曼编码树，并打印输出编码效率分析结果
2、编码：输入的消息字符串中应只含信源能够发出的几个字符，否则，报错
11
计算机科学与工程系
3、译码：注意区分可译序列和不可译序列
4、退出
12