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

华中科技大学

硕士学位论文

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

姓名：刘兴宇

申请学位级别：硕士

专业：计算机软件与理论

指导教师：吴恒山

20040510

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

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

摘要

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

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

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

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

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

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

Ａｂｓｔｒａｃｔ

Ｉｎｖｅｒｔｅｄｉｎｄｅｘｉｓａｎｉｍｐｏｒｔａｎｔｔｅｃｈｎｉｑｕｅｔｏｉｍｐｒｏｖｅｆｕｌｌ—ｔｅｘｔｒｅｔｒｉｅｖａｌｐｅｒｆｏｒｍａｎｃｅ．Ｔｈｅｓｔｏｒａｇｅｕｔｉｌｉｚａｔｉｏｎ，ｄｙｎａｍｉｃｅｆｆｉｃｉｅｎｃｙ，ｃｒｅａｔｉｏｎｅｆｆｉｃｉｅｎｃｙ，ａｎｄｒｅｔｒｉｅｖａｌｅｆｆｉｃｉｅｎｃｙａｒｅｆｏｕｒｃｒｉｔｉｃａｌｐｒｏｂｌｅｍｓｏｆｉｎｖｅｒｔｅｄｉｎｄｅｘ．Ｔｈｉｓｒｅｓｅａｒｃｈｄｉｓｃｕｓｓｅｓｆｏｕｒａｓｐｅｃｔｓｏｆｉｎｖｅｒｔｅｄｉｎｄｅｘｉｎｃｌｕｄｉｎｇｃｏｍｐｒｅｓｓｉｏｎ，ｉｎｃｒｅｍｅｎｔａｌｕｐｄａｔｅ，ｃｒｅａｔｉｏｎｅｆｆｉｃｉｅｎｃｙ，ａｎｄｒｅｔｒｉｅｖａｌｅｆｆｉｃｉｅｎｃｙ．Ｏｕｒｉｎｔｅｎｔｉｏｎｉｓｔｏｔａｋｅｔｈｅｆｏｕｒａｓｐｅｃｔｓｉｎｔｏａｃｃｏｕｎｔａｎｄｅｎｈａｎｃｅｔｈｅｉｒｉｎｔｅｇｒａｔｅｄｐｅｒｆｏｒｍｅｎｃｅ．Ｃｏｍｐｒｅｓｓｉｏｎｏｆｉｎｖｅｒｔｅｄｆｉｌｅｓｗｉｌｌｒｅｓｕｌｔｉｎａｎｉｎｃｒｅａｓｅｉｎｑｕｅｒｙｔｈｒｏｕｇｈｐｕｔ，ｂｅｃａｕｓｅｔｈｅｔｉｍｅｔｏｌｏａｄａｎｄｄｅｃｏｍｐｒｅｓｓａｃｏｍｐｒｅｓｓｅｄｉｎｖｅｒｔｅｄｌｉｓｔｉｓｓｈｏｒｔｅｒｔｈａｎｔｈｅｔｉｍｅｔｏｌｏａｄａｎｅｖｅｒｃｏｍｐｒｅｓｓｅｄｉｎｖｅｒｔｅｄｌｉｓｔ．Ｐｒｅｖｉｏｕｓｓｔｕｄｙｓａｌｍｏｓｔｆｏｃｕｓｅｄｏｎｔｈｅｃｏｍｐｒｅｓｓｉｏｎｒａｔｉｏ，ａｎｄｕｓｕａｌｌｙｉｇｎｏｒｅｔｈｅｄｙｎａｍｉｃｅｆｆｉｃｉｅｎｃｙｏｆｉｎｖｅｒｔｅｄｆｉｌｅ．Ｉｎｏｒｄｅｒｔｏｃｏｍｂｉｎｅｔｈｅｃｏｍｐｒｅｓｓｉｏｎｗｉｍｄｙｎａｍｉｃｅｆｆｉｃｉｅｎｃｙ，ｉｔｉｓｎｅｃｅｓｓａｒｙｔｏｄｅｖｅｌｏｐａｃｏｍｐｒｅｓｓｉｏｎｍｅｔｈｏｄｗｈｉｃｈｓｕｐｐｏｒｔｓｄｙｎａｍｉｃｕｐｄａｔｅ．Ｔｈｉｓｔｈｅｓｉｓａｎａｌｙｓｅｓｔｈｅｄｙｎａｍｉｃｃｈａｒａｃｔｅｒｏｆｉｎｖｅｒｔｅｄｉｎｄｅｘ，ｔｈｅｎｄｒａｗｓａｃｏｎｃｌｕｓｉｏｎｔｈａｔｔｈｅｔｈｒｅｅｓｕｂｌｉｓｔｓｃｏｎｓｎ＇ｕｃｔｅｄｉｎｖｅｒｔｅｄｌｉｓｔｈａｖｅｄｉｆｆｅｒｅｎｔｄｙｎａｍｉｃｃｈａｒａｃｔｅｒｓ．Ｂａｓｅｄｏｎｔｈｉｓｃｏｎｃｌｕｓｉｏｎ，ｗｅｐｕｔｆｏｒｗａｒｄａｈｙｂｒｉｄｃｏｍｐｒｅｓｓｉｏｎｍｅｔｈｏｄ．

