（计算机应用技术专业论文）基于倒排索引的xml文档全文检索技术研究.pdf

哈尔滨工程大学硕士学位论文 摘要 随着信息技术的不断发展，x m l 规范已经得到普遍接受和应用，如何更 高效地查询x m l 文档中的信息也已成为学术界和工业界的研究热点。目前的 几种x m l 文档查询技术中，基于索引的全文检索技术具有很高的技术背景和 广阔的应用前景。 本文在研究和分析基于倒排索引的全文检索技术的基础上，设计了一组 支持x m l 文档倒排索引和全文检索的存储模型及算法。上述结构和算法已经 在本论文研究期间完成的原型系统中得到了应用，并与x p a t h 、x q u e r y 两种 查询语言的查询效率进行了对比。 考虑到全文检索技术是一种i o 密集型的技术，尤其对大规模文档集合进 行全文检索时需要频繁地访问外存设备，因此本文给出了利用交叉缓冲队列 对倒排文件进行缓冲处理的思想。另外，为了能够支持文档集合的更新需要， 本文还研究了基于可扩展位示图的倒排文件存储结构，并对相关算法进行了 描述。 关键词：x m l ；全文检索：倒排索引；缓冲；位示图 哈尔滨工程大学硕士学位论文 a b s t r a c t w i t l lt h ec o n t i n u o u sd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y , t h ex m l s t a n d a r dh a sb e e nw i d e l ya c c e p t e da n da p p l i e d h o wt oi n q u i r i n gi n f o r m a t i o n f r o mx m ld o c u m e n t sm o r ee f f i c i e n t l yh a sb e c o m et h eh o ts p o to fa c a d e m i ca n d i n d u s t r yr e s e a r c h i ns e v e r a lk i n d so fx m l d o c u m e n t si n q u i r i n gt e c h n o l o g y , t h e i n d e xb a s e df u l l - t e x tr e t r i e v a lt e c h n o l o g yh a st h eh i g h e rt e c h n i c a lb a c k g r o u n da n d b r o a da p p l i c a t i o np r o s p e c t sa tp r e s e n t o nt h eb a s i so fr e s e a r c ha n da n a l y s i sf o ri n v e r t e di n d e xb a s e df u l l - t e x t r e t r i e v a lt e c h n o l o g y , ag r o u po f s t o r a g em o d e l sa n da l g o r i t h m sa r ed e s i g n e dw h i c h c o u l ds u p p o r ti n v e r t e di n d e x i n ga n df u l l t e x tr e t r i e v i n gx m ld o c u m e n t s t h e s e s t r u c t u r e sa n da l g o r i t h m sh a v eb e e na p p l i e dw i t hp r o t o t y p e s y s t e md u r i n g i n v e s t i g a t i o n ，a n dw g r ec o m p a r e dw i t ht w ok i n do fx m lq u e r yl a n g u a g e ：x p a t h a n dx q u e r y c o n s i d e r i n gt h a tt h ef u l l - t e x tr e t r i e v a li so n e k i n do f f oi n t e n s i v et e c h n o l o g y , a n de s p e c i a l l yn e e dt ov i s i td i s ke q u i p m e n tf r e q u e n t l yd u r i n gs e a r c hb yl a r g es c a l e d o c u m e n t ss o t ，a ni d e ao f u s i n gc r o s s e dc a c h el i s tt ob u f f e r i n gi n v e r t e di n d e xf i l e i sp r o p o s e d i na d d i t i o n ，i no r d e rt os u p p o r tt h er e n e w a ln e e d so fd o c u m e n t ss e t ， a ni n v e r t e di n d e xf i l es t r u c t u r ea n dr e l a t e da l g o r i t h m sb a s e do nc x t e n s i b l eb i t m a p w e r ea l s oi n t r o d u c e d k e y w o r d s ：x m l ；f u l l t e x tr e t r i e v a l ；i n v e r t e di n d e x ；c a c h e ；b i t m a p 哈尔滨工程大学 学位论文原创性声明 本人声明，所呈交的学位论文是在导师的指导下由 本人独立完成的。有关观点、方法、数据和文献的引用 已经在文中指出，并与参考文献相对应。论文中取得的 研究成果除加以标注和致谢的地方外，不包含其他人己 经发表或撰写过的研究成果，也不包括本人为获得其他 学位而使用过的材料。与我一同工作的同志对本研究所 做的任何贡献均已在论文中作了明确的说明并表示谢 意。 作者。签名，：盔型塑 k i期：们夕年移月，日 哈尔滨工程大学硕士学位论文 第1 章引言 1 1 研究内容的背景 x m l ( e x t e n s i b l em a r k u pl a n g u a g e ，可扩展标记语言) 川是一种新型的标记 语言，能够非常灵活地标记各种应用系统中的数据信息，具有开放性、灵活 性、易读性和平台无关性等特点。随着基于i n t e r n e t 的商业应用的迅速发展， x m l 已经成为信息表示和数据交换的实事上的标准，越来越多的应用系统利 用x m l 表述其底层数据。在这些用于描述数据的x m l 文档中存储了大量的信 息，随之而来的问题就是如何从这些x m l 文档中获取用户感兴趣的信息。 由于x m l 是规范化的，因此规范制订者w 3 c ( w o r l dw i d ew e b c o n s o r t i u m ) 提出了几种x m l 文档查询语言。作为与x m l 规范配套的辅助规 范，x m l 查询语言具有广泛的市场和应用前景。同时，数据库技术的广泛应 用也为基于数据库技术的x m l 查询方向铺平了道路，相关的x m l 数据库产品 也不断出现。另外，x m l 文档又是文本型的，因此学术界很自然地把注意力 放到全文检索技术上。全文信息检索技术是从大规模的信息数据库中检索信 息的有效手段。它可以利用原文中任何有意义的字或词检索原文。由于这种 技术理论成熟，实用性较强，因此将其结合到“l 文档的做法也变得顺理成 童。 上述三种技术从不同角度解决了x m l 文档的查询问题，但是其技术深 度、检索效率、应用前景各不相同。就检索性能来看，全文检索技术无疑是 其中的佼佼者。因此，有必要对该技术进行全面的分析研究，总结出它的应 用特点。本文依据以上思路，结合某个大规模x m l 文档数据库，研究基于倒 排索引的x m l 文档全文检索技术的总体框架、技术要点及其实现方案，同时 探索在全文检索过程中利用缓冲池技术提高检索效率的可行性。 1 2 国内外研究现状 1 2 1x m l 规范 x m l 是w e b 标准化组织w 3 c 对复杂的s g m l 进行简化后制定的一种标 记性语言规范，是s g m l 的一个严格筛选的子集【l 】。它将s g m l 的丰富功能 哈尔滨工程大学硕士学位论文 与h t m l 的易用性相结合，是一种结构简单而又灵活的文档格式规范。h t m l 只是w e b 显示信息的标记语言，它着重描述w e b 页面上的信息如何显示。而 x m l 描述包括w 曲浏览器在内的各种信息处理终端的信息内容，同时x m l 具 有可扩展性，其标记个数不固定，允许用户定义数量不限的层次标记来描述 文档中的资料。x m l 可以描述各种各样的信息，无论这些信息是规则的还是 或不规则的，平面的还是树型的，文本的还是多媒体的。由于其极大的灵活 性，x m l 已经逐渐成为下一代信息描述和交换标准。 x m l 文档由层次结构的元素集合组成，其中每个元素既可以是原子的， 也可以是复合的。在x m l 文档中，和元素一起存储的标记( t a g s ) 描述数据 的语义。下面是一个简单的x m l 文档示例，它对应如图1 1 所示文档树： 叫回复 s d h 5 7 2 4 确实多个a p p l e t 可以在一个j v m 中运行 可回复 2 哈尔滨工程大学硕士学位论文 图1 1 ) n 也文档树示例图 x m l 规范包括d t d ( d o c u m e n tt y p ed e f i n i t i o n s ，文档类型定义) 和x m l s c h e m a 。d t d 定义了文档中添加的标记结构，使得使用该d t d 的x m l 页面更 具有效性。x m ls c h e m a 规范允许按x m l 格式描述x m l 文档的结构和语法。 它保留d t d 原有的文档结构说明能力的同时，扩充了对数据类型的支持等特 点，解决了d t d 中的种种问题。x m l 文档的创建者可以选择性地利用d t d 或 x m ls c h e m a 来确认x m l 文件的有效性。 x m l 规范还包括可扩展格式语言x s ue x t c n s i b l es t y l el a n g u a g e ) 闭和可 扩展链接语言x l l ( e x t e n s i b l el i n k i n gl a n g u a g e ) 口】。x s l 是一种基于x m l 的 语言，它通过层叠式样式表来控制l 数据。最初的x s l 规范仅仪是为了格 式化x m l 并在w e b 页面中显示其内容，但人们很快意识到这种处理过程涉及 到了两个截然不同的步骤，而且都非常有用：一种是将数据结构转换为其它 x m l 格式，另外一种是添加有关x m l 信息在某些特定设备上如何显示的数 据。因此，当前的x s l 主要由用于描述对x m l 数据进行结构化转换的x s l t 和用于描述x m l 显示模式的x m l f o 两部分组成。x l l 是x m l 的链接语言， 但比h t m l 的链接功能更加强大。它支持可扩展的链接和多方向链接。x l l 链接可不受文档制约，完全按用户要求来指定和管理。 与x m l 相关的其他规范和技术还有很多，在此不作一一介绍。这些技术 与x m l 之间的关系如图1 2 所示。 哈尔滨工程大学硕士学位论文 图1 2x 札规范及其关系 1 2 2x m l 查询语言 随着存储在x m l 文档中的信息量的增长，能够高效地访问x m l 的信息也 变得越来越重要。要做到这一点，必须要有一个能够准确的定位和获得所需 信息的查询语言。早期所使用的x m l 查询语言包括x q l 、q u i l t 、x m i , - q l 4 - 6 1 等等。目前在x m l 领域应用最广泛的查询语言是x p a t h 和x q u e r y 。 1 2 2 1x p a t h w 3 c 在1 9 9 9 年1 1 月发布了x p a t h l 0 的推荐标准【”，又在公布x q u c r y l o 标 准时一起宣布了x p a t h 2 0 标准。如今，x p a t h 已成为如x p o i n t e r 和x q u e t y 等很 多x m l 相关规范的核心。x p a t h 的主要目的是对一个x m l 文档进行寻址。为 4 哈尔滨工程大学硕士学位论文 了支持这个目的，它为操作字符串、数值和布尔值提供了一些基本的功能。 x p a t h 利用一个紧凑的，非讧l 的语法来定位x m l 文档中各个部分和选择文 档中的构成部件，如元素、属性、文本等。除了用来寻址外，x p a t h 自身的一 个子集能够用于验证一个节点是否符合某个模式。 x p a t h 定义了七种节点类型，分别是根节点、元素节点、属性节点、文本 节点、处理指令节点、注释节点和名称空间节点。在一个文档的所有节点之 间存在着一种称之为“文档顺序”的序列，该序列对应于x m l 文档中每个节 点的开始标记出现的顺序。具体而言，一个元素节点以及元素的属性、命名 空间出现在该元素的所有孩子节点之前。其中命名空间节点出现在属性节点 之前，多个命名空间节点之间的相对顺序依赖于实现，多个属性节点之间的 顺序也依赖于实现。 x p a t h 中的基本语法单元是表达式，它具有四种基本数据返回类型：节点 集( n o d e s e t ) 、布尔值( b o o l e a n ) 、字符( s t r i n g ) 以及数值( n u m b e r ) 。x p a t h 同时 定义了四种类型值之间的强制转换规则，这种转换有时是自动完成的，有时 则需要显式的函数调用。 表达式是x p a t h 最重要的概念。x p a t h 中最基本的表达式是定位路径表达 式( l o c a t i o np a t h ) 。通过位置路径表达式，我们可以精确地查找到x m l 元素 结点的位置。此外，x p a t h 还有布尔表达式、等式表达式、关系表达式和数值 表达式。 定位路径由一个或多个定位步组成，相邻定位步之间用广分开。定位步 确定了一个与上下文节点集相关的新的节点集，它针对上下文节点集中的每 一个节点进行求值，并将结果集合并成为下一定位步的上下文节点集。一个 定位路径表达式中的所有定位步按从左到右的顺序一次一个地执行，最后一 个定位步产生的节点集就是该定位路径表达式的结果。 例如，x p a t h 的定位路径表达式( 见式1 1 ) ： j a v a 论坛内容t e x t o c o n t a i n s ( 0 9 m 程序”) 】 ( 1 1 ) 首先获取所有“j a v a 论坛”的子节点，其次从这些子节点中选取所有“内 容”节点，再利用t e x t ( ) 函数和c o n t a i n s ( ) 函数返回包含“程序”字样的“内 容”节点。 定位路径表达式使用如下的匹配方法： 哈尔滨工程大学硕士学位论文 ( 1 )路径匹配：使用“”符号表示节点问的父子关系，使用“”符号 表示祖孙节点对。例如，“j a v a 论坛”代表了从根节点出发的所有 j a v a 论坛元素节点；“j a v a 论坛严”则代表了j a v a 论坛元素下的所有 子节点，其中”表示通配任意元素。 ( 2 )位置匹配：当存在同名的子元素时，使用“【n 】”表示其元素序列。 例如，“j a v a 论坛回复【2 】”得到第2 个回复元素节点。 ( 3 1属性值：x p a t h 可以利用属性值来匹配元素。此时，元素的属性名 前需要加上前缀 。例如，“j a v a 论坛回复【 i d - ”l ” ”表示属性i d 的值为1 的回复元素。 ( 4 )元素关系匹配：x p a t h 通过使用轴( a x i s ) 来限定元素的相对关系， 轴包括了p a r e n t ：( 父节点) 、c h i l d ：( 子节点) 、d e s c e n d a n t ：( 后代 节点) 等。例如，路经表达式“j a v a 论坛”又可以表示成 “d e s c e n d a n t ：j a v a 论坛”。 可以把x p a t h 看成与s o l 类似的查询语言，只不过x p a t h 是从x m l 文档中 提取信息。和s q l 语言一样，x p a t h 可以在许多不同的上下文中使用，包括： ( 1 ) a l e xc h a f f e e 的x p a t h e x p l o r e r 、a l t o v a 的x m l s p y 之类的专用查询工 具。 ( 2 ) a p a c h ex m lp r o j e c t 的x l n d i c e 、x h i v ec o r p o r a t i o n 的x - h i v e d b 与 s o f t w a r ea g 的t a m i n o 等自然x m l 数据库。 ( 3 )作为其它更广泛语言的组件，如x s l t 与x q u e v y 。 ( 4 )作为读取x m l 文档的j a v a 、n e t 程序中的搜索组件。 基于j a v a 的开放源代码) ( p a m 引擎包括： ( 1 ) s a x o n8 x ( h t t p ：s a x o n s o u r c e f o r g e n e t ) ：m i c h a e lk a y 编写的速度很 快的x p a t h 引擎，基于m o z i l l a 公用许可证发布。 ( 2 ) x a l a nj ( h t t p ：x m l a p a c h e o r g x a l a n - j ) ：包括c o c o o n 在内的几个 a p a c h e x m l 项目使用的x p a t h 引擎，基于a p a c h e 许可证发布。 ( 3 )j a x e n ( h t t p ：j a x e n o r g ) ：一个独立的x p a t h 实现，适用于d o m 、 j d o m 、d o m 4 j 与e l e c t r i cx m l 。 ( 4 )c o m m o n s - j x p a t h 一1 1 ( h t t p ：，j a k a r t a a p a c h e o r e o m m o n s i n d e x h t m l ) ： 提供了用于搜索j a v a b e a n s 、d o m 、x m l 的a p i ，基于a p a c h e 许可 6 哈尔滨工程大学硕士学位论文 证发布。 1 2 2 2x q u e r y x q u e r y 查询语言工作组于1 9 9 9 年9 月正式成立，其任务是创建一种灵活 的查询语言，以便从x m l 文档中抽取数据。目前w 3 c 所公布的最新x q u e r y 草案是2 0 0 3 年1 1 月1 2 日的版本，它还在不断的修订和完善之中【”。x q u e r y 被 设计为在多种x m l 数据源中广泛适用的查询语言，同时又简洁、易于理解和 有足够灵活性。而且，x q u e r y 还具有从多种数据库中检索信息的能力，它能 对各种数据和文档进行查询。它被看作是x m l 时代的主流查询语言，其地位 和作用如同s q l 对于关系数据库的作用。目前，数据库业界的三大主流厂商 o r a c l e 、i b m 和m i c r o s o f t 都已经在各自的产品中提供了对x q u e r y 规范的支持。 另外，s a x o ni 擎以及x h i v e 仍b 、t a m i n o 等n a t i v ex m l 数据库也都支持 x q u e r y 查询。 x q u e r y1 0 以x p a t h2 0 为基础，而x p a t h2 0 是对x p a t h1 o 的增强，这具 体体现在以下五个方面： ( 1 )支持序列：x p a t h1 0 通常返回节点集，而x p a t h2 o 则返回序列。与 节点集不同，序列是有序的节点集合。 ( 2 )支持更多的数据类型：x p a t h 2 0 除了包含节点集、字符串、数值和 布尔型四种数据类型外，还支持用户自定义的数据类型。 ( 3 )增强的函数集：x p a t h1 o 的函数种类只有4 类，而x p a t h2 0 的核心 函数库定义了1 6 类函数，并允许用户自定义函数。 ( 4 )支持多数据源：x p a t h2 0 能够显式地设置表达式的数据源，从而可 以将多个数据源中的数据合并到单个查询中。 ( 5 )支持更多类型的表达式：x p a t h2 0 的表达式种类远比x p a t h1 0 的丰 富。除传统的x p a t h 定位路径表达式外，还添加了一些新的表达式， 如：f l o w r 表达式、序列、构造器等等。 x q u e r y 遵循一定的查询结构。一个完整的查询包含两个部分：查询序 言( q u e r y p r o l o g ) 和查询体( q u e r y b o d y ) 。查询序言包括一系列处理查询 体的环境定义声明；查询体是待求值的一段查询表达式，是x q u e r y 的主体 部分。当查询体需要用到名字空间、模式信息或函数时，就需要在查询序 言部分中声明【9 】。 7 哈尔滨工程大学硕士学位论文 x q u e r y 表达式是x q u e r y 中的基本构造块，是x q u e r y 查询的基础。 x q u e r y 定义的表达式由关键字、符号以及操作数组成。通常，表达式中的 操作数也是表达式。x q u e r y 是函数化的语言，它允许多表达式的嵌套。同 时，x q u e r y 也是一种强结构化的语言，表达式中的操作数、算子和函数必 须遵循已经定义好的模式。x q u e r y 中共有七种表达式【l o 】：p a t h 表达式、构 造器、f l w r 表达式、包含算子和函数的表达式、条件( c o n d i t i o n a l ) 表 达式、量词( q u a n t i f l e d ) 表达式以及检查和修改数据类型的表达式。 f l w o r 语句是x q u e r y c p 最接近s q l 语言的语句，使用该语句可以更自然 地创建特定的查询。名称“f l w o r ”暗示关键字f o r 、l e t 、w h e l - e 、o r d e r b y 和r e t u r n 。f o r 和l c t 子句生成一个绑定变量的元组序列，称为元组流( t u p l e s t r e a mo 可选的w h e r e 子句用来过滤元组流，保留某些元组并删除其余的元 组。可选子句o r d e rb y 可用来对元组流重新排序。r e t u r n 子句构造f l w o r 表达 式的结果。f l w o r 表达式的结果是一个包含这些计算的连接结果的序列。 1 2 3 全文检索技术 1 2 3 1 中文全文索引和检索技术 英文全文索引与检索技术在许多检索系统中已经应用多年，而中文全文 检索的研究历史则相对较短。两者既有相似之处，又有所不同。 中文全文索引和英文全文索引之间的主要区别是如何确定索引单元 i ”。 这种差别是由汉语本身所造成的。首先，汉语词与词之间不像英文那样有空 格，没有明显的切分标记。其次，迄今为止仍没有一种公认的、确切完备的 汉语分词手段。这个现实导致对汉语文献的全文索引比英文的要困难得多。 另外，汉语中的新词也在不断增加，为基于分词的全文检索手段的应用带来 了困难。 从理论上讲，信息检索是以概念为基本单元，词是概念的基本组成部分。 中文跟英文一样，词也应当是最基本和最小的检索单元。但是，中文构词方 法的复杂性使得人们难以构造一个完全准确、合理的分词机制，因此查全率 直是分词算法难以解决的问题，影响了基于分词的中文全文检索系统的可 靠性。 近年来人们把汉字文本的检索放在单字一级的基础上，以绕开词的切分 哈尔滨工程大学硕士学位论文 问题。所谓单汉字检索系统，就是依据单字的位置信息进行检索的方法。其 索引库的主要部分是每个字的位置信息。建立字索引时，需要扫描整个源文 档，并对出现的每个有效汉字，计算其在文档中出现的位置，并将该位置的 值加入到对应的字索引库中【l ”。当检索一个中文词时，可以根据其中所包含 的每个单字在某个文档中的出现位置是否相邻为依据，确定词语在文档中是 否出现。 以单个汉字为单位建立索引的单汉字索引技术绕开了自动分词的处理障 碍，为全文检索系统的实现提供了一条新思路。， 1 2 3 2 全文索引模型 目前主流的全文索引模型有倒排索引( i n v e r t e d i n d e x ) 、署名文件、位图、 和p a t 数组( 也称s u f f i x 树) 。此外，有人还提出了一些新的全文索引模型， 但就目前来说倒排索引模型的综合性能较好，且应用最为成熟。 倒排索引是从书目索引中受到启发而派生出来的，它也是现在应用最广 泛的全文索引模型 1 3 - 1 7 】。传统的倒排索引由一系列“单词一指针”对组成。单 词实际上是索引的查找键，包括文本集中出现的所有单词( 除无用词外) 。指 针是该单词在文本集中出现的所有位置。因此，由倒排索引可以很快地得知 一个单词在哪些文档的哪些位置出现。随着全文检索技术的广泛应用，出现 了基于单字的倒排索引方法，有效地解决了分词难的问题【1 1 , 1 2 】。 基于单字的倒排索引的结构如图1 3 所示： ( 1 )字表中按汉字的内码顺序保存所有汉字的倒排索引地址。该地址指 向倒排索引文件中该单字的相关记录。 ( 2 )倒排索引文件中记录每个字在整个文档数据库中出现的位置信息。 这些信息组成的动态序列为： 。 9 哈尔滨工程大学硕士学位论文 字表文件倒排索引文件 r 一一一一一一一一一一一- 字1 频度位置文档号1 组数位置1 位置2 下一个记录指针 一 字2 频度位置 涉 文档号2 组数位置1 位置z 下一个记录指针 字3 频度位置文档号3 组数位置1 位置2 下一个记录指针 字4 频度位置文档号4 组数位置1 位置z 下一个记录指针 文档号5 组数位置1 位置2 下一个记录指针 _ 。一 文档号6 组数位置1 位置2 下一个记录指针 电 文档号7 组数位置1 位置2 下一个记录指针 o 文档号8 组数位置1 位置2 下一个记录指针 。一 l 字n 频度位置l 英文词词表 词1 频度位置 词2 频度位置 过j j 词3 频度位置 、 1 文档号p 组数位置1 位置2 下一个记录指针 词4 频度位置 1 文档号q 组数位置l 位置2 下一个记录指针 词m 频度位置 i丰索引立件 ： i文档号1 文件路径索引日期 ： i 文档号2 文件路径索引日期 ： i 文档号3 文件路径索引日期 ： i ： ( 3 )主索引文档中主要记录所有文档的文档号、路径、索引日期等信息。 利用上述结构的倒排索引，对某个词进行检索时，采用如下步骤： ( 1 )将检索词划分成多个单字w l w 2 w 。； ( 2 )对每个单字查询其出现位置； ( 3 )如果w i + i 的某个出现位置= w i 的出现位置+ 1 ，则对应文档为所要检 索的文档。 1 2 3 3 倒排索引的压缩技术 由于倒排索引文件中存储的是每个字符在各个文档中出现的具体位置， 1 0 哈尔滨工程大学硕士学位论文 而不是段落号或行号，所以倒排索引的空间开销与原文基本相当甚至更大。 如何通过压缩技术减少倒排索引文件的大小，同时又不影响检索效率，是倒 排索引的一个研究热点。 目前得到广泛应用的g o l o m b 压缩编码是在1 9 6 6 年首次提出的【l8 1 ， g a l l a g e r 和v a nv o o r h i s 1 9 1 在1 9 7 5 年发展了这种方法。随后，e l i a s 在1 9 7 5 年口o 】 描述了丫编码和d 编码，它们是两种有效的索引压缩方法。1 9 7 8 年t v h o l a 首先 描述了变形贝努里模型，1 9 9 6 年m o 肋t 和s m i v e r 提出内插编码【2 l 】，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 2 】。1 9 9 7 年c h i u e n 及2 0 0 0 年n a v a r r o 提出了利用倒排文件字典作为压缩字典的压缩技术【2 3 。4 】。国 内的赵鹏等人提出了一个基于块地址索引的全文本数据库倒排压缩索引结构 b a i c ，并在此结构上设计出了一些查找算法来获得更好的查找性【25 1 。以上一 系列的工作大大提高了倒排索引的空间利用率。 1 2 3 4 倒排索引动态更新 现实生活中，很少有文档集合保持一成不变的检索系统。恰恰相反，人 们对检索动态文档集合的要求日益迫切。为顺应这一需求，实现索引的动态 性成为全文检索技术的一个必然要求。人们希望倒排索引能够象许多数据库 中的动态索引一样，自如地应对文本的频繁增加、删除等操作。关系数据库 能够胜任数据的频繁变化，得益于索引的基本数据单位小，以及使用了b 树 这类动态索引。关系数据库索引列的总长度往往有限制，如：s q l s e r v e r 2 0 0 0 中索引列的总长度最大为9 0 0 字节。而全文检索处理的基本数据单位是文本， 文本大小相差悬殊，小到几字节，大到上g 字节。 修改文本可看作删除后再进行添加，因此不单独讨论。对于删除文本， 目前的做法多是加删除标记，这是个相对简单快速的过程。对于同样的新文 本集，为其另外创建一个新的索引的速度往往高于在一个已有的索引上添加 这些文本的索引，因此以m i c r o s o f ti n d e xs e r v e r 为代表的大多数全文检索系 统均采用为新文本创建l 临时索引，然后定期将i 临时索引与原有索引合并的方 法。这种方法实现虽然简单，但会降低检索速度，特别是当临时索引积累到 一定数量时，查一个词时要寻遍所有的索引后求并集。 全文索引的动态更新是目前相对较薄弱的环节，倒排索引存在动态调整 效率低的问题。首先，由于倒排表记录的都是绝对位置，因此文本内部的任 哈尔滨工程大学硕士学位论文 何改动，都会改变后续文字的绝对位置，导致大量索引数据的变动。其次， 倒排表还会引发大量索引数据的移动，由于对空间效率的过分追求，倒排索 引几乎都采用紧凑的存储方式，因此动态调整时的移动开销很大。 对全文索引的动态更新的研究，比较有影响的有a m i r 幂l f a r a c h 等提出的 动态词典方法【2 6 如。t h a w 和b o s w e l l 等提出了b + 树与散列函数相结合的方法 2 s j 。c u t t i n g 等人提出在倒排索引的基础上建一b 树 2 9 1 ，来支持倒排索引的 插入和删除。a n t h o n yt o m a s i e 等人针对倒排索引的文档插入提出的 d u a l s t r u c t u r ei n d e x 结构【3 0 】，能够动态地区分长、短倒排列表，并针对长、短 列表采用不同的检索、更新和存储策略。2 0 0 4 年l e s t e r 将全文索引的更新方法 归为三类：重建、即时更新和再合并，并分析对比了三者的性能差异【3 ”。另 外国内的杨成明提出了针对倒排索引的双层b + 树结构【3 2 】。贾崇等人实现了 一种支持高效检索及即时更新的倒排索引，它支持即时增量索引，即对新加 入的文档可以立即加入索引，且不用重新对原内容进行重索引，并且在更新 索引时不会影响查询的进行【3 ”。吴恒山等人提出了一种新的基于可扩展散列 表的倒排索引更新策略，使倒排索引具有良好的可扩展性。它既支持文档的 插入、删除操作，又具有较高的查询效率和空间利用率。并在它的基础上， 实现了倒排索引的增量更新和实时更新【”】。 1 2 - 3 5 智能全文检索 随着w w w 网中信息量呈指数的增长，人们可以使用许多的信息收集工 具来获得网络中的信息。但要使检索到的信息在满足用户个性化需求方面， 即具有高准确率又有高回收率，则是一件很困难的事情。为了解决以上问题， 国内外众多学者将人工智能的相关技术应用于全文检索方面，取得了良好的 效果。人工智能用于信息检索主要有基于人工神经网络的信息检索、基于遗 传算法的信息检索以及基于本体论的信息检索等等。 人工神经网络可以模拟人脑神经系统的结构和功能，运用大量的处理单 元经过广泛的互连，能够较好地模拟人的形象思维，具有大规模并行协同处 理能力、较强的学习能力以及较强的容错能力和联想能力【3 5 】。文献【3 6 】提出了 一种新的搜索引擎的设计思路，把信息检索从基于关键词层面提高到基于知 识( 或概念) 层面，并且利用b p 神经网络的高度非线性特点来进行概念的表 示和计算，并引入相应的反馈机制，以达到提高信息检索的检准率和用户间 1 2 哈尔滨工程大学硕士学位论文 的交互功能。 在基于遗传算法的信息检索方面的研究，国际上已经有了一些研究成果， 例如文献 3 7 】中介绍了对用户模型的提取的方法，文献 3 8 n | j 提出了基于用户 模型的信息检索算法，结果也都非常有效。国内的徐斌等人在现有的搜索引 擎的基础上，利用遗传算法方法实现一个客户端代理系统，并通过用户对少 数几篇检索结果的评分，提取出用户的兴趣模型3 9 1 。张敏等人在大规模标准 测试集合上对经验值设定参数的泛化能力进行实验考察，进一步提出了检索 模型的可信性假设和检索结果的区分性假设，并以此为基础提出两种基于文 档和查询相似关系的适应函数：初次检索结果中前n 篇文档的相似度均值和相 似度方差值，然后通过时用遗传算法，给出一种基于无指导学习的检索系统 参数动态调节方法，使得系统参数自动学习问题得以解决【帅】。 近来“本体论”( o n t o l o g y ) 的研究成为计算机及信息处理领域的热点，它 的一个简要的定义是：本体论是包含各种术语、这些术语的定义以及这些词之 间各种关系的说明的一个系统。o n t o l o g y 的目标是捕获相关领域的知识，提 供对该领域知识的共同理解，确定该领域内共同认可的词汇，并从不同层次 的形式化模式上给出这些词汇( 术语) 和词汇问相互关系的明确定义【4 ”。目前 基于关键词的信息检索技术已经不能满足用户在语义和知识上的需要，由于 o n t o l o g y 具有良好的概念层次结构和对逻辑推理的支持，因此在信息检索领 域有广泛的应用。文献 4 2 】通过建立面向某一知识领域的o n t o l o g y ，并利用 o n t o l o g y 对用户的检索提问进行优化，提出了一个完整的信息检索与聚类的 模型x i i r c ，实现检索结果排序、聚类等。 除此之外，部分学者将模糊集理论、智能a g e n t 理论等应用到信息检索， 也取得了一定的成果4 3 郴】。 1 2 4x m l 数据库 x m l 数据库是一个支持x m l 文档的数据库，这些文档是持久的并且是可 以操作的。x m l 数据库不仅是结构化数据和半结构化数据的存储库，它也要 像传统的关系数据库或面向对象数据库一样，提供存储、修改、查询和删除 数据库中的x m l 文档以及元素的机制，还要具有维护数据的独立性、集成性、 完备性、一致性和访问权限的控制等功能【4 q 。 哈尔滨工程大学硕士学位论文 目前，x m l 数据库主要有两种类型：x m l 本源数据库( n x d ，n a t i v ex m l d a t a b a s e ，也称作纯x m l 数据库) 、支持x m l 的数据库( x e d b ，x m l e n a b l e d a t a b a s e ) 。n x d 是专门对x m l 文档进行存取管理和数据查询的数据库。x e d b 是在传统数据库的基础上，通过增加对x m l 数据的映射功能，从而实现对 x m l 数据的存取管理。x m l 数据库的主要用途可以概括为两方面：对x m l 数据进行有效的管理，提供数据查询和修改功能、对基于w e b 的各种数据源进 行集成【4 “。 1 2 4 1 支持x m l 的数据库 在这类数据库中，x m l 数据通常按传统数据库已有的数据模型来存储， 而不是按x m l 数据本身的模型。另外，这种数据库还为用户提供了访问x m l 数据的接口。常见的商业数据库，如s q ls e r e e v 2 0 0 0 、i b md b 2 、i n f o r m i x 、 o r a c l e 等等，都属于此类数据库。 支持x m l 的传统数据库管理x m l 数据的优点是可以直接利用传统数据 库的许多成熟技术，如查询优化、并发控制、安全管理以及事务处理等。但 是，其缺点也比较明显，这些缺点从本质上说都是由于x m l 数据模型与传统 数据模型之间的区别造成的。首先，从x m l 数据到传统数据模型之间的映射 过程中，由于x m l 数据本身是一种树型结构，使得将这种不规则的结构映射 到传统的关系模型或对象模型变得非常困难；其次，即使完成了上述映射操 作，但是在执行对x m l 数据的查询时，由于需要在x m l 数据之间建立众多的 查询连接，导致x m l 数据的查询效率受到严重影响；最后，由于x m l 数据在 数据库中并没有按照x m l 数据本身的数据模型存储，所以将查询结果按x m l 数据模型重构时，可能需要更多的时间，而且得到与源数据完全一致的结果 非常困难。 1 2 4 2x m l 本源数据库 x m l 本源数据库是专门为x m l 数据的存储和管理而设计的x m l 数据库 管理系统，除了包含存储、索引、查询等基本的数据管理功能以外，还包含 一般数据库的特点，如事务处理、并发控制、查询语言、安全机制、二次开 发接口等等。它与传统数据库的唯一区别是按树型结构存储x m l 数据，而不 是关系模型或对象模型。这类数据库管理系统包括l o r e 4 6 1 、x i n d i c e 4 引、 1 4 哈尔滨工程大学硕士学位论文 t a m i n o 4 9 1 、x h i v e d b 等等。 ， x i n d i e e 是i 扫a p a c h es o f t w a r ef o u n d a t i o n 开发的一个开源x m l 数据库管 理系统，当前的版本号为1 1 b 4 。它采用j a v a 语言编写，可以完成对x m l 文档 的存储、压缩、索引和检索等功能。它的主要特征包括： ( 1 ) x p a t h 查询引擎：可以使用x p a t h 查询x m l 文档，这种方式具有相 当的灵活性。 ( 2 )文档集合：在该系统中，x m l 文档被组织成若干个c o l l e c t i o n 的形式 存储。每当进行x p a t h 查询时，可以通过c o l l e c t i o n 的名称指定用户 要查询的x m l 文档集。 ( 3 ) x m l 索引：为了提高大量文档的查询性能，可以定义元素和属性 的索引。这可以极大的提高查询效率。 ( 4 )数据库更新：当存储x m l 到数据库时，可能需要不检索整个文档 的情况下改变数据。x u p d a t e 是类似于x l i n k 的x m l 数据库更新语 言，它允许对数据库进行查询时替换或增i j i x m l 数据库中的内容。 ( 5 )数据库a p i 实现：针对j a v a 程序员，x i n d i e e 提供了一个x m l ：d ba p i 的实现包。这个包中的a p i 会给x m l 数据库应用程序带来可移植 性。 ( 6 )命令行管理工具：为了帮助系统管理员，x i n d i e e 提供了一套命令行 驱动的管理工具。所有可以通过x m l ：d ba p i 完成的功能，也可以 通过命令行来完成。 ( 7 )模块体系结构：x i n d i c e j 艮务器是以模块化结构搭建的，这使得用户 易于增加或减少组成构件，使其成为一个特殊工作平台，或者将它 嵌入到另一个应用程序中。 和x i n d i e e 类似，其它x m l 本源数据库也提供了文档存储、查询引擎、索 引、命令行工具包等功能。只不过像t a m i n o 数据库，其规模更大，功能更加 丰富，应用也比较广泛。 虽然x m l 数据库具有了传统数据库所具有的特点，但x m l 数据库在有 效的存储组织、合理的索引结构、数据库系统的安全性、事务处理、数据完 整性、触发器、多用户处理机、数据的聚合能力等方面还有待提高 4 4 1 。 哈尔滨工程大学硕士学位论文 1 3 本文的主要工作 鉴于目前x m l 技术的应用和全文检索技术的发展现状，本文对基于倒排 索引的x m l 文档全文检索技术进行了研究。主要内容包括： ( 1 ) 分析了主流的x m