特里vs.后缀树vs.后缀数组

Question

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

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

Answer 1

特里树是第一个发现的这种数据结构。

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

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

该Trie不适用于现实世界，因为它占用了太多空间。

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

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

在同一系列的数据结构中：

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

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

DFCST是FCST的动态版本。

扩展中：

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

CST使用8 GB，但是后缀树的操作速度大大降低了。

后缀数组可以在700兆至2 Gigas的范围内完成相同的操作。但是，您不会在带有后缀数组的DNA中发现遗传错误（这意味着：使用通配符搜索模式要慢得多）。

FCST（完全压缩的后缀树）可以创建800至1.5 gigas的后缀树。速度对CST的影响很小。

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

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

也就是说，后缀树具有非常有趣的搜索结果，用于模式匹配错误。aho
corasick的速度不快（尽管在某些操作中几乎快，但没有错误匹配），但波耶尔摩尔仍留在尘埃中。