后缀树和尝试.有什么区别? [英] Suffix tree and Tries. What is the difference?

问题描述

我正在阅读Tries，通常称为前缀树和后缀树.
尽管我找到了 Trie 的代码，但我找不到 Suffix Tree 的示例.另外我觉得构建 Trie 的代码与 Suffix Tree 的代码相同，唯一的区别是在前一种情况下我们存储前缀，但在后缀.
这是真的?谁能帮我在脑海中清除它?示例代码会很有帮助！

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 之上的数据结构，其中，除了将字符串本身添加到 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.

这篇关于后缀树和尝试.有什么区别?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！