我正在浏览The Algorithm Design Manual中的数据结构章节，并遇到了 Suffix Trees。
该示例指出：
输入：
XYZXYZ$
YZXYZ$
ZXYZ$
XYZ$
YZ$
Z$
$
输出：
我无法理解该树是如何从给定的输入字符串生成的。后缀树用于在给定字符串中查找给定子字符串，但给定树如何帮助实现这一点？我确实理解下面显示的另一个给定的 trie 示例，但是如果下面的 trie 被压缩为后缀树，那么它会是什么样子？
4708 次
3 回答
5
构建后缀树的标准高效算法绝对是不平凡的。这样做的主要算法称为 Ukkonen 算法，它是对朴素算法的修改，具有两个额外的优化。您可能最好阅读这个较早的问题，以了解有关如何构建它的详细信息。
您可以通过使用基数上的标准插入算法来构建后缀树，尝试将每个后缀插入树中，但这样做会花费时间 O(n 2 )，这对于大字符串来说可能很昂贵。
至于进行快速子字符串搜索，请记住后缀树是原始字符串的所有后缀的压缩树（加上一些特殊的字符串结束标记）。如果字符串 S 是初始字符串 T 的子字符串，并且您有 T 的所有后缀的 trie，那么您只需搜索 T 是否是该 trie 中任何字符串的前缀。如果是这样，那么 T 必须是 S 的子串，因为它的所有字符都按顺序存在于 T 中的某个位置。后缀树子串搜索算法正是应用于压缩特里树的这种搜索，您在每一步都遵循适当的边缘。
希望这可以帮助！
于 2012-06-13T17:03:00.963 回答
1
我无法理解该树是如何从给定的输入字符串生成的。
您实际上创建了一个包含您列出的所有后缀的 patricia trie。插入 patricia trie 时，您从输入字符串中的第一个字符开始搜索根以查找子节点，如果存在，则继续沿树向下，如果不存在，则从根中创建一个新节点。根的子节点与输入字符串中的唯一字符（$、a、e、h、i、n、r、s、t、w）一样多。您可以对输入字符串中的每个字符继续该过程。
后缀树用于在给定字符串中查找给定子字符串，但给定树如何帮助实现这一点？
如果您正在寻找子字符串“hen”，则从根开始搜索以“h”开头的子字符串。如果子“h”中字符串的长度，则继续处理子“h”，直到到达字符串的末尾，或者输入字符串和子“h”字符串中的字符不匹配。如果匹配所有子“h”，即输入“hen”匹配子“h”中的“he”，然后继续搜索“h”的子元素，直到找到“n”，如果它未能找到开始的子元素使用“n”则子字符串不存在。
└── (black)
├── (white) as
├── (white) e
│ ├── (white) eir
│ ├── (white) en
│ └── (white) ere
├── (white) he
│ ├── (white) heir
│ ├── (white) hen
│ └── (white) here
├── (white) ir
├── (white) n
├── (white) r
│ └── (white) re
├── (white) s
├── (white) the
│ ├── (white) their
│ └── (white) there
└── (black) w
├── (white) was
└── (white) when
String = the$their$there$was$when$
End of word character = $
└── (0)
├── (22) $
├── (25) as$
├── (9) e
│ ├── (10) ir$
│ ├── (32) n$
│ └── (17) re$
├── (7) he
│ ├── (2) $
│ ├── (8) ir$
│ ├── (31) n$
│ └── (16) re$
├── (11) ir$
├── (33) n$
├── (18) r
│ ├── (12) $
│ └── (19) e$
├── (26) s$
├── (5) the
│ ├── (1) $
│ ├── (6) ir$
│ └── (15) re$
└── (29) w
├── (24) as$
└── (30) hen$
于 2012-06-13T17:04:49.780 回答
0
当没有选择时，后缀树基本上只是将一系列字母压缩在一起。例如，如果您查看问题中 trie 的右侧，在您看到 a 之后w，实际上只有两个选择：was和when。在 trie 中，asinwas和henin 中when的每个字母仍然有一个节点。在后缀树中，您可以将它们放在两个节点中，分别为asand hen，因此您的 trie 的右侧将变为：
于 2012-06-13T17:03:24.307 回答