全文索引技术中索引归并算法的研究与分析

论文摘要

索引的动态维护与更新是全文检索与全文索引技术中的一个重要研究和应用方向,当随着Internet的迅速发展,互联网上信息数据在急剧地增长,而在这种海量数据的情况下,新的数据在不断增长,同时过时的数据就要被淘汰,这就需要对信息数据频繁的插入和删除,因此,索引的动态维护中的归并算法的研究也就处于了一个十分重要的地位。本论文主要针对常见的索引归并算法进行改良,并对改良的算法在时间效率以及可行性上进行了研究论述。索引的过程就是把原始的数据处理成一个有利于高效检索的数据形式,因此索引的基本结构关系到动态索引维护与更新的效率,包括建立索引的过程,索引的组织方式,正排表,倒排文件及倒排索引的建立,本文介绍了构造倒排索引的过程,并分析静态索引技术的优缺点以及增量索引知识,还有索引动态更新对信息检索技术的重要性。本文比较了各种索引更新策略,包括原地更新策略,重建策略,重新归并更新策略,并且分析了这些策略的成本代价,在此基础上研究了基于归并策略的各种不同的索引归并算法,包括有立即归并算法,对数归并算法,几何划分归并算法,类哈夫曼索引归并算法,同时分析了他们的优缺点,提出了各自的改良算法,其中本文的重点是在详细分析几何划分归并算法的基础上,针对原有的几何归并算法在索引过程中没有对文档删除,提出了带有索引垃圾碎片的回收的新的几何归并算法,其中新算法采用了极限值的方法对删除的文档进行处理。最后通过一个开源的全文检索与全文索引平台测试了立即归并算法,对数归并算法及改进算法的索引合并过程和时间,验证了在相同条件下使用改进的算法进行合并,时间上得到了提高。测试了几何归并删除文档索引碎片回收的可行性。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究的技术热点
• 1.3 研究现状
• 1.4 本文组织结构
• 第二章 索引关键技术
• 2.1 索引的基本知识
• 2.1.1 建立索引的过程
• 2.1.2 索引在信息检索中的作用
• 2.2 全文检索与全文索引
• 2.2.1 全文检索
• 2.2.2 全文检索的索引器结构
• 2.3 全文索引的组织方式
• 2.3.1 正排表
• 2.3.2 倒排索引
• 2.3.3 倒排文件索引压缩
• 2.4 静态索引与增量索引
• 2.4.1 静态索引技术
• 2.4.2 增量索引
• 2.5 全文检索中索引的更新维护
• 第三章 索引维护策略的分析
• 3.1 更新维护的策略
• 3.2 原地更新策略
• 3.2.1 策略思想及描述
• 3.2.2 策略耗用成本
• 3.3 重建索引维护策略
• 3.3.1 策略思想及描述
• 3.3.2 策略耗用成本
• 3.4 重新归并索引维护策略
• 3.4.1 策略耗用成本
• 第四章 索引归并算法及其改进思路
• 4.1 立即归并算法及其改进思路
• 4.1.1 立即归并算法
• 4.1.2 立即归并算法的改进
• 4.2 对数归并算法及其改进思路
• 4.2.1 对数归并算法
• 4.2.2 对数归并算法的改进
• 4.3 几何划分归并算法
• 4.3.1 几何划分归并算法思想
• 4.3.2 对几何划分归并的思考
• 4.3.3 几何归并算法的不足之处
• 4.3.4 带索引碎片回收的算法采用
• 4.4 类哈夫曼归并算法
• 4.4.1 动态类哈夫曼树的索引合并
• 4.4.2 类哈夫曼树的算法分析
• 4.5 各种索引归并算法分析
• 第五章 实验测试数据分析
• 5.1 立即归并及改进算法的数据比较
• 5.2 对数归并及改进算法的数据比较
• 5.3 几何划分归并的数据比较
• 5.4 测试总结
• 第六章 结论与展望
• 6.1 本论文总结
• 6.2 展望
• 致谢
• 参考文献
• 攻硕期间取得的研究成果