Trie 与后缀树与后缀数组

trie是发现的第一个此类数据结构。

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

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

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

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

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

在同一系列数据结构中：

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

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

DFCST是FCST的动态版本。

扩大：

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

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

后缀数组可以在大约700兆到2千兆之间做同样的事情。但是，您不会在带有后缀数组的DNA中找到遗传错误（这意味着：使用通配符搜索模式要慢得多）。

FCST（完全压缩的后缀树）可以创建 800 到 1.5 千兆的后缀树。以相当小的速度向科技委恶化。

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

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

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

您计划进行哪些操作？libdivsufsort曾经是C中最好的后缀数组实现。