基于双数组Trie的高效索引结构及其并行化的研究

发布时间：2020-07-31 22:05

【摘要】：字符串搜索被广泛应用于搜索引擎,网络入侵检测、计算机病毒特征码匹配以及DNA序列匹配等诸多问题中。为了有效进行字符串搜索,需要一个合适的存储和管理字符串的数据结构。Trie是一种有效的字符串处理的经典数据结构,尤其适合字符串查找以及前缀查找。常见的Trie树存储方式有矩阵存储和链式存储两种,矩阵存储查询速度快但存在空间浪费严重的问题,链式存储空间利用率高但查询效率比较低。而双数组Trie能有效结合Trie树上述两种表现形式的优点,在具有低的存储空间的同时,具有高的查询效率。双数组Trie虽然结合了上述Trie树的两种表现形式的一些优点,但其创建的效率随着数据量的增加而出现急剧下降的情况。针对此问题,本文通过对双数组Trie索引创建过程深入分析和研究发现,索引创建效率降低的主要原因在于索引创建的过程产生的冲突及冲突处理的开销。为此,本文提出了一种分区双数组Trie索引结构来提高索引创建的效率,该结构主要从以下两个角度提升索引创建的效率:1)开发字典序即将字符串数据集按照字典序进行升序排序,从而可减少索引创建过程中发生冲突时移动的数据量。2)创建首字符分区的分区双数组结构从而可降低冲突的数量以及减少解决冲突所产生的开销。实验结果表明,本文提出的分区双数组Trie索引结构可同时降低冲突的数量及处理冲突的开销,在大幅提高索引创建的效率的同时,还可进一步提高索引的查询效率。为了能进一步提高双数组Trie索引创建的效率,本文在多核平台上基于OpenMP进行并行双数组结构的的研究。为实现高效的并行,本文进一步提出一种等字符串数量的高效分区策略,从而使得线程之间的负载尽量均衡。并通过扩展实验对比了在不同分区策略下索引创建和查询算法的性能,实验结果表明,相对于串行的创建索引,并行创建双数组Trie索引在性能上有着可观的提升。
【学位授予单位】：昆明理工大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：TP391.3
【图文】：

集合K的Arraytrie

数组,复杂度,Trie树,长度

昆明理工大学硕士学位论文样的实现，空置指针的数量是非常庞大的。Trie 树的另一种常见的存储形式即 List Trie[47]树，与 array trie 树相比，更加紧凑。在 Array trie 这种数据结构中，每一级的数组的长度都是不的，所以其存储空间是非常浪费的。但是，如果每一层数组的长度是可层结点的数量进行动态的调整，那么这样就可以避免大量的空间浪费，节省空间的目的。如图 2.3 所示。

【参考文献】