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版本。
