Trie与后缀树与后缀数组

Question

哪种结构可提供最佳性能结果; trie（前缀树），后缀树还是后缀数组？还有其他类似的结构吗？这些结构的Java实现是什么？

编辑：在这种情况下，我想打一个大字典的名称和一个大集自然语言文本之间的字符串匹配，以便查明在文本词典的名字。

Answer 1

这个trie是这种被发现的第一个数据结构。

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

后缀阵列是基于后缀树一个精简的数据结构（无后缀链路（慢错误匹配），但是模式匹配是非常快）。

特里并不适合现实世界使用，因为它消耗太多空间。

后缀树比trie更轻更快，用于索引DNA或优化一些大型的网络搜索引擎。

后缀数组在某些模式搜索中比后缀树慢，但使用的空间较少，并且比后缀树更广泛地使用。

在同一个家庭的数据结构：

还有其他的实现中，CST是使用后缀数组和一些额外的数据结构来获得一些后缀树的搜索功能后缀树的实现。

FCST更进一步，它实现了带后缀数组的采样后缀树。

DFCST是FCST的动态版本。

扩大：

两个重要因素是空间使用和操作执行时间。你可能认为，用现代机器这不是相关的，但索引单个人的DNA将需要40千兆字节的内存（使用未压缩和未优化的后缀树）。而要在这么多的数据上构建其中的一个索引可能需要几天时间。想象一下Google，它有很多可搜索的数据，它们需要对所有网络数据有一个大的索引，并且每次有人构建网页时都不会改变它。他们有某种形式的缓存。但主要指标可能是静态的。每隔几个星期左右他们就会收集所有新的网站和数据，并建立一个新的索引，在完成新的索引时替换旧的索引。我不知道他们使用哪种算法进行索引，但它可能是在分区数据库中具有后缀树属性的后缀数组。

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

后缀数组可以在700 megas到2 Gigas中执行相同的操作。然而，你不会在带有后缀数组的DNA中发现遗传错误（意思是：用通配符搜索模式要慢得多）。

FCST（完全压缩的后缀树）可以创建800到1.5 gigas的后缀树。 CST的速度相对较小。

DFCST使用比FCST多20％的空间，并且速度减慢到FCST的静态实现（但动态索引非常重要）。

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

这就是说，后缀树具有非常有趣的模式匹配搜索结果与错误。 aho corasick没有那么快（尽管对于某些操作来说速度几乎一样快，而不是错误匹配），而且Boyer摩尔被留在尘土中。

Answer 2

使用后缀树，你可以写的东西，将符合您的字典文本在O（N + M + k）的时间，其中n是字母在你的字典里，m是在你的文字字母，k是数量火柴。尝试对此慢得多。我不确定后缀数组是什么，所以我不能对此发表评论。

这就是说，这是代码不平凡，我不知道任何Java库提供必要的功能。

Answer 3

编辑：在这种情况下，我想打一个大字典的名称和一大套的 自然语言文本之间的字符串匹配，以便查明在文本词典的名字。

这听起来像是为Aho-Corasick algorithm的应用程序：构建从字典的自动机（线性时间），其然后可以被用于发现的任何的在多个文本字典字所有出现（也以线性时间）。

（在these lecture notes的描述，从维基百科页面的“外部链接”部分联系在一起，是一个更容易比页面本身的描述阅读。）

Answer 4

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

Answer 5

This实施诱导排序算法（称为sais）有一个用于构建后缀数组的Java版本。

Answer 6

特里VS后缀树

两个数据结构，确保一个非常快的查找，搜索的时间是成正比的查询词，复杂时间O（M）的lenght其中m为查询的lenght字。

这意味着如果我们有查询词有10个字符，所以我们最多需要10个步骤才能找到它。

Trie：用于存储字符串的树，其中每个公共前缀有一个节点。字符串存储在额外的叶节点中。

suffix tree：对应于给定字符串的后缀的树状结构的紧凑表示，其中具有一个子元素的所有节点都与其父元素合并。

DEF是从： 字典算法与数据结构的

通常Trie的用于索引字典中的单词（词汇）或字符串 例如d = {ABCD，abcdd，bxcdf的任何集合，.....，ZZZZ}

通过使用相同的数据结构 “Trie树” 在我们的文本T = {abcdabcg，abcdabc，abcdab，ABCDA，ABCD T = abcdabcg 所有后缀的所有后缀来索引文本后缀树， abc，ab，a}

现在它看起来像一组字符串。 我们在这组字符串（T的所有后缀）上构建了一个Trie。

两种数据结构的构造都是线性的，它在时间和空间上都需要O（n）。

在dicionary（一组字符串）的情况下：n =所有单词的字符总和。文本中的 ：n =文本的长度。

后缀数组：是一种表示压缩sapce中的后缀树的技术，它是一个包含字符串后缀的所有起始位置的数组。

它在搜索时间内比后缀树慢。

欲了解更多信息，请转至维基百科，有一篇关于此主题的优秀文章。