87

我正在阅读Tries通常称为前缀树和Suffix Trees.
虽然我找到了 a 的代码，但Trie我找不到 a 的示例Suffix Tree。我也觉得构建 a 的代码与 a 的代码Trie相同，Suffix Tree唯一的区别是在前一种情况下我们存储前缀但在后缀中。
这是真的？任何人都可以帮我清除这个问题吗？一个示例代码会很有帮助！

4

6 回答 6

68

后缀树可以看作是建立在 trie 之上的数据结构，其中不仅将字符串本身添加到 trie 中，还可以添加该字符串的每个可能的后缀。例如，如果您想在后缀树中索引字符串香蕉，您将使用以下字符串构建一个 trie：

banana
anana
nana
ana
na
a

完成后，您可以搜索任何 n-gram 并查看它是否存在于您的索引字符串中。换句话说，n-gram 搜索是对字符串所有可能后缀的前缀搜索。

这是构建后缀树的最简单和最慢的方法。事实证明，这种数据结构有许多更高级的变体，可以改善空间和构建时间。我对这个领域不够精通，无法给出概述，但您可以从研究后缀数组或此类高级数据结构（第 16 和第 18 讲）开始。

这个答案也很好地解释了这种数据结构的变体。

于 2012-12-15T16:52:40.113 回答
8

如果您想象一个 Trie，其中放置了一些单词的后缀，您将能够非常轻松地查询它以查找字符串的子字符串。这是后缀树背后的主要思想，它基本上是一个“后缀树”。

但是使用这种幼稚的方法，为大小为 n 的字符串构建这棵树将是 O(n^2) 并且占用大量内存。

由于这棵树的所有条目都是同一字符串的后缀，它们共享大量信息，因此有优化的算法可以让您更有效地创建它们。例如，Ukkonen 的算法允许您以 O(n) 的时间复杂度在线创建后缀树。

于 2012-12-15T17:18:29.740 回答
1

区别很简单。后缀树的“虚拟”节点比后缀树少。这些虚拟节点是增加树上查找操作的单个字符

于 2016-01-11T22:24:23.300 回答
0

Trie 的节点具有指向较短上下文的链接，“树”没有它。如果 Tree 的节点链接到较短的上下文，那么它会转向 Trie ;o)

于 2020-05-05T02:47:43.933 回答
0

给定文本的后缀树是给定文本的所有后缀的压缩树。

参考：https ://www.geeksforgeeks.org/pattern-searching-using-suffix-tree/

于 2021-04-04T21:30:19.940 回答
0

我会给你一些片段，让你的理解更清楚。免责声明：我不是专家，并且从编码面试准备中了解这些 DS。

首先，如上所述：suffix trie 是由哈希表（最简单的变体）组成的结构，我们在其中存储所有可能的变体。因此，如果需要，我们可以搜索子字符串。例如：'abc'。

{'a': True, 
  'a': {'b': True},
  'a': {'b': {'c': True}}, 
  'b': True,
  'b': {'c': True},
  'c': True}

Trie 是我们存储完整字符串以检查它们是否存在的时候。前任：{'t': {'h': {'i': {'s': {'*': 'this'}}}}, 'y': {'o': {'*': 'yo'}}

你可以在 Leetcode 上查看更多解释问题：Implement Trie (Prefix Tree)。链接：https ://leetcode.com/problems/implement-trie-prefix-tree/

于 2021-09-03T03:46:51.853 回答