Ｉｎｏｒｄｅｒｔｏｓｕｐｐｏｒｔｄｙｎａｍｉｃｕｐｄａｔｅ，ｗｅｍｅｎｄｔｈｅｄａｔａｓｔｒｕｃｔｕｒｅｏｆｉｎｖｅｒｔｅｄｉｎｄｅｘ，ａｎｄｔａｋｅａｎｅｗｕｐｄａｔｅｓｔｒａｔｅｇｙｏｆｉｎｖｅｒｔｅｄｉｎｄｅｘｂａｓｅｄｏｎｅｘｔｅｎｄｉｂｌｅｈａｓｈｉｎｇｔｏｍａｋｅｉｎｖｅｒｔｅｄｉｎｄｅｘｅｘｔｅｎｄｉｂｌｅ．Ｉｔｎｏｔｏｎｌｙｒｅｄｕｃｅｓｔｈｅｍｏｖｅｏｖｅｒｈｅａｄａｎｄｈａｓｌｉｔｔｌｅｉｎｆｌｕｅｎｃｅｏｎｉｎｖｅｒｔｅｄｉｎｄｅｘｒｅｔｒｉｅｖａｌ．Ｉｔｓｕｐｐｏｒｔｓｄｏｃｕｍｅｎｔｉｎｓｅｒｔｉｏｎａｎｄｄｅｌｅｔｉｏｎ，ａｎｄｐｒｏｖｉｄｅｓｈｉｇｈｒｅｔｒｉｅｖａｌｅｆｆｉｃｉｅｎｃｙａｎｄｓｐａｃｅｕｔｉｌｉｚａｔｉｏｎ．Ｏｎｔｈｅｂａｓｉｓｏｆｔｈｉｓｓｔｒａｔｅｇｙ，ｉｎｃｒｅｍｅｎｔａｌｕｐｄａｔｅａｎｄｒｅａｌ－ｔｉｍｅｕｐｄａｔｅａｒｅｒｅａｌｉｚｅｄ．

Ｔｈｅｓｅａｒｃｈｔｉｍｅｏｆｔｅｒｍｓｌｉｂｒａｒｙｉｓｏｎｅｏｆｔｈｅｆａｃｔｏｒｓｔｈａｔｄｅｔｅｒｍｉｎｅｃｒｅａｔｉｏｎｅｆｆｉｃｉｅｎｃｙａｎｄｒｅｔｒｉｅｖａｌｅｆｆｉｃｉｅｎｃｙｏｆｉｎｖｅｒｔｅｄｉｎｄｅｘ．Ｗｅｕｓｅｏｒｄｅｒｐｒｅｓｅｒｖｉｎｇｍｉｎｉｍａｌｐｅｒｆｅｃｔｈａｓｈｆｕｎｃｔｉｏｎｔｏｒｅａｌｉｚｅｔｈｅｓｅａｒｃｈｏｆｔｅｒｍｓｌｉｂｒａｒｙ．Ｉｔｃａｎｎｏｔｏｎｌｙｕｐｇｒａｄｅｔｈｅｓｅａｒｃｈｓｐｅｅｄ，ｂｕｔａｌｓｏａｖｏｉｄｓｏｒｔｉｎｇ．Ｉｔｃａｎｂｅｓｅｅｎｆｒｏｍｔｈｅｅｘｐｅｒｉｍｅｎｔｔｈａｔｔｈｉｓｍｅｔｈｏｄｃａｎｏｂｔａｉｎｔｗｉｃｅｓｐｅｅｄｏｆｂｉｎａｒｙｓｅａｒｃｈ．

Ｋｅｙｗｏｒｄｓ：ｉｎｆｏｒｍａｔｉｏｎｒｅｔｒｉｅｖａｌ，ｆｕｌｌ－ｔｅｘｔｒｅｔｒｉｅｖａｌ，ｆｕｌｌ—ｔｅｘｔｉｎｄｅｘ，ｉｎｖｅｒｔｅｄｉｎｄｅｘ，ｉｎｖｅｒｔｅｄ

ｉｎｄｅｘｃｏｍｐｒｅｓｓｉｏｎ，ｉｎｃｒｅｍｅｎｔａｌｕｐｄａｔｅＩＩ

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

