基于倒排索引的全文检索技术研究

倒排索引是提高全文检索效率的重要技术,而倒排索引的空间效率、动态性能、创建效率和检索效率一直是倒排索引面临的关键问题,它们之间既紧密联系又相互制约。课题正是围绕倒排索引的压缩、增量更新、填充及检索效率展开,其目的是提高四者的综合性能。

华中科技大学

硕士学位论文

基于倒排索引的全文检索技术研究

姓名：刘兴宇

申请学位级别：硕士

专业：计算机软件与理论

指导教师：吴恒山

20040510

倒排索引是提高全文检索效率的重要技术,而倒排索引的空间效率、动态性能、创建效率和检索效率一直是倒排索引面临的关键问题,它们之间既紧密联系又相互制约。课题正是围绕倒排索引的压缩、增量更新、填充及检索效率展开,其目的是提高四者的综合性能。

华中科技大学硕士学位论文

摘要

倒排索引是提高全文检索效率的重要技术，而倒排索引的空间效率、动态性能、创建效率和检索效率一直是倒排索引面临的关键问题，它们之间既紧密联系又相互制约。课题正是围绕倒排索引的压缩、增量更新、填充及检索效率展开，其目的是提高四者的综合性能。

压缩倒排索引有助于提高查询的吞吐量，因为读和解压已压缩的倒排索引往往比读一个未压缩的倒排索引要快。前人的研究关注得更多的是倒排索引的压缩率，而往往忽略了动态性。为了兼顾动态性，需要研究既能提高压缩率又能方便索引动态更新的压缩方法。在分析倒排列表的动态特点的基础上，得出构成倒排列表的文档编号、单词在文档中的出现频率及相应位置三序列的动态性是不同的，并由此提出一种混合编码的方法。试验表明，混合编码在压缩率方面优于其他支持动态更新的编码。

为了支持倒排索引增量更新，从改进倒排索引的数据结构入手，提出了基于可扩展散列表的倒排索引存储策略。这一策略使倒排索引具有良好的可扩展性，不但减少了动态调整时的移动开销，而且调整后的索引对倒排索引的查询速度影响较小。它既支持文档的插入、删除操作，又具有较高的查询效率和空间利用率。

词库的查找速度是影响倒排索引的填充及检索效率的因素之一。采用有序保留最小完全散列函数实现词库的查找，不但能加快查找速度，而且无需预先对单词排序。试验证明，它能获得比折半查找快近一倍的速度。关键词：信息检索，全文检索，全文索引，倒排索引，倒排索引压缩，增量更新

倒排索引是提高全文检索效率的重要技术,而倒排索引的空间效率、动态性能、创建效率和检索效率一直是倒排索引面临的关键问题,它们之间既紧密联系又相互制约。课题正是围绕倒排索引的压缩、增量更新、填充及检索效率展开,其目的是提高四者的综合性能。

华中科技大学硕士学位论文

Ａｂｓｔｒａｃｔ

Ｉｎｖｅｒｔｅｄｉｎｄｅｘｉｓａｎｉｍｐｏｒｔａｎｔｔｅｃｈｎｉｑｕｅｔｏｉｍｐｒｏｖｅｆｕｌｌ—ｔｅｘｔｒｅｔｒｉｅｖａｌｐｅｒｆｏｒｍａｎｃｅ．Ｔｈｅｓｔｏｒａｇｅｕｔｉｌｉｚａｔｉｏｎ，ｄｙｎａｍｉｃｅｆｆｉｃｉｅｎｃｙ，ｃｒｅａｔｉｏｎｅｆｆｉｃｉｅｎｃｙ，ａｎｄｒｅｔｒｉｅｖａｌｅｆｆｉｃｉｅｎｃｙａｒｅｆｏｕｒｃｒｉｔｉｃａｌｐｒｏｂｌｅｍｓｏｆｉｎｖｅｒｔｅｄｉｎｄｅｘ．Ｔｈｉｓｒｅｓｅａｒｃｈｄｉｓｃｕｓｓｅｓｆｏｕｒａｓｐｅｃｔｓｏｆｉｎｖｅｒｔｅｄｉｎｄｅｘｉｎｃｌｕｄｉｎｇｃｏｍｐｒｅｓｓｉｏｎ，ｉｎｃｒｅｍｅｎｔａｌｕｐｄａｔｅ，ｃｒｅａｔｉｏｎｅｆｆｉｃｉｅｎｃｙ，ａｎｄｒｅｔｒｉｅｖａｌｅｆｆｉｃｉｅｎｃｙ．Ｏｕｒｉｎｔｅｎｔｉｏｎｉｓｔｏｔａｋｅｔｈｅｆｏｕｒａｓｐｅｃｔｓｉｎｔｏａｃｃｏｕｎｔａｎｄｅｎｈａｎｃｅｔｈｅｉｒｉｎｔｅｇｒａｔｅｄｐｅｒｆｏｒｍｅｎｃｅ．Ｃｏｍｐｒｅｓｓｉｏｎｏｆｉｎｖｅｒｔｅｄｆｉｌｅｓｗｉｌｌｒｅｓｕｌｔｉｎａｎｉｎｃｒｅａｓｅｉｎｑｕｅｒｙｔｈｒｏｕｇｈｐｕｔ，ｂｅｃａｕｓｅｔｈｅｔｉｍｅｔｏｌｏａｄａｎｄｄｅｃｏｍｐｒｅｓｓａｃｏｍｐｒｅｓｓｅｄｉｎｖｅｒｔｅｄｌｉｓｔｉｓｓｈｏｒｔｅｒｔｈａｎｔｈｅｔｉｍｅｔｏｌｏａｄａｎｅｖｅｒｃｏｍｐｒｅｓｓｅｄｉｎｖｅｒｔｅｄｌｉｓｔ．Ｐｒｅｖｉｏｕｓｓｔｕｄｙｓａｌｍｏｓｔｆｏｃｕｓｅｄｏｎｔｈｅｃｏｍｐｒｅｓｓｉｏｎｒａｔｉｏ，ａｎｄｕｓｕａｌｌｙｉｇｎｏｒｅｔｈｅｄｙｎａｍｉｃｅｆｆｉｃｉｅｎｃｙｏｆｉｎｖｅｒｔｅｄｆｉｌｅ．Ｉｎｏｒｄｅｒｔｏｃｏｍｂｉｎｅｔｈｅｃｏｍｐｒｅｓｓｉｏｎｗｉｍｄｙｎａｍｉｃｅｆｆｉｃｉｅｎｃｙ，ｉｔｉｓｎｅｃｅｓｓａｒｙｔｏｄｅｖｅｌｏｐａｃｏｍｐｒｅｓｓｉｏｎｍｅｔｈｏｄｗｈｉｃｈｓｕｐｐｏｒｔｓｄｙｎａｍｉｃｕｐｄａｔｅ．Ｔｈｉｓｔｈｅｓｉｓａｎａｌｙｓｅｓｔｈｅｄｙｎａｍｉｃｃｈａｒａｃｔｅｒｏｆｉｎｖｅｒｔｅｄｉｎｄｅｘ，ｔｈｅｎｄｒａｗｓａｃｏｎｃｌｕｓｉｏｎｔｈａｔｔｈｅｔｈｒｅｅｓｕｂｌｉｓｔｓｃｏｎｓｎ＇ｕｃｔｅｄ …… 此处隐藏：12203字，全部文档内容请下载后查看。喜欢就下载吧 ……