我正在浏览The Algorithm Design Manual中的数据结构章节,并遇到了后缀树 .
该示例说明:
输入:
XYZXYZ$
YZXYZ$
ZXYZ$
XYZ$
YZ$
Z$
$
输出:
我无法理解从给定的输入字符串生成该树的方式 . 后缀树用于在给定的字符串中查找给定的子字符串,但给定的树如何帮助它呢?我确实理解下面显示的另一个trie示例,但如果下面的trie被压缩到后缀树,那么它会是什么样子?
我正在浏览The Algorithm Design Manual中的数据结构章节,并遇到了后缀树 .
该示例说明:
输入:
XYZXYZ$
YZXYZ$
ZXYZ$
XYZ$
YZ$
Z$
$
输出:
我无法理解从给定的输入字符串生成该树的方式 . 后缀树用于在给定的字符串中查找给定的子字符串,但给定的树如何帮助它呢?我确实理解下面显示的另一个trie示例,但如果下面的trie被压缩到后缀树,那么它会是什么样子?
3 回答
用于构造后缀树的标准有效算法肯定是非常重要的 . 这样做的主要算法称为Ukkonen算法,并且是对两个额外优化的朴素算法的修改 . 您可能最好阅读this earlier question了解有关如何构建它的详细信息 .
您可以使用radix tries上的标准插入算法构造后缀树,以将每个后缀插入树中,但这样做需要花费时间O(n2),这对于大字符串来说可能很昂贵 .
至于快速子字符串搜索,请记住后缀树是原始字符串的所有后缀的压缩trie(加上一些特殊的字符串结尾标记) . 如果字符串S是初始字符串T的子字符串,并且您拥有T的所有后缀的trie,那么您可以只搜索以查看T是否是该trie中任何字符串的前缀 . 如果是这样,则T必须是S的子字符串,因为它的所有字符都存在于T中的某个位置 . 后缀树子字符串搜索算法正是这种搜索应用于压缩的trie,在每个步骤中都遵循相应的边 .
希望这可以帮助!
你基本上创建了一个patricia trie,其中包含你列出的所有后缀 . 当插入patricia trie时,你会在根目录中搜索从输入字符串中的第一个字符开始的子节点,如果它存在,则继续沿着树继续,但如果不存在,则在根目录下创建一个新节点 . 根将具有与输入字符串中的唯一字符一样多的子项($,a,e,h,i,n,r,s,t,w) . 您可以对输入字符串中的每个字符继续该过程 .
如果您正在寻找子串“hen”,那么从根开始搜索以“h”开头的子项 . 如果子句“h”中的字符串长度继续处理子“h”,直到您到达字符串的末尾或输入字符串和子“h”字符串中的字符不匹配 . 如果你匹配所有孩子“h”,即输入“母鸡”匹配孩子“h”中的“他”,那么继续前进到“h”的孩子,直到你到达“n”,如果它找不到孩子的开头使用“n”,则子串不存在 .
Compact Suffix Trie code:
Suffix Tree code:
当没有选择时,后缀树基本上只是压缩字母串 . 例如,如果你在问题中查看trie的右侧,在看到
w
之后,实际上只有两个选择:was
和when
. 在trie中,was
中的as
和when
中的hen
每个字母仍然有一个节点 . 在后缀树中,你将它们放在两个保持as
和hen
的节点中,因此你的trie的右侧会变成: