面向动态文本的在线索引若干问题研究

摘要

倒排索引是提高检索效率的重要技术,如何平衡倒排索引的空间效率、动态性能和检索效率是倒排索引面临的关键问题。本文主要围绕动态环境下索引的构建合并与更新、压缩存储和查询检索等方面展开研究,以提高检索系统的综合性能。
　　 论文首先介绍了所选课题的研究背景与意义,分析了国内外在线索引的结构模型、压缩及更新维护的现状,同时提出了本课题研究的主要内容。
　　 其次重点分析在线索引的存储问题,设计了在线索引的四级层次结构,并实现了支持在线索引的文件系统,主要包括barrels桶文件、fdd存储域文件、fdl存储域链接文件,voc词典表文件和fot词条频率文件等。
　　 随后,针对海量数据存储空间不足,传统压缩文件的查询、元素的添加、修改和删除操作比较麻烦等问题,在分析Golomb编码和BIC编码等常用编码基础上,提出了面向位操作的动态分块自索引压缩方法(Bit DIB)和面向字节操作的动态分块自索引压缩方法(Byte DIB)。
　　 论文接着研究了在线索引的更新维护问题,设计了基于DIB自索引压缩结构的索引更新算法,该方法适合文本内容更新量较小的情况。随后,针对索引合并问题,提出了合并策略应遵循的四个原则,分析了re-build、re-merge、in-place和hybridapproach四种索引维护方式,在总结GP、LOG和DBT等合并策略的基础上设计了基于N级类状态图(NSD)的索引合并算法。
　　 最后,在理论研究的基础上,设计并实现了在线索引工具(On-line Indexing Tools)的原型系统,为后继研究提供了实验平台。