唯一可译码判决算法

1、云南大学数学与统计学实验教学中心实验报告云南大学数学与统计学实验教学中心实验报告课程名称：计算机网络实验学期：2012-2013学年第二学期成绩：指导教师： 陆正福学生姓名：卢富毓 学生学号：20101910072实验名称：唯一可译码判决算法实验要求： 必做实验学时：4学时8实验编号： No.4实验日期：2013/3/28完成日期：2013/4/4学院：数学与统计学院专业 ： 信息与计算科学年级： 2010级 一、实验目的：通过实验掌握唯一可译码的判决算法，以及其重要思想。二、实验内容： 理解唯一可译码的判决算法 编制程序 参考北京邮电大学信息论方面的实验指导书 参考英文教材第二版中的习题5.

2、27 三、实验环境Win7、Eclipse四、实验过程（请学生认真填写）：实验过程、结果以及相应的解释：1. 预备知识首先要对唯一可译码有一个清晰的认识。唯一可译码：编码的扩展是非奇异的则称作唯一可译码。及时码：码中无任何码字是其他码字的前缀，则称为前缀码或者及时码。认清码之间的关系有助于我们在编写算法实现的时候有一个宏观的思路。Sardings_Patterson算法是判决是否是唯一可译码的重点。Sardings_Patterson算法如是：A、 判断C(x)中码字是否有其他码字的前缀，若是有，则构造一个尾随后缀集合List。B、 找出C(x)中是否有List中元素的前缀，有则将其尾随后缀加

3、入List中，反过来再找出List相对C(x)中的前缀，并将其尾随后缀加入List中。C、 若是list中存在尾随后缀为C(x)中的码字，则表示不是唯一可译码，若不存在则为唯一可译码。2. 实验过程A、 原理分析：对于唯一可以码来说就目前掌握的知识来说我们可以使用两种方法来进行试验：Kraft不等式以及A.A.Sardings-Patterson算法两种。这里用的是后者。具体算法思想如下：程序流：操作结果：Step1:判断是否非奇异否：返回C(x)不是唯一可译码是： next step2Step2:判断是否有前缀否：返回C(x)为唯一可译码是：next step3Step3:构造尾随集合Ste

4、p4: A.A.Sardings-Patterson算法Step5:尾随集合中是否有与C(x)中码字相同的尾随后缀码字否：返回C(x)是唯一可译码是：返回C(x)不是唯一可译码B、 具体代码如下：代码整体结构如下：结果如下：1） 及时码：1 01 001 0001结果：2） 奇异码：1 1 11 10 0100 01结果：3） 不是唯一可译码：a c ad abb bad deb bbcde 、0 10 1100 1110 1011 1101结果：4） 唯一可译码：11 01 1110 00001结果：具体代码如下：/* * author 卢富毓 * 唯一可译码的判断算法的实现 * Sardi

5、ngs_Patterson算法来求唯一可译码 * step1:判断是否奇异 * step2:判断码字中是否有前缀存在 * step3:Sardings_Patterson算法的实现 */package UDC;import java.util.*;public class UDC public static int N; / 信源编码个数public static String Code; / 信源编码public static ArrayList<String> list = new ArrayList<String>(); / list集合是用来放置尾随后缀的pub