独创性声明

本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得

的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。

学位论文作者签名：杀ｌ炭导

日期：ｚｏｏｆ年岁月７日

学位论文版权使用授权书

本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校

有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。

保密口，在年解密后适用本授权书。

本论文属于

不保密豳。

（请在以上方框内打“√”）

学位论文作者签名：刍Ｉ萎孑艚狮躲豸干弛日期：多。ｏ≯年ｊ月７日日期：五∞垆妒／驴日

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

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

１绪论

１．１课题背景

在全球信息化大潮的推动下，信息无节制地膨胀。文本作为信息的主要载体之一，如何快捷有效地管理和检索文本这种非结构化数据成为当前一项紧迫的研究任务，全文检索技术由此应运而生。

全文检索是指以文本为检索对象，允许用户以自然语言根据资料内容而不仅是外在特征来实现信息检索的手段。全面、准确和快速是衡量全文检索系统的关键指标。全文检索不仅可以实现对数据资料的外部特征的检索，诸如标题、作者、摘要、附录等，而且还能直接根据数据资料的内容进行检索，实现了支持多角度、多侧面地综台利用信息资源。最初的全文检索是通过在文本中逐个字符扫描匹配完成的，不需要全文索引这样的辅助数据。随着文本集越来越大，人们对全文检索的需求越来越多样，这，ｅｅＪ顷序比较效率低下的弊端就凸显出来。人们受到书目索引的启发提出了全文索引的思想，而本文研究的倒排索引则是目前应用最广泛的全文索引之～。

由于传统数据库擅长于结构化数据的管理，而文本是典型的非结构化数据，它们之间的巨大差异使得全文检索系统的实现手段以及全文索引的结构与传统数据库截然不同，因此完全照搬传统数据库的各种技术是不可行的，必须寻求全新的理论和方法来提高全文检索的效率。此外，文本检索的研究也能够为对其他几种更复杂的多媒体信息检索的研究提供重要的经验和借鉴。

国内外对全文检索的研究方兴未艾，己有一些较成熟的商用产品相继问世。中文全文检索与英文检索相比，由于自然语苦体系不同，索引机制也不完全相同。英文以词为单位建索引，与字母无关，而中文以字为最小单位。再者，英文的分词以空格和标点为分界符，而汉字的分词往往依赖于词库。因而中文全文检索与英文实现相比困难些。不得不承认目前国内的研究水平与国际上还有较大差距，坐等国外成果，然后加以移植改造的老路是行不通的，因此在国内进行全文检索的研究非常必要。综上所述，全文检索技术是现代信息检索的一项重要技术，在ｗｗｗ搜索引擎、

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

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

数字图书馆等领域中都有广泛的应用价值，因此，研究和探索高效的倒排索引技术不仅具有理论价值，而且极具商业前景。

１．２国内外概况

一般全文索引的研究内容主要有：全文索引的模型、索引的空间效率、索引的检索效率、索引的动态效率、索引的创建效率、索引的语义能力等。新一代的全文检索系统除了全文检索功能外，还应具备语义匹配、文本挖掘这类对语义理解要求较高的功能，而这些功能的完成也有赖于全文索引。

１．２．１全文索引的模型

目前主流的全文索引模型有倒排索引（Ｉｎｖｅｒｔｅｄｉｎｄｅｘ）、署名文件、位图、和Ｐａｔ数组。此外，有人还提出了一些新的全文索引模型，但就目前来说倒排索引模型的综合性能较好，且应用最为成熟，所以我们选用这种模型。

倒排索引是从书目索引中受到启发而派生出来的，它也是现在应用最广泛的全文索引模型。倒排索引由一系列“单词．指针”对组成。单词实际上是索引的查找键，包括文本集中出现的所有单词（除无用词外）。指针是该单词在文本集中出现的所有位置。因此，由倒排索引可以很快地得知一个单词在哪些文档的哪些位置出现。倒排索引按索引词可分为两类：基于单词的索引和基于字符的索引。词索引需要借助于词库，从文本中分离出有意义的词。这不是一个简单的工作，特别是中文，因为需要对上下文的理解。相反，基于字符的索引方法对数据库中所有出现的字符进行索引。基于字符的索引的主要优势是它避免了复杂而且昂贵的语义索引过程，没有词表维护成本，实现简单，缺点是索引效率低。许多研究人员都描述过倒排索引检索的实现方法［１－４］。Ｍｏｆｆａｔ和Ｚｏｂｅｌ于１９９４年曾对ＴＲＥＣ集合的数量所引起的问题进行了描述【５Ｊ。

