（计算机软件与理论专业论文）一种基于潜语义标引的全文检索系统的研究与实现.pdf

摘要： 随着计算机利网络技术的迅猛发展，l b 子信息量越米越巨人，a t i j 对信息检索技术的要求也越来 越高。要从一个海鼙文档集中查找与州户查询相关的文档，集，州户已经不满足于简单的基于词语匹 配的榆索技术应该从语义角度米对文档进行检索，发拥词语之间的语义关系，从而提高检索的准确 率 l i 召同率。 本文彳l ：总结现订方法的基础上，讨论并简单实现了一个基丁潜语义标引技术( l s i ) 的全文信息椅 索系统。本系统试蚓利_ l l j 滞语义标引技术，从文档r ，词语的使刚模式来发掘文档的潜在语义结构，在 文档与查j = f l i 向餐组成的空间中计算它们之间的相关性，剪根据初娟查询结果选择一个相关反馈文档对 查询进行拶充，以获得更好的性能。初步测试结果表明，本系统在一定稗度上实现了语义角度的责询。 本文将从全文检索的基础出发，首先介绍检索技术的发展及全文检索的特点，然后对目前几种主 要的检索模型进彳了介绍和比较，其中包括布尔模型、向量空间模型以及概率模型，其后着重对l s i 技 术及作为其基础的向鼍空间模型进行详细介耋什，最后介绍基于l s i 技术的中文全文检索系统的设计与 实现。 关键词：潜语义标引，全文检索，奇异值分解，相关反馈，向量空间 a b s t r a c t ： a l o n gw i t h t h e d e v e l o p m e n to fc o m p u t e rs c i e n c e a n dn e t w o r k t e c l m o l o g y , e l e c t r o n i c i n f o n n a t i o n b e c o m e sm o r ea n dm o r ea b u n d a n t a st i l ea m o u n to fe l e c t r o n i ci n f o m l a t i o ni n c r e a s e s ，t h ed e m a u dt o i n f o r m a t i o nr e t r i e v a la l s oi n c r e a s e sd a yb yd a y , t or e t r i e v er e l a t i v ed o c u m e n ts u b s e t st ou s e r s q u e r yr e q u e s t i n l a r g e s c a l e ，h e t e r o g e n e o u s d o c u m e n tc o l l e c t i o n s ，t r a d i t i o n a ll e x i c a l ( o rb o o l e a n ) i n f o m r a t i o nr e t r i e v a l t e c h n i q u e sw i l lb e c o m e l e s su s e f u la n dn o tm e e tu s e r s d e m a n da n ym o r e t h u s ，w es h o u l dc o n s i d e rc a r r y i n g d o c u m e n tr e t r i e v a li nt h es e m a n t i cs e n s e ，d i g g i n gn pt h es e m a u t i cr e l a t i o n s h i pb e t w e e nt e r m s ，s ot h a tt h e a c c u r a t er a t ea n dr e c a l lr a t ec a nb ei n c r e a s e d b a s e do i l s u m m a r i z i n g t h e e x i s t i n gt e c h n o l o g y , t h i sp a p e r i s m a i n l y a b o u tt h er e s e a r c ha n d i m p l e m e n t a t i o no f al a t e n ts e m a n t i ci n d e x i n g b a s e df u l l t e x tr e t r i e v a ls y s t e m t i f f ss y s t e ma t t e m p t st ou s e i s i t e c l m o l o g yt od i gt h el a t e n ts e m a n t i cs t r u c t u r e so fd o c u m e n t sf r o mu s a g ep a t t e mo ft e r m si nt h o s e d o c u m e n t s ，a n dt h e nc o m p u t e t h er e l a t i v es i m i l a r i t yb e t w e e nd o c u m e n t sa n d q u e r yr e q u e s t i nt h ev e c t o rs p a c e c o m p o s e do fd o c u m e n ta n dq u e r yv e c t o r s ，a n du s et h et e r m sc o n t a i n e di nt h er e l e v a n td o c u m e n tc h o s e nt o s u p p l e m e n t a n de n r i c ht h eu s e r si n i t i a l k e y w o r dq u e r y , a l l o w i n gg r e a t e r r e t r i e v a l p e r f o r m a n c e t h e e l e m e n t a r ye x p e r i m e n t a lr e s u l t ss h o wt h a t ，t h i ss y s t e mh a si m p l e m e n t e ds e m a n t i ci n f o r m a t i o nr e t r i e v a li na c e r t a i ne x t e n t t i f f s p a p e rs t a r t s w i t ht h ep r i m a r yk n o w l e d g eo ff u l l - t e x ti n f o r m a t i o nr e t r i e v a lt e c h n o l o g y a f t e rt h e d i s c u s s i o no ft h ed e v e l o p m e n to ft h er e t r i e v a lt e c t m o l o g ya n dt h ef e a t u r e so ff u l l t e x ti n f o r m a t i o n r e t r i e v a l ， t h ep a p e rp r e s e n t ss o m ep o p u l a rk i n d so fi n f o r m a t i o nr e t r i e v a lm o d e l sn o w a d a y sa n dm a k e sac o m p a r i s o n a m o n gt h e m ，i n c l u d i n g b o o l e a n l o g i c a lm o d e l ，v e c t o rs p a c em o d e la n d p r o b a b i l i t yr e t r i e v a lm o d e l t h e nt h i s p a p e r f o c u s e so l lt h el s i t e c h n o l o g ya n dv e c t o rs p a c em o d e lt h a ti si t sb a s i s a tl a s t ，t h i sp a p e ri n t r o d u c e st h e d e s i g na n di m p l e m e n t a t i o no f o u r l s i - b a s e df u l l t e x tr e t r i e v a ls y s t e m k e y w o r d ：l a t e n ts e m a n t i ci n d e x i n g ( l s i ) ，f u i l - t e x ti n f o r m a t i o n r e t r i e v a l ，s i n g u l a rv a l u ed e c o m p o s i t i o n r e l a t i v ef e e d b a c k ，v e c t o rs p a c e _一一一 绪鲁 绪言 随着i n t e m e t 的e 速发展以及各种【乜f 信息资源的迅猛增加，检索技术也随着人们的需要得到了极 人发胜，经历了从传统的基1 ：词语的检索到f 然语青检索的发展历程。面对日益膨胀的电子信息总耸， 传统的依据土题词表人： 标引的检索方法显然已经力不从心。首先，人i ：标引的工作量相当庞大，般 部fj 洲i 以承受这样沉重的负担，而且人l 标引要受到标引政策的制约和标引人员意识的影响，检索川户 面对检索系统所得到的实际上是标引人员对文档所作的描述结果，而非文档本身容易导致检索结果与 川户要求山现偏离。 传统的向量空间模型采川自动标引技术为文档提供标引词，并认为这些标引词相互独立，文档和奇 嘟请求在模型中被肴作是m 维向最空间。 f f 疗一个向域，1 2 1 为标引作业中使刚的标引词的数姑，通过计 算查询睛求与文档向量之间的相似程度来实现检索。 向餐字间模型的主要缺点是无法分辨自然语言的语义模糊性。在该模型中，文档自动标引是通过词 频分析来实现的。系统根据词频分析自动选定标引词，将标引词从原文中抽出，根据其在文档中出现的 频率分布赋予权值。在此过程中所考虑的仅仅是孤立的标引词本身，所有其它的语言成分并没有被利用， 然而自然语言词汇具有多义- 性和歧义性，语义的准确表达不仅取决于对词汇的恰当选择和应埘，而且也 取决丁上f 文对词义的限定。如果没有上f 文的语境而仅依赖于孤立的标引词来表示文档内容，并据此 预测文档与查洵请求的相关度，势必会发生许多错误，导致许多非相关文献被命中，难于满足j j 户的要 求。 为了提高检索的质量，就要考虑到上f n ：的语义关联，独立的关键词不可能表述这种关系，冈此， 基于非关键词匹配的文献自动标引技术越来越多地受到关注，本文着重介绍了l s i ( l a t e n tg e m a n t i c i n d e x i n g 潜语义标引) 技术，以及使用该技术进行中文文档全文检索的一个简单系统的设计与实现。由 于标引词之间具有语义关联，它们在文档中的出现频率之间也具有某些联系标引词的使用模式形成了 潜在的语义结构。l s i 用统计方法来捕捉量化了这种关系。 目前这种技术已经在很多领域开始使用，例如信息检索、文档分类、模式识别等。在检索方面，主 要是用于一些两文文档的检索，在中文文档检索方面的实现比较少，主要是因为汉语的一些特性，因此， 本文就试图使用这一技术对中文全文检索进行一定程度的实现，希望可以在一定程度上从文档的语义角 度获得检索结果，从而更加符合用户的需求。 塑二：里鱼堕垦塑塑鉴 第一章全文信息检索概述 随着i n t e m e t 及其相关技术的发展与成熟，在网上检索信息已经成为当今以至未来社会人们获取信 息的重要手段。各种电子信息止在不断地积累，有效、快速、准确地从信息海洋中找到我”j 所需要的信 息，已成为信息时代人们的重要需求。冈此，信息检索技术在信息社会中将发挥越来越重的作h j 。 莉：信息检索领域，英文信息检索发展迅速而且完善，而中文信息检索的发展则相对较慢，原因主要 是中文信息检索自身的特点，它需要语言学、人t i 智能、信息技术与计算机技术等领域共同协作研究。 许多技术还有待于探索解决，要实现完全意义上的全文检索，还需要我们做出不懈的努力。 1 1 计算机检索技术的回顾 通过计算机进行的文献信息检索称为计算机榆索。计算机检索包括光盘数据库、网络数据库检索和 互联网信息检索。由丁计算机检索具有速度快、效率高，数据内容新、范围广、数量人，操作简便，检 索时不受国家和地理位置的限制等特点，冈此它已成为人们获取信息的主要手段之一。 计算机检索是在计算机技术羽i 通信技术发展的基础上建立起来的。它产生于2 0 世纪5 0 年代，发展 于8 0 年代中期，9 0 年代后随着国际互联网技术的发展而进入了一个崭新的时期。回顾计算机文献检索 的发展历程大致可以概括为批量处理、联机检索与网络系统三个阶段。 1 9 5 4 年，美国海军武器实验站图书馆在一台电子管计算机上建立了世界上第一个计算机检索系统。 5 0 年代末，i b m 公司利用台i b m 6 5 0i ：t 1 算机成功地编制出关键词索引，并建立了世界上第一个“定 题情报检索”( s d i ，s e l e c t i v ed i s s e m i n a t i o no f i n f o r m a t i o n ) 系统，为用户定期检索和提供一定主题的新 到文献( 脱机检索，批量处理) ，并很快得到了推广应刚。 进入6 0 年代，计算机检索进入了实_ 【_ j 和全面发展阶段。6 0 年代末，数据通讯网络出现，大容量计 算机分时系统和强功能检索软件研制成功，使脱机检索发展到联机检索井迅速得到了推，。7 0 8 0 年代， 联机检索得到迅速发展，一些联机检索系统开始向公众提供商业性服务，如d i a l o g 、e s a 、o r b i t 、 b r s 等许多世界著名的联机检索系统相继投入商业性运营。 9 0 年代联机检索的发展进入了一个重要的转折时期，随着互联网的迅速发展及超文本技术的山现， 以及基于客户服务器的检索软件的开发，实现了将原来的主机系统转移到服务器上，使客户朋务器联 机检索模式开始取代以往的终端主机结构，成为联机检索的发展趋势，使联机检索进入了又一个崭新 的时期。 计算机技术的不断进步用i 信息量成倍地增加，使人们对信息检索技术的要求也越来越高，尤其是网 2 第一章全文信息检索概述 络技术和多媒体技术的山现，促使信息检索技术也不断地发展。目前，信息检索技术正向两个方向发展： 一是传统信息检索向全文文本、多媒体、多载体、多原理等新型信息检索的发展，在深度上提高管理和 组织信息的能力，如探索自动分词、自动索引、l 动检索、自动文摘、自动分类、自动翻译等；二是信 息资源的网络化和分布化，面向i n t e r n e t 中浩瀚无垠的资源，在“度上提高管理和组织信息的能力。在 信息检索技术研究领域中，基丁概念、超文本信息和多媒体信息检索技术的研究最为活跃，爿：已取得了 突破性发展。网络的发展给信息的获取提供了厂阔的空间，而检索技术的发展为人们利用信息提供更方 便陕捷的手段。 1 2 全文检索的概念与特点 全文检索，简而言之，就是以各类数据诸如文字、声音、图像等为处理对象，提供按照数据资料的 内容而不是外在特征来实现的信息检索手段。它能提供快捷的数据管理工具和强大的数据查询手段，通 过快捷的数据管理i i 具，能快速帮助人们进行大量文档资料的整理和管理工作，强大的数据查询手段， 使人”j 能快速方便地查到他们想要的任何信息。 全文信息检索主要研究对整个文档信息的表示、存储、组织和访问，即根据用户的查询要求，从信 息数据库中检索山相关信息资料。检索系统的中心环1 ，是文件内容表达、信息查询的获得以及相关信息 的匹配。一个好的全文信息检索系统不仅要求将输山信息进行相关性排列，还应该能够根据_ _ l 户的意图、 兴趣及特点白适席和智能化地调整匹配机制，获得_ l j 户满意的检索输出。 与传统的检索相比，全文检索有许多特点： 1 ) 直接性。提供存取全文文本的空间，能直接检查原始文献或解决问题所需要的文献资料，不必 进行二次检索。全文检索得到的是全文文本，而不是文献的摘要或替代品。 2 ) 详尽性。文献的正文部分或附属部分都可以检索和显示。 3 ) 方便灵活性。文本中任何字符或字符串都可以作为检索的入口点，用户可赢接查询文本中的任 何成分或特定单元。 4 ) 广泛适用性。能处理结构化和非结构化的各类文本数据。能够采集各种来源文件，这些来源可 能是跨越r 泛地理分布的，也可以是不同介质、不同格式产生的文本整理转换成标准形式，实 现全文检索。 5 ) 后处理能力。具有对检索出的文本进行处理的能力，并且以用户乐于接受的形式提供检索并加 1 二处理文本，使检索系统功能得到了延伸。 6 ) 用户友好性。易学易用，界面友好，检索方法接近自然语言。 7 ) 易丁自动化。分词、标引易在计算机上实现。 1 嚣一章夸文信息愉索概述 1 , 3 全文检索系统结构 典z 科的全文信息榆索系统分为三个模块：信息预处理模块、商啕模块以及查询反馈模块等。各模块 间的基本结i i = ：7 l l l , f n a 关系如r 图所示： 1 3 1 信息预处理模块 图11 信息检索系统基本结构 信息预处理的主要功能是过滤文件系统信息，为文件系统的表达提供一种满意的索引输出。对于 中英文来说，虽然过滤的方法和步骤不尽相同，但是它wj 的基本目的都是为了获得最优的索引记录，使 用户能很容易地检索到所需信息。其主要功能为：词语切分、词法分析及词性标注和短语识别。 西文的书面语言，单词与单词之间以空格分隔，计算机识别单词很简单；而中文的书面语言，词 与词之间没有任何区分标志，这就使得计算机识别汉语词非常困难。因此，中文全文检索的关键技术之 一是汉语切分问题。常h j 的语词切分方法有按词典进行最大词组匹配、逆向最大词组匹配、最佳匹配法、 联想同溯法、全自动词典分词等。近年来，义出现了基于神经元网络和专家系统的分词方法以及基于 统计利频度分析的分词方法。汉语语词切分中存在切分歧义，如句子“乒乓球拍卖完了”，可以切分为 “乒乓球拍卖完了”也可以切分为“乒乓球拍卖完了”。因此需要利用各种上下文知识解决语词切分 歧义。此外，还需要对语词进行词法分析，识别出各个语词的词干，以便根据词干建立信息索引。在切 d 第一章全文信息检索概述 分的基础t - ，利川基丁规则和统计的方法进行词性标注，还要利j h 备种语法规则，识圳出重要的短语结 构。 1 3 2 查询模块 查询模块是信息检索服务系统的z i z , 环仃。它包括文件信息表达和查询信息表达以及相关信息预 测过科。 信息的表逃有多种方式，如币f 尔表达、向鼙空间表达、门然语言表达等，每种表达方式由鹿川服 务者提供井由整个应川系统的目的雨l 需求决定，并对应r 相应的存储模式和检索算法。信息查询和组纵 的效率，也就是速度和存储空间在很人程度j i 决定了检索服务系统的性能。 1 3 3 查询反馈模块 信息检索中的查洵反馈方法通过川户和已检索文件的交互结果米修止原始查啕，从而达到提商检 索性能的目的。也就是说，用户从专玎次查嘲的结果中，选择内容重要的文档或文档片断，反馈模块根据 这些所选文档的特征，在原始查询基础上增添新的裔淘词语并且重新决定查询词的权重。 反馈网络属。r 人机交互范畴，目的在 j 提高查淘性能和针对性。不同的用户根据实际情况提供不 同的反馈信息，不同的信息检索服务系统按j ! i 【其功能与检索方法也有不同的反馈结构和交互方式，因此 查向结果也不尽相同。 1 , 4 全文检索技术的发展 山丁全文检索技术集中在自由词检索上，从而避开了耗费人力与工时的标引1 ：作，闲此成本大大 下降，用户面也大人扩宽。但是，它对用户或操作者检索经验和领域知识的要求较高，所以，全文检索 系统应在基于自南词榆索技术的基础上，发展各种辅助检索方法与技术，不断地运用新方法，新技术， 推动全文检索技术的发展。 信息检索的新分支一一智能化信息检索是人丁智能和信息检索的交叉学科。目的是使信息检索系 统“理解”用户的信息需要和文件包含的信息内容。它在对内容的分析理解、内容表达、知识学习等基 础上实现检索的智能化。人多数的智能检索模型包括：文件和查洵知识的表达、比较预测机制、相关性 查询结果反馈处理等。 人一【= 智能和信息检索的结合主要包括三方面： 1 ) 信息检索和专家系统。专家系统是在某领域具有专家水平解题能力的程序系统。信息检索中的 号家系统主要研究方向是开发一个专家中介系统来协助裔询形成、搜索策略选抒以及预测检索文 第一帝争立信息检索概述 什。 2 ) 信息检索和c l 然语言处理。自然语言是文件系统和查询表达确认过程中的关键部分。为了有效 地运川自然语言处理，需要有一个甚至比专家系统的运_ l 】仍大得多的领域知识系统。 3 ) 信息检索和知识表达。此领域的研究主要是通过应j = | ；j 领域知识来理解文件和查询的信息内容。 知识的表达处理基于一种自处理机制，即知识处理系统进行自我处理，通过大最的处理节点及其 相互联系之间的交互达到一种智能行为。 第一章几种芏婴信息枪索模型鹄础究j 比较 一 第二章几种主要信息检索模型的研究与比较 为了高效地对各种信恩进行有效检索，人们在理论和实际应州领域进行了不懈的努力，相继提出了 得种信息检索系统模型，相应的不同系统的检索算法也应运面生了。 各种数据信息的检索方法基本都是使川一些简单的概念来检索大规模的信息体。一次检索由川户提 供韵一个查询请求构成，查询请求是描述川户所要寻找信息的字符串，查询请求中的每一个单词都称为 检索词，侮洵请求可以是单个检索词、词组、一个 j 然语言短语、或一个_ l ；| 特殊符号表示的表选式。简 单说爿，信息检索就是将川户的检索需求进行分析，通过提问和逻辑组配，构成检索策略输入计算机， | 计算机将提问标识与索引文件匹配，然历将符台检糍条什的文献输【出。 应该说在i n t e r n e t 应用之前，就已经存在了布尔逻辑的信息检索技术，随着计算机理论和计算机硬 什技术的不断发展进步，器种不同的信息榆索技术也在基本的布尔逻辑方法的基础上得到了氏足的发 展。根据商找相关信息的不同方式，可以将计算机信息检索模型分为：布尔逻辑模型，向量空间模型， 以及概率模型等等。 通过对不同的数据环境的研究测试表明各种不同的检索模型都有其自身的长处和不足。在查询某 娄文档时，使瑚一种检索模型比较快，而检索另一类文档时，可能使用另一种检索模型会更快。因此， 在一个综合性的检索系统中，应该融合多种检索模型，才有可能人大提高系统的整体检索敛率。 2 1 布尔逻辑检索模型( b o o l e a nr e t r i e v a lm o d e l ) 2 1 1 布尔逻辑 布尔逻辑是一种符号逻辑系统，由法国数学家g e o r g eb o o l 发明。在1 8 d 9 年，g e o r g eb o o l 在一篇 名为“思想规律的调查研究”的论文中将一系列规则正式化，该规则将哲学定律中的正式逻辑转化为数 学逻辑。这些规则作为布尔代数而知名，使用操作符( a n d 、o r 、n o t 和w i t h ) 在字词和概念之间 创建关系。布尔代数中定义的逻辑操作符使现代二进制数字计算机成为可能。 布尔逻辑是数理逻辑的基本部分之一一，应片j 丁| 计算机信息检索的布尔逻辑运算符有三种： 1 ) 逻辑利。逻辑和也称逻辑加、逻辑或，其运算结果是使概念范围扩大，它表示两个或两个以上 可能相交也可能不相交的概念及并列关系概念的运算，其符号为“+ u o r ”，含义为或是a 或是 b ，满足两者条件之一即可。图示如l 、： 第：市几种主要信息检索模型的研究l j 比较 2 ) 逻辑积n 逻辑积义称为逻辑乘、逻辑与，其运算结果烛使概念范周缩小。主要_ ： j r 概念具有交 叉关系、限定关系的两个缄两个以上主题词之间的运算。其符号为”a n d ”n ”，含义为既 是a 又是b ，必须属丁检索词a 的文档集台与满足检索词b 的文档集合的相交部分。图示如下： 3 ) 逻辑差。逻辑差又称逻辑非，其运算结果也是使概念范同缩小。是指两个具有从属关系( 上f 位类关系) 主题词的运算。其符号为“一n o t t ”，含义为要满足检索词a 的条件，同时又要排 除满足b 条件的部分，图示如下： 布尔逻辑运算符具有优先级它就好像数学四则运算的“先乘除后加减”一样，它的优先级从商到 低依次排列为：n o t 、a n d 、o r ，括号最优先( 以改变运算的优先级) 。 2 1 2 布尔逻辑运算 布尔运算的原理 首先对检索系统中逻辑运算的过程予以说明。布尔检索系统中，查询请求是一个布尔表达式，即由 布尔逻辑运算符o r 、a n d 和n o t 联结的谓词组成的表达式。只有布尔表达式为真的文档才能被检索 出来。 在计算机检索系统中，实现关键词的组配运算必须先建立起关键词数据库，它至少应包含两个字段， 即荚键词和记录指针，其中记录指针( 倒排表) 是用来与文档数据库相连接的而逻辑运算是通过对记 录指针的比较来完成的。逻辑运算的结果存放在一个目标文件中，该文件最基本的宇段为记录指针，通 过该指针与文档库相连得到检索结果关键词数据库、文档数据库以及目标文件之间的关系如表2 1 所 8 旃_ 二带几种主要情息检索模型的研究与比较 表2 1 关键词数据库、文档数据库以及目标文件关系表 关键词指针 指针题名 计算机 2 ，。x 1 2 3 计算机 3 八 1 0 图书馆 1 0 图书馆 2 图书馆 3 表2 2 给出了三种运算的实现过程、所_ l ；| 的运算次数以及结果数量( 满足条什的记录数) 等。 表2 2 逻辑运算的过程及结果 标题实现过程操作次数结果数量 a + b 将关键词为a 的所有n a + n b + ( n b - n a + b ) n a + n b - n a * b 记录送到目标文件第一个n b 为查找 中，而对关键词为b 的每条记录，首先查 找其指针是否在目标 文件中出现，如果来 山现则将该记录指针 添加到目标文件中， 否则进行f 一条记录 a + b 找出a 与b 中记录较 r a i n ( n a ，n b ) + n a + b n a * b 少的一个，查找其每 m i n 0 项为查找 一条记录的指针是否 在b 中出现，如果出 现则送入目标文件， 否则进行下一条记录 a b检查a 中的每一个记 n a + ( n a - n a + b ) n a - n a * b 录的指针是否在b 中 第一个h a 为查找 山现，如果未出现就 送入目标文件中，否 则进行下一条记录 注：( 1 ) n a 为检索词为a 的记录个数，n b 为检索词为b 的记录个数，n a * b 为检索词a 和检索词b 互i ；一章几种主要信息榆索模型的研究与比较 具有相同指针的记录个数，即两者交集的记录个数，其他以此类推：m i n ( n a , n b ) 是取n a 和n b 的虽小 值。 ( 2 ) 操作次数是写入操作与检索操作的总数。例如：a + b 运算次数是先做n a 次插入运算，然后做 n b 次检索运算，并日再做n b - n a * b 次插入运算，最终得山的运算次数是n a + 2 n b n a * b 。 传统的布尔逻辑二叉树算法 传统算法是先将表达式形成一个二义树，再通过厉序遍历二义树来得到后缀表达式。例如，检索表 达式“( a + b ) + c ”，其二叉树如图2 1 所示。 c a b 经后序遍历得到的后缀表达式为“a b + c ”根据此表达式，计算机首先计算“a + b ”，其结果保 存在一个临删文件中，中间结果再与c 做“t ”运算，将最后结果扶临时文件转移到目标文件中，根据 表2 1 可得操作次数： n a + n b + ( n b n a + b ) + m i n ( n a + n b - n a 4 b ，n c ) 十( n a + c + n b + c - n a + b + c ) 其中：( i ) m i n 0 项希i 第一个n b 项均为查找操作，其余为写操作。 这种过程中有个明显的缺陷，就是当先做“或”运算后做“与非运算时，其临时文件可能变 得很庞大。根据表2 2 其临时文件记录数为n a + n b n a * b 条，如果i 临时文件很大，就不可能全部放入内 存，只能保存丁硬盘。而硬盘的读写速度远远低于内存的渎写速度，所以如果不减少临时文件记录数， 无论怎样改进算法也难以提高其检索效率。 改进二叉树算法 改进算法的核心是对检索表达式形成的二叉树进行改造，将优先级高的算符下移，所形成的新二叉 树都是优先级低的算符在上面，而优先级高的算符在下面，于是就能使其先算与月p ，后做“或”运 算，这样，既可略去中间结果又大大减少了逻辑运算次数，使逻辑运算尽可能在内存中实现，进而达到 提商检索效率的目的。 r 面仍以检索表达式“( a + b ) ，c ”为例，说明改进算法的实现过程。 改造二叉树 首先对原二叉树图2 i 进彳亍先序遍历，当发现父结点算符( ) 优先级高于子结点( 非叫结点) 算符( “+ ”) 时，做以下操作： ( 1 ) 子结点算符( “+ ”) 代替父结点算符( ”) ，原父结点算符( ”) 代替两个子结点。 1 0 鹅_ 二章几种主要信息检索模型的研究与比较 酬2 2 一义树 ( 2 ) 若原子结点算符( “+ ”) 为原父结点算符( “”) 的左子树，则原子结点的左子树( “a ”) 作 为新予结点( “”) 的左子树，而原子结点的右子树( “b ”) 作为新子结点( “”) 兄弟结点( “”) 的 庄子树；原父结点( “”) 的矗子树( “c ”) 作为两个新子结点( “”) 的右子树，如图2 3 所示。 + a cb c 图23 改造后的二义树 若原子结点算符为原父结点算符的右子树，则原子结点的右子树作为新子结点的右子树，原子结点 的左子树作为新子结点兄弟结点的右子树；原父结点的左子树作为两个新子结点的左子树。 ( 3 ) 继续先序遍历，当发现父结点算符优先级高于子结点( 非叶结点) 优先级时，重复执行( i ) 、 ( 2 ) 、( 3 ) ，直到其没有父结点优先级高于子结点优先级为t l ：。 丁是，新二叉树经后序遍历得到新的后缀表达式为“a c * b c * + ”，即“”往前而“+ ”在后。 生成逻辑表达式堆栈 首先开辟一个一维数组作为堆栈，逐一输入后缀表达式，遇到算子就进栈，遇到算符需要判断，如 果算符为“”，则将栈顶与次栈项的算子弹山，把形成的逻辑“与”表达式当作运算结果进栈；如果算 符为“一”，则将栈项的算子弹出，把形成的逻辑“：i p 表达式当作运算结果进栈；如果算符为“+ ”，则 舍弃。这样最后栈中所有的元素都是只含“+ ”或“”的逻辑表达式。生成后缀表达式“a c * b c * + ， 的逻辑表达式堆栈的过程如图2 4 所示。 图2 4 生成逻辑表达式堆栈过程 逻辑运算 栈中所有元素都是逻辑“与月e ”表达式，而栈中各元素之间都是逻辑“或关系。首先对于栈中 每个元素分别进行运算，“与非”运算的过程是开辟一个一维数组存放每一个关键词，找出关键词中记 录数量少的一个作为查找键，根据其指针对另一关键词在关键词库中进行查找，对于“与，运算，若找 1 1 第二章几种主要信息检索模型的i i j 究与比较 钊则将记录指针送入目标文什中，西则进行下一条记录：对于“非”运算，若未找到则将记录指针送入 日标文件中，否则进行卜一条记录。如果不是第一部分表达式，在送入目标文件之前，首先要在目标文 什中奋找一f 该指针是否存在，如果该指针已经存在就不必再装入。在目标文件中查找指针这一过科完 成了栈中备元素之间的“城”运算。 对下榆索表达式“( a + b ) + c ”，改进算法为先算“b * c ”，结果写入目标文件，然后再做“a + c ”运 算，在把结果写入目标文件之前，首先要在目标文件中查找一f 该指针是否存在，如果该指针已经存在 就不必再装入，即同时完成了“b * c ”与“a s c ”之间的“+ ”运算。根据表2 2 可得操作次数： m i n ( n b ，n c ) + n b + c + m i n ( n a ，n c ) + n a + c + ( n a + c - n a + b + c ) 其中r a i n 0 项及第一个n a + c 项均为查找操作，其余为写操作。 此改进算法由丁没有中间结果，且减少了逻辑运算次数( 写操作次数) 。冈此可以人大提高检索效 率。 2 2 向量空间检索模型( v e c t o r - s p a c e r e t r i e v a lm o d e l ) 为了能够给 j 户提供更多更符合用户需求的返回结果，尤其是查询请求较长时，人们构建了一种不 要求文档和查询请求进行精确匹配，而是在杏询请求和文档之间定义某种衡量相似度的检索方法，即向 量空间检索模型。通过此种检索模型，可以根据文档和查询请求的相似程度对所有返阐结果进行排序， 从而使用户可以更方便地选择自己所需要的文档。 2 2 1向量空间检索原理 向量空间检索模型( v s m ) 是g e r a r ds a l t o n 在6 0 年代提出的，它与布尔信息检索模型不同引入 了线性代数的知识，用检索项的向量空间表示用户的检索要求和数据库文档信息，根据向量空间的相关 性，将检索结果排序，并对检索结果进行分类，为用户提供更加准确定位所需要的信息。 可以说向最空间检索模型是一种比较容易理解的检索模型，在许多信息检索软件中已得到了j 泛的 实际应脂。 一个向量空间是由一组线性无关( 1 i n e a r l yi n d e p e n d e n t ) 的基本向量构成。这些向量满足以下条件： 向量维数与向量空间维数一致： 向量可以通过向量空间进行描述： 备向量之间是线性无关的或正交( o r t h o g o n a l ) 的。 1 2 第二章几种主要信息检索模型的研究j 比较 二维向量 三维向量 我们定义文档中可以被检索的一个词为一个术语( t e r m ) 则每个术语可以被此向量空间的一个线 性组合所表示。 t e r m 相关性无关性 c a t02 5 0 7 5 d o g 07 5 0 2 5 无 关 - 眭 文档向量可以被它自己包含的术语向量合成 d o c l 多个文档多个术语之间的几何关系如f a 相关性 无 关 性 d 0 c l 相关性 t e m 3 2 q u 唧 三 d 0 c l 筇一章几种主要信息检索模型的研弘j 比较 我们可以计算山文档集合中每个文档向鼙与查询请求向量的夹角。每个文档的测量结果一q 计算山 来，夹角越小，表明两者的相似度越高，那么此文档越符合刚户的要求，反之，则相似度越低。此时， 就可以把它们从最好的匹配到最坏的匹配进行排序。当然，我们还可以设立一个闽值当夹角犬于此闽 值时，将此文档过滤，这样就可以控制检索返同的文档数量，可以使_ l 户对检索结果更加一目y 然，同 时也加快了检索的速度。 本文所述系统中使用的l s i 技术是基于向量空间检索模型的一种技术，因此将在后面章节中对这一 模裂进行更详细的讨论。 2 3 概率检索模型( p r o b a b i l i s t i cr e t r i e v a lm o d e l ) 2 3 1 概率检索理论 概率检索理论( t h ep r o b a b i l i s t i cr e t r i e v a lm o d e l ) 是由s t e v er o b e r t s o n 和k a r e ns p a r c kj o n e s ( 英国 城市大学信息科学系) 在7 0 年代提出的，它是基于贝n | 斯概率论原理的，它利用相关反馈的归纳学习 方法，获取匹配函数。概率检索是建立在文献内容和h j 户之间相关程度的一种检索模型，这种相关程度 可以用概率论中的概率或概率分布来描述。 所谓相关性反馈就是基丁| 用户对初次检索得到的文档的反馈，对查询串进行修改，来提高一个查询 串的性能。特别是让用户对检索到的文档是否有用进行判断。以便在查询串中增加新的项，或者对查询 项重新评价其相关性。 在概率理论中，用户输入自然形态的、没有结构的词或者词组( 而不是布尔检索系统中的检索式) 提交给系统，系统将这些词或者词组与数据库中的文档进行匹配晟简单的一种概率设计是根据检索词 的匹配度对文档排序。例如，用户输入：a m e r i c a n a r t2 0 c e n t u r y ，检索结果如下表。 表2 3 概率检索实例表 匹配度例子文献 4 4 单词匹配 a m e r i c a na r ti nt h e 2 0 0 c e n t u r y 4 4 单词匹配 a m e r i c a nf o l ka r t ： 2 0 m c e n t u r yb l u e s 3 4 单词匹酉己a r ti nt h e2 0 “ c e n t u r y 1 4 第二章几种主要信息检索模型的研究与比较 2 4 单词匹配 2 0 “c e n t t l r y w o r l d h i s t o r y i 4 单词旺西己m o d e m a n 这种方法：1 1 ：常简单，但许多文档含有相同数量的匹配词或者词组时，此方法依旧不能区分文档的重 要性。给词赋予权重的概率设计方法，可以解决这个问题。其主要思想是对每一个检索词( 或者文档中 的每个检索词) 赋予权重，检索后计算所有文档中这些检索词的权重雨i ，f ：且按照权重和对文档进行排 序，这使得检索结果更为精确和完善。 对检索词赋予权重有三个参量： 文档集频率( c o l l e c t i o nf r e q u e n c y ) 。如果有两个检索词c 1 和c 2 ，假设其它条件相同如果c 1 在 很少文档中现，而c 2 在许多文档中出现，那么我们可以认为。c 1 具有更大的权重。这是冈为，越 不经常使_ _ j 的词，一般它的专指度就越高，对丁文档就越重要。 词频( t e n n f r e q u e n c y ) a 如果有两个检索词c l 和c 2 ，假设其它条件相同如果c 1 在一篇文档中 出现n 1 次，而c 2 在同一篇文档中出现n 2 次，如果n i n 2 ，那么我们可以认为，c 1 具有更大的权重。 这是因为，在同一篇文档中，词频越高，它对于这篇文章则更为重要。 文档长度( d o c u m e n t l e n g t h ) 。如果有两个检索词c 1 和c 2 ，假设其他条件相同，如果c 1 所在的 文档长度为l i t 而c 2 所在的文档k 度为l 2 ，如果l i l 2 ，那么我们可以认为，c 1 具有更大的权重。 这是因为，文档的长度越短其相对词频就越高它对于这篇文章则更为重要。 将以上每种加权方法组合起来，给每一个检索词一个分数，然后再将每个检索词的分数累加得出一 个总分数，从而确定检索的匹配程度。 2 3 2 汉字概率检索理论 概率检索理论是基于英文的，以单词为信息处理基本单位。对于汉字而言汉字概率检索理论的基 本单位是什么? 汉字的基本单位可以有单汉字、词两种选择。本节选择单汉字作为概率检索理论的基本 单位，主要是因为汉语语言单位综合结构的特性使用计算机难以界定个语言单位是语素、词还是词 组。所以选择词或者词组作为汉字概率检索理论的基本单位。计算机切分汉字句子成相应的词是一个比 较难以解决的问题，各种各样的切分方法，虽然有其理论基础和准确率，但离实用还有一段距离。因此 选择词作为概率检索理论的基本单位，在理论上阐述目前有很大难度。在实践中也无法予以实施，相反， 出丁计算机可以非常容易实现单汉字的分离，因此选择单汉字作为概率检索理论的基本单位，可以避开 汉字切分的难题。 在英语中，其) 骺态的变化为区别意义的主要囚索而形态的变化仍然是以单词为基础的：在汉语中： 1 5 第一帝几种主要信息榆索模型的研，与比较 语序足区别意义的主要冈素，而少形态的变化。对丁汉语斫育，单汉字与单汉字位置关系，与数龟关系 一样噩要。通过将位置关系作为概率计算n 勺方法既可以弥补单汉字方法没有切分的缺陷，同时也丰富 了概率检索理论。 从以上分析我们可以得山以f 结论：基于汉字的概率榆索理论( t h ec h i n e s ep r o b a b i l i s t i er e t r i e v a l m 。d e l ) ，其命中记录的概率计算方法，既赢该考虑单汉字数最关系，也考虑单汉字的位置关系，运与 基f 英语的概率检索理论有1 f 常大的4 j 同。传统的概率检索理论仅仅只是一个数量关系，它与语言本身 基本上是脱询的；而考虑单汉字的次序，则是与语言本身联系起来了，虽然这种联系是初步的，但却是 有理论意义和现实意义的。 2 4 三种检索模型的比较 虽然通过对传统的布尔逻辑检索算法进行改进，可以使得检索效率得到提高；但由于布尔逻辑本身 的限制，当检索的数据资料达到一定量时，布尔检索就不可避免地暴露出了其自身的不足： 布尔检索模型的输出数