（计算机应用技术专业论文）基于全文数据库的全文检索模型研究.pdf

基于全文数据库的全文检索模型研究 郭琦娟( 计算机应用技术) 指导教师：陈通照( 高级工程师) 摘要 全文检索技术已经在企业信息门户等领域有了广泛的应用。然而， 目前大部分全文检索系统是面向静态数据库或半动态数据库的，即信 息一旦录入就不能更新，或者只能在预先设置的时间段内统一更新。 这显然不能满足一些实时性要求很高的应用，如报社新闻的查询等。 因此，全文检索的动态性是全文检索技术发展的一个必然趋势。 全文检索的动态性取决于全文索引创建和更新的动态性。通过对 传统模型和新兴模型进行分析，发现互关联后继树模型具有出色的时 间效率和空间效率，但动态更新效率还不是特别理想。为了提高其动 态性能，从存储结构的优化、动态更新索引结构的设计、分布式并行 检索策略的使用三方面进行研究。在优化存储结构方面，将索引文件 分块处理，详细讨论了块、块中记录及文档的算法设计，实验表明： 该方案提高了索引更新的灵活性。在设计动态更新索引结构方面，索 引由主索引、附加索引和删除文件列表组成，实验证明：独特的结构 很好地解决了索引的更新问题。在分布式并行检索策略的使用方面， 给出具体的分布式存储建库和并行处理方法，在一定程度上避免了互 关联后继树模型动态性能不理想的弱点。最后，提出一个整合了以上 各种方案的基于互关联后继树模型的全文检索系统框架，该框架具有 良好的综合性能。 关键词：全文数据库，全文检索，互关联后继树，动念索引 r e s e a r c ho i lf u l l 一1 e x ti n d e xm o d e lb a s e do i lf u l l 1 x t d a t a b a s e g u oq i - j u a n ( c o m p u t e r a p p l i c a t i o nt e c h n o l o g y ) d i r e c t e db ys e n i o re n g i n e e rc h e nt o n g - z h a o a b s t r a c t w i t ht h es p e e do fs t e p p i n gi n t o i n f o r m a t i o n s o c i e t y ”，f u l l t e x t r e t r i e v a lh a sb e e n w i d e l y u s e di n m a n yf i e l d s s u c ha s e n t e r p r i s e i n f o r m a t i o np l a t f o r me t c b u tm o s to ft h ef u l l t e x tr e t r i e v a l s y s t e m su s e s t a t i ci n d e xd a t a b a s eo rp a r t - d y n a m i cd a t a b a s e t h i sk i n do fd a t a b a s ec a n t f u l f i l lt h er e q u e s tf o rg o v e r n m e n to rn e w s p a p e r , b e c a u s ei tc a l l tb e u p d a t e da tr e a l - t i m ea f t e rt h ed a t ah a sb e e ni n p u t t e d ，o rc a l lo n l yb e u p d a t e da tap r e s e tt i m e s o i ti sv e r yn e e d e df o rt h ed y n a m i cf u n c t i o no f f u l l t e x ti n d e xs y s t e m t h ed y n a m i cf u n c t i o no ff u l l t e x ti n d e xs y s t e mi s b a s e do nt h e d y n a m i cf u n c t i o no ft h ec r e a t i o na n du p d a t i n go ff u l l t e x ti n d e x b y c o n t r a s t i n gt o t h et r a d i t i o n a lm o d e la n dt h ee m e r g i n gm o d e l ，a n a l y z i n g e a c hm o d e l sm e r i t sa n dd e f e c t sw ed i s c o v e rt h a ti n t e r - r e l e v a n ts u c c e s s i v e l l e e sm o d e lh a ss p l e n d i dt i m ee f f i c i e n c ya n ds p a t i a l e f f i c i e n c y , b u tt h e d y n a m i cu p d a t ee f f i c i e n c yo ft h ei n d e xd a t ai sn o tv e r yi d e a l i no r d e rt o i m p r o v et h ed y n a m i cf u n c t i o no ft h es y s t e m ，t h i sp a p e rm a d er e s e a r c h e si n t h r e ea s p e c t sl i k et h eo p t i m i z a t i o no fs t o r a g es t r u c t u r e ，t h ed e s i g no fa l l u p d a t i n gi n d e xs t r u c t u r ea n dt h ea p p l i c a t i o no ft h ed i s t r i b u t i o n a lm e m o r y i i i a n dp a r a l l e lr e t r i e v a l i nt h ef i r s ta s p e c t , w e p r e s e n tan e ws t r u c t u r eb vt h e “p a g e ”o fo p e r a t i o ns y s t e ma n dd e f i n es o m ea l g o r i t h m so nb l o c k r e c o r d a n dd o c u m e n t d a t as h o w st h a tt h en e ws t r u c t u r ec a n m a k et h eu 口d a t eo f i n d e xm o r ef l e x i b l ea n dc a l l i m p r o v eo i lt h ed y n a m i cf u n c t i o no ft h e s y s t e m i nt h es e c o n da s p e c t ，t h ei n d e xs t r u c t u r ec o n s i s t so fm a i ni n d e x a d d i t i o n a li n d e xa n dd e l e t e df i l et a b l e t h ee x p e r i m e n ti n d i c a t e st h a ti th a s g o o dp e r f o r m a n c ei ns o l v i n gt h ei n d e xr e n e w a l p r o b l e m i nt h et h i r d a s p e c t w ep r o p o s et h ew a yo f d i s t r i b u t i o n a lm e m o r ya n dp a r a l l e lr e t r i e v a l t oa v o i dt h ew e a k n e s so fi n t e r - r e l e v a n ts u c c e s s i v e t r e e s i nt h ee n d a f u l l _ t e x tr e t r i e v a l s y s t e mf r a m ei sc o n s t r u c t e db y i n t e g r a t i n ga l lt h e s c h e m a sm e n t i o n e da b o v e ，w h i c hb a s e d0 1 1i n t e r - r e l e v a n ts u c c e s s i v et r e e s a n di th a sn i c ef u n c t i o n k e yw o r d s ：f u l l t e x td a t a b a s e ，f u l l t e x tr e t r i e v a l i n t e r r e l e v a n t s u c c e s s i v et r e e s ，d y n a m i ci n d e x 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 中国石油大学或其它教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示了谢意。 签名： 氢煎垄2 d 0 1 年4 月 f 日 关于论文使用授权的说明 本人完全了解中国石油大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件及电子版，允许论文被查阅和借阅； 学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复 制手段保存论文。 ( 保密论文在解密后应遵守此规定) 学生签名：毒鱼熊2 d 。1 年午月f 同 新签名：毒柚雕乙声印月日 中国i i 油人学( 华尔) 硕十论文第1 章前言 第1 章前言 1 1 研究背景 随着人类社会进入信息时代步伐的加快，信息呈现指数增长的趋 势。由于文本是信息的主要载体之一，因此如何有效地管理文本这种 非结构化数据成为当前一项紧迫的研究任务，全文数据库技术和全文 检索技术也就成为各国专家学者研究的热点”。 全文检索就是以文本数据为主要处理对象，根据数据资料的内容 而不是外在特征来实现的信息检索手段。它能提供快捷的数据管理工 具和强大的数据查询手段。快捷的数据管理工具，能帮助人们快速进 行文档资料的整理和管理工作，强大的数据查询手段，使人们能快速 方便地查到他们想要的任何信息。 全文数据库，也可称为文本数据库，是管理大量文本的系统。由 于传统数据库擅长于结构化数据的管理，而文本是典型的非结构化数 据，它们之间的巨大差异使得全文数据库的实现手段以及全文索引的 结构模型完全不同于传统数据库，比如关系数据库，因此无法通过对 传统数据库的移植、借用和变换等简单方法，而必须研究发现全新的 理论和方法来完成这项工作。而且它的研究也能够为其他几种更复杂 的信息载体，如声音、图像等的管理的研究提供重要的经验【2 】。 作为一种特殊的数据库系统，全文数据库要完成的工作仍然是传 统数据库的f i l i 大功能：存储和检索，具体而言就是文本数据的存储和 任意字符串的检索。数据库系统的两大功能中，检索更具有核心的地 位，可以认为全文数据库研究的重点是全文检索，而全文检索的关键 又是全文索引。全文索引的研究内容主要有：( 1 ) 索引的空间效率( 2 ) 中国_ i 油人学( 华尔) 硕十论文第1 章前言 索引的检索效率( 3 ) 索引的创建效率。而更加实用的全文索引还应 该增加曲项研究内容：( 1 ) 索引的动态效率( 2 ) 索引的语义能力。 由于全文检索应用范围的扩大，其动态效率的研究也显得越来越 重要。全文数据库系统一开始被广泛应用于提供资料检索服务的部 门，例如图书馆、档案馆等。随着技术的成熟和整个社会信息量的快 速增长，全文数据库扩大了应用的领域”i 。但是，大多数实用系统是 面向静态数据库的1 4 1 ，即使允许数据库进行动态变化，也是建立在文 本变化相对较少或变化不频繁的假设上，动态性能越强的系统提供的 服务就越少，例如只提供关键词检索或只提供主题检索，因此一般的 全文数据库系统总是在功能和动态性能上进行折衷。由于当前信息的 增长速度和淘汰速度均呈现不断加快的趋势，我们预测不久之后在某 些应用领域将很难再进行类似的折衷，这就需要开发真正意义上的动 态全文数据库。 1 2 研究现状 全文检索的应用导致了信息检索领域的一场革命。从1 9 5 9 年在美 国p i t t s b u r g h 大学诞生到现在，全文检索技术已经在企业信息门户、媒 体网站、政府网站、数字图书馆、搜索引擎及商业网站等各领域有了 广泛的应用。目前，西文全文检索技术己经发展比较成熟，但由于中 文信息的固有特点，中文全文检索技术的研究起步较晚。当今国内外 对全文检索系统的研究方兴未艾。 国外已有一些较成熟的商用产品出现，影响较大的有： k n i 【g h t r i d d e r 联机全文检索系统、s d c 公司的o r b i t 系统、i b m 公 司的s t a i r s 系统、m a s s a c h u s e t t s 大学智能信息检索中心开发的 i n q u e r y 系统、c o m e l l 大学开发的s m a r t 、i b m 的l o t u s n o t e s 系 2 中国i 油人学( 华自、j 硕十论文第1 章前言 统以及m i c r o s o f t 公司的i n d e xs e v e r 系统。其中，i b ml o t u sn o t e s 系 统和m i c r o s o f ti n d e xs e r v e r 系统在许多方面均已达到较高的技术水 准，应用也较为广泛。由于中西文问的巨大差异，坐等国外成果，然 后加以移植改造的老方法是行不通的。 国际上流行的全文检索模型主要有：倒排表模型口j ( i n v e r t e d f i l e s ) 、署名文件川( s i g n a t u r ef i l e s ) 、位图( b i tm a p ) 、p a t 树7 和p a t 数组【8 j 。前三种索引模型从实质上讲，是同一基本观念的变体，即把 文档看成索引项的集合，因此具有同样的弱点：索引数据必须具有文 档一索引项结构，且只能实现简单的查询。p a t 树和p a t 数组将索引数 据看成一组半无限串的叠加，避免了这个弱点。 在国内，从1 9 8 7 年北信易宝开始开发自己的全文检索系统，他 们的t r s 系统是国内第一家拥有自主版权的中文全文检索系统。其他 全文检索系统还有天宇的c g r s 系统、创想科技的t r a n s 系统、尚 唯全文检索系统等。2 相邻矩阵模型州和互关联后继树模型都是针对 中文提出的全文检索模型。这两种模型都能够利用索引生成原文，因 而可以完全抛弃原文，节约存储空间。 目前，全文检索的动态性能并不十分理想，利用b + 树存储的倒排 表能够实现动念操作，但会增大膨胀比。在p a t 树或者p a t 数组中能 够实现数据的动态改变，但代价非常高，我国研究人员还提出过一种 动态的p a t 数组模型，但是以索引空间的增大为代价的。2 邻接矩阵 的动态性能也不好，互关联后继树模型的研究刚刚起步。 综上所述，全文检索技术是现代信息处理的一项重要技术也是 计算机应用技术中的一个难题。进行面向中文文本的全文数据库的研 究，提高检索系统的动态性能不仅有很高的理论价值，而且极具商业 前景。 1 中国f i 油人学( 华j ：) 硕十论文第l 章前言 1 3 主要内容 全文检索的首要问题是全文索引模型的选择。本文j 下是从全文索 引模型着手，介绍、分析并比较了现有几种流行的全文索引模型。特 别地，介绍了一种新的模型互关联后继树模型，包括它的基本思 想和具体实现。对比其他模型，互关联后继树模型对于中文来说，综 合性能良好，符合未来全文检索技术发展要求，但是索引数据的动态 更新效率还不是特别理想。本文主要以互关联后继树模型为基础，讨 论如何提高互关联后继树模型索引维护的整体效率。文中给出了详细 的设计方案，具体包括以下几个方面：( 1 ) 存储结构的优化( 2 ) 动 态更新索引结构的设计( 3 ) 分布式结构管理和并行检索方法。我们 在这里介绍互关联后继树模型的原型系统，研究其动态性能，仅仅是 一个开端，后期还有更多的工作需要进一步来完成，使其具备强大的 生命力。 1 4 本文结构 第1 章前言 介绍全文数据库和全文检索的概念，并概述了国内外研究进展和 本文的主要研究内容。 第2 章全文检索模型综述 介绍全文检索的基本原理及常用的检索模型和索引模型，提出全 文索引优劣的评价标准，最后根据评价标准对目前主流的几种全文检 索模型的性能进行分析比较。理论分析证明互关联后继树模型的综合 性能良好，但是动态性能比较脆弱。 第3 章互关联后继树模型的基本原理及操作算法 详细介绍一种新型海量全文存储、索引模型互关联后继树模 4 中国i i 油人学( 华东) 硕 论文第l 章前言 型。对互关联后继树模型的创建、查询和原文生成算法做了详细分析。 实验数据证明互关联后继树模型是一种极具潜力的全文检索模型，但 是动态性能不够理想。 第4 章瓦关联后继树索引结构的优化 借用操作系统中“分页”的思想，将索引文件分块处理。详细讨 论了块、块中记录的结构与算法设计，最后在对索引块和记录操作的 基础上，介绍了文档操作算法的设计。实验表明：该方案提高了索引 更新的灵活性。 第5 章动态更新索引结构的设计 设计一种基于互关联后继树模型的动态更新索引结构，该索引结 构由主索引、附加索引和删除文件列表组成。实验证明：独特的结构 很好地解决了索引的更新问题。 第6 章基于互关联后继树的全文检索系统框架 提出用分布式结构和并行处理的方法来提高检索速度和动态性 能，并整合各种方案，介绍了一个基于互关联后继树模型的全文检索 系统框架。 第7 章结论 对全文的工作进行总结，并提出新的研究方向。 5 中国f f 油人导( 牛j ，) 硕十论文第2 章全文检索模7 r j 综述 第2 章全文检索模型综述 2 1 全文数据库 拿文数据库，也可称为文本数掘库是管理大量文本的系统，其 核心是全文索引。全文数据库系统的系统结构可用图2 1 表示，全文 数据库有一个相应的全文索引。索引是海量数据库不可缺少的，这是 因为索引从某种意义上是一种将原数据库按检索要求“排序”后的数 据库，它的存在能够大大提高检索的效率。通过索引全文数据库系 统可以提供多种检索服务，例如基于字匹配的全文检索，基于自然语 言匹配的文本检索和进一步的文本挖掘等等。当全文数据库中的文本 发生变化时，索引也随之改变以保持两者的一致性，从而保证检索结 果的j 下确性。 文本的动态增删 2 2 全文检索模型 幽2 1全文数据库系统的结构 ( 1 ) 全文检索的基本原理 全文检索的主要任务是对信息集合与需求集合的匹配与选择，我 们可以把一个信息检索系统形式化描述为一个四元组0 “：s = ( d ，t ， 6 中国i i 油人学( 华东) 硕1 ：论文第2 章全文检索模删综述 q ，p ) 。其中，d = ( d l ，d z ，d 。) ，t = ( t i ，t 2 ，t 。) ，q = ( q l ， q 2 ，q 。) ，p ：q * d 一 r 。式中d 表示某系统中经过标引的文档集合， t 和q 分别代表所有可能存在的标引词集合和检索提0 3 i i q 集合，p 为 匹配函数，其函数值集合r 为检索结果。其过程用图2 2 所示。 图2 - 2 全文检索的基本原理 ( 2 ) 常用的检索模型 文本检索目前主要有三种模型：布尔检索模型l 、概率推理模型 和向量空问模型。布尔检索模型是最早也是最简单的一种检索模型， 它将用户提问表示成布尔表达式，检索系统将提问式与文档进行逻辑 匹配，得出命中文献集合为检索结果。检索结果一般不进行相关性排 序。概率推理模型m 1 由m a s s a c h u s e t t t s 大学b r u c ec r o f t 提出，它的基 本思想是把信息检索看成是事实的推理与证明过程。这个推理网络是 一个有向图，节点表示有效事实，边表示事实间的依赖关系。在网络 中，每个节点都有一个链矩阵，用来计算给定节点的父节点的概率。 7 中国7 i 油人学( 华东) 硕十论文第2 章全文检索模1 q 综述 输出时则按概率大小把文件显示给用户。向量宅l 日j 模型【1 4 1 由c o m e l l 大学的s a l t o n 教授提出。它的基本思想是用检索项的高维向量空间来 表示用户的提问和文本集信息，其中每一维为一个特征。一个用户提 问向量或文本向量的第1 个元素表示用户提问或文本的第1 个特征的 重要度，或称权值。用户提问向量的权值由用户指定；文本向量的权 值则根据特征在文本或文本集中的出现频率决定。提问向量与文本向 量间的余弦角通常用来测定该文本与该用户提问词之间的匹配程度。 上述三种方法中，第一种是完全依赖于字符串的匹配结果。第二种和 第三种则从统计的角度理解用户的检索请求和文本语义。 ( 3 ) 常用的索引模型 从中文全文索引技术角度看，中文和英文的区别主要有：中文 文本中词与词之间没有间隔，且中文词的定义和取舍没有公认的结 果，因此无法直接应用英文系统中的词索引方法；中文词没有形态 变化，因此不用关心英文系统的较繁琐的词形转换技术；中文字符 数量比英文字符要多得多，因此某些索引模型不适宜用于中文文本。 目前使用的系统，基本上都采用倒排表1 作为中文全文检索模型，争 论主要是索引项的选择，即按字索引还足按词索引6 i ，但这种移植， 因为中英文之间的差异，在达到一定程度以后就难以进一步优化索引 和提高查询速度，越来越不能满足实际的需要。与此同时也就产生了 一些新的模型，如2 相邻矩阵模型和互关联后继树模型 ( i n t e r - r e l e v a n ts u c c e s s i v et r e e si r s t ) ，它们都是从中文语言特点出 发提出的模型，有极大的应用和发展空问。 2 3 全文索引优劣的评价标准 衡量面向全文数据库的全文索引优劣的标准主要有 1 7 , 1 8 l ： 3 中国石油大学( 华东) 硕十论文第2 章全文检索模犁综述 ( 1 ) 时日j 复杂度：包括创建索引的时间效率以及检索的时间效 率。对于索引模型更重要的是检索性能，所以，更常考虑的是模型的 检索速度。 ( 2 ) 空问复杂度：由于文本数据库中数据的海量性，索引模型 中任何能够减少文本数据库空间消耗的机制均可导致不可估量的实 用效果。通常，用膨胀比( e r ) 来评价索引模型的空间性能。 e r = ( i s + f s ) f s ( i s 为索引大小，f s 为原文大小) 索引模型的膨胀比与模型的具体实现方式和使用的压缩算法也 有很大关系。同时又会影响索引效率。 ( 3 ) 查询完备性：一个好的全文检索模型应该能够实现多种查 询，如： 字符串查询：包括关键词查询，或较长的字符串查询，比如一 个句子。 前缀查询：在索引库中查询具有某给定前缀的字符串。 l 临近查询：查询所有字符串s ，s 以s l 字符串开始，以s 2 结尾， 而s l ，s 2 之间最多间隔n 个字符( n 由用户给定) 。 范围查询：查询所有在某一词典范围内的字符串。如：“a b r a s i o n ” 在“a b c ”和“a c c ”范围之内，而“a b a c u s ”和“a c r i m o n i o u s ”不在。 最长重复查询：在文档的两个不同位置寻找相同的字符串，而 这个字符串在整个文档中是最长的。 最频繁匹配查询：查询在文档中出现次数最多的字符串。 ( 4 ) 适应性：好的索引模型应该可以处理各种不同类型，具有 不同特点的数据，如：长度相差很大的记录或者没有文档一关键词结构 的数据。 9 中国石油入学( 华尔) 硕十论文第2 章全文检索模掣综述 ( 5 ) 动态性：索引模型最好能够适应数据的动态改变，包括关 键词词典中词条的增加，或索引记录的改变等。 实现索引的动态更新一个很大的难题在于更新时间的非线性特 征。对于一个大小为s 的数据库和一个大小为n s 的数据库，后者索 引的更新时间一般远远超过前者索引更新时间的n 倍，经常呈指数分 布。后来的索引更新算法吸收了索引合并的思想，降低了曲线的指数， 同时也使得索引的“第一次”创建和索引添加之间的差异越来越小， 直至消失。按照系统动态性能的大小，大致可分为三种：准动态、半 动态、全动态。 准动态全文索引 准动态，又称为可增式动态，即索引文件在显式的命令下可以进 行增加和删除。准动态全文数据库其实是静态全文数据库的有限改 进，它把索引的更新分成两种类型：一是索引从无到有的“第一次” 创建，二是在原有的索引上添加。由于索引的“第一次”创建可以看 作在大小为0 的索引上添加数据，因此可以证明，对于同样的新文本 集使用同样的算法，单独为其创建一个新的索引，其效率不会低于在 一个己有的索引上添加这些文本的索引。己有的成果证明，这两种过 程的效率差异非常大，因此以m i c r o s o f ti n d e xs e r v e r 为代表的绝大多数 全文数据库系统均采用为新文本集创建一个新的索引再使其与原有 索引合并的方法。虽然索引合并也是一个牵涉大量外存i o 操作的较费 时的过程，但是准动态全文数据库假设新文本集的大小相对原数掘库 的数据量是很小的，数据库的变化也是不频繁的。 半动态全文索引 半动态全文索引和准动态索引相比，对于前者，当原文本集变动 时，系统并不需人工显式干预才对原索引进行增加或删除，而是系统 i n 中国柯油人学( 华东) 硕士论文第2 章全文检索模型综述 启动时，自动对文本集进行检查，若发现有新增文本或己有文本被删 除，则自动更新索引，以使索引和文本相一致。实现索引半动态的思 路也比较直接，只需在系统启动时，把索引的目录树与文本集的目录 树相比照，若不同，则根据新文本集进行索引更新。 实时动态全文索引 应该说，实时动态全文索引才是完全意义上的动态索引。它不仅 依靠系统本身对文本集的更新进行监测，而且索引更新是实时完成 的，而不是仅在系统刚启动时做一次。 索引动态更新时有很多因素影响它的效率，其中最主要的因素 有：乱新文本索引创建时的i o 次数。计算机中相对最费时的操作是 外存的i j o 操作，它是影响索引建立和同步更新最根本的因素。b 索 引空间。小的索引空间消耗将减少i o 操作，间接影响动态性能。c 索 引结构。当数据库动态变化时，索引结构直接影响索引进行相应变化 的速度。索引变化时对原有的索引数据更改越多( 包括数据本身的更 改和数据位置的更改) 动态性能就越差。 2 4 几种全文检索模型及其比较 ( 1 ) 署名文件模型和位图模型 署名文件也称散列函数法，它为每个文档设定一个宽度为w 的矢 量，把该文档的每个索引项都按照某个散列函数映射到矢量中的某几 位上，并将其置l 。所得结果，即为该文档的署名。 要检测一个查询项是否在给定的文档中出现，首先要计算此查询 项的散列函数值。如果某文档署名中所有的对应位均被设定，则此查 询项可能出现在该文档中。散列函数的使用，使署名文件的查询结果 具有一定的不确定性。为了排除误匹配，必须扫描结果文档以检查查 中国石油人学( 华尔) 硕七论文第2 章全文检索模型综述 询项是否真正出现。 存在误匹配是署名文件的一个主要缺点。可以通过加入文档署名 宽度w 来降低误匹配率，当然这是以索引空间的膨胀为代价的。但无 论如何，总是需要进行误匹配检查，这在相当程度上增加了查询的开 销。假定文档中不同索引项个数为t ，散列函数将每个索引项映射为s 位，文档署名宽度为w ，则误匹配率可以表示为i ”l ： 1 p ( w ，s ，t ) = ( 卜( 1 一二) “) 5 w 位图为每个文档存储一个矢量( b i t v e c t o r ) ，矢量的每个位对应一 个索引项。如果文档中出现某个索引项，该位就置i ，否则置0 。查 询包含某索引项的文档时，只要查看哪些文档矢量对应那个索引项的 位为l 即可。查询仅仅涉及简单的位操作。因而位图使用简便，查询 快捷，尤其适合布尔检索。但是即使使用了一些高效的压缩方法后， 位图的空间开销还是很大。一些实验表明，位图的空间开销可能是原 文本的几十倍。 ( 2 ) 倒排表模型 倒排表模型的思想比较简单，在索引创建过程中只需对文本集进 行顺序扫描并记下位置，不需要更多的分析，对索引的填写总体上也 是顺序进行的，因此外存i o 操作相对较少。倒排表模型主要表现为 空间效率较差、检索效率低下、创建过程烦琐。倒排表模型的索引结 构和工作原理： 完整的倒排表模型的索引由2 个部分组成： 索引头：是一个一维数组，以字符内码为下标，记录各个字符 的索 在索引体中的开始位置。 索引体：实际的索引体是各行数据依次首尾连接形成的一维数 2 中国i 油人学( 华东) 硕十论文第2 章全文检索模型综述 据流。具体结构如图2 - 3 所示，其中b ( 1 j m ) 表示含有字符 a i 的文本的内部代号，n i j 表示文本t u 中字符a i 出现的次数， o u 。o i j b 指出了文本t i j 中字符a i 出现的具体位置。 由于每个字符的索引数据的长度不同，囚此需要索引头中的指针 来指出开始位置。 a l t n ，【o o u b 】 ，( t 1 2 , n 1 2 ，【o 0 1 2 b 】) ， a 2_ - t 2 i ，n 2 1 ， 0 2 k 0 2 1 6 1 ， a t 。i ，n 。i ，【o m ，o i b 】) 图2 - 3 倒排表模型结构 检索时，设待查字符串为a l ，a 2 ，a r ，首先通过字符列表定位各 字符的索引数据，然后对数据进行分析：若a l ，a 2 ，a r 的索引数据中 均含有文本t 的索引记录，在r 个关于文本t 的索引记录中又含有 0 1 ，0 2 ，o ，( o i 是属于字符a i 的索引数据) ，且0 和o 。+ l ( 1 i r 1 ) 的 差值刚好是字符a 所占字节数，则文本t 为一个命中文本。找到所有的 命中文本后( 或分析完毕后仍找不到命中文本) ，检索完成。 ( 3 ) p a t 树和p a t 数组模型 p a t 树很有特色的地方是将一个文本看成一组半无限串的叠加， 而这组半无限串的排序结果被表示成树的形式。它的最大优点是极 大加快了检索速度。尤其对某些特殊的检索，如前缀检索、范围检索 等检索效率更高。它的晟大缺点是空间开销大，创建过程中的空间开 销更大，创建效率也很低，而且无论是创建过程还是检索过程都严重 依赖源文本，而倒排表在检索中是不需要源文本的。下面用一个简单 3 中国4 1 油大学( 华尔) 硕士论文第2 章全文检索模q ! 综述 的例子来说明p a t 树和p a t 数组的原理。设文档：“a b a b c ”。从每个字 符到文档尾字符形成一个字符串( 这种字符串称为半无限串) ，此文 档包含了5 个字符，也包含了5 个半无限串，分别如下：a b a b c i b a b e a b c b e c 。我们用半无限串开始字符的位置标记该半无限串，对 这些半无限串做词典排序，排序结果是。文档对应的p a t - 树和p a t 一数组如图2 - 4 所示。 叵叵叵圈 a b a b ea b c ( 虿) b a b eb c c pat树pat数组 图2 - 4p a t 树和p a t 数组示例 对于p a t 树，如果查询“a b e ”，则从p a t 树的树根按照分支的标志 下降，首先沿着根节点的第一个分支( 标志a b ) 找到第一层的第一个 中间节点，而后再从该中间节点的第二个分支( 标志c ) 找到a b e 的 匹配。p a t 数组是由p a t 树的叶节点串行化得到的，反映了文档中所 有半无限串的词典排序结果，查询可以直接在数组中进行。 ( 4 ) e2 相邻矩阵模型 2 相邻矩阵模型将索引数据看成无环句串的连接，所谓无环句串 实际上就是同一字符至多只出现一次的字符串。如文档“a b a b c ”可以 分解为无环句串“曲”和“a b c ”。如果用有向图来表示该文档如 图2 5 a 所示。 有向图的顶点为构成文档的基本字符；边连接文档中两个邻接字 符，且由前面的字符指向后面的字符。边的标记为该边对应的字符有 1 4 厂萨 a 中国i 油人学( 华；) 硕士论文第2 章全文检索模犁综述 序对所在的句串的标号。若用邻接矩阵表示此有向图就是该文档的相 邻矩阵模型( 图2 - 5 b ) 。如果查询“a b c ”，从邻接矩阵中取出a b 和b c 的值，分别是 1 ，2 ) 和 l ，然后进行集合求交得到l ，即产生一个解。 l 2 1 + h g abc a中t a b中 b 中中t b c t a b = ( 1 ，2 ) c 审中 伞t b c = ( 1 1 图2 5 a ：文档有向图图2 5 b ：相邻矩阵 相邻矩阵中句串的无环性保证了相邻矩阵确定的每个句串是唯 一的，各句串的连接，实际上就是模型中加入的原文档，因而利用相 邻矩阵模型可以进行原文生成。 ( 5 ) 互关联后继树模型 在互关联后继树模型中，对任意文本t 中的任意字符串a b ，a 称 为b 的前驱；b 称为a 的后继。在每个文本t 的末尾人为添加一个不 在该文档中出现的字符，作为该文档的结束符，则文本最后一个字符 的后继为文本结束符。 例如文档b a b a c # ( 其中# 为索引库的结束符) ，b 有两个后继都是 a ，a 有两个后继分别是b 和c ，c 的后继为拌。对于每个字符建立一棵 树，树的分支为该字符的后继，如图2 - 6 所示。图中各分支后继后面 的序号是该后继的后继在以该后继为根的树中的分支号。如b 树的第 二个分支是( a ，2 ) ，因为这个a 在原文中的后继为c ，而c 是a 树的第二 个分支。因此，整个互关联后继树构成的森林记载了文档中所有字符 1 5 中国_ i 油人学( 华东) 硕十论文第2 章全文检索模刮综述 的先后位置，可以利用索引生成原文。 “i ( b ，2 ) ( c ，i ) ( a 1 ) ( a , 2 ) # 图2 6 互关联后继树不例 针对这种索引，如果用户输入查询字符串“b a c ”，还无法直接查 找，检索系统要经过一个匹配的过程。匹配从查询串的第一个字符开 始，在b 为根的树的分支中查找后继为“a ”的分支，发现有两个 分支满足条件，再根据这两个分支的序号，跳转到a 树的l ，2 分支查 看其后继是否为c ，发现第二个分支的内容为“c ”，则“b a c ”在文档 中仅有一个匹配。 ( 6 ) 几种全文检索模型分析比较 下面对上述模型按照评价标准进行分析，由于位图和署名文件使 用较少，将不对其进行讨论。 时间复杂度”l 查询时间复杂度和具体的查询有关。对于全文检索来说，最常用 的查询是字符串匹配，这里就以这类查询的时间复杂度来进行比较。 设查询字符串p 的长度为m ，索引库中文档大小为n 。倒排表的检索 效率与其存储结构有关。通常，可以按照数组、b + 树、散列函数等方 式来实现倒排表，那么查找索引项时需要的比较次数前两者为 o ( 1 0 9 n ) ，而后者为o ( i ) 。如果查询串是单个的关键词，可以直接得出 该索引项所在的文档：如果查询词组或句子，则需要对所有查询关键 词位置信息进行分析合并，因而效率较低，分析处理所需时间与索引 库中关键词的匹配个数有关。p a t 树中查询需要比较m 次以确定p 在 树中的位置，其时间复杂度为o ( m ) 。由于p a t 数组实际上是文档中 1 6 中国j i 油夫学( 华尔) 硕七论文第2 章全文检索模犁综述 半无限串的词典排序，查询时间复杂度为o ( m + i o g n ) 。 2 邻接矩阵模型将p 分解为m 1 个相邻字符对分别进行查询， 需要时间o ( m 1 ) ，而后需要合并查询结果。在互关联后继树模型中 查询p 需要遍历所有与p 具有相同前缀的字符串，直到该字符串与查 询串不符合或者完全相符。设p = a l ，a 2 ，a n ，在索引库中a l 出现f t 次； a 2 出现f 2 次；a n 出现f n 次， 则算法需读取磁盘厂= ，次。若 ，i l 所有与p 具有相同前缀的字符串的平均长度为r ，则算法时间复杂度 为o ( r f ) 。此模型的检索效率高于倒排表模型。 空间复杂度 假设原文档大小为n ，倒排表和p a t 数组基本上都是对文档中的 每个字符存储一定位置信息，索引约占空间n ，则膨胀比为2 。p a t 树 需要存储大量的中间节点，占用空间较大，为4 n 5 n ，膨胀比为5 6 。倒排表和p a t 树模型出现较早，对其研究也更加广泛，产生了许多 压缩算法。虽然解压缩对查询的时间影响很大，但是由于这两种模型 的压缩比很高，且索引减小将引起磁盘交换的减少，从而节约的查询 时间实际上比解压缩要消耗的时间更多。倒排表模型在压缩以后膨胀 比仅为1 0 6 1 1 ，p a t 树则仍需要2 。 对于2 邻接矩阵模型来说，基本上也是为每个字符建立一个索 引，索引存储空间为n 。互关联后继树模型为每个字符存储一个后继 和一个位置信息，则索引空间小于2 n 。由于2 邻接矩阵模型和互关 联后继树模型能够还原原文，无需保留原文档，所以2 邻接矩阵的膨 胀比是l ，互关联后继树模型的膨胀比小于2 。 查询完备性 倒排表模型只能够存储具有文档一索引项结构的数据，按照索引 1 7 中国石油大学( 华东) 硕士论文第2 章全文检索模掣综述 项的不同，有三种形式的倒排表：按字倒排、按词倒排和按关键词( 在 按词倒排的基础上去掉停用词) 倒排。基于字或词的倒排表保留了文 档中所有词的位置信息，可以查询任意字符串；而基于关键词的倒排 表只能查询关键词，若杏询长字符串，需要先将该字符串分解为多个 关键词，分别查询后，合并查询结果。用数组、b + 树存储的倒排表实 际上反映了索引项的词典顺序，所以也可以进行前缀查询和范围查 询。同样，由于记录了索引项在文档中的位置信息，还可以进行i 临近 查询。但是不能够进行最频繁匹配查询和最长重复查询，这是因为通 常这两种查询的结果都不限于一个索引项。p a t 数组、p a t 树的查询功 能十分强大，都可以实现评价标准中的所有查询。当然，在实现最大 重复查询的时候需要增加一定的辅助信息。 2 邻接矩阵模型把文档切成无环句串，实际上把所有查询都限制 在无环句串之内，因而查询功能受到很大的影响。互关联后继树模型 和p a t 树一样能够实现所有的查询。 适应性 倒排表的结构导致其仅仅能处理有文档索引项结构的数据；p a t 树和p a t 数组将处理数掘看成半无限串的叠加，所以不需要索引数据 有任何结构。而2 邻接矩阵模型和互关联后继树模型处理的数据既可 以看作像倒排表一样具有文档索引项结构，又可以像p a t 树一样是无 结构的字符串。因而适用能力最强。 动态性 利用b + 树存储的倒排表能够实现动念操作，但是膨胀比会增大为 1 1 4 1 1 5 。在p a t 树或者p a t 数组中能够实现数据的动态改变，但代 价非常高，这是因为若原数据为u v w ，将其改变为u z w 后( u v w z 均为字符串) ，w 中半无限串的序号也将改变，所以整棵树将做很大 i r 中国f i 油大学f 华东) 硕十论文第2 章全文检索模型综述 的变动。邻接矩阵模型和互关联后继树模型的动态性能也是很脆弱 的。 表2 i 几种全文索引模型的性能比较 倒排表p a t 数组p a t 树 互关联后继捌 查询时间 o ( 1 0 9 n ) + o ( m i + 复杂度合并时间 0 r m + i o g n )o ( m ) 合并时 o f r 0 间 膨胀比 ( 压缩 225 - - 6l电 前) 查询完备 不完备较完备完备不完备完备 性 适应性 弱 由由 强强 动态性强弱弱弱弱 对原文依 生成原文生成原文 生成原 文、查询不依赖 不依赖 赖程度 依赖查询依赖 依赖 1 9 中国石油大学( 华东) 硕十论文第3 章互关联后继树模掣的原珲及操作算法 第3 章互关联后继树模型的原理及操作算法 3 1 模型简介 设是构成文本的基本符号单元的集合，a i ，a 2 ，a - ，a i e ( i = l ，2 ，n ) 是中的一些基本符号，它们的有序组合便可构成一个文 本。我们在每个文本t 的最后人为添加一个不在中的符号，以表示该 文本的结束这个符号称为文本结束符，一般用a s c i i 为0 的字符表示， 为了阅读方便，常使用“# ”。通常把加入某一个索引库的所有文本 的集合叫做该索引库对应的全文。如果一个全文只包含一个文本，那 么这个全文就是一个单文本全文，如果一个全文包含两个或者两个以 上的文本，那么这个全文是一个多文本全文。 定义3 1 前驱和后继 对任意文本t 中的任意字符串a