署名文件有时也称散列函数法，每个文本有一个关联署名，每个索引项作为散列函数的参数产生几个散列值，与这些值相应的署名的位数被置为１。当把文本中每个字符的散列值叠加时，就得到了合并后的文本署名的全集。要检测一个查询项是否在给定的文本中出现，人们就要计算此查询项的散列函数值。如果某些文本的

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

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

描述符中所有的对应位均被设定，则此单词可能出现在该文本中。要确认查询项是否真正出现，必须扫描文本。我们可以通过为每个查询项设置几个位并使署名足够长来降低这种失败匹配的概率，但无论如何，总是需要进行失败匹配的检查，这在相当程度上增加了查询过程的开销。Ｆａｌｏｕｔｓｏｓ和Ｃｈｒｉｓｔｏｄｏｕｌａｋｉｓ分析了署名文件中存储空间与失败概率之间的折衷关系‘６，７１。Ｓａｃｋｓ－－Ｄａｖｉｓ等人在１９８７年，Ｋｅｎｔ在１９９０年描述了基于署名文件的不同结构，其中包括一个二级方案［８，９】。Ｆａｌｏｕｔｓｏｓ等人在１９９２年㈨“ｌｙ．介绍了署名文件。

位图是一种非常简单的索引结构，每个索引项都存储一个位矢量（ｂｉｔｖｅｃｔｏｒ），每个位相当于一个文本。如果索引项出现在某个文本中，该位置１，否则置０。位图使用起来非常容易而且很快，尤其适合布尔检索。但是，位图空间开销特别大，甚至是原文本的几十倍，尽管已经发现了一些高效的位图压缩方法，但压缩后的空间开销仍然远大于倒排索引和署名文件，所以位图是三种索引模型中应用最少的一种。Ｆｒａｅｎｋｅｌ等人描述了层次位图表示法［１”。

署名文件和位图两种模型均需要大量的存储空间。虽然这两种模型往往配合压缩技术，但是由于数据的压缩工作往往在索引生成之后进行，且开销也很大，因此压缩仅仅提高了索引的空间效率，而降低了动态性能。

有人提出了三种索引模型的混合模型，但是这些貌似综合了各种方法优点的混台方案往往将索引的创建过程和检索过程变得更为复杂，增加的复杂度很可能抵消带来的改进。

Ｐａｔ树是一种特殊的Ｐａｔｒｉｃｉａ树，它是Ｍａｎｂｅｒ提出的［１０，１３，１４】。它最具特色的地方是将一个文本看成一组半无限串的叠加，而这组半无限串的排序结果被表示成树的形式。它的最大优点是极大加快了检索速度，尤其对某些特殊的检索，如前缀检索、范围检索等检索效率更高。它的最大缺点是空间开销大，而且创建过程中的空间开销更大，创建效率也很低，此外，无论是创建过程还是检索过程都严重依赖源文本，而倒排索引在检索中是不需要源文本的。Ｐａｔ数组由Ｇｏｎｎｅｔ、Ｍａｎｂｅｒ和Ｍｙｅｒｓ在改进Ｐａｔ树模型的过程中独立地发现并应用，它将Ｐａｔ树的叶节点串行化就得到了Ｐａｔ数组【ｔｏ，ｔ３］。Ｐａｔ数组比Ｐａｔ树更直观，完全可以不通过Ｐａｔ树去理解和创建，但是两者的思想是一致的。由于树这种数据结构放入外存之后Ｉ／０的效率变得很低，－———＿＿＿－●－＿●＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿－＿＿＿＿＿＿＿＿＿＿●－＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿－＿＿＿－＿＿＿＿＿＿－－＿＿＿＿＿＿＿＿＿－＿＿－＿＿＿－＿＿＿＿＿＿＿＿－————————一一

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

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

而且Ｐａｔ树数组索引的创建和合并均需大量移动数据，因此两者的动态性能都不理想。

１．２．２倒排索引的压缩技术

