后缀树与尝试。区别是什么？ [英] Suffix tree and Tries. What is the difference?

问题描述

我念叨尝试俗称preFIX树木和后缀树。
虽然我已经找到code为特里我找不到一个后缀树的例子。此外，我得到的感觉是，code，它建立了一个特里是一样的一只为后缀树与在前者的情况下我们存储prefixes唯一的不同但在后一种后缀。
这是真的？谁能帮我清除了这一点，在我的头上？一个例子code将是很大的帮助！

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!

推荐答案

一个后缀树可以被看作是建立在一个线索，其中顶部的数据结构，而不是仅仅将字符串本身到线索的，你还要补充该字符串的每一个可能的后缀。举个例子，如果你在一个后缀树想索引的字符串香蕉，你将建立一个线索与以下字符串：

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

一旦这样做了，你可以搜索任何正克，看看它是否是present在索引的字符串。换句话说，在正克搜索是preFIX搜索的字符串的所有可能的后缀。

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屋！