algorithm - 为什么我们需要后缀树中的哨兵字符？

Question

为什么我们在实现后缀树时需要将“$”附加到原始字符串？

Answer 1

当使用特定的构造算法时，在字符串末尾附加一个（甚至更多）特殊字符可能有特殊原因——无论是在后缀树和后缀数组的情况下。

然而，就后缀树而言，最根本的根本原因是后缀树的两个属性的组合：

1. 后缀树是 PATRICIA 树，即边缘标签与尝试的边缘标签不同，是由一个或多个字符组成的字符串
2. 内部节点仅存在于分支点

这意味着您可能会遇到一个边缘标签是另一个边缘标签的情况：

这里的想法是右边的黑色节点是叶子节点，即后缀到此结束。但是如果文本有后缀aa，那么单个字符a也必须是后缀。但是我们无法存储后缀在第一个 之后结束的信息a，因为aa它形成了树的一个连续边（上面的属性 1）。我们必须引入一个可以存储信息的中间节点，如下所示：

但这将是非法的，因为属性 2：除非存在分支点，否则不得存在内部节点。

如果我们可以保证文本的最后一个字符是整个字符串中没有其他地方出现的字符，那么问题就解决了。美元符号通常用作它的符号。

显然，如果最后一个字符没有出现在其他地方，则字符串末尾不可能有任何重复（例如aa，甚至更复杂的，例如abcabc），因此不会出现非分支内部节点的问题。在上面的例子中，放在$字符串末尾的效果是：

现在有三个后缀：aa$,a$和$，但没有一个是另一个的前缀。显然，这意味着我们毕竟需要引入一个内部节点，现在一共有三个叶子。所以，可以肯定的是，这样做的好处并不是我们节省了空间或任何东西变得更有效率。这只是保证上述两个属性的一种方式。当我们证明后缀树的某些有用特性时，这些属性很重要，包括它的内部节点数量与字符串长度呈线性关系（如果允许非分支内部节点，则无法证明这一点）。

这也意味着在实践中，您可能会使用不同的方式来处理作为其他后缀前缀的后缀以及非分支内部节点。例如，如果您使用著名的 Ukkonen 算法来构造树，则无需在末尾附加唯一字符即可这样做；您只需要确保在最后一次迭代之后，将非分支内部节点放在每个隐式后缀的末尾（即，每个后缀都在边缘中间结束）。

同样，在构建后缀树或数组之前将其放在文本末尾可能还有更多且非常具体的原因。$例如，在基于 DC（差异覆盖）原理的后缀数组的构造算法中，您必须$在字符串的末尾放置两个符号，以确保即使字符串的最后一个字符也是完整字符三元组的一部分，因为该算法基于三元排序。此外，在某些特定情况下，$必须以特殊方式解释唯一字符。对于 Ukkonen 构造算法，唯一性就足够了$；对于 DC 后缀数组算法，除了唯一性之外，还有必要$在字典上比所有其他字符都小，并且在基于后缀树的圆形字符串切割算法（最近在这里提到）中，实际上有必要将其解释$为字典上最大的字符。

Answer 2

我怀疑它是出于遍历目的。当您从后缀树生成某些内容时，您需要知道您是否在字符串完成的节点处，如果没有，那么您知道您必须继续前进。查看后缀树为其提供线性时间解决方案的最长公共子字符串$，您需要哨兵来确定您已到达字符串终止的节点。之后你不能完成A-NA。

来自维基百科

Answer 3

1.不是帕特里夏

后缀树不是帕特里夏树，它是基数 2。后缀树节点可能有 2 个或更多子节点。

2. 今天没有任何正当理由

除了添加特殊字符之外，没有任何理由

• 要求有2个或更多的孩子
• 对于 n 个字符的字符串，要求恰好有 n 个叶子

后缀树可以以与压缩特里树（或基数树作为其中一种）相同的方式实现，没有任何特殊符号，在这种情况下也没有任何功能上的缺点。

3. 古老的小径

如果您查看 1973 年的旧书，您会看到与名为“未压缩后缀树”的 trie 结构非常相似，但带有值和终止符号。然后他们压缩它。

4. 但有什么不同？

前缀和后缀树在节点中都有元数据，对吧？它被实现为节点的值。

但是对于后缀树，我们有一个有趣的要求——我们需要一个后缀的索引。因此，在最后一个节点中，我们必须保留两个元数据字段，两个值。而且您需要保持节点大小相同，逐个字节。所以他们通过额外的节点，结束节点

在现代世界中，您可以保留任意数量的字段，您不会保存所花费的每个字节，因此您不需要这个技巧。

5. 那么，我们有理由使用结束符号吗？

是的，可能我们有一个非功能性原因 - 在每个非叶节点中保存几个字节。

6. 仍然......结束符号的任何功能原因？

是的，我们可能有一个结束符号S有用的情况 - GENERALIZED suffix tree，而不仅仅是后缀树。

广义后缀树将需要不同的结束标记，在节点上的集合或作为单独的结束符号。同样，您可以使用或不使用特殊符号来实现。

7. 底线

• 这些要求似乎是旧系统的遗留问题
• 随意以与压缩前缀树相同的方式实现后缀树，没有任何警告，除了在每个节点中为未使用的结束索引标志浪费了几个字节。
• 广义后缀树是一种结构，其中结束符号S 可能有用（但您仍然可以在没有它们的情况下构建它）

我希望这将使情况更清楚。