由于倒排索引由索引项和索引项在文本集中出现的所有位置两部分组成，因此倒排索引空间开销与索引项的选择和位置的精确程度密切相关，如果索引项是文本中出现的每个字符，位置是字符在文本中的具体位置，而不是段落号或行号，那么倒排索引的空间开销与原文本基本相当甚至更大。为研究如何减少倒排索引的大小，倒排索引的一个研究热点就是在基本不影响检索效率的前提下，实现倒排索引的压缩。目前得到广泛应用的Ｏｏｌｏｍｂ编码是在１９６６年首次提出【ｌ“，Ｇａｌｌａｇｅｒ和ＶａｎＶｏｏｒｈｉｓｔｌ６１在１９７５年发展了这种方法。随后，Ｅｌｉａｓ在１９７５年描述了Ｙ编码和６编码，它们是两种有效的索引压缩方法【１７１。后来Ｂｅｎｔｌｅｙ和Ｙａｏ在１９７６年作了更详细的描述㈣。１９７８年Ｔｖｈｏｌａ首先描述了变形贝努里模型，Ｍｏｆｆａ和Ｚｏｂｅｌ作了进一步的实验［１９－２２】。１９９２年Ｂｏｏｋｓｔｅｉｎ［２３１、Ｍｏｆｆａｔ和Ｚｏｂｅｌ［１９，２０１、Ｗｉｔｔｅｎ［２４１、Ｂｅｌｌ等圜研究了用于索引压缩的局部贝努里模型。１９９６年Ｍｏｆｉａｔ和Ｓｔｕｉｖｅｒ提出内插编码ｆ２引，２０００年又提出一种二迸制内插编码（ｂｉｎａｒｙｉｎｔｅｒｐｏｌａｔｉｖｅｃｏｄｉｎｇ）［２７１。统计压缩（ｓｔａｔｉｓｔｉｃａｌｃｏｍｐｒｅｓｓｉｏｎ）技术也有很好的压缩率，但是还不够完善，１９９４年Ｂｏｏｋｓｔｅｉｎ提出一种Ｍａｒｋｏｖ方法，２０００年又在此基础上提出Ｂａｙｅｓｉａｎ方法【２８】。１９９７年Ｃｈｉｕｅｎ及２０００年Ｎａｖａｒｒｏ提出了利用倒排文件字典做为压缩字典的压缩技术［２９，３０１。以上一系列的工作大大提高了倒排索引的空间利用率。

１．２．３倒排索引动态更新

现实生活中，文本集保持一成不变的静态集合是很少见的，人们对检索动态文本集的要求日益迫切。为顺应这一需求，实现全文索引的动态性成为全文检索技术的一个必然要求。人们希望倒排索引能够象许多数据库中的动态索引一样，自如地应对文本的频繁增加、删除等操作。关系数据库能够胜任数据的频繁变化，得益于索引的基本数据单位小，以及使用了Ｂ树这类动态索引。关系数据库索引列的总长度往往有限制，如：ＳＱＬＳｅｒｖｅｒ２０００中索引列的总长度最大为９００字节。而全文

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

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

检索处理的基本数据单位是文本，文本大小相差悬殊，小到几字节，大到上Ｇ字节。

修改文本可看作删除再添加，因此不单独讨论。对于删除文本，目前的做法多是加删除标记，这是个相对简单快速的过程。对于同样的新文本集，为其另外创建一个新的索引的速度往往高于在一个己有的索引上添加这些文本的索引，因此阻ＭｉｃｒｃＩｓｏｆｔＩｎｄｅｘＳｅｒｖｅｒ为代表的大多数全文检索系统均采用为新文本创建临时索引，然后定期将临时索引与原有索引合并的方法。这种方法实现虽然简单，但会降低检索速度，特别是当临时索引积累到一定数量时，查～个词时要寻遍所有的索引后求并集。

全文索引的动态更新是目前相对较薄弱的环节，倒排索引和Ｐａｔ数组都存在动态调整效率低的问题。首先，由于倒排表和Ｐａｔ数组记录的都是绝对位置，因此文本内部的任何改动，都会改变后续文字的绝对位置，导致大量索引数据的变动。其次，倒排表还会引发大量索引数据的移动，由于对空间效率的过分追求，倒排索引几乎都采用紧凑的存储方式，因此动态调整时的移动开销很大。而Ｐｍ数组会引发大量文件的打开操作。

对全文索引的动态更新的研究，比较有影响的有Ａｍｉｒ和Ｆａｒａｃｈ等提出的动态词典方法［３１，３２】。ＭｉｎｇＧｕ和ＭａｒｔｉｎＦａｒａｃｈ提出了一种ｂｏｒｄｅｒ树‘３３１，它是在Ｐａｔ树基础上发展起来的一种数据结构。Ｔｈａｒｐ和Ｂｏｓｗｅｌｌ等提出了Ｂ＋树与散列函数相结合的方法［３４】。Ｓｃｈｗｅｉｔｚ和Ｔｈａｒｐ等提出在署名文件中使用自适应散列函数的方法【３５】。ＣｕＲｉｎｇ等人提出在倒排索引的基础上建一Ｂ树【３６。，来支持倒排索引的插入和删除。ＡｎｔｈｏｎｙＴｏｍａｓｉｃ等人针对倒排索引的文档插入提出的Ｄｕａｌ．ＳｔｒｕｃｔｕｒｅＩｎｄｅｘ结构【３７１，这种结构能够动态地区分长、短倒排列表，并针对长、短列表采用不同的检索、更新和存储策略。Ｃｈｉｕｅｈ等人提出了实时更新倒排索引的解决方案。但这些方案都有局限，如对内存大小有特殊要求、不支持文档的删除、对于特小或特大的文档集索引的空间利用率较低等。２００４年Ｌｅｓｔｅｒ将全文索引的更新方法归为三类：重建、即时更新和再合并，并分析对比了三者的性能差异【３８１。另外国内的杨成明提出了针对倒排索引的双层Ｂ＋树结构［３”。但总的来说，迄今为止还没有公认有效的动态全文索引。

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

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

