后缀树和Tries。有什么不同？ [英] Suffix tree and Tries. What is the difference?

问题描述

我正在阅读关于 Tries 通常被称为前缀树和后缀树。

虽然我找到一个 Trie 的代码，我找不到一个后缀树的示例。另外，我感觉到构建 Trie 的代码与后缀树的代码相同，具有唯一的区别是，在前一种情况下，我们存储前缀，但在后面的后缀。

这是真的吗？任何人都可以帮助我清除这一点吗？一个示例代码将是很好的帮助！

I am reading about Tries commonly known as Prefix trees and Suffix Trees.
Although I have found code for a Trie I can not find an example for a Suffix Tree. Also I get the feeling that the code that builds a Trie is the same as the one for a Suffix Tree with the only difference that in the former case we store prefixes but in the latter suffixes.
Is this true? Can anyone help me clear this out in my head? An example code would be great help!

推荐答案

后缀树可以被看作是建立在一个特里的顶部的数据结构， ，而不是将字符串本身添加到trie中，您还可以添加该字符串的每个可能的后缀。例如，如果您想在后缀树中编写字符串 banana ，您将使用以下字符串构建一个特技：

A suffix tree can be viewed as a data structure built on top of a trie where, instead of just adding the string itself into the trie, you would also add every possible suffix of that string. As an example, if you wanted to index the string banana in a suffix tree, you would build a trie with the following strings:

banana
anana
nana
ana
na
a

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

Once that's done you can search for any n-gram and see if it is present in your indexed string. In other words, the n-gram search is a prefix search of all possible suffixes of your string.

这是构建后缀树的最简单和最慢的方法。事实证明，这种数据结构上有许多改进者可以改善空间和构建时间。我在这个领域不够精通，可以概述一下，但您可以先看看后缀数组或这个类高级数据结构（演讲16和18）。

This is the simplest and slowest way to build a suffix tree. It turns out that there are many fancier variants on this data structure that improve on either or both space and build time. I'm not well versed enough in this domain to give an overview but you can start by looking into suffix arrays or this class advanced data structures (lecture 16 and 18).

此答案也解释了这种数据结构的变体，这是一个奇妙的工作。

This answer also does a wonderfull job explaining a variant of this data-structure.

这篇关于后缀树和Tries。有什么不同？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！