6、lic static void main(String args) new UDC().start();void start() init(); / 初始化，输入码字长度以及码字/ 判断是否非奇异，若singular(Code)返回为真，表示奇异编码，便停止计算if (!singular(Code) Sardings_Patterson(Code); / 若是存在前缀的话，进行帕得森算法/数据初始化private void init() int k = 0;String str = ""Scanner sc = new Scanner(System.in);System.o

7、ut.print("请输入信源编码个数：N = ");N = sc.nextInt();Code = new StringN;System.out.print("请输入信源编码 C: ");while (k < N) str = sc.next();Codek = str;k+;/判断是否奇异private boolean singular(String code2) String str = ""int s = -1;for (int i = 0; i < code2.length; i+) str = code2i;f

8、or (int j = 0; j < code2.length - 1; j+) if (i != j) s = pareTo(str); / 两个码字比较，返回0，表示相等if (s = 0) System.out.println("是奇异的！");return true; / 奇异矩阵返回truereturn false; / 若为非奇异，则返回false/Sardings_Patterson算法的实现private void Sardings_Patterson(String code) /ArrayList<String> li

9、st = new ArrayList<String>(); / list集合是用来放置尾随后缀的int s = 0, k;boolean b = true;/ step1 初始时，收集尾随集合for (int i = 0; i < code.length; i+) for (int j = 0; j < code.length; j+) if (i != j) if(codei.length()<codej.length()s = pareTo(codej.substring(0, codei.length();if (s = 0) / 如果有尾

10、随后缀，加入尾随后缀集合中String str = codej.substring(codei.length(),codej.length();if (str != null) list.add(str);/ 若是list 为空,则表示没有尾随后缀集合if (list.isEmpty() System.out.println("无前缀!C(x)为及时码 !");return;k = list.size();/Cprefix_Listprefix/当存在前缀/则需要将C中有list的或者list中有C中的尾随后缀加入list中int l = 0,max=0;for(int i

11、=0; i<code.length; i+)if(max<codei.length()max = codei.length();while(b)l+;b = Cprefix_Listprefix(code, list, k);if(l>max | b = false)b = false;if(l>max)System.out.println("C(x)为唯一可译码 !");/解决尾随后缀与C(x)之间的关系(是否存在尾随后缀)private boolean Cprefix_Listprefix(String code, ArrayList<St

12、ring> list1, int k) int s;/ step2 用C(x)中的元素与list集合中的比较看是否存在尾随后缀/ 若是存在尾随后缀，则加入list集合中for (int i = 0; i < code.length; i+) for (int j = 0; j < list1.size(); j+) if(codei.length() < list1.get(j).length()s = pareTo(list1.get(j).substring(0,codei.length();if (s = 0) / 如果有尾随后缀，加入尾随后缀集

13、合中String str = list1.get(j).substring(codei.length(),list1.get(j).length();if (str != null && NotExist(list1,str) list1.add(str);if(Is_UDC(code, list1, k)return false;k = list1.size();/step3 用list中的元素与C(x)中的元素比较看时候有尾随后缀/ 若是存在尾随后缀，则加入list集合中for (int i = 0; i < list1.size(); i+) for (int j

14、= 0; j < code.length; j+) if(list1.get(i).length() < codej.length()s = list1.get(i).compareTo(codej.substring(0, list1.get(i).length();if (s = 0) / 如果有尾随后缀，加入尾随后缀集合中String str = codej.substring(list1.get(i).length(),codej.length();if (str != null && NotExist(list1,str) list1.add(str);i

15、f(Is_UDC(code, list1, k)return false;list = list1;return true;/解决list尾随后缀集合中存在重复元素private boolean NotExist(ArrayList<String> list, String str) for(int i=0; i<list.size(); i+)if(pareTo(list.get(i) = 0)return false;return true;/判断C(x)中的元素是否与list尾随后缀中的元素相同/若有相同，则便是不是唯一可译码private boolean Is_UDC

16、(String code, ArrayList<String> list, int k) if(k = list.size()boolean b = isUDC(code,list);if(b)System.out.println("C(x)为唯一可译码 !");return true; else boolean b = isUDC(code,list); /做出一个判断if(b)System.out.println("C(x)不是唯一可译码 !");return true;return false;private boolean isUDC(String code2, ArrayList<String> list) int s = -1;for (int i = 0; i < code2.length; i+) for (int j = 0; j < list.size(); j+) s = pareTo(list.get(j);if (s = 0) / 判断是否有相同元素return true;return false;五、实验总结1遇到的问题及分析：遇到问题：在刚开始的时候，不知道怎么判断唯一可译码。 分析并解决：通过对唯一可译码概念的了解以