１．２．４相关产品

目前国内外都已出现了不少商品化的全文检索系统。国外知名的数据库厂商及开源的全文检索系统主要有如下几个。

１．ＳＱＬＳｅｒｖｅｒ全文检索系统

ＭｉｃｒｏｓｏｆｔＳＱＬＳｅｒｖｅｒ于７．０版开始提供微软搜索服务（ＭｉｃｒｏｓｏｆｔＳｅａｒｃｈＳｅｒｖｉｃｅ）。ＳＱＬＳｅｒｖｅｒ２０００之后，更新增了对多种类型文件（包括Ｗｏｒｄ，Ｐｏｗｅｒｐｏｉｎｔ，ＰＤＦ，Ｅｘｃｅｌ，ＨＴＭＬ，ＸＭＬ）进行全文索引的能力。文件过滤器是一个公共的接口，允许各种文件格式的转化被集成到ＳＱＬＳｅｒｖｅｒ中。ＳＱＬＳｅｒｖｅｒ的全文检索系统由五部分组成：ｃｏｎｔｅｎｔｒｅａｄｅｒ、ｆｉｌｔｅｒｄａｅｍｏｎ、ｗｏｒｄｂｒｅａｋｅｒ、ｉｎｄｅｘｅｒ、ｑｕｅｒｙ

ｃｏｎｔｅｎｔｐｒｏｃｅｓｓｏｒ。ｒｅａｄｅｒ扫描表中的文本及相关的元数据包。

ｆｉｌｔｅｒｄａｅｍｏｎ将数据包传给搜索引擎过滤后台进程，后台进程依据文本的格式调用相应的过滤器对其进行格式转化。

ｗｏｒｄｂｒｅａｋｅｒ依据文档所采用的语种对格式转化后的文本分词。

ｉｎｄｅｘｅｒ负责建立倒排索引。索引以压缩的形式来存储以提高存储的效率，但不可避免地增加了更新的开销。

２．Ｏｒａｃｌｅ的Ｏｒａｃｌｅ

ＯｒａｃｌｅＴｅｘｔＴｅｘｔ的早期版本名为ｉｎｔｅｒＭｅｄｉａＴｅｘｔ。ＯｒａｃｌｅＴｅｘｔ使用扩展的ＳＱＬ来索引、查找和分析存储在Ｏｒａｃｌｅ数据库、文件系统和Ｗｅｂ中的文本。ＯｒａｃｌｅＴｅｘｔ可以使用多种方式来查找文本。

（１）全文本查找，包括布尔查询、精确短语、模糊查询、章节查找、拼写错误、逆向、通配符、辞典、等价单词以及权重等。

（２）混合搜索，指全文索引加上关系属性以及主题查找。

（３）查找ＨＴＭＬ和ＸＭＬ章节和标记值。

查找结果可以以各种格式提交，包括纯文本、自动高亮显示关键字ＨＴＭＬ以及原始文档格式。ＯＲＡＣＬＥ采用了ＩＮＳＯ公司开发的１５０多种过滤器，过滤的结果是将各种格式的文档转换为统一的ｈｔｍｌ格式。采用这种格式即便于以后的搜索，又能尽可能地保持文档的原貌。ＯＲＡＣＬＥ目前支持３９个语种，语种根据字符的编码

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

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

方式可分为：单字节语言和多字节语言。对于中、日、韩等多字节语言，ＯＲＡＣＬＥ为它们提供了不同的分词器。

３．ＤＢ２的ＴｅｘｔＥｘｔｅｎｄｅｒ

ＤＢ２ＴｅｘｔＥｘｔｅｎｄｅｒ将文本搜索引擎（ＴｅｘｔＳｅａｒｃｈＥｎｇｉｎｅ，ＴＳＥ）集成到ＤＢ２中，它支持在表上建立全文索引。通过表的关键字将记录和全文索引入口对应起来。全文索引和文本的一致性用触发器来维护。

