唯一可译码的判别程序实现Word文档下载推荐.doc
《唯一可译码的判别程序实现Word文档下载推荐.doc》由会员分享，可在线阅读，更多相关《唯一可译码的判别程序实现Word文档下载推荐.doc（9页珍藏版）》请在冰点文库上搜索。
方法一:
根据异前缀码是唯一可译码来进行判断。
其步骤如下:
首先,观察是否为非奇异码。
若是奇异码,肯定不是唯一可译码;
其次,计算是否满足Kraft不等式。
若不满足一
定不是唯一可译码;
最后,将码画成一棵码树图,观察是否满足异前缀码的码树图的构造,若满足则是唯一可译码。
这种方法的理论基础是异前缀码一定是唯一可译码,通过经典的Kraft不等式及码树图进行判别。
但它的缺点也是显而易见的,若不是异前缀码时,则此方法无法判断是否是唯一可译码。
方法二:
使用A.A.Sardinas和G.W.Patterson设计的判断法。
其判断准则为:
计算分组码C中所有可能的尾随后缀集合F,观察F中有没有包含任一码字,若无则为唯一可译码;
若有则一定不是唯一可译码。
算法中的关键为尾随后缀集合F的构造。
步骤如下：
（1）考查C中所有的码字，若Wi是Wj的前缀，则将相应的后缀作为一个尾随后缀放入集合F0中；
（2）考查C和Fi两个集合，若Wj∈C是Wi∈Fi的前缀或Wi∈Fi是Wj∈C的前缀，则将相应的后缀作为尾随后缀码放入集合Fi+1中；
（3）F=∪Fi即为码C的尾随后缀集合；
（4）若F中出现了C中的元素，则算法终止，返回假（C不是唯一可译码）；
否则若F中没有出现新的元素，则返回真。
本文将以方法二来实现唯一可译码的判别。
一算法流程：
输入码字集合X0
for所有Wi，Wj∈X0
if码字Wi是码字Wj的前缀，
即将相应的后缀作为一个尾随后缀放入新集合X1
endif
endfor
for所有Wi∈X0
for所有Wj∈Xn－1
ifWi是Wj的前缀，
即将相应的后缀作为一个尾随后缀放入新集合Xn中
elseifWj是Wi的前缀，
endif
endfor
endfor
构造尾随后缀集合X←Xi
if有码字Wi∈X0，Wi∈X，则非唯一可译码
二流程框图
开始
输入两个要计算
尾随后缀的字符串
i=0
比较c[i]、d[i]
如果c[i]=d[i]=’/0’
Y
N
如果c[i]=’/0’,将d的剩余部分放入尾随后缀集合
Y
N
如果d[i]=’/0’,将c的剩余部分放入尾随后缀集合
Y
如果c[i]=d[i]
N
i++；
Y
break
三数据结构：
本文需设计的程序中，码字可用如下结构（即条件限制）表示：
charc[100][50]
尾随后缀用如下结构（即条件限制）表示:
charf[300][50]
四程序代码：
#include<
stdio.h>
string.h>
charc[100][50];
charf[300][50];
intN,sum=0;
//N为输入码字的个数，sum为尾随后缀集合中码字的个数
intflag;
//判断是否唯一可译标志位
voidpatterson（charc[],chard[]）//检测尾随后缀
{
inti,j,k;
for（i=0;
;
i++）
{
if（c[i]=='
\0'
&
d[i]=='
）//2字符串一样，跳出
break;
）//d比c长，将d的尾随后缀放入f中
{
for（j=i;
d[j]!
='
j++）f[sum][j-i]=d[j];
f[sum][j-i]='
for（k=0;
k<
sum;
k++）
{
if（strcmp（f[sum],f[k]）==0）/*查看当前生成的尾随后缀在f集合中是否存在*/
{
sum--;
break;
}
}
sum++;
break;
}
if（d[i]=='
）//c比d长，将c的尾随后缀放入f中
c[j]!
j++）f[sum][j-i]=c[j];
if（strcmp（f[sum],f[k]）==0）/*查看当前生成的尾随后缀在f集合中是否存在*/
if（c[i]!
=d[i]）//字符不一样了也退出
}
}
/*主函数*/
main（）
inti,j;
printf（"
请输入码字的个数（小于100）:
"
）;
//输入码得个数
scanf（"
%d"
&
N）;
while（N>
100）
{
printf（"
输入码字个数过大，请输入小于100的数\n"
printf（"
scanf（"
}
flag=0;
请分别输入码字（每个码字长度小于50个字符）:
\n"
i<
N;
scanf（"
%s"
c[i]）;
N-1;
i++）//判断如果码本身是否重复
for（j=i+1;
j<
j++）
{
if（strcmp（c[i],c[j]）==0）
{flag=1;
}
if（flag==1）//如果码本身有重复，就可以断定它不是唯一可译码
这不是唯一可译码。
else
for（i=0;
i++）/*此处是根据原始编码生成的尾随后缀集合s[1]放入f中*/
{
for（j=i+1;
{
patterson（c[i],c[j]）;
}
}
for（i=0;
i++）//根据原始码与s[i]生成s[i+1]也放入f[i]
ints=0;
for（j=0;
j++）/*判断s[i+1]中的字符串是否与s[i]中一样，重复的则不再添加*/
if（i==sum）
{s=1;
else
patterson（f[i],c[j]）;
if（s==1）break;
for（i=0;
i++）/*判断p里的字符串是否与s中重复，重复则不是唯一的*/
for（j=0;
if（strcmp（f[i],c[j]）==0）
{
flag=1;
break;
}
if（flag==1）
printf（"
else
这是唯一可译码。
printf（"
尾随后缀集合为:
for（i=0;
=sum;
\n%s"
f[i]）;
五输入编码：
举简例如下：
1:
10，0,100
2:
10,110，1110
六运行结果
1输入10,0,100时，
2输10,110，1110时，
升级会员 