（计算机软件与理论专业论文）基于倒排索引的全文检索技术研究.pdf

华中科技大学硕士学位论文 摘要 倒排索引是提高全文检索效率的重要技术，而倒排索引的空间效率、动态性能、创 建效率和检索效率一直是倒排索引面临的关键问题，它们之间既紧密联系又相互制约。 课题正是围绕倒排索引的压缩、增量更新、填充及检索效率展开，其目的是提高四者的 综合性能。 压缩倒排索引有助于提高查询的吞吐量，因为读和解压已压缩的倒排索引往往比读 一个未压缩的倒排索引要快。前人的研究关注得更多的是倒排索引的压缩率，而往往忽 略了动态性。为了兼顾动态性，需要研究既能提高压缩率又能方便索引动态更新的压缩 方法。在分析倒排列表的动态特点的基础上，得出构成倒排列表的文档编号、单词在文 档中的出现频率及相应位置三序列的动态性是不同的，并由此提出一种混合编码的方 法。试验表明，混合编码在压缩率方面优于其他支持动态更新的编码。 为了支持倒排索引增量更新，从改进倒排索引的数据结构入手，提出了基于可扩展 散列表的倒排索引存储策略。这一策略使倒排索引具有良好的可扩展性，不但减少了动 态调整时的移动开销，而且调整后的索引对倒排索引的查询速度影响较小。它既支持文 档的插入、删除操作，又具有较高的查询效率和空间利用率。 词库的查找速度是影响倒排索引的填充及检索效率的因素之一。采用有序保留最小 完全散列函数实现词库的查找，不但能加快查找速度，而且无需预先对单词排序。试验 证明，它能获得比折半查找快近一倍的速度。 关键词：信息检索，全文检索，全文索引，倒排索引，倒排索引压缩，增量更新 华中科技大学硕士学位论文 a b s t r a c t i n v e r t e di n d e xi sa ni m p o r t a n tt e c h n i q u et oi m p r o v ef u l l t e x tr e t r i e v a lp e r f o r m a n c e t h e s t o r a g eu t i l i z a t i o n ，d y n a m i ce f f i c i e n c y , c r e a t i o ne f f i c i e n c y , a n dr e t r i e v a le f f i c i e n c y a r ef o u r c r i t i c a lp r o b l e m so fi n v e r t e di n d e x t h i sr e s e a r c hd i s c u s s e sf o u ra s p e c t so fi n v e r t e di n d e x i n c l u d i n gc o m p r e s s i o n ，i n c r e m e n t a lu p d a t e ，c r e a t i o ne f f i c i e n c y , a n dr e t r i e v a le f f i c i e n c y o u r i n t e n t i o ni st ot a k et h ef o u ra s p e c t si n t oa c c o u n ta n de n h a n c et h e i ri n t e g r a t e dp e r f o r m e n c e c o m p r e s s i o n o fi n v e r t e df i l e sw i l lr e s u l ti na ni n c r e a s ei nq u e r yt h r o u g h p u t ，b e c a u s et h e t i m et ol o a da n d d e c o m p r e s s a c o m p r e s s e di n v e r t e dl i s ti ss h o r t e r t h a nt h et i m et ol o a dan e v e r c o m p r e s s e di n v e r t e d l i s t p r e v i o u s s t u d y sa l m o s tf o c u s e do nt h ec o m p r e s s i o nr a t i o ，a n d u s u a l l yi g n o r et h ed y n a m i ce f f i c i e n c yo f i n v e r t e df i l e i no r d e rt oc o m b i n et h ec o m p r e s s i o n w i md y n a m i ce f f i c i e n c y , i ti sn e c e s s a r yt od e v e l o pac o m p r e s s i o nm e t h o dw h i c hs u p p o r t s d y n a m i cu p d a t e t h i st h e s i sa n a l y s e st h ed y n a m i cc h a r a c t e ro f i n v e r t e di n d e x ，t h e nd r a w sa c o n c l u s i o nt h a tt h et h r e es u b l i s t sc o n s n u c t e di n v e r t e dl i s th a v ed i f f e r e n td y n a m i cc h a r a c t e r s b a s e do nt h i sc o n c l u s i o n ，w e p u tf o r w a r d a h y b r i dc o m p r e s s i o n m e t h o d i no r d e rt os u p p o r td y n a m i cu p d a t e ，w em e n dt h ed a t as t r u c t u r eo fi n v e r t e di n d e x ，a n dt a k e an e w u p d a t es t r a t e g yo f i n v e r t e di n d e xb a s e do ne x t e n d i b l eh a s h i n gt om a k ei n v e r t e di n d e x e x t e n d i b l e i tn o to n l yr e d u c e st h em o v eo v e r h e a da n dh a sl i t t l ei n f l u e n c eo ni n v e r t e di n d e x r e t r i e v a l i ts u p p o r t sd o c u m e n ti n s e r t i o na n dd e l e t i o n ，a n dp r o v i d e sh i g hr e t r i e v a le f f i c i e n c y a n ds p a c eu t i l i z a t i o n o nt h eb a s i so ft h i ss t r a t e g y , i n c r e m e n t a lu p d a t ea n dr e a l - t i m eu p d a t e a r er e a l i z e d t h es e a r c ht i m eo ft e r m sl i b r a r yi so n eo ft h ef a c t o r st h a td e t e r m i n ec r e a t i o n e f f i c i e n c ya n d r e t r i e v a le f f i c i e n c yo fi n v e r t e di n d e x w eu s eo r d e rp r e s e r v i n gm i n i m a l p e r f e c th a s hf u n c t i o n t or e a l i z et h es e a r c ho ft e r m sl i b r a r y i tc a nn o to n l yu p g r a d et h es e a r c hs p e e d ，b u ta l s oa v o i d s o r t i n g i tc a nb es e e nf r o m t h ee x p e r i m e n tt h a tt h i sm e t h o dc a no b t a i nt w i c es p e e do f b i n a r y s e a r c h k e yw o r d s ：i n f o r m a t i o nr e t r i e v a l ，f u l l - t e x tr e t r i e v a l ，f u l l t e x ti n d e x ，i n v e r t e di n d e x ，i n v e r t e d i n d e x c o m p r e s s i o n ，i n c r e m e n t a lu p d a t e i i 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：杀l 炭导 日期： z o o f 年岁月7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于 不保密豳。 ( 请在以上方框内打“”) 学位论文作者签名：刍i 萎孑 日期：多。o 年j 月7 日 艚狮躲豸干弛 日期：五垆妒驴日 华中科技大学硕士学位论文 1 绪论 1 1课题背景 在全球信息化大潮的推动下，信息无节制地膨胀。文本作为信息的主要载体之 一，如何快捷有效地管理和检索文本这种非结构化数据成为当前一项紧迫的研究任 务，全文检索技术由此应运而生。 全文检索是指以文本为检索对象，允许用户以自然语言根据资料内容而不仅是 外在特征来实现信息检索的手段。全面、准确和快速是衡量全文检索系统的关键指 标。全文检索不仅可以实现对数据资料的外部特征的检索，诸如标题、作者、摘要、 附录等，而且还能直接根据数据资料的内容进行检索，实现了支持多角度、多侧面 地综台利用信息资源。最初的全文检索是通过在文本中逐个字符扫描匹配完成的， 不需要全文索引这样的辅助数据。随着文本集越来越大，人们对全文检索的需求越 来越多样，这, e ej 顷序比较效率低下的弊端就凸显出来。人们受到书目索引的启发提 出了全文索引的思想，而本文研究的倒排索引则是目前应用最广泛的全文索引之。 由于传统数据库擅长于结构化数据的管理，而文本是典型的非结构化数据，它 们之间的巨大差异使得全文检索系统的实现手段以及全文索引的结构与传统数据库 截然不同，因此完全照搬传统数据库的各种技术是不可行的，必须寻求全新的理论 和方法来提高全文检索的效率。此外，文本检索的研究也能够为对其他几种更复杂 的多媒体信息检索的研究提供重要的经验和借鉴。 国内外对全文检索的研究方兴未艾，己有一些较成熟的商用产品相继问世。中 文全文检索与英文检索相比，由于自然语苦体系不同，索引机制也不完全相同。英 文以词为单位建索引，与字母无关，而中文以字为最小单位。再者，英文的分词以 空格和标点为分界符，而汉字的分词往往依赖于词库。因而中文全文检索与英文实 现相比困难些。不得不承认目前国内的研究水平与国际上还有较大差距，坐等国外 成果，然后加以移植改造的老路是行不通的，因此在国内进行全文检索的研究非常 必要。 综上所述，全文检索技术是现代信息检索的一项重要技术，在w w w 搜索引擎、 华中科技大学硕士学位论文 数字图书馆等领域中都有广泛的应用价值，因此，研究和探索高效的倒排索引技术 不仅具有理论价值，而且极具商业前景。 1 2国内外概况 一般全文索引的研究内容主要有：全文索引的模型、索引的空间效率、索引的 检索效率、索引的动态效率、索引的创建效率、索引的语义能力等。新一代的全文 检索系统除了全文检索功能外，还应具备语义匹配、文本挖掘这类对语义理解要求 较高的功能，而这些功能的完成也有赖于全文索引。 1 2 1 全文索引的模型 目前主流的全文索引模型有倒排索引( i n v e r t e di n d e x ) 、署名文件、位图、和 p a t 数组。此外，有人还提出了一些新的全文索引模型，但就目前来说倒排索引模型 的综合性能较好，且应用最为成熟，所以我们选用这种模型。 倒排索引是从书目索引中受到启发而派生出来的，它也是现在应用最广泛的全 文索引模型。倒排索引由一系列“单词指针”对组成。单词实际上是索引的查找键， 包括文本集中出现的所有单词( 除无用词外) 。指针是该单词在文本集中出现的所 有位置。因此，由倒排索引可以很快地得知一个单词在哪些文档的哪些位置出现。 倒排索引按索引词可分为两类：基于单词的索引和基于字符的索引。词索引需要借 助于词库，从文本中分离出有意义的词。这不是一个简单的工作，特别是中文，因 为需要对上下文的理解。相反，基于字符的索引方法对数据库中所有出现的字符进 行索引。基于字符的索引的主要优势是它避免了复杂而且昂贵的语义索引过程，没 有词表维护成本，实现简单，缺点是索引效率低。许多研究人员都描述过倒排索引 检索的实现方法 1 - 4 。m o f f a t 和z o b e l 于1 9 9 4 年曾对t r e c 集合的数量所引起的问 题进行了描述【5 j 。 署名文件有时也称散列函数法，每个文本有一个关联署名，每个索引项作为散 列函数的参数产生几个散列值，与这些值相应的署名的位数被置为1 。当把文本中 每个字符的散列值叠加时，就得到了合并后的文本署名的全集。要检测一个查询项 是否在给定的文本中出现，人们就要计算此查询项的散列函数值。如果某些文本的 华中科技大学硕士学位论文 描述符中所有的对应位均被设定，则此单词可能出现在该文本中。要确认查询项是 否真正出现，必须扫描文本。我们可以通过为每个查询项设置几个位并使署名足够 长来降低这种失败匹配的概率，但无论如何，总是需要进行失败匹配的检查，这在 相当程度上增加了查询过程的开销。f a l o u t s o s 和c h r i s t o d o u l a k i s 分析了署名文件中 存储空间与失败概率之间的折衷关系6 ，7 1 。s a c k s - - d a v i s 等人在1 9 8 7 年，k e n t 在1 9 9 0 年描述了基于署名文件的不同结构，其中包括一个二级方案 8 ，9 】。f a l o u t s o s 等人在 1 9 9 2 年“l y 介绍了署名文件。 位图是一种非常简单的索引结构，每个索引项都存储一个位矢量( b i t v e c t o r ) ， 每个位相当于一个文本。如果索引项出现在某个文本中，该位置1 ，否则置0 。位图 使用起来非常容易而且很快，尤其适合布尔检索。但是，位图空间开销特别大，甚 至是原文本的几十倍，尽管已经发现了一些高效的位图压缩方法，但压缩后的空间 开销仍然远大于倒排索引和署名文件，所以位图是三种索引模型中应用最少的一种。 f r a e n k e l 等人描述了层次位图表示法 1 ”。 署名文件和位图两种模型均需要大量的存储空间。虽然这两种模型往往配合压 缩技术，但是由于数据的压缩工作往往在索引生成之后进行，且开销也很大，因此 压缩仅仅提高了索引的空间效率，而降低了动态性能。 有人提出了三种索引模型的混合模型，但是这些貌似综合了各种方法优点的混 台方案往往将索引的创建过程和检索过程变得更为复杂，增加的复杂度很可能抵消 带来的改进。 p a t 树是一种特殊的p a t r i c i a 树，它是m a n b e r 提出的 1 0 , 1 3 , 1 4 】。它最具特色的地 方是将一个文本看成一组半无限串的叠加，而这组半无限串的排序结果被表示成树 的形式。它的最大优点是极大加快了检索速度，尤其对某些特殊的检索，如前缀检 索、范围检索等检索效率更高。它的最大缺点是空间开销大，而且创建过程中的空 间开销更大，创建效率也很低，此外，无论是创建过程还是检索过程都严重依赖源 文本，而倒排索引在检索中是不需要源文本的。p a t 数组由g o n n e t 、m a n b e r 和m y e r s 在改进p a t 树模型的过程中独立地发现并应用，它将p a t 树的叶节点串行化就得到了 p a t 数组【t o , t 3 。p a t 数组比p a t 树更直观，完全可以不通过p a t 树去理解和创建，但 是两者的思想是一致的。由于树这种数据结构放入外存之后i 0 的效率变得很低， - _ _ _ - - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ - _ _ _ _ _ _ - - _ _ _ _ _ _ _ _ _ - _ _ - _ _ _ - _ _ _ _ _ _ _ _ - 一一 华中科技大学硕士学位论文 而且p a t 树数组索引的创建和合并均需大量移动数据，因此两者的动态性能都不理 想。 1 2 2 倒排索引的压缩技术 由于倒排索引由索引项和索引项在文本集中出现的所有位置两部分组成，因此 倒排索引空间开销与索引项的选择和位置的精确程度密切相关，如果索引项是文本 中出现的每个字符，位置是字符在文本中的具体位置，而不是段落号或行号，那么 倒排索引的空间开销与原文本基本相当甚至更大。为研究如何减少倒排索引的大小， 倒排索引的一个研究热点就是在基本不影响检索效率的前提下，实现倒排索引的压 缩。目前得到广泛应用的o o l o m b 编码是在1 9 6 6 年首次提出【l “，g a l l a g e r 和v a n v o o r h i s t l 6 1 在1 9 7 5 年发展了这种方法。随后，e l i a s 在1 9 7 5 年描述了y 编码和6 编 码，它们是两种有效的索引压缩方法【1 7 1 。后来b e n t l e y 和y a o 在1 9 7 6 年作了更详细 的描述。1 9 7 8 年t v h o l a 首先描述了变形贝努里模型，m o f f a 和z o b e l 作了进一 步的实验 1 9 - 2 2 】。1 9 9 2 年b o o k s t e i n 2 3 1 、m o f f a t 和z o b e l 1 9 , 2 0 1 、w i t t e n 2 4 1 、b e l l 等圜 研究了用于索引压缩的局部贝努里模型。1 9 9 6 年m o f i a t 和s t u i v e r 提出内插编码f 2 引， 2 0 0 0 年又提出一种二迸制内插编码( b i n a r yi n t e r p o l a t i v ec o d i n g ) 2 7 1 。统计压缩 ( s t a t i s t i c a lc o m p r e s s i o n ) 技术也有很好的压缩率，但是还不够完善，1 9 9 4 年b o o k s t e i n 提出一种m a r k o v 方法，2 0 0 0 年又在此基础上提出b a y e s i a n 方法【2 8 】。1 9 9 7 年c h i u e n 及2 0 0 0 年n a v a r r o 提出了利用倒排文件字典做为压缩字典的压缩技术 2 9 , 3 0 1 。以上一 系列的工作大大提高了倒排索引的空间利用率。 1 2 3 倒排索引动态更新 现实生活中，文本集保持一成不变的静态集合是很少见的，人们对检索动态文 本集的要求日益迫切。为顺应这一需求，实现全文索引的动态性成为全文检索技术 的一个必然要求。人们希望倒排索引能够象许多数据库中的动态索引一样，自如地 应对文本的频繁增加、删除等操作。关系数据库能够胜任数据的频繁变化，得益于 索引的基本数据单位小，以及使用了b 树这类动态索引。关系数据库索引列的总长 度往往有限制，如：s q ls e r v e r2 0 0 0 中索引列的总长度最大为9 0 0 字节。而全文 华中科技大学硕士学位论文 检索处理的基本数据单位是文本，文本大小相差悬殊，小到几字节，大到上g 字节。 修改文本可看作删除再添加，因此不单独讨论。对于删除文本，目前的做法多 是加删除标记，这是个相对简单快速的过程。对于同样的新文本集，为其另外创建 一个新的索引的速度往往高于在一个己有的索引上添加这些文本的索引，因此阻 m i c r c i s o f t i n d e xs e r v e r 为代表的大多数全文检索系统均采用为新文本创建临时索引， 然后定期将临时索引与原有索引合并的方法。这种方法实现虽然简单，但会降低检 索速度，特别是当临时索引积累到一定数量时，查个词时要寻遍所有的索引后求 并集。 全文索引的动态更新是目前相对较薄弱的环节，倒排索引和p a t 数组都存在动 态调整效率低的问题。首先，由于倒排表和p a t 数组记录的都是绝对位置，因此文 本内部的任何改动，都会改变后续文字的绝对位置，导致大量索引数据的变动。其 次，倒排表还会引发大量索引数据的移动，由于对空间效率的过分追求，倒排索引 几乎都采用紧凑的存储方式，因此动态调整时的移动开销很大。而p m 数组会引发 大量文件的打开操作。 对全文索引的动态更新的研究，比较有影响的有a m i r 和f a r a c h 等提出的动态 词典方法 3 1 , 3 2 】。m i n g g u 和m a r t i nf a r a c h 提出了一种b o r d e r 树3 3 1 ，它是在p a t 树基 础上发展起来的一种数据结构。t h a r p 和b o s w e l l 等提出了b + 树与散列函数相结合 的方法 3 4 】。s c h w e i t z 和t h a r p 等提出在署名文件中使用自适应散列函数的方法【3 5 】。 c u r i n g 等人提出在倒排索引的基础上建一b 树【3 6 。，来支持倒排索引的插入和删除。 a n t h o n y t o m a s i c 等人针对倒排索引的文档插入提出的d u a l s t r u c t u r e i n d e x 结构【3 7 1 ， 这种结构能够动态地区分长、短倒排列表，并针对长、短列表采用不同的检索、更 新和存储策略。c h i u e h 等人提出了实时更新倒排索引的解决方案。但这些方案都有 局限，如对内存大小有特殊要求、不支持文档的删除、对于特小或特大的文档集索 引的空间利用率较低等。2 0 0 4 年l e s t e r 将全文索引的更新方法归为三类：重建、即 时更新和再合并，并分析对比了三者的性能差异【38 1 。另外国内的杨成明提出了针对 倒排索引的双层b + 树结构 3 ”。但总的来说，迄今为止还没有公认有效的动态全文 索引。 华中科技大学硕士学位论文 1 2 4 相关产品 目前国内外都已出现了不少商品化的全文检索系统。国外知名的数据库厂商及 开源的全文检索系统主要有如下几个。 1 s q ls e r v e r 全文检索系统 m i c r o s o f ts q ls e r v e r 于7 0 版开始提供微软搜索服务( m i c r o s o f ts e a r c h s e r v i c e ) 。s q ls e r v e r2 0 0 0 之后，更新增了对多种类型文件( 包括w o r d ，p o w e r p o i n t ， p d f ，e x c e l ，h t m l ，x m l ) 进行全文索引的能力。文件过滤器是一个公共的接口， 允许各种文件格式的转化被集成到s q ls e r v e r 中。s q ls e r v e r 的全文检索系统由五 部分组成：c o n t e n tr e a d e r 、f i l t e rd a e m o n 、w o r db r e a k e r 、i n d e x e r 、q u e r yp r o c e s s o r 。 c o n t e n tr e a d e r 扫描表中的文本及相关的元数据包。 f i l t e rd a e m o n 将数据包传给搜索引擎过滤后台进程，后台进程依据文本的格式 调用相应的过滤器对其进行格式转化。 w o r db r e a k e r 依据文档所采用的语种对格式转化后的文本分词。 i n d e x e r 负责建立倒排索引。索引以压缩的形式来存储以提高存储的效率，但不 可避免地增加了更新的开销。 2 o r a c l e 的o r a c l et e x t o r a c l et e x t 的早期版本名为i n t e r m e d i at e x t 。o r a c l et e x t 使用扩展的s q l 来索 引、查找和分析存储在o r a c l e 数据库、文件系统和w e b 中的文本。o r a c l et e x t 可 以使用多种方式来查找文本。 ( 1 ) 全文本查找，包括布尔查询、精确短语、模糊查询、章节查找、拼写错误、 逆向、通配符、辞典、等价单词以及权重等。 ( 2 ) 混合搜索，指全文索引加上关系属性以及主题查找。 ( 3 ) 查找h t m l 和x m l 章节和标记值。 查找结果可以以各种格式提交，包括纯文本、自动高亮显示关键字h t m l 以 及原始文档格式。o r a c l e 采用了i n s o 公司开发的1 5 0 多种过滤器，过滤的结果 是将各种格式的文档转换为统一的h t m l 格式。采用这种格式即便于以后的搜索，又 能尽可能地保持文档的原貌。o r a c l e 目前支持3 9 个语种，语种根据字符的编码 华中科技大学硕士学位论文 方式可分为：单字节语言和多字节语言。对于中、日、韩等多字节语言，o r a c l e 为它们提供了不同的分词器。 3 d b 2 的t e x te x t e n d e r d b 2t e x te x t e n d e r 将文本搜索引擎( t e x ts e a r c he n g i n e ，t s e ) 集成到d b 2 中， 它支持在表上建立全文索引。通过表的关键字将记录和全文索引入口对应起来。全 文索引和文本的一致性用触发器来维护。 t e x te x t e n d e r 有效地利用了d b 2 的s q l 可扩展特性，将查询分解和连接加入 到关系数据库中。为了减轻文本信息扩展部件( t e x t i n f o r m a t i o ne x t e n d e r ，t i e ) 元数 据的分解和文本检索表函数连接的负担，设计了查询重写部件。为了优化查询，增 加了一组a p i 来完成t s e 和d b 2 优化器间的信息互换，还新增了一组d b 2 的嵌入 函数和相关的查询重写以实现友好的s q l 文本查询语句。 t i e 适合于基于内容的应用，特别是文本和关系查询条件的复合查询，这些查 询通常要求完整的结果集。相反，电子商务应用则主要是简单查询、无条件查询或 只有一个简单的条件，它只要求返回一些相关结果。对此，i b m 提供了n e ts e a r c h e x t e n d e r ，它利用主存技术来达到特别高的执行效率和性能。 4 l u c e n e 全文检索工具包 l u c e n e 是a p a c h e 基金会j a k a r t a 的一个开源的子项目，它并非是一个完整的 全文检索系统，而是一个用j a v a 编写的全文检索工具包，可以方便地嵌入到各种应 用中。已经有很多的j a v a 项目都使用l u c e n e 作为后台的全文检索引擎，如：j i v e 、 e y e b r o w s 、c o c o o n 、e c l i p s e 。l u c e n e 能很方便得实现对中文的支持，只需对其语言 词法分析接口进行扩展即可。 1 3课题主要研究工作 本课题是在武汉华工达梦数据库有限公司开发的拥有自主版权的数据库管理系 统d m 3 的基础上进行研究与开发的。作为d m 3 的予系统之一，全文检索系统可以 从空间效率、动态效率、填充效率、检索效率、语义能力五方面的性能来评价。现 有的全文检索系统虽已初具雏形，具备基本的功能，但从以上五方面来衡量都还不 够完善。本课题主要是针对其中的空间效率、动态效率、填充效率、检索效率四项 华中科技大学硕士学位论文 性能的优化来展开的。 概括来说，本课题的主要研究工作包括。 1 对d m 3 全文检索系统原有的倒排索引实现机制进行研究，分析该系统存在 的不足。 2 通过对当前全文索引模型特别是倒排索引模型的索引压缩技术的深入研究， 及引入倒排索引动态性后可能给索引压缩带来的问题的分析，提出既便于倒排索引 动态更新又具有高效压缩性能的倒排索引压缩方案。 3 研究实现倒排索引动态性的难点，分析目前倒排索引更新策略的解决思路及 存在的不足，在此基础上，提出更有效地支持倒排索引动态性的数据结构，并基于 这种结构实现倒排索引的增量更新。 4 研究提高倒排索引填充和检索速度的方法，其中索引填充包括完全填充、批 量填充和实时填充三种方式。 华中科技大学硕士学位论文 2 数据库管理系统达梦3 全文检索子系统的改进方案 达梦3 ( d m 3 ) 全文检索系统是d m 3 数据库管理系统的一个相对独立的子系统， 己具备的功能有全文索引的定义和删除、全文索引的填充、全文检索、词库维护。本章 首先介绍全文检索子系统的软件架构，然后从性能上分析现有系统存在b 0 不足，并在此 基础上提出改进的设想和要求。 2 1达梦3 全文检索系统 d m 3 全文检索子系统选用倒排列表作为全文索引的模型，一个倒排索引是以独立 于数据库的文件存在操作系统上的，分为单词表和索引数据前后两部分。一个单词可能 有对应的索引数据，亦可能没有。若有索引数据，则该单阋对应的索引数据称为一个倒 排列表( i n v e r t e dl i s t ) ，每个倒排列表都占用一片连续的磁盘空间。单词表存储了词库 中所有单词及该单词的倒排列表在索引文件中的位置，不同单词的倒排列表间采用连续 的紧凑的存储方式。 d m 3 全文检索子系统按功能可分为：全文索引的定义和删除、全文索引的填充、 全文检索、词库维护，它们的实现依赖于一些公用模块，其软件架构如图2 1 所示。 图2 1 全文检索子系统的功能实现示意图 全文索引的定义和删除负责建立和删除倒排索引文件。 全文索引的填充现只具备完全填充功能，其工作过程为：全表扫描，从数据库中取 华中科技大学硕士学位论文 出一个表的全部文本；将每一个文本送交分词模块，分词模块根据中英文词库对原始文 本分词：获取每个字词出现的位置信息( 文本号+ 文本中的位置) ，填充全文索引。当 文本列数据更新后，倒排索引信息将会失效，需要再次完全填充全文索引，以确保查询 的有效性。 全文检索模块的工作过程为：将查询的文本送交分词模块分词，耿吲分词结果；x , j 分词后的每一个词取出它在倒排索引中的条目，进行运算后得到满足条件的元组集合； 取出元组集合并输出。 词库维护模块用于更新和维护词库。全文索引使用的分词算法依赖于一个大的巾英 文词库，目前d m 3 使用的词库包含1 7 1 9 3 1 个词，其中英文词1 2 3 7 0 个，中文词1 5 9 5 6 1 个。 2 2 达梦3 全文检索系统性能分析及评价 全文检索系统优劣的可以从五个方面来衡量：索引的空间丌销、索引的创建效率、 索引的检索效率、索引的动态性能、索引的检索质量。下面围绕这五个方面对d m 3 原 有的全文检索系统进行评价。 倒排索引的空间开销是d m 3 全文检索系统面临的最为突出的问题。一方面，倒排 索引的单词表部分完全照搬了词库中所有的词，大小为固定值6 m b 。事实上，其中绝 大多数词是没有索引数据( 即倒排列表) 的，这部分词没有必要纳入单词表。另一方面， 倒排索引的索引数据部分由于采用4 字节的整数类型表示每一个整数，没有采用任何的 压缩手段，所以造成极大的空间开销。此外，倒排索引的大小还和分词的粒度有关，太 细的分词导致索引项增多，索引空间也随之增大；而太粗的分词虽然节省索引空削，但 会降低查询的查全率。 倒排索引的创建依赖大量的外存 o 操作，特别是对于海量文本，丽 o 是影响创 建速度的决定性因素，因此，要提高索引创建的效率，应从三方面入手：提高内存在索 引创建过程中的工作比例：降低外存i o 操作的次数：减少被迫写入外存的临时数据。 目前d m 3 中倒排索引的创建过程使用缓冲区和临时文件做为辅助，i o 还是较为频繁 的，可以考虑使用存储映射文件取代临时文件等方法加以改善。 倒排索引的检索时间主要由两部分时间决定：在单词表中查找检索词的时阳j ，读取 1 0 华中科技大学硕士学位论文 倒排索引中相关倒排列表的时间。目前d m 3 对单词表的查找采用折半查找，最坏情况 下对于含n 个元素的单词表，查找时间复杂度为l o g n 。而读取倒排列表的时间与倒排列 表的大小等因素有关。 d m 3 的全文索引只支持完全填充，索引不能随数据的操纵永远保持最新状态，必 须定期地完全填充。为及时反映动态文本集的变化，有必要补充倒排索引增量填充的功 能。 索引的检索质量由查全率和查准率两个标准来衡量。上文提到查全率跟分词的粒度 有关，由于d m 3 建倒排索引时采用的是细粒度的分词策略，所以保证了较好的查全率。 查准率的决定因素比较复杂多样，它跟语义有一定的相关性，需要在对文本或检索词进 行分词的过程中引入某些约束规则及推理机制。比如，查“全文”若把“安全文件”也检索 出来，显然与用户的意愿相违，这就降低了查准率。这方面在d m 3 全文检索系统中还 是个空白。 2 3改进的要求 针对2 2 节中提到的原有d m 3 全文检索系统存在的不足，拟从其中最主要的倒排 索引的空间开销、索引的动态性能、索引的检索时间、索引的创建时间这四个方面对全 文检索系统加以改善。 要降低倒排索引的空间开销，可以从分词粒度、单词表、倒排索引压缩等几个方面 着手。本文重点讨论倒排索引压缩的问题。寻求压缩方案时，不但需要考虑压缩率和解 压速度，而且要兼顾到是否方便索引的更新维护。 索引的动态性能跟索引结构有直接的关系。当数据库动态变化时，索引结构直接影 响索引进行相应变化的速度。一般来说，索引变化时对原有的索引数据更改越多( 包括 数据本身的更改和数据的移动) ，动态性能就越差。因此，索引的更新应尽可能减少更 新索引的时间开销，同时尽量不影响索引查询的速度。 不论是倒排索引的填充还是检索过程中，都需要在词库中进行查找来实现分词，尤 其是填充索引的过程中这种查找更是频繁，如果能寻求到一种比折半查找更有效的方 法，势必加快索引创建和检索的速度。 华中科技大学硕士学位论文 2 4本章小结 本章首先介绍了d m 3 全文检索系统的软件架构，然后从衡量全文索引性能的索引 的空问开销、索引的创建效率、索引的检索效率、索引的动态性能、索引的检索质量五 个方面分析了原有系统存在的问题和不足，最后，提出了改进索引空间、动态性能、索 引填充速度和检索速度的设想和欲达到的目标。 1 2 华中科技大学硕士学位论文 3 倒排索引的压缩 压缩倒排文件有助于提高查询的吞吐量，因为读和解压一个己压缩的倒排索引 很可能比读一个未压缩的倒排索引节省i o 时间【4 0 ，4 ”。本章首先说明倒排索引具有 显而易见的压缩性的根源。然后归纳分析了目前较有影响的倒排索引压缩方法。前 人的研究关注得更多的是压缩率，而往往忽略了倒排列表的动态性。为了兼顾二者， 使压缩率和动态性结合起来，需要研究既支持倒排索引动态性又能保证压缩率的压 缩方法。为此，本章在分析倒排列表的动态特点的基础上，提出了一种混合编码的 压缩方案。 3 1 倒排索引压缩技术概述 一个倒排索引通常由字典表文件( d i c t i o n a r yf i l e ) 和记录文件( p o s t i n g sf i l e ) 两部分组成。字典文件记录了文本集中出现的每个单词及其倒排列表在记录文件中 的位置和大小等信患。一个单词对应的倒排列表可以表示如下。 n ， ， ， n 表示单词在n 个文档中出现，d 。为文档i d ，f l 为单词在文档d 。中出现的词频， 是单词出现在某个文档中的位置列表。事实上，一个倒排列表可拆分 为三部分。 1 一个文档i d 序列 ( 1 i n ) 。 2 n 个位置序歹l j 。 3 ，一个词频序n 。 其中，第1 和第2 两个序列都是递增的整数序列。鉴于这种递增的特性，可以 用间隔d l + 1 一d l 和p i k + ! - p i k 来代替序列中的值，那么上边三个整数序列就转化为如下形 式。 1 一个文档i d 间隔序列 。 2 n 个位置间隔序j 7 1 j 。 3 一个词频序列 。 转化成间隔后，没有损失任何信息，因为初始倒排列表总是可以通过计算间隔 华中科技大学硕士学位论文 的和还原，此外，还给序列的取值带来了两个影响：样本空间缩小、概率分布不均 衡性扩大，因此预示着存在基于概率分布的高效压缩方法。目前己经提出了一些模 型描述整数值的概率分布，适用于对以上任一序列的压缩。这些模型可以分成两类。 1 全局模型，所有序列使用相同的压缩参数。 2 局部模型，对于不同序列，其压缩参数是不同的，这个参数通常是单词的 出现频率。 局部模型的压缩效率一般高于全局模型，且在解码速度方面也很有优势，但实 现更复杂。 3 1 1 非参数化模型 非参数化模型是一种全局模型，其编码本身隐含了整数序列中数值的概率分布， 这种隐含概率分布的特性使非参数化模型不但能用于静态整数序列的压缩，而且也 适用于动态整数序列的压缩。非参数化模型依编码长度的可变性分为定长编码和变 长编码两类。理想编码长度l ( x ) 和数值的概率p r ( x ) 2 _ r 司的香农关系( 1 ( x ) = 一l o g p r ( x ) ) 可以用来确定任一编码方法所隐含的概率分布。 1 定长编码 最简单的全局模型是定长编码，它的压缩效率有限。定长编码隐含的概率模型 是：p r ( x ) = 1 ( 为整数序列的最大值) ，即整数值在数值空间上均匀分布，每个 数值的编码长度均为l ( x ) = l l o g n i 。这显然不符合实际情况，一般地，高频词出现间 隔比较小，低频词出现间隔比较大。 2 变长编码( v a r i a b l eb y t ec o d i n g ) 可变字节编码【4 1 】是一种变长编码，它是一种字节对齐的编码方式。将整数转化 成二进制后，以7 位为单位对其分段，每段前加一位成为8 位，恰好用一个字节表 示，这一位为0 表示该段是最后一段，为1 表示还有后续段。例如，1 3 5 可表示为 1 0 0 0 0 0 0 1 ，0 0 0 0 0 1 1 1 。对于3 2 位的整数，小于1 2 8 的数可用1 字节来表示，节省了 3 4 的空间；而大于2 0 9 7 1 5 1 的数需要5 字节，不但没达到压缩的目的，反而增大了 空间。由于计算机多以字节为操作单位，字节对齐的编码往往更能发挥硬件的优势， 所以可变字节编码的压缩和解压速度都较快。 华中科技大学硕士学位论文 3 一元编码( u n a r yc o d i n g ) 一元编码也属于变长编码，它将一个整数x 编码成x 1 个1 位，其后紧跟一个0 位，如3 的编码为1 1 0 ，因此对值为x 的整数，其编码就需要x 位，编码长度l ( x ) 2 x 。 一元编码倾向于值很小的整数，但这种倾向太极端了。一元编码隐含的概率分布为 p r f x ) = 2 ，概率随x 值的增大按2 的指数衰减，当x 达到一定值，这个概率值就太 小了，显然不能反映实际概率值。一元编码易于编码和解码，但对大些的数只会消 耗更多的空间，因此很少使用。 4 y 编码( g a m m a c o d i n g ) 定长编码和一元编码是两种极端的编码模型。还有几种编码。其隐含的概率分 布在由定长编码所设定的均匀分布和由一元编码所隐含的2 的指数衰减形式之间。 其中一种是y 编码f 1 ，它可表示为：对于整数x ，将其编码为前后两部分，前缀部 分值为l + l l o g x j ，用一元编码表示，需l + l l o g x j 4 立；后缀部分值为x 2 u ”“，用定 长编码表示，需l l o g x j 4 ，所以编码长度l ( x ) = 1 + 2 l l o g x j 。实际上，一元部分指出了 编码x 所需位数。例如，9 的y 编码为1 1 1 0 ，0 0 1 。y 编码隐含慨率是：p r ( x ) = 可l ， 它给出了整数大小和概率之间的平方倒数关系。一元编码也易于编码和解码，解码 时先取出一元编码部分，设值为c ，再取其后c 一1 位的定长编码，设值为