ＴｅｘｔＥｘｔｅｎｄｅｒ有效地利用了ＤＢ２的ＳＱＬ可扩展特性，将查询分解和连接加入到关系数据库中。为了减轻文本信息扩展部件（ＴｅｘｔＩｎｆｏｒｍａｔｉｏｎＥｘｔｅｎｄｅｒ，ＴＩＥ）元数据的分解和文本检索表函数连接的负担，设计了查询重写部件。为了优化查询，增加了一组ＡＰＩ来完成ＴＳＥ和ＤＢ２优化器间的信息互换，还新增了一组ＤＢ２的嵌入函数和相关的查询重写以实现友好的ＳＱＬ文本查询语句。

ＴＩＥ适合于基于内容的应用，特别是文本和关系查询条件的复合查询，这些查询通常要求完整的结果集。相反，电子商务应用则主要是简单查询、无条件查询或只有一个简单的条件，它只要求返回一些相关结果。对此，ＩＢＭ提供了ＮｅｔＳｅａｒｃｈＥｘｔｅｎｄｅｒ，它利用主存技术来达到特别高的执行效率和性能。

４．Ｌｕｃｅｎｅ全文检索工具包

Ｌｕｃｅｎｅ是ＡＰＡＣＨＥ基金会ｊａｋａｒｔａ的一个开源的子项目，它并非是一个完整的全文检索系统，而是一个用Ｊａｖａ编写的全文检索工具包，可以方便地嵌入到各种应用中。。已经有很多的Ｊａｖａ项目都使用Ｌｕｃｅｎｅ作为后台的全文检索引擎，如：Ｊｉｖｅ、Ｅｙｅｂｒｏｗｓ、Ｃｏｃｏｏｎ、Ｅｃｌｉｐｓｅ。Ｌｕｃｅｎｅ能很方便得实现对中文的支持，只需对其语言词法分析接口进行扩展即可。

１．３课题主要研究工作

本课题是在武汉华工达梦数据库有限公司开发的拥有自主版权的数据库管理系统ＤＭ３的基础上进行研究与开发的。作为ＤＭ３的予系统之一，全文检索系统可以从空间效率、动态效率、填充效率、检索效率、语义能力五方面的性能来评价。现有的全文检索系统虽已初具雏形，具备基本的功能，但从以上五方面来衡量都还不够完善。本课题主要是针对其中的空间效率、动态效率、填充效率、检索效率四项

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

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

性能的优化来展开的。

概括来说，本课题的主要研究工作包括。

１．对ＤＭ３全文检索系统原有的倒排索引实现机制进行研究，分析该系统存在的不足。

２．通过对当前全文索引模型特别是倒排索引模型的索引压缩技术的深入研究，及引入倒排索引动态性后可能给索引压缩带来的问题的分析，提出既便于倒排索引动态更新又具有高效压缩性能的倒排索引压缩方案。

３．研究实现倒排索引动态性的难点，分析目前倒排索引更新策略的解决思路及存在的不足，在此基础上，提出更有效地支持倒排索引动态性的数据结构，并基于这种结构实现倒排索引的增量更新。

４．研究提高倒排索引填充和检索速度的方法，其中索引填充包括完全填充、批量填充和实时填充三种方式。

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

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

２数据库管理系统达梦３全文检索子系统的改进方案

达梦３（ＤＭ３）全文检索系统是ＤＭ３数据库管理系统的一个相对独立的子系统，己具备的功能有全文索引的定义和删除、全文索引的填充、全文检索、词库维护。本章首先介绍全文检索子系统的软件架构，然后从性能上分析现有系统存在Ｂ０不足，并在此基础上提出改进的设想和要求。

２．１达梦３全文检索系统

ＤＭ３全文检索子系统选用倒排列表作为全文索引的模型，一个倒排索引是以独立于数据库的文件存在操作系统上的，分为单词表和索引数据前后两部分。一个单词可能有对应的索引数据，亦可能没有。若有索引数据，则该单阋对应的索引数据称为一个倒排列表（ｉｎｖｅｒｔｅｄｌｉｓｔ），每个倒排列表都占用一片连续的磁盘空间。单词表存储了词库中所有单词及该单词的倒排列表在索引文件中的位置，不同单词的倒排列表间采用连续的紧凑的存储方式。

ＤＭ３全文检索子系统按功能可分为：全文索引的定义和删除、全文索引的填充、全文检索、词库维护，它们的实现依赖于一些公用模块，其软件架构如图２．１所示。

图２．１全文检索子系统的功能实现示意图

全文索引的定义和删除负责建立和删除倒排索引文件。全文索引的填充现只具备完全填充功能，其工作过程为：全表扫描，从数据库中取

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

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

出一个表的全部文本；将每一个文本送交分词模块，分词模块根据中英文词库对原始文本分词：获取每个字／词出现的位置信息（文本号＋文本中的位置），填充全文索引。当文本列数据更新后，倒排索引信息将会失效，需要再次完全填充全文索引，以确保查询的有效性。

