3

我们可以使用带有后缀树的圆形字符串吗？所以最后一个字符后面是列表中的第一个字符。

如果是这样，这个后缀树的表示与普通的后缀树有什么不同？

4

3 回答 3

1

这取决于您所说的“使用”是什么意思。

1） 首先，以最直接的方式解释您的问题，考虑一个长度为 n 的圆形字符串，即每 n 个字符重复一次的无限字符串。这样的对象没有通常意义上的后缀，因为它永远不会结束，所以你不能构造它的后缀树。

2)然而，这个想法肯定是我们有一个循环字符串的有限表示，它使用从最后一个字符到第一个字符的链接。以类似的方式，我们可以通过使用指向表示循环字符串的所有（无限长）后缀的循环后缀树的链接来扩展给定的后缀树。请注意，这不能通过插入从每个叶子到节点根的链接来完成，因为从根开始，所有节点都有出边字符串的后缀，但是从这样一个圆形字符串的叶子中，只能有一个出边。示例：代表“mississippi$”的后缀“ssippi$”的叶子应该有一个带有无限标签“mississippi$mississippi$mississippi$....”的出边，并且没有其他边。如果您要将它链接到树的根部，将会有更多不正确的延续。

所以有两件事是必要的：

  • 叶子的出边（毕竟这是一个有趣的概念）。每片叶子都有一个出边。
  • 带有无限标签的边缘。该标签可以表示为圆形字符串（并且该圆形字符串对于叶子的所有传出边缘都是相同的）。

这将为您提供循环字符串的所有（无限）后缀的有效表示。

3）我不确定这种表示是否对任何事情有用。如果构建后缀树的目的是启用子字符串搜索，那么将循环字符串（不包括链接）的有限表示连接到自身并从中构造后缀树的常用技巧就足够了，除非您搜索的子字符串本身长于 n 个字符。

同样重要的是要注意，后缀树的某些其他用途需要引入进一步的“无限”概念。例如，对于某些应用程序，可能需要在该节点中存储树节点的字符深度（即从根到特定节点的边标签的组合长度）。在上面提出的“循环后缀树”中，叶子的出边会导致某种特殊的“极限叶子”，并带有一个圆形字符串作为标签。任何匹配到这样一个循环字符串的查询都需要一种特殊的方式来跟踪匹配深度，因为该边上没有内部节点来存储深度信息。

4)说了这么多，实际上至少有一种已知的后缀树应用于圆形字符串，但不是上面 (1)、(2) 或 (3) 的意义，即通过使用后缀树。而是使用循环字符串的有限子字符串的后缀树来解决字典最小旋转问题。该问题在Wikipedia上进行了描述，尽管其中列出的解决方案不包括任何使用后缀树的解决方案。然而，Dan Gusfield在 7.13 节中的字符串、树和序列算法中描述了解决方案。

这个想法是，您认为长度为 n 的字符串 S 的字典最小旋转集合等效于圆形字符串的第一个长度为 n 的子字符串的集合。那么这个问题就等价于找到一个词典最小的分界点。Gusfield 通过构造字符串 SS$ 的后缀树来解决它，通过在每个节点处获取字典最小边并因此在对应于字典最小截止点的节点处遍历该树。

因此，如 (4) 所示，在循环字符串的上下文中，后缀树有一些实际的“用途”，但我不确定这是否是您感兴趣的那种用途。

于 2012-11-16T07:31:08.783 回答
0

是的，鉴于字符串的长度是有限的，您可以存储圆形字符串。

让我们考虑一个词banban。

下面是结构

root -> b -> a -> n -> b -> a -> n -> $

                    -> $

root -> a -> n -> b -> a -> n -> $

                -> $

root -> n -> b -> a -> n -> $

          -> $

美元符号表示后缀的终止

编辑：

可以在这里找到使用 Java 编程语言的后缀树的简洁实现

编辑：如评论部分所述：

“如果我有字符串 Mississippi 并且我想搜索 'pim' 怎么办？”

pim 不是密西西比的后缀，因此搜索将失败。

编辑：但是 pim 在圆形字符串中，我也想将它添加到 trie

为此，您必须将 prim 视为一个单独的单词并将其添加到 trie 以形成全局增强后缀 trie。

考虑 anb 在原始单词 banban 的循环字符串中。

因此，全局增强后缀 trie 将是：

root -> b -> a -> n -> b -> a -> n -> $ (original word)

          -> a -> n -> $ (original word)

          -> $ (from anb)

root -> a -> n -> b -> a -> n -> $ (original word)

               -> $ (original word)

               -> b -> $ (from anb)

root -> n -> b -> a -> n -> $ (original word)

                -> $ (from anb)

          -> $ (original word)
于 2012-11-15T18:24:35.253 回答
0

我会考虑你想要这个，并考虑以下解决方法：

如果你有一个循环字符串的后缀数组，这将主要是字符串内的偏移量列表，这样从每个偏移量开始的序列都是按排序顺序排列的。

现在假设你有一个通过环绕 ABCD 制成的圆形字符串。考虑通过将除自身的一个字符之外的所有字符附加到它所形成的字符串 - ABCDABC，以及如果从它构建一个后缀数组会发生什么。循环字符串 (ABCD BCDA CDAB DABC) 中的所有序列都出现在 ABCDABC 内，因此当您从中构建后缀数组时，您将获得与从循环字符串构建它相同的后缀数组，其中一些序列带有附加字符结尾（ABCDABC 而不是 ABCD）和一些太短的额外序列（ABC）。您可以通过查看子序列的长度或等效地查看其在 ABCDABC 中的起始位置来识别这两种情况。

显然，您可以在mississippimississipp 中找到pim。

于 2012-11-15T20:18:27.163 回答