哪种结构能提供最好的性能结果； trie(前缀树)、后缀树还是后缀数组？还有其他类似的结构吗？这些结构有哪些好的 Java 实现？
编辑:在这种情况下，我想在大型名称字典和大量自然语言文本之间进行字符串匹配，以便识别文本上字典的名称。
最佳答案
trie 是发现的第一个此类数据结构。
后缀树是对 trie 的改进(它具有允许线性错误搜索的后缀链接，后缀树修剪了 trie 的不必要分支，因此它不需要太多空间)。
后缀数组是基于后缀树的精简数据结构(没有后缀链接(错误匹配慢)，但模式匹配非常快)。
trie 不适用于现实世界，因为它占用了太多空间。
后缀树比 trie 更轻更快，用于索引 DNA 或优化一些大型网络搜索引擎。
在某些模式搜索中，后缀数组比后缀树慢，但占用的空间更少，比后缀树使用更广泛。
在同一系列的数据结构中:
还有其他实现，CST 是后缀树的实现，使用后缀数组和一些额外的数据结构来获得一些后缀树搜索功能。
FCST 更进一步，它实现了一个带有后缀数组的采样后缀树。
DFCST 是 FCST 的动态版本。
扩展:
两个重要的因素是空间使用和操作执行时间。您可能认为这与现代机器无关，但索引一个人的 DNA 需要 40 GB 的内存(使用未压缩和未优化的后缀树)。在这么多数据上构建其中一个索引可能需要数天时间。想象一下谷歌，它有很多可搜索的数据，他们需要一个包含所有网络数据的大型索引，而且他们不会在每次有人构建网页时都更改它。他们为此提供了某种形式的缓存。然而，主要指数可能是静态的。每隔几周左右，他们就会收集所有新的网站和数据，并建立一个新的索引，在新的完成后替换旧的。我不知道他们使用哪种算法来索引，但它可能是一个在分区数据库上具有后缀树属性的后缀数组。
CST 使用 8 GB，但后缀树操作速度大大降低。
后缀阵列可以在大约 700 兆到 2 兆的情况下执行相同的操作。但是，您不会在带有后缀数组的 DNA 中发现遗传错误(意思是:搜索带有通配符的模式要慢得多)。
FCST(完全压缩的后缀树)可以创建 800 到 1.5 千兆的后缀树。向 CST 方向的速度下降幅度很小。
DFCST 使用的空间比 FCST 多 20%，并且速度比 FCST 的静态实现慢(但是动态索引非常重要)。
后缀树的可行(空间方面)实现并不多，因为很难使操作速度提升补偿数据结构 RAM 空间成本。
这就是说，后缀树对于带有错误的模式匹配有非常有趣的搜索结果。 aho corasick 没有那么快(尽管对于某些操作来说几乎一样快，而不是错误匹配)，并且 boyer moore 被抛在了尘土中。
关于java - Trie vs. 后缀树 vs. 后缀数组，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2487576/