需要协助了解Sardinas-Patterson算法(提供的算法和示例)
我从下面的幻灯片中了解Sardinas-Patterson算法有困难:
我们如何获得C1和C2 ???
我也从互联网上获得了这些信息:
该算法是有限的,因为添加到列表中的所有悬空后缀都是有限的一组码字的后缀,并且悬挂后缀最多可以添加一次.
- {0,01,11}.代码字0是前缀01,因此添加悬空后缀1. {0,01,11,1}.代码字0是前缀01,但悬挂后缀1已经在列表中; 代码字1是11的前缀,但悬挂后缀1已经在列表中.没有其他悬空后缀,因此得出结论,该集合是唯一可解码的.
- {0,01,10}.代码字0是前缀01,因此将悬挂后缀1添加到列表中.{0,01,10,1}.码字1是10的前缀,但悬挂后缀0是码字.因此,得出结论,代码不是唯一可解码的.
该wiki文章是一个很好的解释
幻灯片中的C对应于wiki文章中的S i.
这是我的描述:
重要的操作是从C中获取两个字符串,如果其中一个字符串是另一个字符串的前缀,则记录删除前缀时留下的后缀.这就是获得C 1的方式.
使用以下C 2,C 3等.您再次想要查找来自C的单词,这些单词是来自C i的单词的前缀并取剩余的后缀,但您还要查看来自C_i的单词并删除单词和来自C是前缀.C (i + 1)是这些集合的联合.
一旦C i包含来自C的单词,您就知道代码不是唯一可解码的.
所以:
C = 1,011,01110,1110,10011
C 1 = 110(因为(1)110在C中),0011(因为(1)0011在C中),10(因为(011)10在C中)
C 2 = {10(因为(1)10在C 1中),0(因为(1)0在C 1中)} union {011,因为(10)011在C中}
通过查看C中的任何代码字是否是C中任何其他代码字的前缀来找到C1,如果是,则将后缀添加到集合C1中.例如1是1110的前缀,因此你得到后缀110,它被添加到C1.
对于C2,首先检查C中的代码字是否是C1中任何其他代码字的前缀,如果它是一组所有"悬挂后缀",则检查C1是否是任何代码的前缀C中的单词,如果它再次成为一组所有"悬挂后缀".然后你取两个集合的结合,产生C2.
希望这有点意义.