后缀树 VS Tries - 用简单的英语来说，有什么区别？

Question

我已经查看了 this questions ，但我仍然没有看到后缀树和 Trie 之间的区别。

两者都具有给定字符串的所有子字符串，那么它们之间有何不同？

Answer 1

后缀树——给出了大文本。查询 - 多次搜索文本中的任何单词。
例子： 您正在使用 solitaire 和 kittens 实现您自己的酷文本编辑器 =) 您将实现

CTRL+F

功能。可能的实现 - 索引文档（创建后缀树），当用户查找某个单词时 - 在树中搜索它。

Trie - 给出一个大文本。查询 - 多次搜索文本中的预定义单词。
示例： 您正在用扑克和贾斯汀·比伯的粉丝实现您自己的酷脸谱=）您不希望您的用户发布脏话。可能的实现 - 创建脏话字典树。当用户输入一些文本时，搜索禁止的单词并将其替换为 *。

一般来说，后缀树= trie。后缀树是某个单词的所有后缀的字典树。当你想在字典中搜索某些内容时，请使用 trie。当您在纯文本中搜索某些内容时，请使用后缀树。

重要提示 - 为大文本构建/重建后缀树是复杂的操作。更改文本后，您必须重新创建后缀树。重建 trie 是一个简单的操作 - 只需在

O(wordLength)

中添加新单词即可

结论
后缀树。 您对未来的查询一无所知。花时间创建后缀树一次，您就可以处理请求了。 已知信息是文本。请求未知但文本已给出且不会经常更改的情况适合使用后缀树。例如，您不能在

CTRL+F

实现中使用 trie（aho-corasick 算法） - 因为您不能将字典作为基于 trie 的 aho-corasick 算法的输入。

特里。 您对要执行搜索的文本一无所知。 但是您知道未来的查询。花时间为查询预处理/准备数据结构，您可以在任何文本中执行搜索查询。例如，在“替换禁用词”任务中，您不知道用户将发布什么文本，但您知道禁用词。 为每个简短的新帖子创建后缀树太愚蠢了=）UPD正如@mightyWOZ在评论中注意到的那样，纯trie不适用，但我们可以使用Aho-Corasick算法，它是trie的扩展。因此，对于 trie 来说，声明仍然成立 - 存在一种方法（Aho-Corasick），它使用 trie 作为基础，预处理查询，然后可以处理任何文本。

Answer 2

trie（来自“检索”）是一棵树，就像二叉树一样，但是键分布在树本身中，每个节点都包含键的一部分，因此所有后代节点共享公共前缀。从功能上讲，它仍然是一棵树，您可以在其中提供一个密钥来访问该节点。与二叉树的两个显着区别是：1）如果您有大量可排序键（例如单词字典），则该树可以更紧凑； 2）典型的用例意味着您更感兴趣的是查找其中是否存在某个键，然后拥有与之相关的一些值；即有时根本没有值，只有键；

现在是后缀树。

从技术上讲，这是一样的，区别在于你使用什么作为密钥。

例如，如果您在 trie 中存储单词“monkey”，那么您的密钥就是这个单词 - “monkey”。但如果你想将其存储在后缀树中，那么你首先需要列出该单词的所有可能后缀：

猴子

• 驴子
• nkey
• 键
• 嘿
• y
然后你就有了 6 个密钥，它们存储在一个…trie 中。结果是后缀树。

可能的用法：你想找到“key”这个词在文本中的位置（文本是“monkey”这个词）；你可以立即找到它 - 只需向下看树，它距离文本开头偏移 3 处。

是的，后缀树也应该存储偏移量。

在最顶层，这就是差异。

（现在的问题是：如何在后缀树中表示长文本？另一个答案说可以 - 但我对此不确定）。