Trie与后缀树与后缀数组

哪个结构提供了最佳的性能结果; trie(前缀树),后缀树还是后缀数组? 还有其他类似的结构吗? 什么是这些结构的好的Java实现?

编辑:在这种情况下,我想进行string匹配一个大的名称字典和大量的自然语言文本之间,以便确定文本字典的名称。

这是我们发现的第一个数据结构。

后缀树是对trie的改进(它具有允许线性错误search的后缀链接,后缀树修剪了trie的不必要的分支,因此不需要太多的空间)。

后缀数组是基于后缀树(无后缀链接(慢速错误匹配),但模式匹配非常快)的精简数据结构。

由于消耗太多空间,因此不适合现实世界使用。

后缀树比trie更轻更快,用于索引DNA或优化一些大型的networkingsearch引擎。

后缀数组在一些模式search中比后缀树慢,但使用较less的空间,并且比后缀树更广泛地使用。

在同一个数据结构家族中:

还有其他一些实现,CST是使用后缀数组和一些额外的数据结构来获得一些后缀树searchfunction的后缀树的实现。

FCST进一步采用后缀数组实现采样后缀树。

DFCST是FCST的dynamic版本。

拓展:

两个重要的因素是空间使用和操作执行时间。 你可能会认为,用现代的机器这是不相关的,但索引一个人的DNA将需要40千兆字节的内存(使用未压缩和未优化的后缀树)。 而build立这个索引之一,这个数据可能需要几天时间。 想象一下Google,它有很多可search的数据,他们需要对所有networking数据有一个大的索引,而且每次有人build立网页时都不会改变它。 他们有某种forms的caching。 但主要指标可能是静态的。 每隔几个星期左右,他们会收集所有新的网站和数据,并build立一个新的索引,在新的完成时取代旧的索引。 我不知道他们使用哪种algorithm进行索引,但是它可能是一个在分区数据库中具有后缀树属性的后缀数组。

CST使用8千兆字节,但后缀树操作速度大大降低。

后缀数组可以在700兆到2千兆赫的范围内进行。 然而,你不会发现带有后缀数组的DNA遗传错误(意思是:用通配符search模式要慢得多)。

FCST(完全压缩的后缀树)可以创build800到1.5千兆字节的后缀树。 CST的速度相对较小。

DFCST使用比FCST多20%的空间,并且对FCST的静态实施(但是dynamic指标非常重要)速度减慢。

后缀树没有太多可行的(空间明智的)实现,因为很难使操作速度提高来弥补数据结构RAM空间的成本。

这就是说,后缀树具有非常有趣的模式匹配search结果与错误。 aho corasick没有那么快(虽然几乎和一些操作一样快,而且没有错误匹配),而且Boyer摩尔被留在尘土中。

你打算做什么操作? libdivsufsort曾经是C语言中最好的后缀数组实现

使用后缀树,您可以在O(n + m + k)时间内将字典与您的字典匹配,其中n是字典中的字母,m是文本中的字母,k是匹配的数量。 尝试是慢得多的。 我不确定什么是后缀数组,所以我不能对此发表评论。

也就是说,编码并不重要,我也不知道任何提供必要function的Java库。

编辑:在这种情况下,我想进行string匹配的大型名称字典和大量的自然语言文本之间,以便确定文本字典的名称。

这听起来像是Aho-Corasickalgorithm的一个应用:从字典(线性时间)构造一个自动机,然后可以用它来查找多个文本(也是线性时间)中任何字典单词的所有出现。

( 这些讲义中的描述,从维基百科页面的“外部链接”部分链接起来,比页面上的描述更易于阅读)。

Trie vs后缀树

两种数据结构都保证了查询速度非常快,查询时间与查询词的长度成正比,复杂度时间O(m),其中m是查询词的长度。

这意味着如果我们有10个字符的查询词,那么我们最多需要10个步骤才能find它。

Trie :用于存储string的树,每个公共前缀有一个节点。 string存储在额外的叶节点中。

suffix tree(后缀树) :与特定string的后缀相对应的trie 树的紧凑表示,其中具有一个子元素的所有节点都与其父元素合并。

def来自:algorithm和数据结构字典

通常Trie用于索引字典词汇(词典)或任何string集合,例如D = {abcd,abcdd,bxcdf,…..,zzzz}

一个后缀树,用于通过在我们的文本的所有后缀上使用相同的数据结构“Trie”来索引文本T = abcdabcg所有后缀T = {abcdabcg,abcdabc,abcdab,abcda,abcd,abc,ab,a}

现在它看起来像一组string。 我们build立一个Trie在这组string(T的所有后缀)上。

数据结构的构build是线性的,在时间和空间上占用O(n)。

在dicionary(一组string)的情况下:n =所有单词的字符总和。 在文本中:n =文本的长度。

后缀数组:是一种表示压缩后缀后缀树的技术,它是一个string后缀所有起始位置的数组。

它在search时间比后缀树慢。

欲了解更多信息去维基百科,有一个很好的文章谈这个话题。

诱导sortingalgorithm(称为sais)的这种实现具有用于构build后缀数组的Java版本。