Trie、后缀树、后缀数组

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

编辑：在这种情况下，我想在大型名称词典和大量自然语言文本之间进行字符串匹配，以便识别文本上词典的名称。

特里树是第一个被发现的此类数据结构。

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

后缀数组是基于后缀树的精简数据结构（没有后缀链接（错误匹配缓慢），但模式匹配非常快）。

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

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

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

在同一族数据结构中：

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

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

DFCST 是 FCST 的动态版本。

扩展：

两个重要因素是空间使用和操作执行时间。您可能认为对于现代机器来说这无关紧要，但索引单个人类的 DNA 将需要 40 GB 内存（使用未压缩且未优化的后缀树）。针对如此多的数据构建索引之一可能需要数天的时间。想象一下谷歌，它有大量可搜索的数据，他们需要所有网络数据的大型索引，并且他们不会在每次有人构建网页时更改它。他们有某种形式的缓存。然而，主要索引可能是静态的。每隔几周左右，他们就会收集所有新的网站和数据并建立一个新的索引，当新的索引完成后替换旧的索引。我不知道他们使用哪种算法来索引，但它可能是分区数据库上具有后缀树属性的后缀数组。

CST 使用 8 GB，但后缀树运算速度大大降低。

后缀阵列可以在大约 700 兆到 2 千兆的范围内执行相同的操作。然而，您不会在具有后缀数组的 DNA 中发现遗传错误（这意味着：使用通配符搜索模式要慢得多）。

FCST（完全压缩后缀树）可以创建 800 到 1.5 GB 的后缀树。朝向 CST 的速度下降相当小。

DFCST 比 FCST 多使用 20% 的空间，并且速度低于 FCST 的静态实现（但是动态索引非常重要）。

后缀树的可行（空间方面）实现并不多，因为很难使操作速度提升补偿数据结构 RAM 空间成本。

也就是说，后缀树对于有错误的模式匹配具有非常有趣的搜索结果。 aho corasick 的速度没有那么快（尽管对于某些操作来说几乎一样快，但不是错误匹配），而 boyer moore 则被抛在了后面。