2

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

3 回答 3

9

wiki文章是一个很好的解释

幻灯片中的 C 对应于 wiki 文章中的 S i。

这是我的描述：

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

使用以下 C 2， C 3等。您再次要查找 C 中的单词，这些单词是 C i中单词的前缀并取剩余的后缀，但是您还想查看 C_i 中的单词并删除单词 from 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 }

于 2012-08-14T04:42:45.247 回答
5

通过查看 C 中的任何代码字是否是 C 中任何其他代码字的前缀来找到 C1，如果是，则将后缀添加到集合 C1。例如，1 是 1110 的前缀，因此您会得到添加到 C1 的后缀 110。

对于 C2，首先检查 C 中的代码字是否是 C1 中任何其他代码字的前缀，如果它是所有“悬空后缀”的集合，然后检查 C1 是否是任何代码的前缀如果是 C 中的单词，则再次制作一组所有“悬空后缀”。然后你取这两组的并集，得到 C2。

希望这有点道理。

于 2012-08-14T04:47:26.450 回答
4

集合 C1 和 C2 对应于这篇 Wikipedia 文章中的 S1 和 S2 。

具体来说，C1 是在我们从 C 中取出一个单词并删除其也在 C 中的一些前缀之后可以保留的单词集。

对于 C2，在我们从 C 中取出一个词并从 C1 中删除一个前缀之后，或者在我们从 C1 中取出一个词并从 C 中删除一个前缀之后，我们可以保留这些词。

如果我们想计算 C3，我们将在我们从 C 中取出一个词并删除它在 C2 中的一些前缀之后，取出可以保留的词，以及在我们从 C2 中取出一个词并删除它的一些前缀之后可以保留的词那是在C中。

因此，C3 将是：{[empty word], 0, 011, 10, 11, 1110}。它包含空字，因此算法停止并确定 C 不是唯一可解码的。

于 2012-08-14T04:40:36.717 回答