（计算机软件与理论专业论文）xml文档查询技术研究及在数字图书馆中的应用.pdf

摘要 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 ) 己成为因特网上的数据存 储、交换和表示的标准。随着x m l 应用的普及，越来越多的数据以x m l 的形式存储和交换，对x m l 文档中的数据进行查询的要求也就越来越 高。为充分利用x m l 的特点开展查询，本文详细研究了x m l 查询改进技 术。m a r c x c h a n g e 文档是一种应用在数字化图书馆领域里的x m l 文档类 型，可以作为通用的数据交换格式在w e b 环境下共享。为更好地促进 数字图书馆建设，本文还详细研究t m a r c x c h a n g e 文档的索引和查询 技术。 本文的主要贡献有： 1 提出了一种改进的基于l i - m o o n 编码的x m l 索引，当我们对 x m l 编码后的索引文档进行b + 树结构化处理后，能大大减少索引文 档的大小，因而能有效提高查询速度。 2 针对s t a c k t r e e - d e s c 算法没有利用索引改善连接效率，浏 览了一些不必要的节点浪费了资源，影响了查询速度。本文提出了 一种新的连接算法，通过b + 树查找定位，来跳过祖先和后裔列表不 必要的元素以提高查询速度。 3 本文提出了一种基于m a r c x c h a n g e 文档的结构索引方法一 m a r c i n d e x ，该索引方法根据m a r c x c h a n g e 文档的特点采用l i m o o n 编码方式，有效地实现了对文档树中任意两个结点之间祖先后裔关 系和双亲孩子关系的检测。该索引另外的创新之处还在于有效结合 b + 树和倒排索引这两种方法，从而综合两者的优点，克服双方的缺 陷以提高查询效率。最后，本文还提出了一个基于m a r c i n d e x 索引 的查询处理算法。 关键词：x m l ，l i - m o o n 编码，b + 树，m a r c x c h a n g e ，查询 a b s t r a c t 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 ) h a sa l r e a d yb e e nt h es t a n d a r d o fd a t as t o r a g e ，e x c h a n g ea n dr e p r e s e n t a t i o no nt h ei n t e r n e t w i t ht h e s p r e a do fx m la p p l i c a t i o n ，m o r ea n dm o r ed a t ai ss t o r e da n de x c h a n g e d i nt h ef o r mo fx m l a sar e s u l t ，t h ed e m a n df o rq u e r yd a t ac o n t a i n e di n t h ex m ld o c u m e n t si sb e c o m i n gm o r ea n dm o r ec r i t i c a l t of u l l ya p p l y t h ec h a r a c t e r so fx m lt oq u e r y ，w ep r e s e n to u rc o n t r i b u t i o n st ot h e i m p r o v e m e n tt e c h n i q u e so fx m lq u e r y m a r c x c h a n g ed o c u m e n ti s a k i n do fx m ld o c u m e n tt y p ef o ra p p l i c a t i o ni nt h ed i g i t a ll i b r a r y , w h i c h c a nb eu s e da sac o m m o nd a t ae x c h a n g es t a n d a r dt os h a r ei nt h ew e b e n v i r o n m e n t i no r d e rt op r o m o t et h ed i g i t a ll i b r a r yc o n s t r u c t i o n ，t h e p a p e rs t u d i e si nd e t a i li n d e xa n dq u e r yt e c h n o l o g yo fm a r c x c h a n g e 1 t h i s p a p e rp r o p o s e s a ni m p r o v e dx m li n d e xb a s e do n l i m o o nc o d e ，w h e nw ee n c o d ei n d e x e dd o c u m e n t sb yb + t r e e s t r u c t u r e ，i tg r e a t l yr e d u c e st h e s i z eo fi n d e x e dd o c u m e n t ss ot h a t e f f e c t i v e l yi m p r o v eq u e r ys p e e d 2 f o rs t a c k t r e e d e s c a l g o r i t h mi m p r o v i n g t h ec o n n e c t i o n e f f i c i e n c yw i t h o u ti n d e xa n db r o w s i n gan u m b e ro fu n n e c e s s a r yn o d e s t o w a s t er e s o u r c e sa n da f f e c tt h eq u e r ys p e e d an e wc o n n e c t i o na l g o r i t h m i sp r o p o s e df o ri m p r o v i n gq u e r ys p e e dt h a ti ts e a r c h e sp o s i t i o nb yb + t r e ei n d e xt os k i pu n n e c e s s a r ye l e m e n ti nt h el i s to fa n c e s t o r sa n d l i d e s c e n d a n t s 3 m a r ci n d e xb a s e do nm a r c x c h a n g ed o c u m e n t si sp r o p o s e dt h a t i su s i n gl i m o o nc o d ei na c c o r d a n c ew i t ht h ec h a r a c t e r i s t i c so ft h e m a r c x c h a n g ed o c u m e n t s ，a c h i e v e se f f e c t i v e l yd e t e c t i o no ft w on o d e s a n c e s t o r d e s c e n d a n tr e l a t i o n sa n dp a r e n t c h i l dr e l a t i o n si nt h ed o c u m e n t t r e e t h eo t h e ri n n o v a t i o no ft h ei n d e xi st h a ti ti n t e g r a t ee f f e c t i v e l y a d v a n t a g e s b o t hb + t r e ea n di n v e r t e d i n d e xt oo v e r c o m et h e s h o r t c o m i n g si no r d e rt oi m p r o v eq u e r ye f f i c i e n c y f i n a l l y , t h ep a p e r a l s op r o p o s e daq u e r yp r o c e s s i n ga l g o r i t h m sb a s e do nm a r c i n d e x k e yw o r d s ：x m l ，l i m o o nc o d e ，b + t r e e ，m a r c x c h a n g e ，q u e r y i i i 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不合任何其他个人或集体已经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位论文作者签名：本吨力一7 年6 月日 o a 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 研究生在校攻读学位期间论文工作的知识产权单位属湖南师范大学。 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权湖南师范大学可以将本学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密留。 ( 请在以上相应方框内打“ 竹) 作者签名：枣乓 日期：一件6 月 日 导师签名：m 嵋 嗍：1 年易月小 x b t l 文档查询技术研究及在数字图1 5 馆中的应用 1 1 本文的研究背景和意义 1 绪论 随着因特网技术的发展，网络上的数据越来越丰富，这些数据 具有分布性、异构性、动态性等特点，人们极其需要一种网上数据 描述、数据交换的标准，由于x m l 具有开放性、自描述性、元语言 等特点，正好满足了这种需求。 目前，传统的信息检索技术一般采用单纯的全文检索，忽略了 结构信息，信息服务难以深入和拓展，而x m l 文档既有文本内容， 又包含结构信息，如果能对其结构信息进一步利用，有利于人类对 知识的挖掘和获取。此外，从信息服务的发展背景看，用户对信息 的不同范围、不同规模、不同层次的需求，要求信息服务能够在深 度和广度上进行不断拓展。信息服务的深度，简单理解，就是从编 码到数据到信息再到知识的不断深入，是一个语法、语义、语用的 深入过程，最终目的是要实现语义互操作、知识互操作。 而x m l 己经成为语义w e b 和w e b 服务共同的语言基础，这也 是目前x m l 技术得以广泛应用的一个推动因素。因此，我们认为， 面向x m l 文档的信息检索研究是互联网空间下信息服务技术的基 础和重点。随着x m l 技术的不断发展及其应用领域的不断扩展，越 来越多的数据开始采用x m l 进行描述、存储、交换和表现，传统的 信息检索技术将会因为x m l 文档的出现而面临新的挑战，跨越不同 数据源的面向x m l 文档的信息检索技术变得日益重要。 在图书馆领域，书目数据是图书馆提供给用户的最大信息资源， 但以往的书目格式( m a r c ) 成为图书馆数据资源整合进入网络流通的 障碍，由于h t m l 只能描述形式而不揭示内容，所以在h t m l 内无 法充分表达m a r c 格式所描述的书目数据【1 1 。可扩展x m l 不仅可以 硕：e 学位论文 表示数据，而且可以揭示内容，是一种能够有效表达网络上各种资源 信息为信息的整理、存储、交换、检索提供有效途径的技术。国际 标准化组织信息和文献工作技术协作委员会制定了一个通用的、能 够满足世界上所有遵循i s o2 7 0 9 的m a r c 格式的x m l 文档模式，称 为m a r c x c h a n g e 文档，它是一种应用在数字化图书馆领域里的x m l 文档类型，可以作为x m l 描述的m a r c 数据的格式交换工具，也 作为i s o2 7 0 9 格式的m a r c 数据交换的一种补充 2 1 。这个标准说明 了通用的、基于x m l 交换格式的书目记录和其他类型元数据的功能 需求；它没有定义单个记录的长度或内容，也没有为字段标识、指示 符、标识符以及执行格式的功能说明赋予任何定义；它描述了一个一 般结构，即主要设计目的是作为数据处理系统中进行通信的框架，同 时也可以作为系统内部的处理格式进行使用。因而，m a r c x c h a n g e 文 档将会大大加快图书馆信息化进程，与其相关的技术也越来越重要。 1 2 国内外研究现状 目前国内外面向x m l 文档的信息检索技术的研究涉及数据模 型、文档存储、索引结构、查询语言、系统实现等多个方面。 s a b i t e b o u l 提出了半结构化数据的概念，概括了半结构化数据 的特点，并从模型、查询、视图、重构等方面对半结构化数据进行 了详细的研究分析【3 】；r o b e r tw p 从非结构化、半结构化、结构化 三种索引类型出发，讨论并概述了f l a t f i l e 、基于字段( f i e l d b a s e d ) 、 基于分段( s e g m e n t b a s e d ) 、基于树( t r e e b a s e d ) 、 i s a m 、b 树、 倒排文档、基于路径( p a t h b a s e d ) 、基于位置( p o s i t i o n b a s e d ) 、多维 索引等多种索引方法应用于x m l 文档的可行性、有效性【4 】。目前作 为标准的关于x m l 数据模型的描述则体现在w 3 c 关于x m l 的几 个规范之中，并成为对x m l 文档进行编程操作、查询处理的基础。 w 3 c 组织于1 9 9 9 年9 月成立了x m l 查询工作组，并确立了具体的 x m l 文档杏询技术研究及在数字图侈馆中的应用 工作目标：为x m l 文档建立一个数据模型、基于这个数据模型的一 组查询运算符、以及建立在这些查询运算符操作上的查询语言。 a s a l m i n e n 提出了x m l 数据库的定义1 5 】：“一个x m l 数据库是 x m l 文档及其部件的集合。并通过一个具有能力管理和控制这个文 档集合本身及其所表示信息的系统来维护。x m l 数据库不仅是结构 化数据和半结构化数据的存储库，像管理其它数据一样，持久的 x m l 数据管理还应当包括数据的独立性、集成性、访问权限、视图、 完备性、冗余性、一致性以及数据恢复等。”r o n a l db o u r r e t 介绍了 如何通过数据库存取x m l 数据，如何将x m l 文档的结构和数据映 射为关系数据库或内容管理系统，还给出了d t d 到关系模式的映射 算法【6 】。在系统实现方面，还介绍了将结构化文本检索系统集成进一 个面向对象数据库中，用户可以用标准的数据库查询语言来访问检索 系统【7 1 。 近年来，x m l 数据应用越来越广泛，如何在众多的x m l 文档 中寻找使用者所需要的文件与数据，也成为了一个很重要的议题。由 于x m l 文档如同h t m l 文件一样，是属于文本格式的，所以很多研 究者延续信息检索的技术，希望能取出包含特定关键词的x m l 文档。 研究人员将x m l 文档内属于数据的部份看作字词，将每个字词去除 同样的前缀字尾，使字词的数量降到最低，再用所获得的字词来建立 索引，如此可减少索引的大小，进而缩短了索引与查询的时间【8 1 。另 外，除了单一的关键词外，在x m l 文档内也可利用x p a t h ，来取出 位于特定位置或符合限制条件的数据。有些研究者特别针对无法预先 取得的大量数据，像是股票数据等，做符合x p a t h 叙述的信息检索， 将多条x p a t h 依照节点来转换成s u b s t r i n g ，然后再将s u b s t r i n g 当做 关键词，使用x t r i e 来建立索引结构，之后便可以此x t r i e 来实时的过 滤数据【9 】。上述方法主要着重在筛选出包含特定数据的文件，不能快 速地处理一般化的查询语句。 硕 ：学位论文 在编码方面，作者将x m l 文档上的每一个节点x 给予两个编码 数字，分别对应到节点的起点与终点，代表x 节点所包含的范围。 若节点x 是y 的祖先，则x 所描述的范围会包含y 所描述的范围。 我们让x 所描述的范围有剩余的空间，于是若x 要新增子节点，就 可以不必修改其范围而可继续使用【l o l 。在些基础上，有人利用s i b l i n g p o i n t e r 指针来指向标签名称一样的节点，如此在做两元素的结构连接 时，可以先将对应到两元素的节点各自放到两个串行内，并按照它们 的节点起点编码来排序，然后就可通过指针略过不用参与结构连接的 节点，从而加速结构连接的速度【1 1 1 。文献【1 2 】不采用绝对位置方式的 节点编码，而是让节点编码的起点与终点是相对于自己父节点编码的 起点与终点，采用此种相对位置的节点编码，当有节点要更新时，所 影响到的节点，只有要被更新节点的祖先以及这些祖先的兄弟节点。 依照此特性将相对位置的节点编码聚集起来储存在一起，那么在更新 时会有较佳的i o 效率。文献【1 3 】则是提出多种索引来加快查询的速 度，包括了针对节点名称的n a m ei n d e x 、对节点值做索引的v a l u e i n d e x 、与加快x p a t h 查询的p a t hi n d e x 。 1 3 本文的研究内容和组织结构 本文在查阅大量相关文献的基础上，进行了如下几个方面的工 作： 进行了相关的基础理论研究，包括x m l 技术和数字图书馆 的基本概念和相关技术。 分析了现有的x m l 文档的索引结构及查询算法，提出了一 种新的索引结构，并介绍了x m l 数据查询算法，通过仿真实验加以 证明其查询效率较高。 综合上面的技术，本文具体研究了x m l 查询技术在数字图 书馆中的应用，即通过对数字图书馆领域的x m l 数据类型 4 x m l 文档杏询技术研究及在数字图二 5 馆中的应用 - - m a r c x c h a n g e 文档进行l i m o o n 编码后，引入b + 树结构索引， 描述了索引框架和实现算法，并提出了一种新的基于m a r c i n d e x 索 引的路径表达式查询方案，通过仿真实验加以证明其效率是比较高 的。 本文的创新之处有以下几点： 提出了一种改进的基于l i m o o n 编码的x m l 索引，它是 一种索引中的索引，当我们对x m l 编码后的文档进行b + 树结构化 处理后，能减少索引文档的大小，利用b + 树索引查找快的优点来有 效提高查询速度。 针对s t a c k t r e e d e s c 算法没有利用索引改善连接效率，浏览 了一些不必要的节点浪费了资源，影响了查询速度。提出了一种新 的连接算法，通过b + 树结构索引查找定位，来跳过祖先和后裔列表 不必要的元素以提高查询速度。 关于x m l 的结构索引研究的文献比较多，但再结合m a r c ， 却只应用于搜索引擎，关于结构索引的研究还未见到文献报道。本 文提出了一种基于m a r c x c h a n g e 文档的结构索引方法m a r ci n d e x ， 该索引方法根据m a r c x c h a n g e 文档的特点采用l i m o o n 编码方式， 有效地实现了对文档树中任意两个结点之间祖先后裔关系和双亲 孩子关系的检测。该索引另外的创新之处还在于有效结合b + 树编码 索引法和倒排索引法这两种方法，从而综合两者的优点，克服双方 的缺陷以提高查询效率。 本文还提出了一个基于m a r ci n d e x 索引的查询处理算法。 通过元素属性目录，得到某结点，这个结点作为路径的起点，沿此 路径能够达到一个目标节点，使该路径与结构树进行匹配，成功输 出结果集。 具体章节安排如下： 在第一章中，论述了本文的研究背景和意义、国内外研究现状 硕十学位论文 以及本文的研究内容和章节安排。 在第二章中，对x m l 技术和数字图书馆做了简单介绍，主要介 绍了x m l 的s c h e m a 模式、l i m o o n 编码、路径表达式、m a r c 、 m a r c x c h a n g e 以及数字图书馆中的信息检索技术。 在第三章中，在讨论了现有的x m l 文档的索引结构及其存在的 不足的基础上，提出了一种新的索引结构。实验证明，这种方法是可 行的，效率也比较高。 在第四章中，详细介绍了如何使用新的索引结构进行x m l 数据 查询以及查询路径表达式的查询算法。 在第五章中，结合第三章和第四章的技术，本章具体对了x m l 技术在数字图书馆中的应用进行详细的研究。通过对数字图书馆中 的x m l 数据类型m a r c x c h a n g e 文档进行l i m o o n 编码后，结合 b + 树索引，描述了m a r c x c h a n g e 文档的结构索引框架，并列出了结 构索引的实现算法。并提出了一种新的基于m a r ci n d e x 索引的路径 表达式查询方案：在处理路径表达式时，当遇到父子关系时，用结 构索引进行查找。而遇到祖先后代关系时，则用结构连接的方法执 行查询；如果路径表达式是带多分支的路径表达式，将其分解为多 个简单路径表达式进行查询；并提出了路径表达式查询的优化策略， 即路径缩短策略，从而使查询时间缩短，减少查询代价。 最后给出本文的总结和对未来的展望。 x m l 文档查洵技术研究及在数字图书馆中的应用 2 1x m l 基础知识 x m l 和数字图书馆基础知识 为了更好的理解和阐述x m l 结构索引的研究工作，本章介绍了 x m l 的一些基础知识。包括x m l 文档的构成，x m l 文档的数据模 型表示，路径表达式相关概念以及针对x m l 文档的主要查询语言 x p a t h 和x q u e r y 。 2 1 1x m i _ 文档 x m l 是由w 3 c 的x m l 工作组定义的。这个工作组是这样描 述该语言的：“x m l 允许普通的s g m l 在w e b 上以目前h t m l 的 方式被服务、接收和处理。x m l 被设计成易于实现，且可在s g m l 和h t m l 之间互相操作【7 l 。 x m l 是一套定义语义标记的规则，这些标记将文档分成许多部 件并对这些部件加以表示。它不像h t 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 文档 中应该包括一个根元素，所有其它子元素必须包含在根元素内，虽 然在h t m l 中允许像 或 这样的单标签元索，但是x m l 中 所有元素都必须有一个结束标签。x m l 元素间是通过父子关系进行 硕士学位论文 关联的。 2 1 2s c h e m a 简介 x m ls c h e m a 最重要的处理是模式的验证。实例与模式之间有 多种对应关系。个模式可以描述许多有效的实例，同样一个实例 也可以被多个模式描述。模式的验证用来判断实例是否符合模式中 所描述的所有约束。它涉及到检查实例中所有元素和属性，从而确 定它们是否有声明，以及它们是否符合这些声明及相应的数据类型 定义。而这里所说的模式就是x l v l ls c h e m a ，而实例就是符合x m l s c h e m a 描述的x m l 文档【1 4 1 。 一个s c h e m a 通常是一组为了描述一类给定的x m l 文档而预 先定好的规则。它定义了可以在指定x m l 文档中出现的各个元素以 及和某个元素相关的若干属性。它同时定义了关于x m l 文档的结构 化信息，比如哪几个元素是其他元素的子元素，子元素出现的顺序 和他们的数量。它还可以定义一个元素是否为空，能否包含文本或 者属性是否有默认值。 2 1 3x m l 查询语言和路径表达式 目前已经有许多x m l 查询语言，比较典型的有x p a t h 、x q u e r y 、 l o r e l 、x q l 等恻。 x _ p a t h 的主要构件是表达式。其中，最重要的表达式是定位路径 ( 1 0 c a t i o np a t h ) 表达式，简称路径表达式，它与计算机系统使用的文 件系统极为相似。x p a t h 中用上下文结点集来描述定位路径的求值过 程的。x q u e r y 是定义为对x m l 数据集进行查询的，x m l 数据不仅 包括文档，还指一切看起来像x m l 的数据，包括关系数据库中的数 据。x q u e r y 对于x m l 数据，就像s q l 对于关系数据一样。x q u e r y 是基于x p a t h 的，它具备x p a t h 的所有功能，除此之外，x q u e r y 还 x m i 。文档查询技术研究及在数字图+ 侈馆中的应用 扩充了部分其他功能，每个x q u e r y 查询包括一个或多个查询表达 式。常用的x q u e r y 语法有：路径表达式、序列表达式、算术表达式 与布尔表达式、f l w o r 表达式、条件表达式、构造器、定量表达 式以及函数调用等。 路径表达式用于浏览x m l 文档的层次结构，找到满足条件的元 素。除此之外，路径表达式还常常用于x m l 文档的过滤。另外一些 x m l 查询语言还有构造x m l 的能力。应该说，路径表达式是x m l 数据不同于关系数据的关键所在，因此路径表达式的表示、简化和 处理是x m l 查询和过滤的核心技术之一。路径表达式用于定位文档 中的节点，如元素节点、属性节点和文本节点。路径表达式可以是 相对的，也可以是绝对的。这两种表达式的说明如下： 相对路径表达式由个或多个步骤组成，步骤间以单斜杠或双 斜杠分隔。绝对路径表达式以单斜杠或双斜杠开头，后面跟有可选 的相对路径。如果绝对路径以单斜杠开头，则它后面未必跟有相对 路径。如果仅指定单斜杠，则表达式将返回上下文节点的根节点。 对于x m l 数据类型，根节点为其文档节点。给定一个路径表达式 r ，如果我们能够通过将通配符替代为某一标签值，将循环符展开等 处理方法得到某一个具体的标签路径。我们就说这个标签路径是匹 配于该路径表达式的。 2 2 数字图书馆基础知识 数字图书馆这一概念最早出自欧美，美国在1 9 9 4 年启动的持续 了4 年的“数字图书馆 项目，带动了整个数字图书馆的研究，掀 起了数字图书馆研究的热潮。 数字图书馆的概念可以从多个不同的角度去理解f 1 6 1 。首先，对 于传统的图书馆工作人员来说，这意味着引进新的技术与新的载体、 用全新手段来完成传统的图书馆工作( 包括分类、编目、存储、查找 硕十学位论文 以及维护管理等) ；其次，对于计算机技术人员，数字图书馆是一种 包含多种信息载体、多种信息内容、跨地区、跨国界的大型分布式 计算机网络，他们注重的是网络技术、多媒体技术、安全可靠性以 及查询的效率、速度等等；再次，相对于研究管理人员，数字图书 馆是一种新的协调或协同工作的手段，强调的重点是一个组织、一 个机构中的人员共享知识、交流信息，并且创造新思想、开发新产 品以至领导新潮流：最后，对于教育工作者来说，数字图书馆将对学 习过程提供强有力的支持和帮助，不论是正规学习还是非正规教育 都将因数字图书馆的产生而大受裨益，并由此产生深刻地变化。数 字图书馆的出现使众多的图书不再散布于世界各地孤立的图书馆 中，其馆藏通过各种磁、光、电介质永久存储并流动于全球信息网 络e 。 2 2 1m a r c 文档和m a r c x c h a n g e 文档 m a r c 是用于描述、存储、交换、控制和检索的一套机读书目数 据标准，起源于2 0 世纪6 0 年代后期，m a r c 格式主要由三部分组成 f 1 刁：头标区、目次区、数据区。头标区位于每条记录的开端，共有2 4 个字符长度，提供此记录的必要参数。目次区m a r c 记录中每个可变 长字段的索引，由一系列固定长数据项目组成，包括每个可变长字 段的字段标识符、字段长度和字段起始字符位置。每项1 2 个字符位， 在终端上不显示，目次区包括9 个功能块：标识块、编码信息块、标 目块、标目附注块、单纯参照根查块、相关参照根查块、分类号块、 连接标目块和来源信息块。数据区由多个可变长字段组成，是著录 资料信息的具体体现，m a r c 格式的著录就是将图书馆的各种信息资 源进行综合分析处理，提取主要的信息要素，按一定的规范格式组 织起来，提供给人们检索。 随着网络技术的发展，m a r c 成为图书馆的数据资源整合的最大 x m l 文档杏询技术研究及在数字图i 弓馆中的应用 障碍，2 0 0 3 年5 月，i s ot c 4 6 ，s c 4 ( 信息和文献工作技术协作委员 会) 在罗马会议上提出要制定一个通用的、能够满足世界上所有遵循 i s o2 7 0 9 的m a r c 格式的m a r c x m l + 模式，并确定该模式为美国国 会图书馆的m a r c x m l 和i s 0 2 7 0 9 的补充及扩展。2 0 0 4 年1 0 月， 华盛顿会议上，丹麦推荐给i s ot c 4 6 ，s c 4 一个称为“m a r c x c h a n g e ” 的x m l 模式，它是m a r c x m l 模式的扩展，并于2 0 0 5 年1 1 月3 0 日，成为标准草案i s o d i s2 5 5 7 7 。 2 2 2 数字图书馆中的信息检索技术 图书馆作为信息资源的重要提供者，在随着科学技术以前所未有 的高速度向前发展而产生出大量的信息的形式下，如何科学、高效地 去管理这些文字信息、数字信息、多媒体信息、如何在庞大的信息资 源中帮助用户科学地、高效率地发现信息，为用户提供有效的检索信 息的手段，是图书馆在新的时期面临的新挑战【1 8 1 。 信息检索亦称情报检索( i n f o r m a t i o nr e t r i e v e ) 。该词是1 9 5 0 年在 一次国际数学家会议上被提出来的，包括信息存储和检索两个方面。 在检索之前，必须将信息收集起来，按科学方法进行整理，并按一定 规律存储起来，形成书本式检索工具或计算机可读数据库。在检索时 通过手工方法或计算机，按存储信息所依据的规律，将用户所需的信 息找出来。 纵观计算机信息检索系统的发展，可以将其发展过程划分为四个 阶段： 第一阶段：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 n l i n ec o m p u t e rl i b r a r yc e n t e r ) ，s d c 公司建立的s y s t e m d 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 系统都是在 线商用数据库查询系统。这一阶段的特点是联机数据库集中管理， 具有完备的数据库联机检索功能，但其数据通信能力较差。 第三阶段：以i n t e r n e t 的出现为标志。系统大多采用分布式的网 络化管理，其信息资源的主要特点是：数字形式表达、多媒体和多载 体、内容覆盖全社会领域、分布无序、难于规范化和结构化、内容特 征抽取复杂、用户界面要求高等。这些特点导致了信息处理从传统模 式向新型模式的转变，如体系结构从终端主机方式到客户j j 及务器结 构方式、网络环境从局域网到i n t e r n e t 等开放网，应用接口从封闭界 面到l l 和z 3 9 5 0 等，信息结构从结构化到非结构化，系统功能从 单纯信息检索到综合信息管理和服务，等等。其中较著名的系统有 y a h o o 、w e bc r a w l e r 等。 第四阶段：在前三个阶段的基础上，随着连续性语音识别技术的 不断发展，预计计算机信息检索系统将会跨入一个新的阶段。 建设数字图书馆将改变目前图书馆的工作方式和服务模式。数字 图书馆可以更好地履行图书馆在倡导、组织和服务全民读书中的重要 职能。图书馆馆员将成为捕捉和整理信息的专家，读者可以在世界各 地通过网络阅览数字图书馆中的丰富信息。 图书馆提供检索服务时，不可能为每一个查询去扫描所有馆藏， 进行逐个比较，必须有某种形式的索引，使得系统能够通过查找索引 条目来检索信息，为提供快速有效的检索方法提供信息依据。所以说 对数字图书馆中索引技术的研究意义重大。 x b l l 文档查询技术研究及在数字图一t 5 馆中的应用 2 3 本章小结 本章介绍了x m l 的一些基础知识。包括x m l 文档的构成， s c h e m a 及路径表达式的基本概念，以及针对x m l 文档的主要查询 语言x p a t h 和x q u e r y 。不论是x p a t h 还是x q u e r y ，基于路径表达 式的查询都是其查询的核心部分，而为x m l 文档构建结构索引可以 有效地加快路径表达式查询。 x d l 文档布询技术研究及在数字图书馆中的戍用 3 x m l 文档索引 3 1 现有的x m l 文档索引及其不足 利用索引技术来优化x m l 的查询，这几年得到了一定的发展， 一些索引技术相继被提出，有代表性的大致有以下几种【1 9 】： 基于路径的索引法：将相同或相似路径进行合并，一方面压缩了 x m l 树型结构，另一方面减少了查询遍历的分支数。其代表有 d a t a g u i d e ，a ( k ) ，d ( k ) 等。 树结构分片索引法：将树型结构分片，然后对每个树结构片建立 索引，这样就可以随机访问树型结构的一些内部节点。其代表是 i n d e x f a b r i c 。 编码索引法：该方法是当前国际上的研究热点之一，其主要思想 是将各个节点进行相对位置编码，编码一般采用前序+ 后序遍历，其 代表有x i s s 。 倒排索引法：利用现有的倒排索引技术对x m l 进行索引。在s o l s e r v e r2 0 0 5 ，n a t i v e 中都有实现。 关系数据库存储法：主要思想是将x m l 数据拆分存入关系表，从 而利用关系数据库的强大功能对x m l 数据进行查询。其代表是 s t o r e d ，o r a c l el o g 对此进行了实现。 d a t a g u i d e 2 0 】是从根结点为起始的精练路径的一种结构摘要。边标 签串联在一起形成的字符串路径只描述一次。d a t a g u i d e 减少了遍历 路径查询时所需的部分结点，它对从根部遍历x m l 文档是有效的。 然而，由于它不能提供关于结点之间父子或祖先后代关系的任何结构 信息，因此它不使用于一般的从任意结点为开始的查询。 这种方法的缺点是：一方面，结构摘要不稳定，当x m l 文档有任 何的更新，结构摘要都要重新生成；另一方面，由于结构摘要不包含 硕士学位论文 所有的元素结点，因而在进行查询时许多路径仍需要检测。 t - i n d e x l 2 1 】是特定的路径索引，它不是对所有的路径建立索引，而 仅仅对有限的路径抽取结构摘要信息来建立索引。1 - i n d e x 和2 。i n d e x 是t - i n d e x 的特定情况。 l o r e 索引【2 2 】通过采用两个附加的索引结构b i n d e x 和l i n d e x 向前 向后遍历来解决d a t a g u i d e 中的一些问题。 然而，这些索引与d a t a g u i d e 一样没有采用数据树结构信息。尽 管这些索引结构减少了指针转移操作的次数，但是路径信息的缺乏在 向前和向后搜索时产生了大量的冗余数据，从而造成查询代价较大。 i n d e xf a b r i c 索引【2 3 1 是在p a t r i c i at r e e 基础上采用关键字压缩机制 来为大量的字符串建立索引，它通过前缀编码的方式将r a wp a t h 和 r e f i n e dp a t h 编码成字符串，然后插入索引中。i n d e xf a b r i c 索引树是 一种平衡树，对索引的所有访问都只需要同样小的i 0 资源。在检索 i n d e xf a b r i c 索引时，从最左边的水平层的根结点开始，在一个块内 部，沿着这些边将所要查找的字符串与边标签进行比较。如果带标签 的边是远程连接，搜索处理就向右在下一层的某个不同块中进行查 找。 如果没有带标签的边与所要查询的关键字字符串相匹配，搜索处 理就沿着非标签边到下一层中一个新的块中进行查找。查询处理就这 样一层一层地进行查询，直到底层即o 层。在o 层中进行搜索期间， 如果没有标签边与要查找的字符串相匹配，则该关键字的索引就不存 在。否则，顺着路径就能够找到该关键字字符串。 这种索引结构适合于以文档根结点为起点的路径查询，而其它路 径查询则要求查询多个索引或要经过一个预处理。为了弥补这个不 足，它提出了精确路径的概念。然而，在利用索引进行查询之前，这 种精确路径要经过多次预选择。 于是为了快速确定元素之间的关系，出现了n u m b e r i n g s c h e m a ， x m l 文档杏洵技术研究及在数字图书馆中的虑用 并在此基础上提出了一个新的索引和存储x 2 c l l 数据的系统，叫做 x i s s 索引系统【2 4 1 。n u m b e r i n gs c h e m a 能够快速地确定元素之间的祖 先后代关系，x j s s 索引系统能够有效地找到同名字符串的元素和属 性。x i s s 索引结构主要由三部分组成，即e l e m e n ti n d e x ， a t t r i b u t e i n d e x 和s t r u c t u r ei n d e x 。 这种索引系统的不足是： 该索引系统所采用的n u m b e r i n gs c h e m a 的 对中 的o r d e r 和s i z e 值都是任意的整数，这样不便于为以后插入的元素分 配 值。 一些重复出现的元素会在n a m ei n d e x 和e l e m e n ti n d e x 以及 a t t r i b u t ei n d e x 中重复建立索引、重复存储，这样会浪费存储空间、 增加检索的时间，降低检索效率。 3 2 一种改进的基于li - m o o n 编码x m l 索引技术 为了有效支持x m l 查询，人们已经提出了很多编码方案，主 要包括：位向量编码、前缀编码、p b i t r e e 编码和区间编码等瞄】。d e w e y 提出了前缀编码：将一个结点的双亲结点的编码作为该结点编码的 前缀。树t 的一个结点u 的前缀编码为c ( u ) ，则结点u 的孩子结点v 的前缀编码c ( v ) - c ( u ) n ，其中n 是结点v 在结点u 的所有孩子结点 中从左到右的序号。如果需要判断一个结点v 是否是另一个结u 的 后裔，只需判断字符串c ( u ) 是否是字符串c ( v ) 的前缀。以结点r 为根 的子树中的任意一个结点u ，它的前缀编码c ( u ) 大于( 小于) 它的左兄 弟子树( 右兄弟子树) 中所有结点的前缀编码。因此，前缀编码不仅能 够有效地支持包含关系的计算，而且能够有效地支持文档位置关系 的计算。但是层数比较大的结点的编码就会出现很多的分隔符“”， 这会增加额外的编码长度，而且还会影响编码效率。最早的区间编 码是p f d i e t z 提出，称为d i e t z 编码，它的编码规则为：树t 中 硕十学位论文 每个元素节点赋予一个编码为一个二元组( s t a r t ，e n d ) ，其中s t a r t 和 e n d 分别表示节点在树中先序遍历序号和后序遍历序号。由于树t 中的一个祖先结点u 在先序遍历( 后序遍历) 中必须出现在它的后 裔结点之前( 之后) ，因此结点u 和v 是祖先后裔关系，当且仅当： u s t a r t v s