需要理解Sardinas-Patterson算法(算法和示例)
需要理解Sardinas-Patterson算法(算法和示例)
提问于 2012-08-14 04:04:08
我很难从下面的幻灯片中理解Sardinas算法：
我们如何得到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是码字。因此，得出结论，代码不是唯一可解码的。
回答 2
Stack Overflow用户
发布于 2012-08-14 04:47:26
C1是通过查看C中的任何代码单词是否是C中任何其他代码单词的前缀来找到的，如果是，则将后缀添加到集合C1中。例如，1是1110的前缀，因此你会得到后缀110，它被添加到C1中。
对于C2，首先检查C中的代码单词是否是C1中任何其他代码单词的前缀，如果它是所有“悬空后缀”的集合，则检查C1是否是C中任何代码单词的前缀，如果是，则再次生成一组所有“悬空后缀”。然后，取这两组的总和，得到C2。
希望这有点道理。
Stack Overflow用户
发布于 2012-08-14 04:40:36
集合C1和C2对应于这篇维基百科文章中的S1和S2。
具体来说，C1是在我们从C中取下一个单词并删除它的前缀(也在C中)之后，可以保留的一组单词。
对于C2，在从C中取单词并从C1中移除前缀后，或在从C1中取一个单词并从C中移除前缀后，仍然可以保留这些单词。
如果我们想计算C3，我们将在从C中取下一个单词并删除它的前缀(在C2中)之后，取下可以保留的单词，以及在我们从C2中取下一个单词并删除它的前缀(在C中)之后可以保留的单词。
因此，C3将是：{空字，0,011，10，11,1110}。它包含空字，因此算法停止并确定C不是唯一可解码的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/11945627
复制相关文章
相似问题
腾讯云开发者
