首页 文章

后缀树如何工作?

提问于
浏览
5

我正在浏览The Algorithm Design Manual中的数据结构章节,并遇到了后缀树 .

该示例说明:

输入:

XYZXYZ$
 YZXYZ$
  ZXYZ$
   XYZ$
    YZ$
     Z$
      $

输出:

enter image description here

我无法理解从给定的输入字符串生成该树的方式 . 后缀树用于在给定的字符串中查找给定的子字符串,但给定的树如何帮助它呢?我确实理解下面显示的另一个trie示例,但如果下面的trie被压缩到后缀树,那么它会是什么样子?

enter image description here

3 回答

  • 5

    用于构造后缀树的标准有效算法肯定是非常重要的 . 这样做的主要算法称为Ukkonen算法,并且是对两个额外优化的朴素算法的修改 . 您可能最好阅读this earlier question了解有关如何构建它的详细信息 .

    您可以使用radix tries上的标准插入算法构造后缀树,以将每个后缀插入树中,但这样做需要花费时间O(n2),这对于大字符串来说可能很昂贵 .

    至于快速子字符串搜索,请记住后缀树是原始字符串的所有后缀的压缩trie(加上一些特殊的字符串结尾标记) . 如果字符串S是初始字符串T的子字符串,并且您拥有T的所有后缀的trie,那么您可以只搜索以查看T是否是该trie中任何字符串的前缀 . 如果是这样,则T必须是S的子字符串,因为它的所有字符都存在于T中的某个位置 . 后缀树子字符串搜索算法正是这种搜索应用于压缩的trie,在每个步骤中都遵循相应的边 .

    希望这可以帮助!

  • 0

    我无法理解从给定的输入字符串生成该树的方式 .

    你基本上创建了一个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

    └── (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
    

    Suffix Tree code

    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$
    
  • 1

    当没有选择时,后缀树基本上只是压缩字母串 . 例如,如果你在问题中查看trie的右侧,在看到 w 之后,实际上只有两个选择: waswhen . 在trie中, was 中的 aswhen 中的 hen 每个字母仍然有一个节点 . 在后缀树中,你将它们放在两个保持 ashen 的节点中,因此你的trie的右侧会变成:

    enter image description here

相关问题