信息论课程设计报告唯可译码lzw编码算数编码.docx
《信息论课程设计报告唯可译码lzw编码算数编码.docx》由会员分享，可在线阅读，更多相关《信息论课程设计报告唯可译码lzw编码算数编码.docx（23页珍藏版）》请在冰点文库上搜索。
信息论课程设计报告唯可译码lzw编码算数编码
1.判定唯一可译码
2.LZw编码
3.算数编码
一判定唯一可译码
1．任务说明
输入：
任意的一个码（即已知码字个数及每个具体的码字）
输出：
判决结果（是/不是）
输入文件:
in1.txt，含至少2组码，每组的结尾为”$”符
输出文件:
out1.txt，对每组码的判断结果
说明：
为了简化设计，可以假定码字为0，1串
2．问题分析、实现原理、流程图
参考算法伪代码：
Forall
do
if
是
的前缀then
将相应的后缀作为一个尾随后缀放入集合
中
Endif
Endfor
Loop
Forall
do
Forall
do
if
是
的前缀then
将相应的后缀作为一个尾随后缀放入集合
中
Elseif
是
的前缀then
将相应的后缀作为一个尾随后缀放入集合
中
Endif
Endfor
Endfor
If
then
Returnfalse
ElseifF中未出现新的元素then
Returntrue
Endif
//能走到这里，说明F中有新的元素出现，需继续
Endloop
3．实现源码
#include
#include
usingnamespacestd;
structstrings
{
char*string;
structstrings*next;
};
structstringsFstr,*Fh,*FP;
//输出当前集合
voidoutputstr（strings*str）
{
do
{
cout<string<str=str->next;
}while（str）;
cout<}
inlineintMIN（inta,intb）
{returna>b?
b:
a;}
inlineintMAX（inta,intb）
{returna>b?
a:
b;}
#definelength_a（strlen（CP））
#definelength_b（strlen（tempPtr））
//判断一个码是否在一个码集合中，在则返回0，不在返回1
intcomparing（strings*st_string,char*code）
{
while（st_string->next）
{
st_string=st_string->next;
if（!
strcmp（st_string->string,code））
return0;
}
return1;
}
//判断两个码字是否一个是另一个的前缀，如果是则生成后缀码
voidhouzhui（char*CP,char*tempPtr）
{
if（!
strcmp（CP,tempPtr））
{
cout<<"集合C和集合F中有相同码字:
"<<<<"不是唯一可译码码组!
"<exit
（1）;
}
if（!
strncmp（CP,tempPtr,MIN（length_a,length_b）））
{
structstrings*cp_temp;
cp_temp=new（structstrings）;
cp_temp->next=NULL;
cp_temp->string=newchar[abs（length_a-length_b）+1];
char*longstr;
longstr=（length_a>length_b?
CP:
tempPtr）;//将长度长的码赋给longstr
//取出后缀
for（intk=MIN（length_a,length_b）;kcp_temp->string[k-MIN（length_a,length_b）]=longstr[k];
cp_temp->string[abs（length_a-length_b）]=NULL;
//判断新生成的后缀码是否已在集合F里，不在则加入F集合
if（comparing（Fh,cp_temp->string））
{
FP->next=cp_temp;
FP=FP->next;
}
}
}
voidmain（）
{
//功能提示和程序初始化准备
cout<<"\t\t唯一可译码的判断!
\n"<structstringsCstr,*Ch,*CP,*tempPtr;
Ch=&Cstr;
CP=Ch;
Fh=&Fstr;
FP=Fh;
charc[]="C:
";
Ch->string=newchar[strlen（c）];
strcpy（Ch->string,c）;
Ch->next=NULL;
charf[]="F:
";
Fh->string=newchar[strlen（f）];
strcpy（Fh->string,f）;
Fh->next=NULL;
//输入待检测码的个数
intCnum;
cout<<"输入待检测码的个数:
";
cin>>Cnum;
cout<<"输入待检测码"<for（inti=0;i{
cout<";
chartempstr[10];
cin>>tempstr;
CP->next=new（structstrings）;
CP=CP->next;
CP->string=newchar[strlen（tempstr）];
strcpy（CP->string,tempstr）;
CP->next=NULL;
}
outputstr（Ch）;
CP=Ch;
while（CP->next->next）
{
CP=CP->next;
tempPtr=CP;
do
{
tempPtr=tempPtr->next;
houzhui（CP->string,tempPtr->string）;
}while（tempPtr->next）;
}
outputstr（Fh）;
structstrings*Fbegin,*Fend;
Fend=Fh;
while
（1）
{
if（Fend==FP）
{
cout<<"是唯一可译码码组!
"<exit
（1）;
}
Fbegin=Fend;
Fend=FP;
CP=Ch;
while（CP->next）
{
CP=CP->next;
tempPtr=Fbegin;
for（;;）
{
tempPtr=tempPtr->next;
houzhui（CP->string,tempPtr->string）;
if（tempPtr==Fend）
break;
}
}
outputstr（Fh）;//输出F集合中全部元素
}
}
4.运行结果：
输入、输出及结果分析
5．设计体会
通过对判定唯一可译码算法的实现，我进一步了解判定唯一可译码缩的基本原理及过，体会到了其重要性,同时也锻炼了我独立分析问题以及解决问题的能力,这次课程设计让我深刻认识到了自己编程能力的不足，在以后的学习中要加强自己的编程能力。
二LZw编码
1.任务说明
输入：
由集合{a,b,c,d}内字符构成的输入串，输入序列长度L<=100
处理：
先编码，再对编码结果译码
输出：
编码结果，译码结果
输入文件:
in4.txt，含至少两组输入，每组包含满足要求的串
输出文件:
out4.txt，对每组输入的编码和译码结果
2.问题分析、实现原理、流程图
实现原理：
LZW就是通过建立一个字符串表,用较短的代码来表示较长的字符串来实现压缩.字符串和编码的对应关系是在压缩过程中动态生成的,并且隐含在压缩数据中,解压的时候根据表来进行恢复,算是一种无损压缩.在本次实验中我们就进行了LZW编码以及译码简单算法的编写。
LZW编码又称字串表编码，是无损压缩技术改进后的压缩方法。
它采用了一种先进的串表压缩，将每个第一次出现的串放在一个串表当中，用一个数字来表示串，压缩文件只进行数字的存贮，则不存贮串，从而使图像文件的压缩效率得到了较大的提高。
LZW编码算法的原理是首先建立一个词典，即跟缀表。
对于字符串流，我们要进行分析，从词典中寻找最长匹配串，即字符串P在词典中，而字符串P+后一个字符C不在词典中。
此时，输出P对应的码字，将P+C放入词典中。
编码参考算法：
（以下为基于4叉树字典的伪代码，同学们可另外自行设计，参见教材P335）
1.字典初始化：
建一个初始的4叉树。
该树的每个节点包含了字典序号信息。
若字典序号非0，表示该节点对应的字典已建立。
每个节点的儿子按顺序依次对应于输入字符a,b,c,d.
根节点有4个儿子节点A、B、C、D，分别对应初始字典中的a,b,c,d，其对应的序号分别为1，2，3，4；而A、B、C、D节点均设4个儿子，其对应的序号设为0，对应的字典串分别为aa,ab,ac,ad;ba,bb,bc,bd;ca,cb,cc,cd;da,db,dc,dd
建议：
字典采用4叉树结构
3.实现源码
#include
#include
#include
usingnamespacestd;
stringdic[30];
intn;
intfind（strings）
{
inttemp=-1;
for（inti=0;i<30;i++）
{
if（dic[i]==s）temp=i+1;
}
returntemp;
}
voidinit（）
{
dic[0]="a";
dic[1]="b";
dic[2]="c";
dic[3]="d";
for（inti=4;i<30;i++）
{
dic[i]="";
}
}
voidcode（stringstr）
{
init（）;
chartemp[2];
temp[0]=str[0];
temp[1]='\0';
stringw=temp;
inti=1;
intj=3;
cout<<"\n编码为：
";
for（;;）
{
chart[2];
t[0]=str[i];
t[1]='\0';
stringk=t;
if（k==""）
{
cout<<""<break;
}
if（find（w+k）>-1）
{
w=w+k;
i++;
}
else
{
cout<<""<stringwk=w+k;
dic[j++]=wk;
w=k;
i++;
}
}
cout<for（i=0;i{
cout<}
cout<}
voiddecode（intc[]）
{
init（）;
intpw,cw;
cw=c[0];
intj=2;
cout<<"\n译码为：
";
cout<for（inti=0;i{
pw=cw;
cw=c[i+1];
if（cw<=j+1）
{
cout<chart[2];
t[0]=dic[cw-1][0];
t[1]='\0';
stringk=t;
j++;
dic[j]=dic[pw-1]+k;
}
else
{
chart[2];
t[0]=dic[pw-1][0];
t[1]='\0';
stringk=t;
j++;
dic[j]=dic[pw-1]+k;
cout<}
}
cout<for（inti=0;i{
cout<}
cout<}
voidmain（）
{
stringstr;
while
（1）
{
cout<<"\n\n\ta.编码\tb.译码\n\n";
cout<<"请选择：
";
charcha;
cin>>cha;
if（cha=='a'）
{
cout<<"\n输入要编码的字符串（由a,b,c,d组成）：
";
cin>>str;
code（str）;
}
else
{
intc[30];
cout<<"\n消息序列长度是：
";
cin>>n;
cout<<"\n消息码字依次是：
";
for（inti=0;i{
cin>>c[i];
}
decode（c）;
}
}
}
4.运行结果：
输入、输出及结果分析
5．设计体会
在实验设计过程中，遇到的主要问题是对文件操作和字典的生成比较难,对于这个算法的编写我觉得设计难度比较大，因为长时间不用,对语言也有些生疏.。
所以设计起来比较吃力。
通过对LZW算法的实现，我进一步了解LZW算法进行数据压缩的基本原理及过程，体会到了其重要性，同时也锻炼了我独立分析问题以及解决问题的能力,这次课程设计让我深刻认识到了自己编程能力的不足，在以后的学习中要加强自己的编程能力。
三算数编码
1.任务说明
要求：
输入字符集为{a,b},且p（a）=1/4,p
（2）=3/4.对长度L<=20的序列进行算术编码,并进行反向译码
输入文件:
in3.txt，含至少两组输入，每组为满足要求的串
输出文件:
out3.txt，对每组输入的编码和译码结果
参考算法：
略
2.问题分析、实现原理、流程图
算术编码是把一个信源表示为实轴上0和1之间的一个区间，信源集合中的每一个元素都用来缩短这个区间。
算法流程
（1）输入信源符号个数，信源概率分布，还有需要编码的符号序列，
（2）根据概率可以算出初始编码间隔，
High——当前编码的上限，
Low——当前编码的下限，
high——中间变量，用来计算下一个编码符号的当前间隔的上限，
low——中间变量，用来计算下一个编码符号的当前间隔的下限，
d——当前间隔之间的距离。
（3）扫描需编码的符号序列，确定编码空间
第1个编码符号的当前间隔为其初始的编码间隔，
第i个编码符号的当前间隔为第i-1个编码后的[Low，High），
第i+1个编码符号的当前间隔算法如下：
high=Low+d*第i+1个初始编码符号对应的上限，low=Low+d*第i+1个编码符号对应的下限，然后High=high，Low=low，d=d*第i个编码符号的概率。
3.实现源码
#include
usingnamespacestd;
#include"math.h"
charS[100],A[10];
floatP[10],f[10],gFs;
//编码程序
voidbianma（inta,inth）
{
inti,j;
floatfr;
floatps=1;
floatFs=0;
floatSp[100],b[100],F[100];//以待编码的个数和字符个数为循环周期将待编码的字符所对应的概率存入到Fs中
for（i=0;i{
for（j=0;j{
if（S[i]==A[j]）
{
Sp[i]=P
[j];
fr=f[j];//将划分好的[0,1）区间的对应点赋值给fr
}
}
Fs=Fs+ps*fr;//从选择的子区间中继续进行下一轮的分割。
不断的进行这个过程直到所有符号编码完毕。
ps*=Sp[i];//求Ps
}
cout<<"Fs="<floatl=log（（float）1/ps）/log（（float）2）;//计算算术编码的码字长度l
if（l>（int）l）l=（int）l+1;
elsel=int（l）;//将Fs转换成二进制的形式
intd[20];
intm=0;
while（l>m）
{
Fs=2*Fs;
if（Fs>1）
{
Fs=Fs-1;
d[m]=1;
}
elseif（Fs<1）d[m]=0;
else{d[m]=1;break;}
m++;
}
intz=m;//解决有关算术编码的进位问题,给二进制数加
if（m>=l）
{
while
（1）
{
d[m-1]=（d[m-1]+1）%2;//最后位加
if（d[m-1]==1）break;
elsem--;
}
}
cout<<"s=";
for（inte=0;ecout<cout<}
//解码程序
voidjiema（inta,inth）
{
inti,j;
floatFt,Pt;
floatFs=0,Ps=1;
for（i=0;i{
for（intj=a-1;j>-1;j--）
{
Ft=Fs;
Pt=Ps;
Ft+=Pt*f[j];//对进行逆编码
Pt*=P[j];
if（gFs>=Ft）//对其进行判断并且将值存入到数组A中
{
Fs=Ft;
Ps=Pt;
cout<break;
}
}
}
cout<}
voidmain（）
{
cout<<"输入编码个数"<inta,i,h=0;
cin>>a;
cout<<"输入编码符号和概率值"<for（i=0;i{
charx;
floaty;
cin>>x;
A[i]=x;//将字符依次存入数组A中
cin>>y;
P[i]=y;//将字符所对应的概率依次存入到数组P中
}
for（i=1;i{
f[0]=0;
f[i]=f[i-1]+P[i-1];//将要编码的数据映射到一个位于[0,1）的实数区间中
}
cout<<"输入需要编码的符号序列，同时用$结尾"<while
（1）//这个while语句的作用是将要编码的字符存入到数组S中
{
charcc;
cin>>cc;
if（cc=='$'）break;//在以“$”为结尾的时候结束存储
S[h++]=cc;
}
cout<<"算术编码结果：
"<bianma（a,h）;
cout<<"对应的解码结果：
"<jiema（a,h）;
system（"pause"）;
}
4.运行结果：
输入、输出及结果分析
5．设计体会
通过本次试验，我进一步学习了C++语言概念和熟悉visualstudio2008编程环境。
学会了算术编码基本流程,基本能够调试算术编码程序。
对信息论相关知识有了进一步的认识。
升级会员 