后缀树如何工作？

我正在浏览The Algorithm Design Manual中的数据结构章节，并且遇到了后缀树。后缀树如何工作？

的例子指出：

输入：

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

输出：

enter image description here

我无法理解该如何获取树从给定的输入字符串产生。后缀树用于在给定的字符串中查找给定的子字符串，但给定的树如何帮助它？我确实理解另一个给出的如下所示的trie的示例，但是如果下面的trie被压缩为后缀树，那么它会是什么样子？

enter image description here

来源

2012-06-13 Anthony

我发现这2个视频了解后缀树非常有帮助。 http://www.youtube.com/watch?v=VA9m_l6LpwI＆http://www.youtube.com/watch?v=F3nbY3hIDLQ#t=2360 – spats

构建一个后缀树的标准高效的算法肯定是平凡的。这样做的主要算法称为Ukkonen算法，它是对两个额外优化的朴素算法的修改。有关如何构建它的详细信息，您可能最好阅读this earlier question。

可以通过使用上radix tries标准插入算法来插入每个后缀到树，但这样做wlil需要时间为O（n 2 ），其可以是用于大型字符串昂贵构造后缀树。

至于做快速子串搜索，请记住后缀树是原始字符串的所有后缀（加上一些特殊的字符串结束标记）的压缩树。如果一个字符串S是初始字符串T的一个子字符串，并且你有一个T的所有后缀的trie，那么你可以做一个搜索来查看T是否是该字典中任何字符串的前缀。如果是这样，那么T必须是S的子串，因为它的所有字符都按顺序存在于T中。后缀树子串搜索算法恰恰是将这种搜索应用于压缩的树状结构，在这里你遵循每一步的适当边缘。

希望这会有所帮助！

来源

2012-06-13 17:03:00 templatetypedef

后缀树基本上只是在没有可供选择的情况下将字母串压缩在一起。例如，如果您在问题中查看问题的右侧，看到w后，实际上只有两个选择：was和when。在特里，as在was和hen在when每个仍然有一个节点为每个字母。在一个后缀树，你就会把这些汇集成控股as和hen两个节点，所以您的线索的右侧就会变成：

enter image description here

来源

2012-06-13 17:03:24

看起来像一个压缩的trie也 – DarthVader

@DarthVader：引用[ Wiki]（http://en.wikipedia.org/wiki/Suffix_tree）（在这种罕见的情况下，实际上似乎有些事情是正确的）：“字符串”S“的后缀树是一个树，其边缘用字符串，使得每个后缀对应于从树的根到叶的恰好一条路径，因此它是基数树（更具体地说，是一个帕特里夏树），用于后缀“S”。 –

我无法理解怎么说树从给定的输入字符串中生成。

本质上，您创建了一个包含您列出的所有后缀的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”表示子字符串不存在。

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$

来源

2012-06-13 17:04:49 Justin

后缀树如何工作？

回答

相关问题