Dav*_*pos 39 java arrays trie data-structures
哪种结构提供最佳性能结果; trie(前缀树),后缀树或后缀数组？还有其他类似的结构吗？这些结构有哪些优秀的Java实现？
编辑:在这种情况下,我想在一个大的名字字典和一大组自然语言文本之间进行字符串匹配,以便识别文本上字典的名称.
Mig*_*edo 56
trie是第一个发现的数据结构.
后缀树是对trie的改进(它具有后缀链接,允许线性错误搜索,后缀树修剪trie的不必要的分支,因此它不需要那么多的空间).
后缀数组是基于后缀树的精简数据结构(没有后缀链接(慢错误匹配),但模式匹配非常快).
trie不适合现实世界使用,因为它占用太多空间.
后缀树比trie更轻更快,用于索引DNA或优化一些大型网络搜索引擎.
某些模式搜索中的后缀数组比后缀树慢,但使用的空间更少,并且比后缀树使用得更广泛.
在同一系列的数据结构中:
还有其他实现,CST是后缀树的实现,使用后缀数组和一些额外的数据结构来获得一些后缀树搜索功能.
FCST进一步采用它,它实现了带后缀数组的采样后缀树.
DFCST是FCST的动态版本.
拓展:
两个重要因素是空间使用和操作执行时间.你可能会认为,对于现代机器而言,这是不相关的,但索引单个人的DNA将需要40千兆字节的内存(使用未压缩和未优化的后缀树).要在这么多数据上构建其中一个索引可能需要数天时间.想象一下谷歌,它有很多可搜索的数据,他们需要一个大的索引覆盖所有的网络数据,并且每次有人建立网页时都不会改变它.他们有某种形式的缓存.然而,主要指数可能是静态的.每隔几周左右,他们会收集所有新的网站和数据,并建立一个新的索引,在新的完成时替换旧的索引.我不知道他们使用哪种算法进行索引,但它可能是一个后缀数组,在分区数据库上有后缀树属性.
CST使用8千兆字节,但后缀树操作速度大大降低.
后缀数组可以在700 megas到2 Gigas中执行相同的操作.但是,您不会在带有后缀数组的DNA中发现遗传错误(意味着:使用通配符搜索模式要慢得多).
FCST(完全压缩的后缀树)可以创建800到1.5千兆的后缀树.对CST的速度恶化相当小.
DFCST使用的空间比FCST多20%,并且失去了FCST静态实现的速度(但动态索引非常重要).
后缀树的可行(空间明智)实现并不多,因为很难使操作速度提升补偿数据结构RAM空间成本.
这就是说,后缀树具有非常有趣的搜索结果,用于匹配错误的模式.aho corasick不是那么快(虽然对于某些操作几乎同样快,而不是错误匹配)并且boyer moore留在尘埃中.