熟悉唯一可译码判决准则。 掌握C语言字符串处理程序的设计和调试技术
已知:信源符号个数r、码字集合C。 输入:任意的一个码。码字个数和每个具体的码字在运行时从键盘输入 输出:判决(是唯一可译码/不是唯一可译码)。
A.A.Sardinas和G.W.Patterson于1957年提出了一种用于判断码C的唯一可译性。算法原理如下:
其中 和 都是码字。可知,当且仅当某个有限长的码符号序列能译成不同的码字序列时,此码不是唯一可译码,此时 一定是 的前缀,而 的尾随后缀一定是另一个码字 的前缀;而 的尾随后缀优势其他他码字的前缀。最后,吗符号序列的尾部一定是一个码字。设C为码字集合,按以下步骤构造此码的尾随后缀集合
(1)考察C中所有的码字,若$W_i$ 是
主要的工作是构造C和F这两个集合,其中集合C是待判决的码字集合,通过输入获得,集合F是尾随码集合,集合F的构造过程就是整个算法实现的核心。用构造的链表来存储集合F。 链表基本数据类型
struct strings
{
char *string;
struct strings *next;
};
程序的核心函数
1 . void houzhui(char *CP, char *tempPtr)
2. int comparing(strings *st_string, char *code)
用来判断两个码字是否一个是另一个的前缀,如果是则生成后缀码
3. void outputstr(strings *str)
用来输出字符串。
完整代码见Gitub仓库
首先输入一组为唯一可译的码,各个码字分别为1222 1345 2222 4567共四个码字 下面看一下当码字不是唯一可译的情况,同样输入四个不同的码字,分别是1234 123 111 1 。但是码字不是异字头码,即有的码字是其他码字的头部。 程序运行结果显示该码不是唯一可译码,该测试程序有效。