全文检索模块的工作过程为：将查询的文本送交分词模块分词，耿吲分词结果；Ｘ，Ｊ分词后的每一个词取出它在倒排索引中的条目，进行运算后得到满足条件的元组集合；取出元组集合并输出。

词库维护模块用于更新和维护词库。全文索引使用的分词算法依赖于一个大的巾英文词库，目前ＤＭ３使用的词库包含１７１９３１个词，其中英文词１２３７０个，中文词１５９５６１个。

２．２达梦３全文检索系统性能分析及评价

全文检索系统优劣的可以从五个方面来衡量：索引的空间丌销、索引的创建效率、索引的检索效率、索引的动态性能、索引的检索质量。下面围绕这五个方面对ＤＭ３原有的全文检索系统进行评价。

倒排索引的空间开销是ＤＭ３全文检索系统面临的最为突出的问题。一方面，倒排索引的单词表部分完全照搬了词库中所有的词，大小为固定值６ＭＢ。事实上，其中绝大多数词是没有索引数据（即倒排列表）的，这部分词没有必要纳入单词表。另一方面，倒排索引的索引数据部分由于采用４字节的整数类型表示每一个整数，没有采用任何的压缩手段，所以造成极大的空间开销。此外，倒排索引的大小还和分词的粒度有关，太细的分词导致索引项增多，索引空间也随之增大；而太粗的分词虽然节省索引空削，但会降低查询的查全率。

倒排索引的创建依赖大量的外存］／ｏ操作，特别是对于海量文本，丽］／ｏ是影响创建速度的决定性因素，因此，要提高索引创建的效率，应从三方面入手：提高内存在索引创建过程中的工作比例：降低外存Ｉ／Ｏ操作的次数：减少被迫写入外存的临时数据。目前ＤＭ３中倒排索引的创建过程使用缓冲区和临时文件做为辅助，Ｉ／Ｏ还是较为频繁的，可以考虑使用存储映射文件取代临时文件等方法加以改善。

倒排索引的检索时间主要由两部分时间决定：在单词表中查找检索词的时阳ｊ，读取１０

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

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

倒排索引中相关倒排列表的时间。目前ＤＭ３对单词表的查找采用折半查找，最坏情况下对于含ｎ个元素的单词表，查找时间复杂度为ｌｏｇｎ。而读取倒排列表的时间与倒排列表的大小等因素有关。

ＤＭ３的全文索引只支持完全填充，索引不能随数据的操纵永远保持最新状态，必须定期地完全填充。为及时反映动态文本集的变化，有必要补充倒排索引增量填充的功能。

索引的检索质量由查全率和查准率两个标准来衡量。上文提到查全率跟分词的粒度有关，由于ＤＭ３建倒排索引时采用的是细粒度的分词策略，所以保证了较好的查全率。查准率的决定因素比较复杂多样，它跟语义有一定的相关性，需要在对文本或检索词进行分词的过程中引入某些约束规则及推理机制。比如，查“全文”若把“安全文件”也检索出来，显然与用户的意愿相违，这就降低了查准率。这方面在ＤＭ３全文检索系统中还是个空白。

２．３改进的要求

针对２．２节中提到的原有ＤＭ３全文检索系统存在的不足，拟从其中最主要的倒排索引的空间开销、索引的动态性能、索引的检索时间、索引的创建时间这四个方面对全文检索系统加以改善。

要降低倒排索引的空间开销，可以从分词粒度、单词表、倒排索引压缩等几个方面着手。本文重点讨论倒排索引压缩的问题。寻求压缩方案时，不但需要考虑压缩率和解压速度，而且要兼顾到是否方便索引的更新维护。

索引的动态性能跟索引结构有直接的关系。当数据库动态变化时，索引结构直接影响索引进行相应变化的速度。一般来说，索引变化时对原有的索引数据更改越多（包括数据本身的更改和数据的移动），动态性能就越差。因此，索引的更新应尽可能减少更新索引的时间开销，同时尽量不影响索引查询的速度。

不论是倒排索引的填充还是检索过程中，都需要在词库中进行查找来实现分词，尤其是填充索引的过程中这种查找更是频繁，如果能寻求到一种比折半查找更有效的方法，势必加快索引创建和检索的速度。

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

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

２．４本章小结

本章首先介绍了ＤＭ３全文检索系统的软件架构，然后从衡量全文索引性能的索引的空问开销、索引的创建效率、索引的检索效率、索引的动态性能、索引的检索质量五个方面分析了原有系统存在的问题和不足，最后，提出了改进索引空间、动态性能、索引填充速度和检索速度的设想和欲达到的目标。１２