为什么我们在后缀树中需要一个哨兵字符？

Question

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

Answer 1

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

然而，在后缀树的情况下，最根本的根本原因是后缀树的两个属性的组合：

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

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

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

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

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

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

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

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

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