后缀树和Trie树有什么区别？

Question

后缀树和Trie树有什么区别？

94

我正在阅读关于“Tries”（字典树）和“Suffix Trees”（后缀树）的内容。
虽然我已经找到了一个“Trie”的代码，但是我找不到一个“Suffix Tree”的例子。而且我感觉建立“Trie”的代码和建立“Suffix Tree”的代码是一样的，唯一的区别在于前者存储前缀，后者存储后缀。
这是真的吗？有人能帮助我澄清这个问题吗？提供一个示例代码将是很好的帮助！

- Cratylus

2

简而言之，字符串的后缀树是其所有后缀的Patricia Trie。它唯一特殊的地方在于边缘标签是原始字符串的子字符串，因此它们可以表示为一对索引并且仅占用常量空间。这也是为什么它可以在线性时间内构建的原因。 - Niklas B.

7个回答

8

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

但是使用这种朴素的方法，为大小为n的字符串构建此树将是O(n^2)并且需要大量内存。

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

- Juan Lopes

2

那么你的意思是后缀树和后缀 Trie 是一样的吗？ - batman

1

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

- curious

0

希望这个使用JS的后缀树示例能够帮到你。

class SuffixTrie {
  constructor(string) {
    this.root = {};
    this.endSymbol = '*';
    this.populateSuffixTrieFrom(string);
  }

  // O(n^2) time | O(n^2) space
  populateSuffixTrieFrom(string) {
    for (let i = 0; i < string.length; i++)
      this.insertSubStringStartingAt(i, string);
  }

  insertSubStringStartingAt(i, string) {
      let node = this.root;
      for (let j = i; j < string.length; j++) {
        const letter = string[j];
        if (!node.hasOwnProperty(letter)) node[letter] = {};
        node = node[letter];
      }

      node[this.endSymbol] = true;
  }

  // O(m) time | O(1) space
  contains(string) {
    let node = this.root;
    for (let letter of string) {
      if (!node.hasOwnProperty(letter)) return false;
      node = node[letter];
    }
    return node.hasOwnProperty(this.endSymbol);
  }
}

- Wesam Mustafa

0

我会给你一些片段来让你更清楚地理解。免责声明：我不是专家，这些数据结构是从编程面试准备中学到的。

首先，如上所述：后缀字典树是由哈希表（最简单的变体）组成的结构，我们在其中存储所有可能的变体。因此，如果需要，我们可以搜索子字符串。例如：'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 上查看有关此问题的更多解释：实现 Trie (前缀树)。链接：https://leetcode.com/problems/implement-trie-prefix-tree/

- SleeplessChallenger

0

Trie的节点具有指向较短上下文的链接，而“Tree”没有。如果树的节点得到指向较短上下文的链接，则会变成Trie；o）

- Stephan Banev

0

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

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

- Liquidpie

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ze Blob · Accepted Answer

后缀树可以看作是基于字典树的一种数据结构，不仅将字符串本身添加到字典树中，还会添加该字符串的每个可能的后缀。例如，如果您想在后缀树中索引字符串banana，则需要使用以下字符串构建字典树：

banana
anana
nana
ana
na
a

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

这是构建后缀树最简单但速度最慢的方法。事实证明，该数据结构有许多更高级的变体，可以提高空间和构建时间的一种或两者的效果。我在这个领域不太熟悉，无法进行概述，但您可以开始查看后缀数组或这个班级高级数据结构（第16和18讲）。

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