实验一
无失真信源编码
一、实验目的与要求
1. 理解并掌握无失真信源编码定理的内容及支撑理论； 2. 掌握唯一可译码的含义及判断方法； 3. 掌握赫夫曼码的数学基础、编码原理与实现技术； 4. 掌握二进制、三进制赫夫曼码的编码方法与结果分析； 5. 基于 Visual C++环境使用面向对象方法设计赫夫曼编码软件。
二、实验仪器与设备
1. 微型电子计算机
80 台 2. Windows 2000 以上版本操作系统
80 套 3. Visual C++ 6.0 开发系统
80 套 三、实验内容与步骤
（一）二进制赫夫曼编码 使用以下两种不同的方法编写二进制赫夫曼码：
·信源合并后的新符号排在其它相同概率的符号的前面； ·合并后的新符号排在其它相同概率的符号的后面。
具体要求：
1.使用 Visual C++6.0 开发环境，应用面向对象的程序设计模式，编写 CHuffman_2 类，并根据具体要求，添加必须的数据成员和成员函数； 2.分别求出两种编码方法下的平均码长、信息率和编码效率，并分析实际中应选择哪种编码方法； 3.添加成员函数 IsUniDecodableCdoe()，以判断赫夫曼码是否唯一可译码； 4.添加成员函数 IsCodingwithoutDistoryion()，以判断赫夫曼码是否满足无失真编码定理； 5.用户可以随机输入多个心愿符号信息，并在主函数中至少测试两组数据，并显示有关结果信息。
（二）三进制赫夫曼编码 与上述步骤类似，设计 CHuffman_3 类，编写三进制赫夫曼码。要求使用相同的测试数据，并比较平均码长、信息率及编码效率等，给出自己的思考结论。
（三）m m 进制赫夫曼编码 设计 CHuffman_m 类，编写 m 进制赫夫曼码。m 在运行时由用户输入。其它要求同上。
综合实验代码及分析：
#include <iostream.h> #include <math.h> #include <string.h> #include <stdio.h> #include <stdlib.h> #include <vector>
using namespace std;
#define MAX 10
//输入进制，最多 10 进制 struct Huffman_InformationSource
//信源类型
{
char InformationSign[10];
//信源符号
double Probability;
//概率
char Code[20];
//编码结果
int CodeLength;
//码长 }; struct HuffNode
//赫夫曼树的节点类型 {
char InformationSign[10];
double Probability;
HuffNode *Subtree[MAX];
//子树
HuffNode *Next;
char Code[20];
int CodeLength; }; class CHuffman_m
//赫夫曼编码 { public:
CHuffman_m(int M)
//初始化
{
m=M;
ISNumber=0;
AvageCodeLength=0.0;
InformationRate=0.0;
CodeEfficiency=0.0;
}
~CHuffman_m()
{ //
DestroyBTree(HuffTree);
}
void Huffman_Input();
//输入信息
void Huffman_Sort();
//排序
void Huffman_Tree();
//构造赫夫曼树
void Huffman_Coding();
//生成赫夫曼编码
void Huffman_CodeAnalyzing();
//结果分析
void Huffman_Display();
//显示结果信息
void DestroyBTree(HuffNode *TreePointer); //释放资源 private:
vector<Huffman_InformationSource>ISarray; //声明 ISarray 数组，初始时为空
int ISNumber;
//符号个数
double AvageCodeLength;
//平均码长
double InformationRate;
//信息率
double CodeEfficiency;
//编码效率
int m;
// m 进制
HuffNode * HuffTree;
//赫夫曼树 private:
void Huffman_Code(HuffNode *TreePointer); };
//输入信源信息 void CHuffman_m::Huffman_Input() {
int n,i,j;
double sum=0;
cout<<"请输入信源符号个数:
";
cin>>n;
cout<<"请信源符号和概率:
"<<endl;
for(i=0;i<n;i++)
{
Huffman_InformationSource temp;
cin>>temp.InformationSign;
cin>>temp.Probability;
strcpy(temp.Code,"");
temp.CodeLength=0;
ISarray.push_back(temp);
ISNumber=ISarray.size();
}
for(j=0;j<ISarray.size();j++)
sum+=ISarray[j].Probability;
if(sum==1)
return;
else
{
cout<<"\a\a\a 概率和不为 1！请重新输入"<<endl;
ISarray.clear();
CHuffman_m::Huffman_Input();
} } //按概率"从大到小"排序：
void CHuffman_m::Huffman_Sort() {
Huffman_InformationSource temp;
int i,j;
for(i=0;i<ISNumber-1;i++)
for(j=i+1;j<ISNumber;j++)
if(ISarray[i].Probability<ISarray[j].Probability)
{
temp=ISarray[i];
ISarray[i]=ISarray[j];
ISarray[j]=temp;
}
} //基于 ISarray 数组构造赫夫曼树 void CHuffman_m::Huffman_Tree() {
int i,j;
HuffNode *ptr1,*ptr2;
//（1）：基于数组，创建单向链表
ptr1=new HuffNode;
strcpy(ptr1->InformationSign,ISarray[0].InformationSign);
ptr1->Probability=ISarray[0].Probability;
strcpy(ptr1->Code,ISarray[0].Code);
for(j=0;j<m;j++)
//初始化子树
ptr1->Subtree[j] =NULL;
ptr1->Next=NULL;
HuffTree=ptr1;
//赋给数据成员 HuffTree
for(i=1;i<ISNumber;i++)
{
ptr2=new HuffNode;
strcpy(ptr2->InformationSign,ISarray[i].InformationSign);
ptr2->Probability=ISarray[i].Probability;
strcpy(ptr2->Code,ISarray[i].Code);
for(j=0;j<m;j++)
//初始化子树
ptr2->Subtree[j] =NULL;
ptr2->Next=ptr1;
ptr1=ptr2;
}
//结果：链表的表头为数组的最小元素。
HuffTree=ptr1;
//使 HuffTree 指向链表头
//（2）：基于链表，构造赫夫曼树
int k;
//树的层次
int s;
//需要添加的无用符号的数目。参看教材 P140-150。
k=ceil((double)(ISNumber-m)/(m-1));//"m"：表示 m 进制
//ceil 函数：向上取整；
//floor 函数：向下取整
s=m+k*(m-1)-ISNumber;
HuffNode *ptr4,*temp1,*temp2;
if(s!=0)
//第一次取 m-s 个符号
{
ptr4=new HuffNode;
strcpy(ptr4->InformationSign,"*"); //新节点的符号为"*"
ptr2=ptr1;
ptr4->Probability=0;
for(j=0;j<m-s;j++)
{
ptr4->Probability+=ptr2->Probability;
ptr4->Subtree[m-s-j-1]=ptr2;
//最小节点成为 ptr4 的"第 m-s-1 个子树"，将来赋予码元"m-s-1"
ptr2=ptr2->Next;
}
for(j=m-s;j<m;j++)
ptr4->Subtree[j] =NULL;
strcpy(ptr4->Code,"");
HuffTree=ptr2;
//重新排序：
temp1=HuffTree;
while(temp1&&(ptr4->Probability>temp1->Probability))
{
temp2=temp1;
temp1=temp1->Next;
}
ptr4->Next=temp1;
//插在当前节点 temp1 之前
if(temp1==HuffTree)
HuffTree=ptr4;
else
temp2->Next=ptr4; //插在 temp2 节点之后
ptr1=HuffTree;
}
while(ptr1->Next)
{
//合并概率最小的 m 个节点，生成一个新节点 ptr4：
ptr4=new HuffNode;
strcpy(ptr4->InformationSign,"*"); //新节点的符号为"*"
ptr4->Probability=0;
ptr2=ptr1;
for(j=0;j<m;j++)
{
ptr4->Probability+=ptr2->Probability;
ptr4->Subtree[m-j-1]=ptr2;
//最小节点成为 ptr4 的"第 m-1 个子树"，将来赋予码元"m-1"
ptr2=ptr2->Next;
}
strcpy(ptr4->Code,"");
HuffTree=ptr2;
//重新排序：
temp1=HuffTree;
while(temp1&&(ptr4->Probability>temp1->Probability))
{
temp2=temp1;
temp1=temp1->Next;
}
ptr4->Next=temp1;
//插在当前节点 temp1 之前
if(temp1==HuffTree)
HuffTree=ptr4;
else
temp2->Next=ptr4; //插在 temp2 节点之后
ptr1=HuffTree;
}
//释放：
ptr1=NULL;
ptr2=NULL;
ptr4=NULL;
temp1=NULL;
temp2=NULL;
//设置根节点：
strcpy(HuffTree->Code,"");
HuffTree->CodeLength=0; } //生成赫夫曼码：
void CHuffman_m::Huffman_Code(HuffNode *TreePointer) {
if (TreePointer == NULL)
return;
int i;
for(i=0;i<m;i++)
if(TreePointer->Subtree[i])
break;
if(i==m) //如果所有子树均为 NULL
{
for(int i=0;i<ISNumber;i++)
if(strcmp(ISarray[i].InformationSign,TreePointer->InformationSign)==0)
{
strcpy(ISarray[i].Code,TreePointer->Code);
ISarray[i].CodeLength=TreePointer->CodeLength;
return;
}
return;
}
for(i=0;i<m;i++)
{
if(TreePointer->Subtree[i])
{
//生成子树编码：
char tempch[5],tempstr[10]="";
strcpy(tempstr,TreePointer->Code);
itoa(i,tempch,10); //将 10 进制整数 i 转换为字符串，保存在 tempch 中。
strcat(tempstr,tempch);
strcpy(TreePointer->Subtree[i]->Code,tempstr);
TreePointer->Subtree[i]->CodeLength=TreePointer->CodeLength+1;
Huffman_Code(TreePointer->Subtree[i]);
}
} } void CHuffman_m::Huffman_Coding() {
Huffman_Code(HuffTree); } //编码结果分析 void CHuffman_m::Huffman_CodeAnalyzing() {
//(1):平均码长
for(int i=0;i<ISNumber;i++)
AvageCodeLength+=ISarray[i].Probability*ISarray[i].CodeLength;
//(2):信息率
int L=1;
//单符号时，L=1
InformationRate=AvageCodeLength/L*(log(m)/log(2));
//(3):编码效率
double Hx=0;
for(int j=0;j<ISNumber;j++) //求信源熵
Hx+=-ISarray[j].Probability*log(ISarray[j].Probability)/log(2);
CodeEfficiency=Hx/InformationRate; } //显示结果 void CHuffman_m::Huffman_Display() {
cout<<"编码结果："<<endl;
for(int i=0;i<ISNumber;i++)
{
cout<<"\""<<ISarray[i].InformationSign<<"\""<<":
"<<ISarray[i].Code<<endl;
}
cout<<endl;
cout<<"平均码长："<<AvageCodeLength<<endl<<endl;
cout<<"信息率
："<<InformationRate<<endl<<endl;
cout<<"编码效率："<<CodeEfficiency<<endl<<endl; } //释放资源
void CHuffman_m::DestroyBTree(HuffNode *TreePointer) {
if (TreePointer!= NULL)
{
for(int i=0;i<m;i++)
if(TreePointer->Subtree[i])
DestroyBTree(TreePointer->Subtree[i]);
delete TreePointer;
TreePointer = NULL;
} } //主函数：
void main() {
int m;
do{
cout<<"请输入进制数 m（2-9）:";
cin>>m;
}while(m>9||m<2);
CHuffman_m YYY(m);
YYY.Huffman_Input();
YYY.Huffman_Sort();
YYY.Huffman_Tree();
YYY.Huffman_Coding();
YYY.Huffman_CodeAnalyzing();
YYY.Huffman_Display(); } （四）实验结果 1.二进制编码实验截图：
图 1-1 二进制编码结果
2.三进制编码实验截图：
图 1-2 三进制编码结果
3.M 进制编码实验截图：
图 1-3 M 进制编码结果
四、实验小结
这次做的关于无失真信源编码的实验，一方面是为了巩固我们在课堂之上所学习的知识，另一方面，让我们可以有机会自己亲身体验用所学知识设计具有特定功能的程序。这也给了我们一个机会让我们可以将学到的知识与实践的操作得以有机的磨合。在实验过程中，老师将二进制、三进制赫夫曼码的编码代码示例发给了我们，让我们作为参考并设计 M 进制的程序，这在一定程度上为我们减小了难度。通过实验，我对成员函数 IsUniDecodableCdoe()是如何判断赫夫曼码是否是唯一可译码有了进一步的理解。同时我也了解到，赫夫曼编码是一种效率比较高的变长无失真信源编码方法，并学会了将其编码方法应用到电脑中，也算是有了不小的收获。