（计算机应用技术专业论文）面向web的xml检索关键技术研究.pdf

摘要 w e b 作为一个全球化信息空间，蕴含着海量的信息和知识。随着w 曲上资源的日趋丰富，各种基于 w e b 的信息检索服务应运而生并得到了迅速发展。实践证明，w e b 搜索引擎是一个非常有用的信息检索 工具。但对任一用户查询，搜索引擎都将返回成千上万个所谓的“匹配”文档，其中可能只有一小部分 与用户的查询目标有关，而绝大部分毫无关系。如何组织和消化如此大量的信息，一直是困扰着最终用 户的难题。如何帮助用户准确提出信息需求，并快速获得“满意”的查询结果，从而提高检索的效率， 一直是研究的热点。尽管目前有大量的研究工作关注于w e b 数据检索，但现有的技术还远不能令人满意。 目前x m l 已经成为表示w e b 上多样性数据的事实标准，可以预见w 曲上的数据将主要以x m l 形 式存在。x m l 规范的提出，使得信息的组织更加规范，使更准确的信息查询成为可能。随着x m l 获得 越来越广泛的应用以及w 曲技术的不断发展，如何检索w e b 上海量的x m l 数据受到学术界越来越多的 重视。在对目前国内外研究现状进行深入剖析的基础上，本文提出了一种面向w e b 的x m l 信息检索系 统解决方案，对其中的检索模型、文档聚类、索引以及检索等关键技术进行了深入研究。 本文的主要工作可以概括为以下几个方面 1 提出了检索模型x 2 v s m 。针对w e b 上x m l 信息检索的特点，本文对目前信息检索系统中应 用最广泛的信息检索模型一向量空间模型( v s m ) 进行了扩展，提出了适合x m l 的信息检索 模型x 2 v s m 。与v s m 中的关键词t e m 对应，加入相应的路径限定信息，提出了x t e n 的概 念：针对x m l 的元素嵌套的特点，提出逻辑文档的概念；提出逻辑x m l 文档和x m l 查询的 统一向量表示方法；定义了x t e 1 1 的权重计算方法，并给出了文档和查询向量的相似度计算方 法。x 2 v s m 支持对x m l 文档进行内容和结构查询，支持任意嵌套层次的元素作为返回结果， 还支持基于内容和结构相关性的查询结果排序，同时继承和保持了v s m 简单易用等优点。 2 研究了x m l 文档的聚类。分析和比较了直接和间接的聚类策略，在此基础上提出一种基于路 径信息的x m l 文档问接结构聚类算法p b s c 。它没有直接计算文档的结构距离，而是采用间接 聚类的策略。与其它基于编辑距离的算法相比，具有算法简单、效率较高以及聚类过程直观等 优点。聚类结果可用于用户导航以及提高检索的效果。 3 研究了x m l 的结构索引问题。提出一种基于广义后缀树的m 。结构索引p i g s t 。通过p i g s t ， 把对x m l 文档的路径查询转换为后缀树中的字符串匹配，显著提高了查询处理效率；对传统 的后缀树构建算法做了改进，使之能够用来创建由路径集合转换得到的字符串集合的广义后缀 树；提出了间接包含路径查询，即查询式包含子孙一后代关系( 含有“，”) 的高效处理算法。 p i g s t 的构造时间复杂度和空间复杂度是线性的，只与查询字符串的长度有关。 4 研究了查询处理算法。基于我们提出的x m l 信息检索模型x 2 v s m ，提出了一种支持x m l 元 素相关性计算的查询处理算法；对传统的倒排索引进行了扩展，提出了一种带d e w e y 编码的倒 排索引；结合结构索引p i g s t ，提出了一种高效的内容索引和结构索引的联合索引结构，以支 持对x m l 文档的检索及权重的动态计算；研究了路径的相似性问题，给出相应的计算方法， 并将其集成于查询处理算法x r a n k ，使x r a n l ( 不仅支持内容相关排序，同时还支持结构( 路径) 相关性排序。 关键词：w e b ，x m l ，索引结构，信息检索，文档聚类，检索模型 i i i a b s t r a c t a st h e9 1 0 b a l i n f o h n a t i o nm a 丽x w w wc o n t a i n sa l lk i n d so fd a t a ，i n c l u d i n gs t m c t l l r e d ，s e m i s t r u c t u r e d a n dn os t r u c m f e dd a t a m u c hr e s e a r c hh a sf o c u s e do nt h es t l 】d yo fw e bj n f o m a t i o nr e t r i e v a l h o w e v e li t s c u r r e n ts t a t u si ss t l l lf 打f 如ms a t i s f a c t i o no f w e bu s e r s x m lh a sb e c o m et h ed ef a c t os t m d a r dt or e p r e s e n td a t aj nw w wa 1 】di tp r o v i d e sau n i f b md a t am o d e l f o rw 曲d a t a1 ti sr e a s o n a b l et oi m a g j n et h a tm o s to f t h ed a t ao nw e bw j l lb ei nx m 巴，a st h er e s u l t ，r e s e a r c ho n x m l p l a yac r u c i a ir o 】ei nw e b i n f o m a t j o nr e t e v a l t h ed i s s e 九a t i o nf o c u s e so nt h e k e yt e c h n j q u e sf o rx m li n f b 邢a t i o nr e t r i e v a l i s s u e s t h em a i n c o n t r i b u t i o n so f t l l i sp 印e ri n c l u d et h ef 0 1 l o w i n g 1 x m la l i o w sr 印r e s e n t i n gb o t hc o n t e n ta 1 1 ds t r u 咖- l r eo fd o c u m e n t sa ni n f b m l a t i o nr e t r i e v a lm o d e lf o r x m lc a l 】e dx 2 v s mi sp r 。p o s e dw h j c hi sa ne x t e n s i o no f t h ew e l l l ( 1 1 0 w nr e 仃e v a lm o d e l ，v e c t o rs p a c e m o d e l ( v s m ) at e m li nv s m j sa d d e dw i t l l8p a t hs p e c m c a t i o nu n d e rw h i c hi ta p p e a r sa n di sc a 儿e da n x 1 色m w ee x t e n dt h ed e f i n i t i o no f t e mf r e q u e n c y ( t f ) a i l di n v e r s ed o c u m e mf b q u e n c y ( i d f ) t ot h en e e do f x m ls e a r c h o n l yt e m su n d e rs p e c m e dp a t l l sa r ei n v o l v e di nt 1 1 ec a l c u l a t i o no ft f sa 1 1 di d f s b o t ht f sa 工l d i d f sa r ec a l c u l a t e dw i mr e s p e c tt 0t l l eq u e r i e sd ”a 1 1 1 i c a l 】yw ed e 行n et h ew e i g h to f x t e n i la n dr e p r e s e n t b o t l lx m ed a t aa 1 1 dq u e r i e sa sw e 适h tv e c t o r s w ea l s od e n n et | l es i m i l 积t yb e t w e e nx m ld a t aa n dq u e 而e s w i t hx 1 色mq u 鲥e s ，w ec a r ii n q u i r eb o t h 蛐m c 如r a la n dc o n t e n ti n f o r m 8 n o no fx m l r e r u m i n gr e s u l t s c a nb ew h 0 1 ed o c u m e n t so re l e m e n t sw j t hr e l e v a l 】c er a n k i n gs c o r e 2 w ei n v e s t i g a t e 也ep r o b l e mo fx m ld o c u m e n tc l u s t e r i n ga 1 1 dp r e s e n tan o v e l 印p r o a c hc a l l e dp a t h - b a s e d c l u s t e r i n g ( p b s c )i n s t e a do fc o m p a n gx 匝d o c u m e n t ss t n 】c t l l r ea n dc l u s t e r i n gt h e md i r e c t ly ，w e c 】u s t e rt h ep a t h sc o m a i n e di nt h e s ed o c u m e n t s f o re a c hp a t h ，w ef o r mac l u s t e rc o n t a i n i n gd o c u m e m st h a t h a v em a tp a t h a f t e rt h a t ，w ec o m b i n ec l u s t e r st l l a tc o n t a i ns i m 玎a rs e t so fd o c 岫e n t s t h er e s u l h n g c l u s t e r sw i l lc o n t a i nd o c u m e n t st h a ts h a r eas j m i l a rs e to fp a t h s c o m p a r e dt 0e d i td i s t a l l c eb a s e d 印p r o a c h e s ，p b s ci sm u c hm o r ee 衔c j e n t 3 t h i sp 印e rp r o p o s e sa ni n d e xs t r u c t i l r eb a s e do ng e n e 删i z e ds u 币xt r e e 口i g s t ) a n dp r e s e n t saq u e r y e v a i u “0 na l g o r i t h t h ed i s t i i l c tp a t h si na nx m lc o l l e c t i o na r em a p p e di 1 1 t os 砸n g s t h ec o n s 仃u c t i o n a l g o r i t h mo ft h ep i g s tf o rt 1 1 ep a t hs t r i n g si sp r e s e m e db a s e do nt 1 1 em o d m c a t i o na 1 1 di m p r o v e m e n to fa w e l l - k n o w ns u 茄x 订e ec o n s t 兀l c t i o na l g o r i t | l mt h a to n l yr e q u i r e sl i n e a rt i m ea 1 1 ds p a c ec o m p l e x j t yt h e q u e r yp r o c e s sm e r e l yn e e d s 坍c h a r a c t e rc o m p 撕s o n sf o rd i r e c tc o n t a i 衄e n tq u e r i e s ，w h e r e 肌i st h e1 e n g h o faq u e 呵s 盯i n ga ne 面c i e n tp r o c e s s i n gm e t h o df o r 协ej n d i r e c tc o n t a i n m e n tq u e 订e st h a ta v o i d s t h e i n e 币c i e n tt r e et r a v e r s a lo p e r a t i o ni sa l s op r e s e n t e d 4 w ep r o p o s eac o m b i l l e di n d e xs 廿u c t u r eo fp a t hi n d e xa 1 1 dc o n t e n ti n d e x w eu s ei 1 1 v e n e df i l e se x t e n d e d w i t hd e w e ye n c o d i n gt os t o r et h ec o m e n ti n d e x b a s e do no u ri n d e xs t r u c t u r e ，a na i g o t l mc a l l e dx r a r 出 i sp r o p o s e dt op m c e s sq u e r i e s t h es i m i l 抓t yb e t 、v e e np a t h si si n v e s t i g a t e da 1 1 d 廿l es i m i l 撕t ym e a s u r e m e n t i si m e g r a t e di m ox r a n kt h u s ，x r a n kn o to n l ys u p p o r tc o n t e n t - b a s e ds i m i l a r i t ys e a r c h ，b u ta l s os u p p o r t s t r u c t u r e ( p 8 t | 1 ) b a s e ds i m 钉a r i t ys e a r c h k e y w o r d s ：w e b ，x m l ，s c h e m a li n f o m l a t i o nr e t r i e v a l ，d e w e yi d ，s u 衔xt r e e 】v 论文插图目录 图1 1x f i n d e r 系统框架 图2 1x m l 应用分类 图2 2x m l 文档 图23 x m l 文档树 图2 4x m l 文档片段 图3 】信息检索模型的分类 图4 1x m l 文档集合1 图42x m l 文档树集合 图4 3 x m l 文档集合2 图44 x m l 文档集合3 ， 图4 5x m l 文档集合4 图4 6 文档向量 图4 7 算法p a t l l e x t r a c t i o n 一 图4 8 算法m a l ( e m a 埘x 图4 9 聚类结果 图4 1 0 p b s c 和直接文档聚类方法的计算时间比较 图4 i 】p b s c 和x y d i f r 的计算时间比较 图5 1 “b a n a n a s ”的后缀t r i e ， 图5 ，2 字符串“b a n a n a s ”的后缀树 图5 3 “b a n a n a ”的后缀树 图5 4 带后缀链( 虚线) 的字符串b a b a c 的后缀树 图5 5 边的数据结构 图5 6 后缀数的据结构 图5 7 后缀树构建算法 图5 8 字符串“t h e d o g ”和“t 1 1 ec a t ”g s t 的生成过程中的结点分裂 图5 9p l a y d t d 图5l o 三条路径的p i g s t 图5 1 1 存储空间 图51 2 查询处理时间 图51 3x m l 数据 图5 1 4 倒排索引 图5 1 5i c q 处理时间。 图6 1 传统倒排索引 图6 2 x m l 文档树 图63d e w e yi d 图6 4 带d e w e y i d 的倒排索引 图6 5x m l 文档集合 图6 6 联合索引 图67 算法x r a n k 图6 8 x 1 1 e r r n 检索和t e n n 检索的返回结果 v i i r 一坦b h加丝勰凹如如让弛扔m舶撕眚!舫m躬舭甜舶胛m册鼬邡埘m曲觏 表4 1 测试数据 表4 2 聚类实验数据集 表5 1 元素字符映射表 表6 1 样例路径 表6 2 内容索引尺寸比较 表6 3 样例查询 论文表格目录 - 3 4 3 5 4 6 5 7 6 0 6 2 v i i i 东南大学学位论文 独创性声明及使用授权的说明 一、学位论文独创性声明 f 飞尸 出 9 二3 8 6 l 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知， 除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 二、关于学位论文使用授权的说明 签名秒鹇 日期： 2 0 0 5 年9 月 东南大学、中i 雪科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电子文 档，可以采用影印、缩印或其他复制手段保存论文。 在保密期内的保密论文外，允许论文被查阅和借阅， 的公布( 包括刊登) 授权东南大学研究生院办理。 本人电子文档的内容和纸质论文的内容相致。除 可以公布( 包括刊登) 论文的全部或部分内容。论文 签名 导师签 绷 名：拗 日期： 2 0 0 5 年9 月 第一章绪论 第一章绪论 s ow e 。v eb e to u rc o m p a n yo nx m lt h es a m ew a yw eb e tad e c a d ea g oo n 日a p h i c si n t e r f a c ea n dt h e r e s b e e ng r e a tp r o g r e s sa r o u n dt h i s w e 。r er e b u i l d i n ga | lo f o u rs o n w a r e w i n d o w s ，s q l ，o 塌c e ，p r o j e c t a r o u n d x m la st h ek e yd a t at y p ef o rt l j se a s y e a s ye x c h a 兀g e ” 一m l c r o s o 竹b 川g a t e s 本章从信息检索技术的发展历史出发，论述x m l 技术和w e b 技术给信息检索带来的机遇和挑战， 追溯面向w e b 的x m l 信息检索技术问题的由来，分析现有的解决方案存在的不足，概要地介绍我们的 研究方案，并给出论文的研究内容，最后简要介绍获得的研究成果和论文的组织结构。 1 1 研究背景 w e b 信息检索技术是计算机信息检索技术和w e b 技术发展到一定程度的产物，它受w e b 技术和信 息检索技术的共同驱动。在研究面向w e b 的x m l 信息检索技术之前，有必要对影响w e b 信息、检索技术 发展的w e b 技术和信息检索技术进行简单的回顾和分析，以便踢确w 曲信息检索技术发展的内在和外 在动力，发现w e b 信息检索技术发展的规律和前景。 1 1 1 信息检索技术的发展 纵观计算机信息检索技术的发展，可以将其划分为四个阶段： 第一阶段1 9 7 1 年以前建立了许多信息检索系统，并取得了一定的进展。其工作方式是传统的批处理 检索方式。如1 9 5 4 年美国海军兵器中心( n o t s ) 图书馆在i b m 7 0 1 型计算机上成功建立的世界上第一 个计算机文献检索系统。这一阶段的数据存取与数据通信能力都比较差。 第二阶段1 9 7 1 年以后，产生并发展了联机情报检索系统。其中，美国国家医药图书馆中心建立的在 线计算机国书馆中心o c l c ( o h i oc 0 1 1 e g el i b r a 呵c e n t e r ) 、s d c 公可建立的s y s t e md e v e l o p m e n tc o m p a n y 及l o c k h e e dc o r p o r a t i o n 的d i a l o g 系统都是在线商用数据库查询( 本文中，查询与检索意义相同) 系统。 这一阶段的特点是联机数据库集中管理，具有完备的数据库联机检索功能，但其数据通信能力较差。 第三阶段以j n t e m e t 的出现为标志。系统大多采用分布式的网络化管理，其信息资源的主要特点是： 数字形式表达、多媒体和载体多样化、内容覆盖各个社会领域、分布无序、难于规范化和结构化、内容 特征抽取复杂、用户界面要求高等。这些特点导致了信息处理从传统模式向新型模式的转变，如体系结 构从终端主机方式到客户服务器结构方式，网络环境从局域网到i n t e m e t 等开放网，应用接口从封闭界 面到v 邢唧，和z 3 9 5 0 ，信息结构从结构化到非结构化，系统功能从单纯信息检索到综合信息管理和服务 等等，其中较著名的系统有a l t a v i s t a 、m o o ! 、w e b c r a w 】e r 等。 第四阶段在前三个阶段的基础上，随着语义w e b 和自然语言处理技术的不断发展，预计计算机信息 检索系统将会跨入一个新的阶段。 东南大学博士学位论文 我国计算机全文检索起步于8 0 年代初期，并在计算机编制主题词表、汉语自动分词和标引、数据库 建造、情报检索和相关软件的研制、联机检索、机器翻译、图书馆业务管理、全文检索理论等主要领域 取得了很大进步。在微机工作平台上，目前已建立了十几种中英文检索软件，其中比较著名的有易宝北 信的t r s 、北大方正的m i r s 、中国百科术语数据库和海文q u 】c k 等。这些全文检索系统软件在建库、 检索方法、检索速度、检索准确性等方面各有千秋，多适于单机用户使用，有的也采用了客户朋务器 方式。 由于汉语语言的独特性，十几年来，我国的计算机信息检索基本上仍以传统的顺序检索或顺序检索 与倒排文档相结合的检索方法为主，局限于以传统人工赋词标引方法为主的目录或摘要二次文献，以及 以词检索为主的全文检索系统，这与国外的信息检索系统有一定的差距。 目前，信息检索技术正向两个方向发展。一是传统信息检索向全文文本、多媒体等新型信息检索发 展，在深度上应能对提问的内容进行分析和理解，提高查准率，探索自动抽词、自动索引、自动检索、 自动文摘、自动分类、自动翻译等解决方案，提高管理和组织信息的能力；二是信息资源的网络化和分 布化，面对i n t e m e t 中浩瀚无垠的资源，提高查全率。基于概念的信息检索系统与超文本网络信息检索 系统对以上方面进行了一些研究，作出了新的贡献。 1 1 2w e b 技术发展为信息检索带来新的挑战 在当今信息时代，互联网的迅速发展改变了人们的生活和工作方式，而这其中w e b 起到了关键性作 用。w 曲采用超文本、超媒体的方式进行信息的存储与传递，能把各种信息资源有机地结合起来，具有 图文并茂的信息集成能力及超文本链接能力的信息检索服务。 随着i n t e m e t 的发展，w e b 上的资源在不断丰富，基于i n t e m e t 的各类信息检索服务应运面生并得到 了迅速发展。目前常用的信息查询技术有基于超文本的信息查询、基于目录的信息查询以及基于搜索引 擎的信息查询。现在发展最迅速的是基于搜索引擎的信息查询方式，在互联网上出现了许多著名的搜索 引擎，如y a h o o 、e x c i t e 、l o y c o s 、a 1 t a v i s t a 等。实践证明，w e b 搜索引擎是一种非常有用的信息检索工 具，但是对任一用户查询，搜索引擎都将返回成千上万个所谓的“匹配”文档，其中可能只有一小部分 与查询目标有关，而绝大部分毫无关系( 据统计，7 5 的信息是与用户的信息需求无关的 2 7 ) 。如何组 织和消化如此大量的信息，对最终用户来讲是件非常困难的事情，而且一个特定的搜索引擎主要包含某 一特定领域的信息。现在有些搜索引擎，如y a h o o 、i n f o s e e k 等，提供了这样的功能，当用户没有找到 合适的信息时，可以转向其它搜索引擎，它只是提供了一种将用户导向到其它搜索引擎的方式而已。基 于现有搜索引擎的元搜索引擎的研究，国内夕卜已经出现了如m e t a - s e a r c h 、i n q u i n l s 等元搜索引擎，这类 搜索引擎的优点是返回结果的信息量更大、更全，缺点是不能够充分利用所调用的搜索引擎的功能，对 返回的大量结果，用户需要做更多的筛选。 1 1 3x m l 为w e b 信息检索带来新的希望 x m l 1 提出的目的之一就是为了提高信息检索的效率和准确率，方便w 曲上信息的交换和获取。 x m l 文档由一系列元素组成，其元素遵从用户定义的层次结构关系。每一个元素有一个用户指定的元素 名称，比如p 表示段落。元素的数据或者位于元素的开始标签和结尾标签之间，或者作为元素的属性出 2 第一章绪论 现。例如元素p 的数据可位于其开始标签 庐和结尾标签 之间，也可以以属性 的形式出 现。一些特定的属| 生类型被保留，用来表示信息的引用关系，例如i d r e f 。访问x m l 元素的典型方式是 使用x p a t h 语言，孩子元素和父亲元素之间用斜线隔开。例如查询x p a t h h e a d e r a u t h o r f l r s t 首先访 问根元素 幽然后是孩子元素a u 曲。，最后是元素疗”f 。 x m l 并不是唯一标记语言，但是) ( m l 以其建模简单、适用面广等特点迅速被广泛采用。h t m l 与x m l 同为s g m l 的子集，但h t m l 关注的是信息的表现，它使用统一定义的标记来描述信息对用户显示的外观。 在使用h t m l 标记信息的文档中，信息被组织在一定的结构中，但这个结构描述的只是信息的表现，缺乏 对信息含义的表达能力。与h t m l 不同，在x m l 中，用户可以自由定义标签和嵌套的结构，将注意力放在 信息内容的结构上，而不是信息的表现形式。在这种使用用户自定义标签的文档中，比较清楚地表明了 信息内容上的组织结构、各部分之间语义上的联系。与h t m l 相比，x m l 另一个明显的优势在于用户可以 定义自己的标签。这些有特定含义的标签名称有以下功能：或者标明内容的语义，或者标明内容的类型。 通过使用元素名称，就可查囱内容的某些语义，为查询提供某种主题限定。虽然s g m l 比x m l 的适应面更 广，但是x m l 更简单、易用、容易部署。而且，s g m l 的复杂性对绝大多数的信息检索问题没有帮助。此 外，目前市场上，已经有一系列应用广泛的工具支持) ( m l 的显示、格式检验及与数据库的相互转换等， 如浏览器、样式表、解析器。与s g m l 相比，l 较容易实例化，已经在许多信息检索系统中得到使用。 例如，基于移动客户端的w e b 信息检索系统 1 7 已经使用晰l ( w i r e l e s sm a r k u pl a n g u a g e ) ，一种由埘l 衍生的标记语言，来实现移动业务。与其它一些私有文档格式如m sw o r d 或a d o b e 相比，x m l 是一种开 放的并支持多语言的文档格式。 具体来讲，x m l 将为信息检索带来如下影响： 1 x m l 标记明确表达了部分语义。搜索引擎就可以根据关键词和内容之间的依存关系，进行准确定位， 从而根据用户提交的关键词，返回正确的结果。 2 辨别模糊语义。由于自然语言的词汇常常具有多义性，采用x m l 技术，就可以根据上下文关系确定 查询关键词的确切含义，从而提高查询准确率。 3 利用结构信息提高相似性计算效果。可以利用x m l 提供的结构信息对检索结果作相关性排序。 4 查询各种类型的数据。x m l 表示的文档很容易实现对如数值数据、地理位置、温度等非文本数据的 检索，而通常这些很难作为关键词来使用。 5 信息集成的灵活性。x m l 有助于异构信息源的集成，有助于灵活方便的进行复杂和自动的信息组织和 处理。 概括的讲，由于具有结构化、自描述以及带有元数据( 例如r d f ) 等特点，l 的出现使基于上下文或 类别的搜索成为可能，为实现更精确的信息裣索带来了希望。并且瑚l 具有集成异构数据模型的能力， 可以将将数据库信息和文本信息集成在统一的数据模型下，从而使得搜索引擎能够处理异构文档或数据。 也就是说，它的出现和使用，使世界上最大的信息源一w e b 中的信息更易于被检索和利用。 3 东南大学博士学位论文 1 2 研究现状 本论文研究的主要目标是w e b 上的x m l 文档检索所涉及的关键技术。本节将在研究和总结现有的x m l 检索系统的基础上，分析现有解决方案及其不足，总结出需进一步研究的问题，在此基础上提出论文的 解决方案。 1 2 1 现有的解决方案及存在的问题 目前的x m l 检索系统有许多，我们将它们分为三类讨论，即数据库方式、信息检索方式和混合方式。 1 数据库方式 这种方式是指将x m l 数据转换为数据库的数据，然后通过数据库检索技术来实现对x m l 的检索。数 据库的成熟技术和优越的性能为煳l 的存储提供了基础：数据库通常可以处理海量的数据信息，允许多 个用户同时处理信息，支持版本控制和不同级别的安全访问控制等。基于瑚l 模式来进行文档到数据库 的映射，目前已有的一些方法基本上是通过文档所遵从的d t d 来进行。目前的d t d 在数据和引用完整性 限制方面非常不完备，当) ( i l 文档被输入到数据库系统时可能会引起问题。为了克服这个问题，w 3 c 起 草了文档内容说明d c d s 8 3 及x m ls c h e m a 8 4 ，以处理更加严格的数据类型限制。除关系数据库外，还 可使用面向对象数据库来存储和检索x m l 文档，例如e x c e l o n 公司 8 5 在其数据库产品o b j e c t s t o r e 中 就使用了面向对象数据库技术来索引和检索脚l 文档。面向对象数据库的一个问题是其使用公共索引来 索引层次编码签名 8 6 ，8 7 ，可能会导致误查。另外一个难题是列l 文档可来自不同的数据源，将这些 文档转换到一个面向对象数据库的时候，难免会出现命名冲突。 2 信息检索方式 可使用信息检索技术来查询x m l 文档，它将每个文档看作是添加了标注标签信息的文本文档。标注 标签的处理方法有几种：一种方法是丢掉全部标签，该方法的优点在于简单，缺点是信息丢失，将会降 低检索效果；一种方法是从要检索的x m l 文档中抽取重要的结构和上下文信息，并建立索引。另一种更 复杂的方法是为标签建立索引，如同普通索引词一样。显然，无需为结束标签建立索引，因为开始标签 已经提供了结构信息。最好的方式是为标签和元素内容建立不同的独立的索引，以便支持更灵活的检索 需求。例如，用户的查询需求可分为以下三类：( 1 ) 仅含某个标签的文档，( 2 ) 仅含某个单词的文档， 或者( 3 ) 包含几个单词，同时这些单词必须位于特定元素内部。 3 混合方式 除了上述两种方式外，还有一种方式结合了数据库和信息检索方式的优点，使用较简单的查询表达 实现对x m l 文档的内容和结构信息的查询 8 l ，8 8 ，5 6 ，4 5 。例如，下列语句查询有一个作者名字( 孩子 元素或属性) 的全部文档： a u t h o r n a m ea u t h o r n a m e 混合方式的另一种实现方法是采用多层解决方案。当收到检索请求时，首先进行基于信息检索技术的类 搜索。一旦发现相关类，则提交标准数据库查询( 例如s 。l 语句) 。x y z f i n d 8 9 是采用这种混合的方法的 4 第一章绪论 一个例子，这种方法的好处是它能迅速地过滤出最好的备查数据库，并且数据库查询提供了非常高效的 查询处理能力。 由前文可知，数据库方式的优势在于( 1 ) 可使用标准( 关系和面向对象) 数据库引擎，无需投资开发新 的系统；( 2 ) 使用标准数据库查询语言( s q l ) ，从而减少使用新查询系统所必须的培训和学习。不过，这 种方法也有许多缺陷。首先，直接把遵从不同模式的异构x m l 文档导入数据库引擎是困难的。其次，在 因特网这样的动态环境下，数据的结构会经常发生改变，这将导致数据库模式的频繁更新。 信息检索方式可以应用于x m l 文档的检索，以获得更好的准确率。该方法的有以下三个优点：( 1 ) 现 存的检索系统只需作某些修改，就可应用于x m l 文档的检索；( 2 ) x m l 搜索引擎的使用与传统搜索引擎相 似，用户无需训练即可轻松使用；( 3 ) 由于它不包括结构信息，它的索引代价更小。但是这种方式的问题 是它可能不象数据库方式一样准确，因为它基于内容近似匹配的技术，不支持复杂的文档结构匹配。 混合方式结合了许多流行的技术来实现x m l 文档的查询，例如在x q l 中就把x p a t h 路径查询和全文 检索结合在一起，这种方式很可能给出一个更准确的搜索结果。混合方式的一个优点在于灵活性，既象 标准信息搜索引擎一样，又象数据库引擎( 充分的路径定义) 一样工作。既方便初学者使用，用户可以象 使用搜索引擎一样来使用它，又方便专家用户使用，以便得到更准确的查询。但是，灵活性是通过付出 存储代价获得的。另外，要想锝到更准确的结果，甩户需掌握x p 8 t h s 的一些知识。 从上面的分析可知，对于l 文档的检索，混合方式是一种较为可行的方式，接下来的问题是如何 有效地克服上述两个缺陷，为普通用户提供一种简单方便的高效的) ( h l l 信息检索工具，这涉及到) ( m l 文 档的表示及组织、高效索引的建立、查询式的给出以及高效的查询处理算法等，下面给予详细的讨论。 1 2 2 需要解决的问题 我们对当前删l 检索技术做了简要的回顾。关于x m l 信息检索的研究刚刚起步，依然有许多课题需 要深入的研究，下面将简要阐述几个亟需进一步研究的方向。 1 检索模型( r e t r i e v a l o d e l ) 检索模型是将文档表示、查询以及它们之间关系进行建模的框架。本文将它们分为两类：内容模型 和结构模型，内容模型包括布尔模型、向量模型和概率模型，结构模型包括非重叠链表模型和邻近结点 模型，近年来还发展了子串检索模型和树匹配模型。上述模型适合索引和检索l 文档的程度依赖于检 索的上下文。在新模型的探索方面，x q l 2 6 和x i r q l 做了有益的尝试。但是，它们只是基于某种查询语 言，帮助用户定义信息需求，而不是关注检索模型本身。 2 文档聚类 在传统i r 中，文档聚类技术是非常有用的技术。与文本文件相比，x m l 文档增加了结构信息，如何 利用这些信息来提高聚类的效果是一个有趣的问题。目前，就此问题已经有了许多成果。但是这些方法 的一个共同的缺陷是算法的复杂度很高，很难应用于w e b 环境下的信息检索，因此有必要研究新的更为 高效的结构聚类算法。此外，如何组织聚类过程产生的文档类的结构信息，也是一个有意义的课题，这 是因为通过利用反馈的结构信息，就可以较容易的帮助用户定义对文档的结构的查询，用户无需学习各 5 东南大学博上学位论文 种复杂的查询语言。 3 索引技术 目前已经有几种方法( 技术) 可用来对x m l 文档进行索引操作，根据包含结构信息的多少，将它们 分为以下三类：( 1 ) 平面文件索引技术，( 2 ) 半结构化索引技术和( 3 ) 结构化索引技术。由于x m l 本质 上是一种半结构化数据，所以，半结构化索引更为适用，更能保证在检索效率和表达能力两者之间做好 平衡。 在半结构化索引技术中，并不对所有的结构信息都建立索引。一种做法只是提供一个预先设计的结 构，然后将信息按此结构组织起来，而另外一些方法则利用特定的结构类型，比如树或者段来建立索引。 基于固定结构的索引只支持简单的固定域查询，查询结果不能是嵌套结构，所有返回的元素属于同一类 型。基于树的索引能够处理树形结构的文档，如x m l 文档( 包括引用、指针和链接) ，它们的一个共同的 特征是均将文档视为川! 介树( k 一”yt r e e ) ，将整数啪赋给树中每个结点。但是，采用此种索引，当数 据项( 厉d 插入到单词w 的倒排索引时，元素f 的每一个后代元素的文本内容必须也含有n 这将导 致存储空间的巨大浪费( 需重复保存r 信息) 。 x r s 2 1 采用b u s 索引结构来索引和检索结构化文档，其主要思想与l n o n ( i n v e r t e di n d e xf o rl e a f n o d e so n l y ) 2 4 的倒排索引类似，在索引中只保存叶子结点的文本信息和属性，该方法的创新之处在 于检索过程中的x p a t h s 的动态生成和匹配，以及根据动态匹配的结果元素结点信息来计算排序的权重。 如果采用b u s 框架结构，一个新的问题是如何高效的更新索引。在实际应用中，文档的更新是很普遍的， 比如p a t e n t 集合就会经常会被更新。b u s 的一种实现方法是采用关系数据库来支持索引的更新，但是这 种方案的存储开销太大，几乎与原始文档的大小一样。而且，在建立索引时，必须考虑如何高效的插入 新的文档，最坏的情况就是重新为所有文档建立索引。所以，有必要研究新的索引结构，支持结构和内 容的联合查询，支持查询任意层次的元素，同时保证增量更新的特性。 4 高效查询处理和结果排序算法 研究如何结合内容和结构信息给出合适的排序策略，在此基础上，根据检索模型，提出高效的查 询处理和结果排序算法。需着重考虑以下三个方面的问题：( 1 ) 词频的计算。由于l 检索返回的结果 可能是嵌套的元素，如何累加位于不同叶子结点下的词频是值得研究的问题；( 2 ) 逆文档频率( i d f ) 的 计算方法。因为i d f 是根据文档数目计算得到的，而x m l 的检索单位可能是元素，在这种情况下，如何 有效计算i d f 是值得考虑的；( 3 ) 结构相似性的计算。x m l 中的相似性的计算是非线性的，相似性计算 必须考虑捌l 的逻辑树形结构。 1 3 研究方案 在这一节中将介绍我们提出面向w 曲的x m l 信息检索系统的解决方案及其关键技术，也将给出论 文研究的主要内容，介绍论文工作采用的研究方法和研究工