实验三算术编码
一、实验内容
编程实现算术编码算法
二、实验环境
1.计算机
2.Windows 2000 或以上
3.VS2005
三、实验目的
1.进一步熟悉算术编码算法；
2.掌握C语言编程（尤其是数值的进制转换，数值与字符串之间的转换等）
四、实验要求
1.提前预习实验，认真阅读实验原理。
2.认真高效的完成实验，实验过程中服从实验室管理人员以及实验指导老
师的管理。
3.认真填写实验报告。
五、实验原理
算术编码是把一个信源表示为实轴上0和1之间的一个区间，信源集合中的每一个元素都用来缩短这个区间。
1.算法流程
六、参考书
1.《信息论——基础理论及应用》傅祖芸，电子工业出版社
七、程序设计
7.1程序流程图
7.2关键代码设计
1）计算部分最终得到Low
for(i = 1;i < length;i++)
for(j = 0;j < count;j++)
{
if(code[i] == number[j])
{
if(j == 0)
{
low = Low;
high = Low + chance[j] * d;
High = high;
d *= chance[j];
}
else
{
double chance_l = 0.0;
for(int k = 0;k <= j-1;k++)
chance_l += chance[k];
low = Low + d * chance_l;
high = Low + d * (chance_l + chance[j]);
Low = low;
High = high;
d *= chance[j];
}
}
else
continue;
}
2）计算码长
for (int i = 0;i < length;i++)
for (int j = 0;j < count;j++)
{
if (code[i] == number[j])
sum *= chance[i];
}
int L = (int) log(1.00/sum);
3）求最终编码
for(int i = 0;i < L;i++)
{
Low *= 2;
if (Low > 1)
{
cout << 1;
Low -= 1;
}
else
cout<<0;
}
7.3程序运行结果
输入信源符号及对应的概率分布：
输入符号序列：
得到相应的结果：
该数据来源为课件。
7.4、程序分析
在网上下的程序并未对码长以及最终编码进行计算和输出，根据可见所讲，将信息熵求出后计算了码长，并输出了最后的编码结果。
重新认识了算术编码的编码过程，对于解码部分，并未做相应的编程实现。但是了解了其解码过程，虽然对能否无损解码持怀疑态度。
八、源代码
#include
using namespace std;
#include
#define M 100
#define N 4
class suanshu
{
int count,length;
char number[N],n;
long double chance[N],c;
char code[M];
long double High,Low,high,low,d;
public:
suanshu()
{High=0;Low=0;}
void get_number();
void get_code();
void coding();
void print();
~suanshu(){};
};
void suanshu::get_number()
{
cout<<"输入信源符号及其对应概率:"< int i; long double sum = 0.00; for(i = 0;i < N && sum <= 1;i++) { cin >> n >> c; number[i] = n; chance[i] = c; sum += c; } if(i == 20) cout<<"信源符号数溢出."< if (sum > 1) cout<<"概率和超过."< count = i; } void suanshu::get_code() { cout<<"输入符号序列长:"; cin>>length; while(length>=M) { cout<<"输入的符号序列超长，请改小!"; cin>>length; } for(int i=0;i cin>>code[i]; } void suanshu::coding() { int i,j=0; for(i=0;i if(code[0]==number[i]) break; while(j Low += chance[j++]; d = chance[j]; High = Low + d; for(i = 1;i < length;i++) for(j = 0;j < count;j++) { if(code[i] == number[j]) { if(j == 0) { low = Low; high = Low + chance[j] * d; High = high; d *= chance[j]; } else { double chance_l = 0.0; for(int k = 0;k <= j-1;k++) chance_l += chance[k]; low = Low + d * chance_l; high = Low + d * (chance_l + chance[j]); Low = low; High = high; d *= chance[j]; } } else continue; } } void suanshu::print() { cout<<"算数编码结果为:"< cout<<"二进制结果:"< double sum = 1.00; for (int i = 0;i < length;i++) for (int j = 0;j < count;j++) { if (code[i] == number[j]) sum *= chance[i]; } int L = (int) log(1.00/sum); for(int i = 0;i < L;i++) { Low *= 2; if (Low > 1) { cout << 1; Low -= 1; } else cout<<0; } cout< } void main() { suanshu a; a.get_number(); a.get_code(); a.coding(); a.print(); } 实验四 Huffman编码对英文文本的压缩和解压缩 一、实验内容 根据信源压缩编码——Huffman编码的原理，制作对英文文本进行压缩和解压缩的软件。要求软件有简单的用户界面，软件能够对运行的状态生成报告，分别是：字符频率统计报告、编码报告、压缩程度信息报告、码表存储空间报告。 二、实验环境 4.计算机 5.Windows 2000 或以上 6.Microsoft Office 2000 或以上 7.VS2005 三、实验目的 3.掌握Huffman编码的原理 4.掌握VC开发环境的使用（尤其是程序调试技巧） 5.掌握C语言编程（尤其是位运算和文件的操作） 6.掌握数据结构的内容：链表、顺序表、堆栈、最优二叉树 7.掌握结构化程序分析和开发的软件工程原理 四、实验要求 4.提前预习实验，认真阅读实验原理。 5.认真高效的完成实验，实验过程中服从实验室管理人员以及实验指导老 师的管理。 6.认真填写实验报告。 五、实验原理 压缩/解压缩流程 压缩流程： 解压缩流程： 六、参考书 1.《信息论——基础理论及应用》傅祖芸，电子工业出版社 2.《数据结构》，清华大学出版社 七、程序设计 7.1数据结构描述： 以下是哈夫曼树结点的结构： 哈夫曼树以数组形式保存，其Array元素个数是2n-1，其中n为叶子数。 对应结点的哈夫曼编码用一个数组 记录，该数组元素是指向字符的指 针 7.2主要算法描述 7.2.1压缩 其基本实现方法是，因为英文 文件中都是ACSII码（包括英文的 标点符号），所以对选定的文件文本 读入，一次读入一个字符，然后对 每个ASCII字符进行统计，如此循 换，这就统计出文件的每个字符的 权值了。 得出文件各字节的权值后，就 可以构造对应哈夫曼的哈夫曼树， 从而就可以构造出对应字符的哈夫 曼编码了。每个字符的哈夫曼编码 都知道了，那么文件的哈夫曼编码 就可以求出了。 7.2.2关于解压 解压时，先读出哈夫曼编码的节点及其权值，然后对编码部分读取一个字节（8 bit）用一个函数转换为8个字符（用一个数组记录，其元素只是一个0或一个1），然后按哈夫曼树从顶向下查找，如果到达叶子结点，就读出该叶子结点的值，放入缓冲区中，如果不是，则继续找，如此重复，直到缓冲区满了，就写入到解压文件中，再循环以上过程，直到处理完所有数据。 7.3具体函数设计 7.3.1压缩函数设计 点击压缩后，调用压缩函数EnCodeFile() SaveHuffHead(fpt); //写入压缩文件的头信息!!!注意，此时lastcodelenth为空，需压缩结束时重置 l=data=0; puts("Encoding ... "); //编码压缩过程，依次对源文件字符进行编码 while(true){ //存入一个字符中，用移位操作实现，每位前c=fgetc(fp); //缀码对应一个字符，将该字符存入目标文件， if(feof(fp)) break; //最终不足位的记录最后一位占用的前缀码长度 soucelen++; //源文件长度增加 for(i=0;i data<<=1; //对当前字符的前缀码当前们存储于data 中 data+=code[c][i]; if(++l%8==0){ //满位，则存储 fputc(data,fpt); targetlen++; //目标文件长度增加 } } } //对最后的一个字符进行处理 lastcodelenth=l%8; //记录实际占用位的长度 data<<=8-lastcodelenth; //空出剩余位 fputc(data,fpt); //输出至文件 targetlen++; //目标文件长度增加 该函数主要是涉及三个步骤：构造哈夫曼树、构造哈弗曼编码、压缩。7.3.2解压函数设计 点击解压后，调用解压函数DeCodeFile（） DeCodePre(fp); l=0; puts("Decoding ... "); fscanf(fp,"%c",&c); //解码过程，压缩过程的逆过程，取出编码了的字符， //按位取出，存于tmp[]中，找出前缀码对应的字符 while(!feof(fp)){ soucelen++; fscanf(fp,"%c",&t); if(feof(fp))break; for(i=l+7;i>=l;i--){ //按位取出前缀码 tmp[i]=c&1;c>>=1; }l+=8; while(l>=32){ //如果当前前缀码段超出一定的长度，则取出前缀码进行解码 for(i=0,cur=arr[size-1];!cur.c;i++) cur=tmp[i]?arr[cur.rt]:arr[cur.lt];//找到前缀码段对应第一个字符fprintf(fpt,"%c",cur.c); //输出至目标文件 l-=i;targetlen++; //前缀码段减去当前字符前缀码长度 memmove(tmp,tmp+i,sizeof(bool)*l); //数组顺移至开头，即从开始记录当前的前缀码段 }c=t; } for(i=l+7;i>=l;i--){ //对最后一个字符做特殊处理tmp[i]=c&1; //取出每一位 c>>=1; } l+=lastcodelenth; //只利用最后一个字符的前lastcodelenth位 while(l){ //输出剩余的前缀码段对应的字符 for(i=0,cur=arr[size-1];!cur.c;i++) cur=tmp[i]?arr[cur.rt]:arr[cur.lt]; fprintf(fpt,"%c",cur.c);l-=i;targetlen++; memmove(tmp,tmp+i,sizeof(bool)*l); } fclose(fp);fclose(fpt); //关闭文件 7.4程序体验 7.4.1程序界面： 7.4.2选择文件并压缩： 源文件“test.txt”的内容 选取文件 压缩完成 选择的源文件为：“D:\我的文档\test.txt”压缩后的文件存储在相同路径 下，压缩后的文件名：“test.huf”，文件长度减小了7908。其内容为下： 压缩后的内容 7.4.3解压 选择刚才的压缩文件进行解压： 选取文件 解压成功 解压后的文件名为：“test.txt” 解压后的文件内容 经过压缩解压后得到的文件内容和压缩前的一致。 利用MD5比较，得到压缩前文件与解压得到的文件为同一文件。 DE01E3358BCA716ACB444661E862CBDD DE01E3358BCA716ACB444661E862CBDD 八、源代码 Huffman.h: #pragma once //*************************************************************** //课程：信息论与编码 //题目：霍夫曼编码实现文本压缩解压 //老师：余林琛 //作者：刘宇豪 //时间：-11-2 //*************************************************************** #include #include #include"stdafx.h" #define ASCIIL 256 #define F(x) ((x-1)>>1) #define L(x) ((x<<1)+1) #define R(x) ((x<<1)+2) #define SWAP(a,b,tmp) {tmp=a;a=b;b=tmp;} using namespace std; //实现二叉堆模板类，小顶堆 template class CHeap { HeapType *data,tmp; int size; void HeapUp(int ix) {//自底向顶维护堆 int f; for(f=F(ix);ix&&data[ix] SWAP(data[ix],data[f],tmp); } void HeapDown(int ix) {//自顶向底维护堆 int l,r,t; HeapType min,tmp; if(ix>=size) return ; l=L(ix),r=R(ix); min=data[ix],t=ix; if(l t=l,min=data[l]; if(r t=r,min=data[l]; SWAP(data[ix],data[t],tmp); if(ix!=t) HeapDown(t); } public: CHeap() {//这里特殊应用，堆内元素个数不超过 size=0; data=new HeapType[256]; } ~CHeap() {//释放内存 delete data; } int getsize() {//返回堆大小 return size; } void clear() {//清空堆 size=0; } void insert(HeapType e) {//向堆尾中插入元素，并向顶维护堆 data[size++]=e; HeapUp(size-1); } HeapType top() {//从堆顶取出元素，并向底维护堆 HeapType ret=data[0]; data[0]=data[--size]; HeapDown(0);return ret; } }; //哈夫曼树结点结构体实现 typedef struct talNode{ unsigned char c; //叶结点时对应ASCII值 int weight; //该结点权值 int lt,rt; //左、右结点下标 talNode(){} talNode(unsigned char _c,int _p): c(_c),weight(_p),lt(-1),rt(-1) {} talNode(unsigned char _c,int _p,int l,int r) :c(_c),weight(_p),lt(l),rt(r) {} bool operator < (talNode a) {//重载运算符“<”用于二叉堆内的比较 return weight } }HuffNode; class CHuffMan{ HuffNode arr[512]; //哈夫曼树结点数组 int size; //哈夫曼树结点个数 bool code[256][64]; //ASCII对应编码方案 int lenth[256]; //ASCII对应编码长度 //lastcodelenth,ps[256],用于存储压缩文件中作为文件头 int lastcodelenth; //文件最后一个字符实用几位 int ps[256]; //ASCII对应出现频率 int soucelen,targetlen; //源及目标文件长度 //私有成员函数，用于实现内部功能 void SetHuffTree(int []); //根据字符频率生成哈夫曼树 void SetHuffCode(int ,bool [],int );//根据哈夫曼树生成编码方案 void CreateHuff(int []); //创建哈夫曼树及编码方案 void EnCodePre(CString); //压缩前预处理 void DeCodePre(FILE *); //解压前预处理 void SaveHuffHead(FILE *); //保存压缩文件头 void ReadHuffHead(FILE *); //读取压缩文件头 public: CHuffMan(){Clear();} //构造函数 ~CHuffMan(){} //析构函数 //公有成员函数，用于提供使用接口 void Clear(); //清空当前对象内容 void EnCodeFile(CString,CString); //编码，用于压缩文件，第一个参数为源文件名，第二个参数为目标文件名 void DeCodeFile(CString,CString); //解码，用于解压文件，第一个参数为源文件名，第二个参数为目标文件名 int GetSouceLen(); //输出当前工作项的源文件长度 int GetTargetLen(); //输出当前工作项的目标文件长度 }; void CHuffMan::SetHuffTree(int ps[]) { //每次取出两权值最小的结点合并成新树， //加入堆，直至堆中只余有一个元素 CHeap for(int i=0;i hp.insert(HuffNode(i,ps[i])); } size=0; //初始化哈夫曼树中结点个数 while(hp.getsize()>1){ arr[size++]=hp.top(); //取出权值最小的两个结点 arr[size++]=hp.top(); hp.insert(HuffNode(0, arr[size-1].weight+arr[size-2].weight, size-1,size-2)); //合并结点，并插入堆 } arr[size++]=hp.top(); //arr[size-1]为哈夫曼树根 } void CHuffMan::SetHuffCode(int ix,bool stk[],int top) { //递归深搜哈夫曼树，生成所有存在的ASCII的前缀码 if(arr[ix].c){ //如果 if(top){ //此判断用于只含有一类字符的文件 memmove(code[arr[ix].c],stk,sizeof(bool)*top); lenth[arr[ix].c]=top; } else lenth[arr[ix].c]=1; return ; } stk[top]=0; //左子树的边设为 SetHuffCode(arr[ix].lt,stk,top+1); //递归进入左子树 stk[top]=1; //右子树的边设为 SetHuffCode(arr[ix].rt,stk,top+1); //递归进入右子树 } void CHuffMan::CreateHuff(int ps[]) { //构造哈夫曼树及前缀码 bool stk[64]; SetHuffTree(ps); //根据字符频率构造哈夫曼树 SetHuffCode(size-1,stk,0); //根据哈夫曼树生成前缀码 } void CHuffMan::EnCodePre(CString sfilename) { //压缩文件预处理，读取字符出现频率FILE *fp; //及构造哈夫曼树及前缀码 int c; char *file_tmp; DWORD dwNum = WideCharToMultiByte(CP_OEMCP,NULL,sfilename,-1,NULL,0,NULL,FALSE); file_tmp = new char[dwNum]; WideCharToMultiByte(CP_OEMCP,NULL,sfilename,-1,file_tmp,dwNum,NULL,FALSE); fp=fopen(file_tmp,"rb"); if(fp==NULL){ if(MessageBox(NULL,L"打开文件出错",L"梦已喂马",MB_OK)) exit(0); } memset(ps,0,sizeof(ps)); //读取字符出现频率 while(true){ c=fgetc(fp); if(feof(fp))break; ps[c]++; } fclose(fp); CreateHuff(ps); //构造哈夫曼树及前缀码 } void CHuffMan::DeCodePre(FILE *fp) { //解压文件预处理，读取压缩文件头//根据读取头信息构千哈夫曼树及前缀码 ReadHuffHead(fp); CreateHuff(ps); } void CHuffMan::SaveHuffHead(FILE *fp) { //向压缩文件中写文件头fwrite((void *)&lastcodelenth,4,257,fp);//从lastcodelenth的地址开始的连续 //4*257个字节，即lastcodelenth和 //ps[256]数组内容 targetlen+=4*257; } void CHuffMan::ReadHuffHead(FILE *fp) { //从缩文件中读文件头 fread((void *)&lastcodelenth,4,257,fp); //从lastcodelenth的地址开始的连续 //4*257个字节，即lastcodelenth和 soucelen+=4*257; //ps[256]数组内容 } void CHuffMan::Clear() { //清空前前工作项 size=0;soucelen=targetlen=0; lastcodelenth=0; memset(lenth,0,sizeof(lenth)); memset(ps,0,sizeof(ps)); } int CHuffMan::GetSouceLen() { //获取当前工作项的源文件长度return soucelen; } int CHuffMan::GetTargetLen() { //获取当前工作项的目标文件长度return targetlen; } void CHuffMan::EnCodeFile(CString sfilename,CString gfilename) { //将文件sfilename压缩为文件gfilename FILE *fp,*fpt; int c,data,l,i; char *file_tmp; file_tmp = new char[sfilename.GetLength() + 1]; DWORD dwNum = WideCharToMultiByte(CP_OEMCP,NULL,sfilename,-1,NULL,0,NULL,FALSE); file_tmp = new char[dwNum]; WideCharToMultiByte (CP_OEMCP,NULL,sfilename,-1,file_tmp,dwNum,NULL,FALSE); EnCodePre(sfilename); //压缩预处理，生成哈曼树及字符前缀码fp=fopen(file_tmp,"rb"); if(fp==NULL){ if(MessageBox(NULL,L"打开文件出错",L"梦已喂马",MB_OK)) exit(0); } delete [] file_tmp; dwNum = WideCharToMultiByte(CP_OEMCP,NULL,gfilename,-1,NULL,0,NULL,FALSE); file_tmp= new char[dwNum]; WideCharToMultiByte (CP_OEMCP,NULL,gfilename,-1,file_tmp,dwNum,NULL,FALSE); fpt=fopen(file_tmp,"wb"); SaveHuffHead(fpt); //写入压缩文件的头信息!!!注意，此时lastcodelenth为空，需压缩结束时重置 l=data=0; puts("Encoding ... "); //编码压缩过程，依次对源文件字符进行编码 while(true){ //存入一个字符中，用移位操作实现，每位前c=fgetc(fp); //缀码对应一个字符，将该字符存入目标文件，if(feof(fp)) break; //最终不足位的记录最后一位占用的前缀码长度 soucelen++; //源文件长度增加 for(i=0;i data<<=1; //对当前字符的前缀码当前们存储于data 中 data+=code[c][i]; if(++l%8==0){ //满位，则存储 fputc(data,fpt); targetlen++; //目标文件长度增加 } } } //对最后的一个字符进行处理 lastcodelenth=l%8; //记录实际占用位的长度 data<<=8-lastcodelenth; //空出剩余位 fputc(data,fpt); //输出至文件 targetlen++; //目标文件长度增加 fseek(fpt,0,SEEK_SET); //!!!回溯至文件头，更新lastcodelenth 至 fwrite(&lastcodelenth,4,1,fpt); //真实值 fclose(fp); //关闭文件 fclose(fpt); } void CHuffMan::DeCodeFile(CString sfilename,CString gfilename)
相关主题
文本预览