algorithm - 需要帮助理解 Sardinas-Patterson 算法(提供算法和示例)

Question

我很难从下面的幻灯片中理解 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 是一个码字。因此，得出代码不是唯一可解码的结论。

Answer 1

wiki article很好的解释

幻灯片中的 C 对应于维基文章中的 S_i。

这是我的描述:

重要的操作是从 C 中取出两个字符串，如果其中一个是另一个字符串的前缀，则记录删除前缀后留下的后缀。C₁就是这样得到的。

有以下C₂、C₃等。您再次想要从 C 中查找作为 C_i 中的单词前缀的单词并获取剩余的后缀，但您还想查看 C_i 中的单词并删除 C 中作为前缀的单词. C_(i+1) 是这些集合的并集。

只要某些 C_i 包含来自 C 的单词，您就知道代码不是唯一可解码的。

所以:

C = 1, 011, 01110, 1110, 10011

C₁ = 110(因为 (1)110 在 C 中)，0011(因为 (1)0011 在 C 中)，10(因为 (011)10 在 C 中)

C₂ = {10(因为(1)10在C₁)，0(因为(1)0在C₁)} union { 011, 因为 (10)011 在 C 中 }