（计算机软件与理论专业论文）无结构和半结构信息检索相关技术研究.pdf

摘要 摘要 信息检索( i n f o m a t i o nr e t r i e v a l ， i r ) 相关技术是当前最为活跃的研究领 域之一，它指的是对信息项进行表示、组织、存贮和查询。借助于计算机和网络 等信息技术，如今人们已经能够快速有效的检索到所需的大量信息，但是，随着 信息时代的发展，信息总量进一步增长，加勿农，照给宅彩崔钴稽标霍彰的倩垂，蓉 量上更霍前矽裁纠所雾要彩倩怠，这是摆在研究者面前的一个问题。 现代信息检索均以一定的模型或者索引机制作为基础。本文在信息检索模型 一互关联后继树一的基础上，提出了若干算法模型以期达到更好的检索性能，并 使之适用于一些新的应用领域。 本文前面部分总结了互关联后继树本身的模型和特点。为了进一步提高模型 的检索速度，本文提出在二元后继树的基础上提高排序程度，从而得到了双排序 后继树( d o u b l eo r d e rs u c c e s s i v et r e e ，d o s t ) 。然后本文进一步讨论了该模型 与p a t 数组结构的关系，从而进一步奠定了互关联后继树体系在信息检索方面的 理论基础。作为文本检索和x m l 检索的共同的基础，二元后继树模型对于支持 无结构和半结构化数掘检索意义重大。因此本文对围绕该模型的一系列问题进行 了进一步研究，本文讨论了分库合库算法，模型增量修改，压缩编码等算法问题 及相应措施。 近年来，以x m l 为代表的半结构化数据相关应用得到迅速发展。咖何利刀 半结构化数据中现有的结构信息优化检索以及如何进行半结构化数据中的全丈 信良逆行绣洽查苟，这是信息检索领域面临的新问题。本文讨论了将二元后继树 引入x m l 索引领域得到的半结构化信息检索模型一x i s t r e e 一的基本性质和相关 算法。文中在实现x i s t r e e 模型的基础上，首先与x i s s 进行了对比实验，然后与 有名的n a t i v ex m ld b 实用系统t i m b e r 和x i n d i c e 进行了对比实验。结果表明， 本系统在大数据集下，对于己知路径模式的简单查询和分支算法的性能都取得了 非常好的成果。 将文本等无结构化数据的检索转化为半结构化检索问题从而最终实现基于 语义的检索是当前研究者们努力的一个方向，因此基于概念语义的半结构化信息 检索受到人们的普遍关注的信息检索新领域。咖匆更霍功彩度量锣户雳求和数据 之闻的关系，更高放矽返回缮栗从而提高用户的拦孝举验，将成为未来的研究发 展进一步需要解决的问题。在本文中，主要针对半结构化数据中的概念检索问题， 提出了概念语义模型构建的基本思想以及概念语义相关度匹配算法思路以及如 何利用x m l 的结构信息进行s l c a 查询。与以往的s l c a 算法相比，本文所提 l v 摘要 出的算法在时间复杂度上有了较大提高。 概念相关性是信息检索的重要内容，为了自动发现概念相关性，需要借助概 念相关频繁项挖掘算法，因此本文还提出了在一种模式数据上挖掘的算法一自适 应的频繁项挖掘算法。本文首先提出了一种基于f p t r e e 的简单深度优先搜索算 法n d f s ，并简单分析了其在不同数据集上的特性；随后本文进一步将n d f s 和 经典的f p g r o 叭h 算法进行结合，提出了一种在挖掘过程中根据局部空间特征动 态采用不同策略的自适应算法( s e l f _ a d a p t i v ef p g r o w t l l ， s a f p ) 。 本文对我们所开发的x m l 原型系统和二元后继树模型在中国电信集团黄页 信息有限公司项目黄页信息检索中的应用进行了简单的介绍，并试图阐述如 何将前面几章讨论的文本索引技术和基于概念的语义索引方法结合起来，形成一 个综合了结构化、半结构化和无结构化数据的信息检索系统。最后本文对到目前 为止所做的工作进行了回顾，并提出了对未来进一步的工作的展望。 关键词：信息检索，文本检索，x m l ，互关联后继树，双排序后继树，概念检索 中图法分类号：t p 3 9 1 ；t p l 8 v a b s t r a c t a bs t r a c t i n f o 衄a t i o nr e t i i e v a l ( i r ) i so n eo ft h em o s th o tr e s e a r c ha r e a l si nc o m p u t e r s c i e n c e ，a n di t sm a i nr o l ei st or e p r e s e n t ，o 唱a n i z ea 1 1 ds t o r et h eu s e 向l i n f o r m a t i o n i t e m sf o rt h ea i mo fm t u r eq u e r y i n g b ya v a i lo fm o d e mc o m p u t e ra j l dn e t 、v o r k t e c h n o l o g i e s ，w ec a ne f j f i c i e n t l y r e t r i e v em u c hi n f b m l a t i o n b u ta l o n gw i t ht h e i n c r e a s i n go ft h et o t a ls u mo fi n f o 衄a t i o nm o r ea n dm o r er a p i d l y ，h o wt oe n f o r c e i n f o n a t i o nr e t r i e v a lu n d e rn e wc i r c 啪s t a n c ec h a l l e n g ea 1 1 da c h i e v eb e 骶r p e r f b m a n c e ，i sar e s e a r c hi s s u eu 1 ：l r e s o l v e dt or e s e a r c h e r s m o d e mi n f o m a t i o nr e t r i e v a l i sa l w a y sd i s c u s s e do nt h eb a l s i so fc e r t a i nk i n d so f m o d e lo ri i l d e x i n gm e c h a n i s m t m sp 印e rm a i n l yp r o p o s e ss o m em o d e lb a s e do n i n t e r r e l e v a n ts u c c e s s i v e1 r e e s ( i r s t ) ，w 1 1 i c hi sd e v e l o p e df o rm a n yy e a r si no u r r e s e a l r c h 伊o u p i nt h i sp a p e r ，、v eh a v ea d a p t e di r s ts u c c e s s 如l l yb e t t e ri n 向l l t e x t d o m a i na n dg a i n e dg o o dp e r f o 咖a n c emt h ea r e ao fx m lr e l a t e ds e m i s t r u c t u r e d d a t a f i r s t l yt h i sp a p e rd i s c u s s e st h em o d e lo fi r s tu n d e rt h ec o n t e x to ft e x tr e t r i e v a l t oe n h a n c et h es p e e do fq u e r ) ，i n g ，i ta l t e r st w od i m e n s i o n a li r s tt ob e t t e rs o r to r d e r v e c t o r s ，w h i c hi sc a l l e dd o s t ( d o u b l e - 0 r d e rs u c c e s s i v et r e e s ) t h e ni t 凡n h e r i n v e s t i g a t e st h er e l a t i o n s h i pb e t w e e nd o s ta u l dp a ta r r a yt om a k e0 u tt h et h e o r ) ， b a s i sa n da b i l i t i e so ft h ei r s tf a m i l y a st h ec o m m o nf o u n d a t i o no ft e x tr e t r i e v a la n d x m lr e t r i e v a l ，t w o - d i m e n s i o n a ls u c c e s s i v et t e e s ( t w s t ) i si m p o n a n tt os u p p o r t b o t hn o n - s t m c t u r e da n ds e m i s t m c t u r e dd a t a s ot h i sp 印e ri n v e s t i g a t es o m ec r i t i c a l t o p i c s a b o u tt w s t ，s u c ha ss u b d ba n dd b m e r g i n g ， i n s e i r t i n g a n d d e l e t i n g p e r f o m a n c e ，c o d ec o m p r e s s i o na l g o r i t h m s h o wt oa v a i lt h es t r u c t u r e si n c l u d e di ns e m i s t n l c t u r ed a t at op r o m o t eb o t h n o n n a la n df u l l t e x tr e t r i e v a li ss t i uap r o b l e mt ob ei n l p r o v e d t h i sp a p e rp r o p o s e s x m li n t e r - r e l e v a n ts u c c e s s i v et t e e s ( x i s t r e e ) ，t h e ni td i s c u s s e st h ep r o p e l r t i e sa n d r e l a t e da l g o r i t h m sc o n c e m i n gx i s t r e e ，a tl a s ti ti n t r o d u c e st h eo 曜a n i z a t i o no ft h e e x p e r i m e n t sr e f e r r i n gt ox i s s ，t i m b e ra n dx i n d i c e c o n c e p ta s s i s t e di n f o m a t i o nr e t r i e v a l i san e wr e s e a r c ha r e ai nr e c e n ty e a r s ，i t s c o n c e m e db yp e o p l ef o ri t sa c c u r a c ya n dg o o du s e ri n t e r f a c es oa st op r o m o t eu s e r u s a b i l i t y ，s oi tw i l lb ea ni m p o i r t a n tt r e n di nt h en e a rf u t u r e r h i sp 印e rm a i n l yf o c u s e s o nt h ec o n c e p tq u e r y i n gp r o b l e m s ，w h i c hi n c l u d e ss l c aa l g o r i t o nd o c u m e n t a b s t r a c t s t r u c t u r ew i t hn o d en 锄e ， c o n c e p ts e m a n t i c m o d e lc r e a t i n g ， a 1 1 dr e l e v a n c e n u m b e r i n g & r a r 汰i n gm e t h o d s ，e t c 7 n l i sa r t i c l ea l s ob u i l d sar o b u s ta l g o r i t h mb ym e t h o d i c a u yc o m b i n i n gt 、 ，o d i e r e n tm i n i n ga l g o r i t h m so nf p t r e ew h i l ea d j u s t i n gt h em i n i n gs t i a t e g y d y n 锄i c a l l ya j l da l i t o m a t i c a l l yd u r i n gac o m p l e t ep r o c e s so ff r e q u e n tp a t t e mm i n i n g t h i sa r t i c l ef i r s t l yp r o p o s e st h en a i v ed e p t hf i r s ts e a r c ha l g o r i t h m ( n d f s ) t h a ti s b a s e do nf p t r e e ，a n dt h e nb r i e n ya j l a l y z e si t sp e 面r m a n c eo nd i f r e r e n td a t a s e t s a r e rt h a t ，an e ws e l f - a d a p t i v ea l g o r i t h m ( s a f p ) i sp r o p o s e d ，w 址c hc o m b i n e st h e n d f sw i t ht h ef p - g r o 、t hb yad y n 锄i cm i n i n gs t r a t e g yo nc o n d i t i o n a lf p - t r e e s e x p e r i m e n t sd e m o n s t r a t et h a tt h es a f pi sm o r er o b u s ta n de m c i e n tt h a i lb o t ht h e n d f sa i l dm ef p 一伊o w mo nv a r i o u sd a t a s e t s f i n a l l y ，t i l i sp a p e rs u l i l m 撕z e st h ew o r kt i l ln o w ，a n dt r i e s t oc o m b i n et h e t e d m 0 1 0 9 i e sd i s c u s s e di nf o n n e rc h 印t e r st o c o n s t i t u t ear e t r i e v i n gs y s t e mt h a t i n c l u d e ss t r u c m i e d ，s e m i s t m c t u r e da n dn o n - s t c t u r e dd a t a a tl a s tt h ed e m os y s t e m a n dt h ep r o j e c tt h a t 印p l y i n gt w s ti sb r i e n yi n t r o d u c e d k e y w o r d ：i n f o n n a t i o nr e m e v a l ，t e x tr e t r i e v a l ，x m l ，i r s t ，d o s t ，c o n c e p tr e t r i e v a l v i i 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作j ，明确的声明 并表示了谢意。 作者签名：日期：2 叩7 川g 论文使用授权声明 木人完全了解复目大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名：至纽导师签 第一章引言 第一章引言 本章首先阐述了信息检索的研究背景、研究意义，以及当前国内外的研究状况和研 究热点，然后介绍了本文的研究目的、研究内容和论文的组织结构。 1 1 研究背景和研究意义 1 1 1 概述 近年来，随着计算机和通信等信息技术飞速发展，电子媒体等各种应用和 用户数量激增，传统行业信息化也取得了长足的进步，工业和科研数据自动化和 半自动化产生，这一切，使得各种数据大量累积；另一方面存储技术发展的日新 月异也使得数据总量的增长势头越来越快。据统计，八十年代全世界信息总量就 以指数级数增长，每隔2 0 个月就增加近一倍。在九十年代，各类机构开始引入 数据库系统，美国政府部门的一个典型的数据库每天要接收约5 t b 数据量。根据 i d c 的报告，全球仅在2 0 0 6 年一年内就制造了约有1 6 亿t b 的数字信息，其中 包括了图片、视频、文本、音频和其它各种格式的内容。可以说，如今信息产生 的速度远远大于人类对这些信息进行充分消化的速度，这就是人们所描述的信息 时代的“信息爆炸”。 另一方面，随着全球化步伐的日益加快和各个领域的日渐交叉与融合，使 得事务处理日益复杂，人们对问题进行有效决策所需要的信息量也大为增加，这 就形成了这样的局面：信息总量和现代决策需要的信息量越来越大。在这样的背 景下，人们似乎感受到了比从前更为明显的“信息匮乏”! 在信息爆炸时代的“信 息匮乏”，这似乎是一个悖论，却是不无原因的。首先，信息总量和信息需求都 大为增加；其次，信息产生和呈现的方式和顺序并不一定正好与受众决策所需要 的信息完全一致。因此，如果说信息总量和信息需求的有效交集可以得到满意解， 那么，这两者的同时增长使得求解的复杂度急剧增长。这个问题可以通过一个例 子来说明：过去需要在3 0 0 m 的数据库上查找某个问题，如今却需要在3 g 的数据 总量上查找1 0 个不同的问题! 在这样的背景下，如果不借助于有效的检索机制，信息量过大所产生的效 果与无信息可言的效果是一样的，“过犹不及”，这正好和中国古代圣人孔子说 过的一句话有着相通的道理，真正有价值的信息被大多数无关的数据所淹没。因 此，信息检索问题同益受到学界和业界的普遍关注，各种现代信息检索技术和应 第l 页 第一章引言 用也应运而生，各应用领域很快的实现了从手工检索到计算机检索再到目前网络 化等发展阶段的转变。其中，最为典型的、广为人知的应用就是针对w e b 信息的 检索技术即搜索引擎技术。 现代意义上的最早的搜索引擎始于1 9 9 4 年7 月m i c h a e lm a u l d i n 将网页爬 虫( s p i d e r ) 程序与索引程序结合起来，创建了l y c o s 【l 】。与此同时，斯坦福 ( s t a n f o r d ) 大学的d a v i df i l o 和g e r r yy a n g 共同创办了基于目录分类体系的 索引y a h o o ，并成功地使搜索引擎进入商业运作，从此搜索引擎进入了高速发展 时期。目前，互联网上有名有姓的搜索引擎己达数百家，功能也从仅仅是索引和 检索文档集合发展成为包括文本建模，分类、聚类，支持相关反馈等功能的系统， 其中最有代表意义的是g o o g l e ，y a h o o ， m s n 等系统。 现代搜索引擎技术从根本上改变了人们生产和生活的方式，因而获得了相 当大的成功。但是，数据是时刻不断的在增长，因此信息检索将永远不会成为能 够被彻底解决的问题，在现有的搜索引擎还在企图通过改进算法以实现在新的信 息总量上保证原有性能的同时，新的检索问题和需要又在不断的产生： 如何支持在异构的w e b 数据库也就是所谓的d e e pw e b 上进行检索问题； 半结构化数据的检索问题不能简单的采用文本检索的方法解决，大容量、 更快速度、更好性能的数据检索方法业已成为业界所面临的亟待解决的问题； 如何将文本、数值以及其他类型的数据检索与半结构化信息检索进行有 效的结合从而求出满意解； 决定检索结果匹配程度的往往是返回结果的语义与人们所期望的结果之 间的匹配程度，因此如何采取更贴近于人的查询问题，基于概念语义的检索技术 有待进一步发展。 1 1 2 研究的理论意义 自上个世纪7 0 年代由时任i b m 研究员的e f c o d d 博士提出的关系模型以 来，经过多年的发展，基于关系数据库的理论模型已经能够很好的存储和查询结 构化数据；如今，对于非结构化数据，例如全文信息、w e b 信息也有了相应的信 息检索方案；但是，对于半结构化数据( 如x m l 等) 以及半结构和无结构混合的 数据，虽然受到较早就被提出 2 】， 3 ， 4 】，以至于相当长的一段时间内成为业 界研究的热点，但迄今为止，尚没有统一的和公认有效的解决方案。因此，提高 半结构化和无结构化数据的综合检索性能，找到联合检索的更优的索引机制，乃 至于进一步提出一种结构通用、功能完善的半结构化数据管理系统，对于解决信 第2 页 第一章引言 息检索中若干难题，意义重大。 本文在二元后继树的基础上，提出了字符和偏移均有序的后继树，提高了 查询性能，并从理论上证明了其与p a t 数组的等价性，从而能够更清楚的评价和 比较互关联后继模型在全文索引模型体系的地位以及性能特征。 本文提出的x m l 结构索引方法能够将半结构化数据中的结构信息统一为表 和向量的结构，并能保证无损的保存源数据中的结构信息，本文采用的自底向上 索引结构有利于缩减半结构和无结构数据结合情形下的检索搜索空间的问题。 本文提出了一种新的概念检索模型，这对于进一步深入开展半结构化的概 念语义检索有着积极的意义。此外，本文还在探讨模式路径和模式上下文的过程 中发现了一种自适应的频繁项挖掘算法，该算法对于不同分布特征的数据集有较 好的适应性，从而能够提高挖掘的效率。该算法也适用于通常的频繁项挖掘问题。 1 1 3 主要领域 从信息内容的格式来说，计算机信息检索又可分为结构化、半结构化和无结 构化数据信息检索。其中，结构化数据是指那些能够为计算机所理解的，有着良 好的结构说明和格式规则的数据，比较典型的例子是关系型数据库；而无结构数 据指的是那些无法存放到数据库中的数据，包括文本，图像，音频以及视频文件 等，据统计，无结构数据占数据总量的百分之八十五；半结构化数掘是介于这两 者之间的数据，半结构化数据有一定的结构，但这些结构经常动态变化，没有固 定的统一的模式，因而难以为传统的模式所定义，比较典型的形式是w 曲数据 以及x m l 数据。 关于结构化数据检索，一般采用s q l 或者其他规范化的语法作为查询语言， 在各类信息系统中已有广泛应用，相应地，围绕结构化数据的信息检索也己相对 完善。x m l 数据检索是针对半结构化数据的信息检索，近年来已经成为国内外 研究的热点，但是现有商业系统和研究类原型系统都难以高效的支持海量数据 ( g b 、t b 级) 的查询要求。全文检索是在自然语言、基因信息学等领域的无结 构数据( 文本) 检索，它分为基于词的串检索和基于字的串检索，前者主要采用 布尔模型、向量模型和随机模型等方法体系，后者多采用p a t 数组，s u m xa h a y 等结构实现。本文第二章中主要探讨基于字的文本检索。 目前，信息检索技术已广泛应用于w e b 检索、自然语言处理、文本挖掘、 信号处理、基因信息学、多媒体检索等领域，其中主要应用领域如下： w e b 信息检索 第3 页 第一章引言 w w w ( w o r l dw i d ew e b ) 是迄今为止互联网发展最为成功和最为广泛的应用。 自从1 9 9 1 年被t i mb e r n e r s l e e 发明以来，各种w e b 应用迅速增加，网页数量 呈指数增长，从某种程度来说，它也可以看成一个非结构的，海量的文本数据库。 为了在这样的数据库上通过关键词而不是导航的方式来定位w e b 文档，就必须对 文本信息进行有效的索引组织从而实现准确的查找和定位。 数字图书馆信息检索 早期的图书馆是通过卡片对图书进行进行目录式管理。计算机技术被引入 图书馆管理领域之后，初期的图书馆系统开始采用基于书目等描述信息检索的数 据库，后来发展成为基于工程索引( e n g i n e e “n gi n d e x ) ，人文科学( h i s t o r i c a l a b s t r a c t ) 等分类体系进行检索；再进一步的，就是采用某种索引机制( 比如倒 排表) 来对内容进行索引。如今存储芯片的成本低廉，数字格式更容易分发和保 存，印刷品反居二线，很多文献都仅仅以电子版的形式存在。美国国会图书馆( t h e l i b r a r yo fc o n g r e s s ，简称l c ) 5 】是世界上最大的图书馆，同时也是世界上最 早的数字图书馆之一，每月平均因特网访达问量为7 亿多人次。 基因数据信息检索 人类基因组有约1 0 万个基因，3 0 亿个碱基对。随着后基因组时代的到来， 基因组学的研究的重点已逐步从结构基因学过渡到功能基因学，要“读懂 人类 的基因，确定病变等困扰人类的问题在基因层面上的生物基础，这些分析工作的 完成，必须借助于先进的信息检索技术。 生物信息学是是随着人类基因组计划的启动而兴起的一门交叉学科，它涉 及生物学，数学，计算机科学等，以生物实验和衍生数据的存储为中心。美国基 因数据库检索叫e n b a n k 6 】提供了全文检索、e n t r e z 高级检索功能，可以检索 核酸和蛋白质序列，也可以进行序列局部相似性查询( b l a s t ) 。 企业数据检索 i d c 研究表明，企业内部数字内容量大约每1 8 个月翻一倍。企业信息检索 主要体现在企业内部的信息处理与检索，企业之间的电子数据交换相关的信息检 索以及面向服务的语义w e b 的自动检索等。据f o r r e s t e rr e s e a r c h 预测，企业 内容管理市场规模每年将以近2 0 的速度持续增长，2 0 0 8 年将达到近4 0 亿美元。 多媒体信息检索 多媒体技术的发展带来带给我们的是多媒体信息的海洋，在充满了音频、 图片、视频数据的仓库中，如果仅能通过一些人为定义的关键词，对多媒体信息 的进行描述和检索是非常困难的，这就需要有一种更有效的多媒体检索方式。 第4 页 第一章引言 基于内容的信息检索( c o n t e n t b a s e dr e t r i v a l ) 是根据图像中的纹理， 或视频中的场景、片断进行特征分析和提取，是对多媒体对象的内容及上下文语 义环境进行检索，并基于这些特征进行相似性匹配。如何有效的帮助人们快速、 准确地找到所需要的多媒体信息，成了多媒体信息库所要解决的核心问题。 1 2 问题描述 1 2 1 基本概念 本节将首先对一些概念给出相关说明。 信息检索( i n f o r m a t i o nr e t r i e v a l ，i r ) 是指将信息按一定的方式组织和 存储起来，并根据用户的查询要求迅速而方便地找出包含指定特征( 关键词、检 索表达式) 的文档、段落或句群供用户阅读的过程和技术。也是信息用户为处理 解决各种问题而查找、识别、获取相关的事实、数据、知识的活动及过程。 计算机信息检索是利用计算机系统有效存储和快速查找的能力发展起来的 一种计算机应用技术。它与信息的构造、分析、组织、存储和传播有关。计算机 信息检索系统是信息检索所用的硬件资源、系统软件和检索软件的总和。它能存 储大量的信息，并对信息条目进行分类、编目或编制索引。它可以根据用户要求 从已存储的信息集合中抽取出特定的信息，并提供插入、修改和删除某些信息的 能力。 网络信息检索，也即网络信息搜索，是指互联网用户在网络终端，通过特定 的网络搜索工具或是通过浏览的方式，查找并获取信息的行为。 结构化数据 结构化数据指的是那些遵守着良好的格式规范定义( 数据类型 和数据关系约束) 的数据集合。现存的商业数据库管理系统中进行存储和处理的 大多是结构化数据。 半结构化数据半结构化数据是不严格遵守预定的格式规范的数据。用x m l 和h t m l 等标记语言描述的数据可以认为是比较典型的半结构化数据。 无结构数据无结构化数据是指数据集合中最小数据单位之问都处于并列 关系的平板结构的数据。比较典型的无结构数据包括图书及包括、基因数据、股 票数据等文本数据。 异构数据采用多种数据格式，有着不同的数据模型和语义环境的数据。在 如今的i n t e r n e t 环境下，各个站点的w e b 页面，x m l 数据，w e b 数据库等属于异 第5 页 第一章引言 构数据。 数据互操作性异构数据环境下数据之间的相互转换。 搜索和检索的区别和联系搜索在是搜集( 采集) 和检索的简称，是 i n t e r n e t 的产物，旨在i n t e r n e t 世界里如同浩瀚的宇宙中搜索符合要求的结 果，重点在未知世界里发现新东西；检索强调的是在己知世界里快速准确全面 地找到所要的东西。 脱机处理和联机检索两种检索方式。对于前者，用户提交书面检索要求，操 作员按期打印出结果交付用户。对于后者，用户通过联机终端打入检索命令，系 统当时给出回答。通过计算机网络，用户还可以进行远程脱机处理或远程联机检 索。 检索语言通常包括检索命令和提问逻辑表达式两个部分。命令传达用户对系 统的请示，逻辑表达式则提供执行该命令时的逻辑条件。逻辑表达式是逻辑运算 符( 与、或、非) 、逻辑关系符和不同属性的组合。系统提供一组程序来解释和 执行检索语言。 效能评价计算机信息检索系统的效能通常根据漏检索、误检率、查全率、 查准率和响应时间( 对联机检索) 等来衡量。查全率指检出的相关信息条目数与 信息库中的相关条目数之比。查准率指检出的相关条目数与所有检出的条目数之 比 7 】，【8 】。 全文检索指的是一种检索方式，可以通过扫描文档中的每一个特征项并对 其建立索引，并能通过该特征项找到其在文档中出现的次数和位置相关信息，当 用户查询时，可以根据事先建立的索引进行查找，并将查找的结果反馈给用户。 全字匹配要求关键词和原文严格一致的匹配方法，也称为按字匹配。 按词匹配指对语义单位( 文档中的词) 建立索引，查询时按词检索。 索引膨胀比指的是为了支持检索而建立的索引与原纯文档在所占存储空 间上的比率。 检索响应时间任一服务器的执行时问再加上网络的通信时间。因为具体的 网络环境与检索系统本身性能关系不大，因此实际检索响应时问往往不考虑将检 索结果通过网络传送到读者桌面上的时间。 概念检索概念是人对客观事物和一些观念存在的一种抽象和概括，是客观 事物在人头脑中的反映。因此概念检索是克服字面全字匹配局限于表面形式的缺 陷，根据词所表达的概念意义来认识和处理用户的检索请求。 第6 页 第一章引言 1 2 2 信息检索问题形式化模型 1 ) 全文检索模型 给定字符表c ，一个定义在c 上的由文档集d = d ，d ：，d n ( n 为文档的 总个数) 组成的文本数据库t ，对于给定的第i 个用户查询q 。，能够在所要求的 系统响应时间c ；内求出满足查询q 。所有解s 。，其中s i _ d 。，d ：，d 。) ( m 为满 足条件的解的总个数) ，q 。为由查询关键词k 。组成的通过查询语言l 来描述查 询体。由于用户总是期望能够从规模可能会很大的m 中找到最相关的解，因此还 必须在返回的结果集中给出每个解相应的匹配度m ；= m ，m 。，) 。因此文 本数据库的基本模型可以从形式上描述为t = c ，d ，l ，s ，m ) 。 全文检索模型主要分为：布尔模型、概率模型和向量空间模型。 顾名思义，布尔模型是基于二值的严格匹配模型。对于每一个查询串，如果 文本中出现了对应的特征项，则变量取“t m e ”，否则取“f a l s e ”。文本查询通 过逻辑运算符( “a n d ”、“o r ”、“n o t ”) 连接查询串特征项，查询的过程遵循布 尔运算的法则。布尔检索模型主要的优点有：速度较快；易于表示同义关系和词 组。缺点是缺乏灵活性，不能表述模糊查询的相似度。d i a l o g 等商用检索系统 是基于布尔模型。 概率模型主要针对相关文本匹配度的不确定性以及查询表达的模糊性而提 出。对于给定的用户查询q ，文本d 可以表示为d = ( d l ，d 2 ，d n ) ，n 为特征 个数，d i _ 1 表示特征项i 在文本中出现；d i _ o 表示特征项i 在文本中不出现。那 么对所有的文本d 计算概率p ( r i d ，q ) 并从大到小进行排序，其中r 表示文本d 与查询q 的相关性。 向量空间模型把文本表示成向量空间中的点，并用向量间的夹角余弦作为相 似性度量。向量空问模型的计算过程是，首先确定用户查询和文本的向量，然后 在这两个向量的基础上进行相似性计算。 向量空间模型的特点是用向量表示文本和查询的特征项及权值集合，从而把 查询操作转换为向量空间上的运算，通过简单的统计可以计算出向量的权重。但 是，该模型也存在一定的缺点，主要表现在它假设这一模型的特征项之间正交， 但是由于自然语言中词或短语之间存在着各种同义或者近义等错综复杂的语义 关系，因此检索结果的可信性受到了一定的影响。 第7 页 第一章引言 2 ) 半结构化数据检索模型 x m l 是比较典型的半结构化数据。与文本等“平板 类型的无结构化数据 相比较，半结构化数据结点具有一定的层次结构和逻辑关系，数据中的信息单元 在文档中的地位很不相同；与结构化数据相比较，半结构化数据没有固定的模式， 它们一般采用将描述信息和数据混合存放的方法，因此也可以称作是自描述的数 据类型。研究者们一般把半结构化数据划分为两种模型： 树模型。每个文档有唯一的根结点。除了根结点之外，每个结点都有唯一的 父亲结点，每个结点都有且仅有一个结点名称。叶结点是原子结点，其中包括了 具体的值；值的类型各异，如数值型，文本型，图像语音等多媒体型等等，其他 结点通过叶结点逐层描述。 有向图模型。整个文档由一系列的结点构成，结点之间由有向边连接，每个 结点都有且仅有一个结点名，每个结点都有唯一的标志符以相互区分。图中包含 了值且没有输出边的结点称为原子结点，每个这样的结点都唯一对应一个基本类 型，如数值型，文本型，图像语音等多媒体型等等。 3 ) 性能指标 全文检索模型常用的一些性能指标归纳如下： 查准率和查全率：查全率指检出的相关信息条目数与信息库中的相关条 目数之比。查准率指检出的相关条目数与所有检出的条目数之比。 时间复杂度：包括创建索引的时间效率以及检索的时间效率对于索引模 型更重要的是检索性能，所以，我们更常考虑的是模型的检索速度。 空问复杂度：由于现在索引数据的海量性，索引模型中任何能够减少索引 空间消耗的机制均可导致不可估量的实用效果通常，我们用膨胀比( e r ) 来评价 索引模型的空间性能e r = ( i s + f s ) f s ( i s 为索引大小，f s 为原文大小) 。索引 模型的膨胀比与模型的具体实现方式和使用的压缩算法也有很大关系。同时又会 影响索引效率 查询完备性：一个好的全文检索模型应该能够实现多种查询，如： i 字符串查询：包括关键词查询，或较长的字符串查询，比如一个句子 i i 前缀查询：在索引库中查询具有某给定前缀的字符串。 i i i 临近查询：查询所有字符串s ，s 以s 1 字符串开始，以s 2 结尾，而 第8 页 第一章引言 s 1 ，s 2 之问的最多间隔n 个字符( n 由用户给定) i v 范围查询：查询所有在某一词典范围内的字符串。如：”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 不在。 v 最长重复查询：在文档的两个不同位置寻找相同的字符串，而这个字 符串在整个文档中是最长的。 v i 最频繁匹配查询：查询在文档中出现次数最多的字符串。 适应性：好的索引模型应该可以处理各种不同类型，具有不同特点的数 据，如：长度相差很大的记录，或者没有文档，关键词结构的数据。 动态性：索引模型最好能够适应数据的动态改变，包括关键词词典中词条 的增加，或索引记录的改变等。 1 3 研究现状 1 3 1 国内外研究状况 全文索引领域 文 9 】， 1 0 】， 1 1 综述了全文索引领域发展的基本脉络。在文本数据库上执 行查询有两种方法：一种是基于模式匹配的联机查询，顺序扫描文本，目前来说 最著名的算法是k m p 算法 1 2 】，采用该算法进行检索时的优点是不需要额外的空 间建立索引，并且能够及时反应文本修改的情况。算法通过预先计算模式串中相 应字符处的模式特征，避免了以往算法模式匹配时不必要的回溯，从而提高了效 率，时间复杂度为0 ( m + n ) ( 其中m ，n 分别为模式串和文本库的规模) 。但是这 个算法至少要将库遍历一次，只能适应库中文本总量较小的情况，在海量的数据 集上进行查询是不可能的。 将检索算法进一步提高的办法是为文本库建立专用索引，通过花费额外的 空间来换取时问。按照索引模型的不同，又可以分为倒排索引，p a t 树，后缀树 结构，署名文件等等。下面本文将简单的介绍这几种索引机制。 倒排表是目前应用最广泛的一种索引机制。其主要思想是根据关键词按序 集中存储包括了该关键词的文档的集合，在查询到该关键词时，系统将该文档集 合返回。该方法的好处是创建索引和更新索引代价较低，在受限查询功能和性能 的基础上，索引膨胀比比较低，大约为1 0 一1 0 0 之间。但是，倒排索引是一种 基于词的索引机制，这就导致在其索引之上的查询功能非常有限。e l i a s 在1 9 7 5 第9 页 第一章引言 年【1 3 描述的y 和6 编码法是一种有效的索引压缩方法。目前在静态全文数据库 中得到广泛应用的g 0 1 0 m b 编码是在1 9 6 6 年首次提出 1 4 ，g a l l a g e r 和v a n v o o r h i s 【1 5 在1 9 7 5 年发展了这种方法。 署名文件能提供比倒排表更迅速的查询处理，但需要大量的存储空间，因 此它们往往与压缩技术配合使用。署名文件有时也称散列函数法，每个文档有一 个关联署名或描述符，每个索引项作为散列函数的参数产生几个散列值，与这些 值相应的署名的位数被置为1 。当把文本中每个字符的散列值叠加时，就得到了 合并后的文本署名的全集。要检测一个查询项是否在给定的文本中出现，就要计 算此查询项的散列函数值。如果某些文档的描述符中所有的对应位均被设定，则 此术语可能出现在该文本中。要解决这种不确定性，必须读入并扫描文本以检查 查询项是否真正出现。可以通过位每个查询项设置几个位并使署名足够长来降低 这种失败匹配的概率。但无论如何，总是需要进行失败匹配的检查，这在相当程 度上增加了查询过程的开销。f a l o u t s o s 1 6 和c h r i s t o d o u l a k i s 【1 7 】分析了署名 文件中存储空间与失败概率之间的折衷关系。s a c k s d a v i s 等人在1 9 8 7 年，k e n t 在1 9 9 0 年描述了基于署名文件的不同结构，其中包括一个二级方案。 p a t 树模型中假定查询可以从文档的任意字符开始，查询文本的长度支持从 文档开始到结束。p a t 树是一种特殊的p a t r i c i a 树，它由g o n n e t 和m a n b e r ( 1 8 ， 1 9 ， 2 0 】) 提出。它很有特色的地方是将一个文本看成一组半无限串的叠加，而 这组半无限串的排序结果被表示成树的形式。它的最大优点是极大加快了检索速 度，尤其对某些特殊的检索，如前缀检索、范围检索等检索效率更高。它的最大 缺点是空间开销大，而且创建过程中的空间开销更大，创建效率也很低。 p a t 数组由g o n n e t ( 1 9 8 7 ) 2 1 】和m a n b e r 和m y e r s ( 1 9 9 0 ) 【1 9 】独立地发现 并应用的。p a t 数组的发现是在p a t 树发现之后，将p a t 树的叶节点串行化就得 到了p a t 数组，但p a t 数组的思想实质比p a t 树更直观，完全可以不通过p a t 树去理解和创建。p a t 数组将文本中所有可能出现的字符串做了排序，待检索的 字符串可在其上实施多种检索手段。一般地，在排序的数组中采用二分法是最快 的。进行两次二分法，分别找到待检索串在数组中的上确