（计算机软件与理论专业论文）基于有监督学习技术的web和xml查询.pdf

基十古监督学习技术的w e b 和x m l 查询摘要 。 甲1 6 7 3 3 摘要 ( i n t e r n e t 的出现和i 丑速发展极大的改变了人们的生活方式，人们的生活从此 有了革命性的发展。) 任于w e b 上的数据与传统的文本数据和数据库数据有着很 大的区别，使得现有的信息检索、信息抽取和数据库技术无法直接使用在w e b 数据上，人们采用了各种新技术来对w e b 数据进行挖掘。而x m l ( e x t e n s i b l e m a r k u pl a n g u a g e ，可扩展标记语言) 的出现，更是推动了各项新技术的出现和 发展，由于x m l 有着比h t m l 更良好的特性，使得x m l 将成为i n t e r a c t 上的 数据存储和交换的标准。本文在归纳和总结现有w e b 和x m l 数据查询技术的基 础上，提出了利用有监督学习的技术，对w 曲和x m l 文档进行查询的新方法。 ， 具体来说，本文的贡献如下： 1 合作设计并实现了一个基于学习的w e b 查询系统：f a c t 。与一般的搜 索引擎不同的是，f a c t 最终返回给普通用户的不是网页地址或者网页 的页面，而是用户真正关心的那一部分信息，而这些信息可能不在搜索 引擎返回的第一个页面上，也可能只是某页面中的一小部分。虽然某 些查询无法使用几个简单的关键词来表示，但是用户只需要输入几个关 键词，然后浏览很少几个网站。而该系统将利用用户浏览学习得到的知 识，来明确用户查询的条件( 这些条件可能无法用简单的几个关键词来 表示) ，对剩余网站进行查询，最终把符合条件的那部分信息作为查询 结果返回给用户。 技术 2 提出了利用有监督学习技术，对那些不包含d t d 的x m l 文档进行近 似查询的算法。由于不同x m l 文档的来源不同，因此它们的标识符可 能存在异名同义的情况，而该算法正是利用有监督学习技术来找出这一 情况。实验表明，该算法能较好的进行这一情况下的x m l 近似查询。夕川 关键词：w e b 挖掘，搜索引擎，w e b 查询，x m l ，近似查询，有监督学习 中图分类号：h 弓9 2 7 i 薹主塑堕塑兰翌垫查塑鉴! 塑! 坚! 壅塑一j 堕墨 a b s t r a c t w i t ht h ee m e r g e n c ea n dt h ed e v e l o p m e n to fi n t e m e tt e c h n o l o g y ，i n t e m e ta n d w e bh a v ec h a n g e dp e o p l e sl i f er a p i d l y b e c a u s eo f t h ed i f f e r e n c eb e t w e e nw e bd a t aa n d t e x td a t ao rd a t a b a s ed a t a ，t h et e c h n o l o g yu s e di nt h ef i e l d o fi n f o r m a t i o nr e t r i e v a l 近f o n n a 如ne x 垃a c 曲na n dd a t a b a s ec a r l tb eu s e di nw e b d a t ar e s e a r c ha r e av e r yw e l l p e o p l eh a v ed e v e l o p e d s o m en e wt e c h n o l o g i e st o p r o c e s s w e bq u e r y ，w h i c hi sa n i m p o r t a n tf i e l do fw e bm i n i n g a n d b e c a u s eo ft h ef e a m r eo fx m l ( e x t e n s i b l em a r k u p l a n g u a g e ) ，i t w i l lb e c o m et h es t a n d a r do f d a t as t o r a g e a n dd a t ae x c h a n g eo nt h ei n t e m e t a f t e r p r o v i d i n g 8s u r v e yo f r e c e n tr e s e a r c hw o r ko f w e ba n dx m l q u e r y ，t h i st h e s i sw i l l p r e s e n tt w oa l g o r i t h m o f w e ba n dx m ls e a r c hb a s e do n s u p e r v i s e dl e a n i n gt e c h n o l o g y t h ec o n t r i b u t i o no ft h i st h 【e s i si sa sf o l l o w s ： 1 c o d e s i g n a n d i m p l e m e n t aw e b q u e r ys y s t e m ：f a c t d i f f e r e n t f r o m c o m i t i o f ls e a r c h e n g i n e s t i l e r e s u l t sr e t u r n e d b y f a c ta r en e i t h e r 出e a d d r e s s e so fw e b p a g e s n o rt h o s ew e bp a g e st h e m s e l v e s n e r e s u l t sr e t u r n e d t ot h eu s e ra r ej u s tm ei n f o r m a t i o nt h eu s e rc o n c e r n se x a c 吐y ，w h i c ha r en o t l o c a t e di nt h ee r s tp a g er e t u r n e db yc o r n f f i o ns e a r c he n g i n ea n da r ej u s tt h e f r a c d o no fo n ew e bp a g ep e r h a p s t h o u g hs o m eq u e r yc a n tb ee x p r e s s e d c l e a d vi ns e v e r a ls i m p l ek e y w o r d s w h a td l eu s e ro ff a c ts h o u l dd oa r eo n l y t oi n p u ts o m ek e y w o r d sa n db r o w s ef e ws i t e st ol o c a t et h ei n f o r m a t i o n , t h e s y s t e m w i l lu s et h ek n o w l e d g eo ft h eu s e rt os p e d f yt h eq u e r ya n d p r o c e s st h e r e m a i ns i t e sa tl a s tt h ei n f o r m a t i o nw i l lb er e t u r n e dt ou s e r 2 p r o v i d ea n a l g o r i t h m ，w h i c h i su s e dt o p r o c e s sa p p r o x i m a t e s e a r c hi n n o n d t dx m ld o c u m e n t b e c a u s ed l ex m ld o c u m e n t sa r ef r o md i f f e r e n t s o u r c e s p e r h a p s a l o to fx m ld o c u m e n t s m a y n o t a l w a y s h a v ea n a c c o m p a n y i n gd t d a n dt h et a g s w i t l ld i f f e r e n tn a m e si nd i f f e r e n tx m l d o c u m e n t sc a l lh a v et h es a l x k e m e a n i n g 丁舡s i ，e s i sp r o v i d ea na l g o r i t h m w h i c hu s e st h es u p e r v i s e dl e a r n i n gt e c h n o l o g yt op r o c e s sa p p r o x i m a t es e a r c h a n df i n do u tt j 】ee l e m e n t sw i 出d i e r e n td a l l i e sb u td l es m t l em e a n i n gi nt h i s c a s e a n dt h ee x p e r i m e n ts h o w st h a td l er e s u l ti s e n c o u r a g i n g k e y w o r d s ：w e bm i n i n g ，s e a r c he n g i n e ，w e bq u e r y ，x m l ，a p p r o x i m a t es e a r c h ， s u p e r v i s e dl e a r n i n g 苎主童鉴篁兰望垫查塑些! 塑兰坚! 奎塑一盥 1 1w e b 挖掘的背景与定义 第一章前言 i n t e m e t 的前身是美国国防部高级研究计划署( d a r p a ) 于1 9 6 9 年组建的用于军事用途 的a r p a 网。当时，a r p a 网是苏美冷战的产物，建立该网络的目的是保证分散的指挥系统 在受到攻击的时候不至于全部被摧毁。当时。a r p a 网的发展速度是相当慢的，到1 9 7 2 年， 该网络的节点个数也只有4 0 个，节点之间的也只能传输些较小的文件。当进入八十年代 后，特别是到了九十年代，随着各项技术的出现和日益成熟，i n t e r n e t 进入了蓬勃发展的时 期。据初步估计，在2 0 0 0 年，使用i n t e r n e t 的用户个数已经达到了十几亿，主机( 注册过 i p 地址的计算机系统) 个数达到了九千万以上。i n t c m e t 提供的服务也从最原始的文件传输 功能扩大到h r r p 、f t p 、电子邮件、新闻组、网络聊天等多种功能。而且随着各项新技术 进一步的完善和出现，i n t e m e t 将会提供更多样的服务，例如网络视频点播( r o d ) ，电子商 务( e g o m m e l ) ，数字图书馆( d i g i t a ll i b r a r y ) 等。可以这么说，p c 机和i n t c m e t 的出现和迅 速发展是使得计算机从实验室走进普通人生活的两大革命性的里程碑。它们的出现彻底改变 了人们的生活方式，大大缩短了人与人的距离，并且将会不断地给人们带来更快，更便捷的 生活。 但是随着i n t c m e t 的日益普及，人们又面临了新的问题。据调查，在1 9 9 8 年，i n t e m e t 上的数据总量就超过了6 t b 的数据，包含的页面也超过了6 亿个 l g 9 9 b 。人们面临的问题 已经不是能不能从i n t e m e t 上找到所需要的信息。而是如何从这么大量的信息中既快又准确 的找到真正需要的数据。因此如何自动、准确地帮助用户找到信息成了i n t e r n e t 需要解决的 首要问题。在这种背景下，w e b 挖掘技术应运而生。 人们认为，w e b 挖掘( w e bm i n i n g ) 可以有如下定义 c m s 9 7 ： w e b 挖掘是从互联殛上发现、分析、解释和表示有雨信息曲挖掘技术， 而w e b 挖掘所面临的问题是多种多样的。例如如何进行查询，如何从不同w e b 数据源 中集成数据，如何对w e b 结构进行重构。本章的下面几节将对w e b 挖掘进行一个大致的介 绍。 1 2 w e b 挖掘的主要任务与分类 和普通的数据挖掘相仿，w e b 挖掘本身是一个相当复杂的任务。这里，我们把w e b 挖掘 分成以下四个子任务 k b 0 0 ： 资源发现；如何在i n t e r n e t 上自动地找到用户所不熟悉的文档和服务。当前资 源发现的i ：具主要集中在搜索引擎中，今后，资源发现系统将解决如何自动地 使用文本分类技术把w e b 文档分类。这种技术可以把i n t e r n e t 上的文档自动地 分成像y a h o o ! 中的层次结构；也可以用于过滤搜索引擎返回的结果。例如，对 丁二类似于“帮我找到关于英特尔公司产品的介绍”的查询资源发现系统应该 能够从普通搜索引擎返回的含有“英特尔”关键字的w e b 文档中，自动找出真 正介绍英特尔公司芯片、存储器等产品的文档。 苎主塑些堑兰翌垫查竺鉴! 塑兰坚! 壅塑一! 堕 信息抽取：一旦资源发现系统找到了相关资源( 文档，服务) 后，信息抽取的 任务就是如何从这些资源中自动地发现信息。例如，如何从个人主页中找到教 授的联系方法，如电话号码、住址和电子邮件地址；如何从公司产品主页中得 到各产品的价格、型号等信息。 信息泛化：当信息抽取系统从大量文档中找到相关信息后，下一步的任务就是 怎么从这些信息中产生更高一层的信息和知识。例如判断某一个w e b 页面是某 一教授的个人主页还是公司的产品主页：根据用户的姓名和从属关系( 例如职 业等) ，自动准确的找到用户的个人主页。 挖掘结果的分析和表示：当w e b 挖掘系统完成以上三个步骤以后，需要对上 面三个步臻得到的挖掘结果进行必要、合理的分析，并将结果表示成能为人们 所认识的形式。只有完成了第四步以后，w e b 挖掘出的结果才能真正的被人们 所利用。 根据w e b 挖掘研究内容的侧重点不同，w e b 挖掘可以分成下列三类 w e b 内容挖掘基于w e b 内容的挖掘主要是从单一的w e b 文档中找到需要的 信息。基于内容的挖掘可以是找到包含某一关键词的w e b 文档，也可以是对 w e b 文档进行分类、聚类操作。也可以是发现文档内部的模式和结构。 _ e b 结构挖掘基于w e b 结构的挖掘主要是利用文档之间超链接信息。由于 w e b 文档和普通文本不同，文档之间的超链接提供了大量有用的信息。如何 从这些超链接中发现、利用相关信息，也是w e b 挖掘的一个重要课题。 w e b 使用挖掘如何利用用户浏览w e b 时的行为信息是w e b 使用挖掘所关心 的问题。它所挖掘的数据是= 级数据，即用户交互行为的数据。通常，w e b 使用挖掘使用的数据主要有用户日志( l o g ) 、w e b 服务器日志、代理服务器 日志、浏览日志、鼠标的点击和滚动行为等。w e b 使用挖掘所关心的数据可 以是某一个用户的行为，也可以是多个用户的行为。 当然，上面的分类标准并不是有非常明显的界限的。很多w e b 挖掘技术是同时属于几类 的。例如，某些搜索引擎既采用了w e b 页面之间的超链接信息，同时又利用了w e b 文档内 部的信息。又如某些智能代理系统既使用了用户浏览页面的行为或日志，又使用了w e b 文 档结构和文档内部的相关信息来提高系统的准确率和查全率。个好的w e b 挖掘技术往往 是结合了以上两种或三种技术的。 1 3w e b 挖掘与其他技术的差异 虽然w e b 挖掘技术出现较晚，可以借鉴计算机科学中其他领域的研究成果，但是w e b 挖掘技术与普通的数据库和数据挖掘技术、人工智能技术、信息检索( i n f o r m a t i o nr e t r i e v a l ) 和信息抽取( i n f o r m a t i o ne x t r a c t i o n ) 技术有着很大的区别： 处理的数据量不同普通的数据挖掘和信息检索、抽取技术所处理的数据量是 几百m b 到儿g b 的数据量。而w e b 挖掘技术往往需要关心几十g b 到几百 g b ，甚至t b 级的数据量。而且这些数据还包含了大量的噪音数据和局外数据。 数据量之间的巨大差异导致了使用普通的数据挖掘和信息检索或抽取技术无 法有效地处理w e b 挖掘所需要处理的数据集。 2 董主童堕篁兰翌垫查塑鉴! 塑兰坚! 壅塑 一! 堕 处理的数据来源不同传统的数据库或者数据仓库的数据是来自于相同或相似 数据源的。而i n t e m e t 上的数据来源多样，内容复杂，数据质量也无法保证 如何利用、集成这些异数据源，是w e b 挖掘所面临的一个新问题。 处理的数据类型不同传统的数据库技术主要是处理结构化的数据类型，例如 数据库本身具有很强的数据库模式。而传统的信息检索主要处理无结构的数据 ( 例如文本) 和某些半结构化的数据。而w e b 挖掘所处理的数据类型主要是半 结构化的数据类型，也包含了某些无结构化的数据类型和结构化的数据类型。 因此w e b 挖掘技术不能简单的采用数据库或者信息检索的方法。 数据种类差异大w e b 挖掘处理的数据不单包括了文本信息和数据库信息，还 包含了h t m l 、p d f 、图像、视频、声音等多媒体信息。特别是w e b 页面的内 部结构( 例如h t m l 和x m l 文档) 和外部结构( 超链接信息) 的存在，导致 了w e b 挖掘处理的数据和其他领域处理的数据有着很大的不同。 目的和任务不同例如全文检索和数据库查询的目的是找到全部符合查询条件 的结果。但是w e b 查询却不是这样：用户更多关心的不是能否找到了全部符合 条件的结果，而是返回结果的准确率是否较高。而且用户希望真正关心的结果 能出现在结果集的最前面。另外，普通数据挖掘服务的目的是能向专家提供决 策支持，而w e b 挖掘的服务对象可能是普通的用户或者其他w e b 应用。 正是因为w e b 挖掘和传统的数据库、数据挖掘、信息检索、信息抽取技术有着巨大的差 异，导致w e b 挖掘具有不同与其他领域的独特技术，从而也使得w e b 挖掘成为计算机科学 中重要的研究领域。 1 4 本文的工作 本文的工作主要体现在以下两个方面 1 合作设计并实现了一个基于学习的w e b 查询系统：f a c t 。与一般的搜索引擎不 同的是，f a c t 最终返回给普通用户的不是网页地址或者网页的页面，而是用户 真正关心的那一部分信息。而这些信息可能不在搜索引擎返回的第一个页面上， 也可能只是某一页面中的一小部分。而f a c t 只需要用户输入几个关键词，然后 浏览很少几个网站，标记出需要查询的部分。用户浏览页面的时候，一个后台的 进程将记录下用户浏览页面所经过的超链接的信息和用户对感兴趣的部分作标 记的信息，并把这两类信息分别转化成导航知识和分类知识，存储在知识库中。 当对需要查询的网站进行处理的时候，对正在处理的页面利用这两类知识进行分 析，判断出是应该选取该页面的某一部分，还是应该选取某个超链接以处理下一 个页面。该系统的学习策略分别有顺序学习、随机学习和交互式学习。实验表明， f a c t 的准确率和查全率较高，结果令人满意。 2 提出了利用有监督学习技术，对那些不包含d t d 的x m l 文档进行近似查询的算 法。由于不同x m l 文档的来源不同，这些x m l 文档可能不包含相应的d t d ， 而且它们的标识符可能存在异名同义的情况。因此一般的x m l 查询语言无法对 这些文档进行查询，而且一般的x m l 查询语言虽然功能强大，但是语法复杂， 无法被普通用户所使用。而该算法只需要用户浏览少数x m l 文档，对需要查询 的那些x m l 文档片断作上标记。该算法将使用有监督学 - j 方法，利用用户作标 基于有监督学习技术的w e b 和x m l 查询 前言 记的那些x m l 文档片断的标识符的信息，对剩余需要查询的x m l 文档的标识符 进行分析，找到与用户学习的x i v l l 文档片断相似的片断，并把这些x m l 文档片 断作为查询结果返回给用户。实验表明，该算法能较好的进行x m l 近似查询。 1 5 本文的组织 本文的第二章将着重介绍w e b 挖掘技术中一个重要领域：w e b 查询和搜索的各种主要 技术和系统。在第三章中，作者将提出一个新的基于学习的w e b 查询系统f a c t 。第四章中 作者将对w e b 上最新的研究方向：x m l 进行一个大致的介绍，并对x m l 的相关研究成果 作一个简单的综述。在本文的第五章中，作者将提出利用有监督学习方法，针对不同来源、 模式不同且标识符可能存在异名同义情况的x m l 文档进行近似查询的方法。晟后，在第六 章中，作者对本文进行了总结，并在此基础上提出未来的研究方向。 4 - 墨! 塑堕! 堂望垫查塑翌! 塑茎坚! 壅塑 一些塑查堕型坐翌旦薹! ! ! ! 堕 第二章w e b 查询相关研究和系统综述 在第一章中，我们介绍了w e b 挖掘的背景、任务与分类以及w e b 挖掘技术与其他技 术的差别。而w e b 挖掘技术中，w e b 查询是其中一个非常重要的方面。人们大多从信息检 索( 1 n f o r m a t i o nr e t r i e v a l ) 和数据库( d a t a b a s e ) 两个角度来研究w e b 查询。在本章的2 1 节和2 2 节中，我们将分别对这两方面进行介绍。在本章的2 3 节中，我们将对一些著名的 实用搜索引擎作个简单的介绍。 2 1 信息检索和智能代理观点的w e b 查询 2 1 1 概述 信息检索领域的研究人员把信息检索领域中已有的研究成果，结合w e b 查询本身的特 点，提出了基于信息检索角度的w e b 查询技术。他们或者使用分类、聚类等传统信息检索 方法来帮助用户查询：或者利用w e b 页面的超链接信息或者w e b 的拓扑结构来帮助用户查 询( h i t g i g r 9 8 ，p a g e r a n k b p 9 8 等) ；或者使用智能代理技术来帮助用户进行w e b 查询。 在本节中，我们将首先介绍智能代理技术的发展情况，然后介绍一个使用w e b 拓扑结构来 进行w e b 查询的方法。 智能代理通常可以分为以下几类 1 一部分智能代理属于信息过滤或分类的智能代理，它们依赖于搜索引擎的结果来 帮助用户查找w e b 文档。c i t e s e e r b l g 9 8 是一个自动的代理系统，它能自动搜索论文。 a h o y ! s l e 9 7 月o 是一个基于元搜索引擎和用户交互的个人主页搜索代理。当给定人名和从属 关系后，a h o y ! 将利用用户的交互行为来过滤m e t a c r a w l e r 返回的查询结果最后把最合适 的一个或两个个人主页返回给用户。w e b f i n d ( h t t p ：w w w w e b f i n d c o r n a t o 也是一个查询论文 的智能代理，但它依赖于一个信息仓库来完成启发式的查询。h y p u r s u i t w v s + 9 6 是利用超 链接结构和文档内容中包含的语义信息，把超文本文档分类成一棵层次树。b o m s 9 6 贝1 结 合了层次聚类技术和用户的交互行为来组织w e b 文档。 2 另外一类智能代理是个性化( p e r s o n a l i z e d ) 的智能代理，它们通过学习用户浏览 的信息来帮助用户搜索信息。例如s y s k i l l w e b e r t p i d b 9 g 首先让用户标记出索引页面所指 的某些页面的兴趣度( 高、中、低) ，然后学习用户知识，最后对索引页面所指的其余页面 进行评分。w e b w a t c h e r a f 3 + 9 5 ，j f m 9 7 】则认为如果某一个页面a 有两个链接分别指向页面 b 和c ，那么页面b 和c 包含的主题很有可能是相关的，从而为用户建议应该点击的超链 接和相关主题的页面。w e b m a t e c s 9 6 a 是另一个颇为有效的查询工具。其，它使用t f - i b f 多向量来跟踪用户在各个不同领域的需求。并从用户标记正确的信息中学习；其二，它使用 触发机制自动地抽取关键字来优化今后的查询。其他一些智能代理，例如队【n t 0 p w 9 4 、 b s y 9 5 也属于这一类型的智能代理。 3 第三类智能代理使用某一特定域的特性来组织和解释发现的信息。 f a q - f i n d e r s h b i l 9 5 中，用户使用自然语言来提问，问题中的词将被利用在与已经存在的 常见问题进行匹配，因为常见问题文件数量比i n t e r n e t 上的w e b 文档要少得多，因此 茎主童些塑堂翌垫查塑坠! 塑苎坚! 壅塑受生壅塑塑鲞堕壅塑墨竺鲢 f a q f i n d e r s 返回的查询结果质量较高。l l a p e 9 5 则学习已熟悉的信息资源的模式，然后 对不熟悉的那些资源进行查询。而s h o p b o t d 聃9 6 则使用产品的概括信息从零售商站点上 获取产品信息。例如产品的价格，操作系统( m a c 或者w i n d n w s ) ，实验表明使用s h o p b o t 可 以比普通的用户浏览购物要快4 倍。 以下。我们将介绍一个使用拓扑结构来进行w e b 查询的系统h j t e g x r 9 8 3 2 1 2 使用拓扑结构进行w e b 查询的系统：t 当个用户输入某些关键词后，搜索引擎般将返回大量包含关键词的w e b 页面。但 是，用户所需要查找的内容通常只存在于一至两个w e b 页面上。用户就需要解决如何确定 少量但又“权威”的w e b 页面的问题。例如，用户输入关键词“f u d a n ”，搜索引擎a l t a v i s t a ( h t t p ：w w w a l t a v i s t a c n m ) 将返回9 。9 3 8 个页面，但是真正的复旦大学主页： h t t p ：w w w f u d a n e d u c n 并不出现在搜索结果的最前面。如何在不需要人的干预的情况下， 确定h t t p ：w w w , f u d a n e d u c n 才是关于“f u d a n ”主题最“权威”的页面昵? 在h i t 中，提出了两个概念：即权威页面( a u t h o r i t i e s ) 和连接页面( h u b ) 。权威页 面是包含了大量与某个主题相关内容的页面：而连接页面则是包含了大量指向权威页面超链 接的页面。而h i t 的思想是基于以下这个基本前提：即一个好的连接页面链接到很多好的 权威页面：而一个好的权威页面也被很多好的连接页面所链接。 图2 1 把核心集s 扩展到集合t 下面我们将阐述h i t 是如何得到权威页面和连接页面的。 1 对于一个给定的查询，h i t 将把搜索引擎返回的页面( 例如2 0 0 个) 作为核心集s 。然 后把s 扩展到集台t ，即把所有指向s 中某个页面的页面和s 中某页面所指向的页面都 加入到集合t 中。为了防止实际操作时，t 中页面数量过大，t 的数量一般取个固定 值。图2 1 表示了集合s 和集合t 之间的关系。 2 每一个页面p 都有一个连接权重h ( p ) 和一个权威权重“p ) ，初始化都为1 。符号p q 表示页面p 有一个指向页面q 的超链接。然后h i t 使用下列的计算公式进行迭代计算： 口( p ) - 矗( 留) p p 由( p ) = 口( g ) ，啼g 6 苎兰宣些篁堂翟垫查塑坠! 塑! 坚! 壅塑 堕! 壅塑塑茎塑塑塑墨竺鳖堕 3 对所有的页面都使用上述公式进行多次迭代计算( 每一次迭代后都对权重进行标准化) ， 可以证明上述迭代过程是收敛的。最后选取1 0 个p ) 值最高的页面作为权威页面，选 取l o 个h ( p ) 值最高的页面作为连接页面。 实验表明，h i t 不但可以找到关于某个主题的权威页面。而且可以对某些主题进行泛 化。例如主题“d e n n i sr i t c h i e ”( c 语言的创造者) 。h i t 返回的前三个主题权威页面是： h t t p ：w w w c m c f a c u k d a v e c c e h t m l h t t p ：l l w w w e y b e r d i e m c o m v i n l e a r n h t m l h t t p ：w w w 1 y s a t o r 1 i u s e e i n d e x h t m l 这些页面都是与c 语言密切相关的，但是“d e n n i sr i t c h i e ”的个人信息并不包含在这 些权威页面中的。 2 2 数据库观点的w e b 查询 2 2 1 概述 数据库领域的研究人员把i n t e m e t 看作是一个极大的，异构的数据库。他们研究的主要 目的是如何把w e b 上这些异构的，半结构化的数据组织和整合成更结构化和较高层的资源， 例如关系数据库。然后使用传统的数据库查询技术和数据挖掘技术来访问这些信息。他们把 w e b 视作一个有向图。每个结点是个网页，边就是网页之间的超链接。然后提出某种w e b 查询语言来按照这种结构来搜索相关的网页，这种查询语言可以是针对网页的内容的，也可 以是超链接的结构的。在数据库领域的w e b 查询语言主要经历了以下两代： 第一代查询语言以w 3 q l k s 9 5 ，w c b s q l i 删m 9 7 ，w e b l o g l s s 9 6 等为代表a 它们的目 的是结合基于内容的查询和基于结构的查询。例如在w e b s o l 中认为w e b 是一个关系数据库。 而w e b 中的文档是一个关系模式： d o c u m e n tf u r l ，t i t l e ，t e x t t y p e ，l e n g t h ，m o d i f j 为了体现w e b 中的超链接结构，在w e b s q l 中还用下列关系模式来表示一个超链接信 息( 严格来说，a n c h o r 应该不是一个关系模式，因为同个文档可以包含指向同地址， 而超链接的文字信息又相同的多个超链接) ： a n c h o rf b a s e ，h r e f ，l a b e l 】 然后用户就可以使用类似于s o l 的查询语言对w e b 进行查询。为了限定查询结果， r e b s o l 在f r o m 和w h e r e 子句中可以对查询条件作一些限定：例如使用m e n t i o n s 和c o n t a i n s 关键词对文档包含的文字内容进行限定；使用符号一，一，；所组成的正则路径表达式来限 定文档所在的位置。 而w e b l o g 则是使用演绎规则而不是类s o l 语言来表示查询的。 第二代查询语言以w e b o o lj a m 9 8 ，s t r u o l f f s 9 7 和f l o r i d t t l l + 9 7 为代表。和第 一代查询语言不同，第一，它们有了自己处理过的并可提供访问的w e b 对象；第二，它可以 创建种新的且更复杂的结构作为查询结果。下面本文将对w e b 0 q l 做一个简单的介绍。 7 蔓主童些筻堂翌垫查塑鉴! 塑兰坚! 壅塑 一竺生熏塑塑茎塑墨塑墨! ! ! ! 堕 2 2 2 查询语言w e b o o l w e b o q l 的数据模型 图2 2 一棵包含出版论文数据库的超树 w e b o q l 提出了一个被称之为超树( h y p e r t r e e s ) 的数据模型。超树是一棵有向弧上 做了标记的有序树。超树的有向弧分为两类：一类是内部弧，用于表示半结构对象( 例如 h t m l 文档) ，一般用实线箭头表示：另外一类是外部弧，用于表示对象之间的引用关系( 例 如表示h u n l 文档之间的超链接) ，一般用虚线箭头表示，如图2 2 所示。超树的外部弧是指 向叶子节点的弧，即该节点不能有出弧；而且标识外部弧的记录必须要有一个域是u r l 。在 对w e b 中存在的信息进行模型化的时候，一棵超树可以对应于一个h t m l 文档，也可以对应 于一张关系数据表或者具有层次结构的目录树。 为了表述方便，w e b o q l 给出了下列三个定义 - 超树的尾( t a i l ) ：对于给定的超树t ，它的尾就是超树t 去掉左j 盘子树( 可以 为空) 的那部分。 - 简单树( s i m p l et r e e ) ：对于给定的超树t ，简单树就是那些由一段从t 的根出 发的弧和该弧所连接的那棵树( 可以为空) 而共同构成的树。 子树( s u b t r e e ) ：对于给定的超树t ，子树就是那些根处于从t 的根出发的某 段弧的末端的树。 为了更好的说明上述定义，我们在图2 、3 中表示了上述三个定义。 8 薹壹堕竺兰翌垫查塑坠! 塑! 坚! 壅塑 一! 竺望墅塑塑薹竺墨塑墨! ! ! ! 塑量 图2 3 超树的尾、简单树和子树 为了能较好地表示查询和重构，w e b o q l 定义了一个类似于s q l 语句的查询语言。下 面我们通过几个例子来说明这一查询语言。 q 1 ：s e l e c t y 7 i t l e ，y 1 u r l f r o mxi nc s p a p e r s ，yi nx 广、 响e r ey a u t h 。r s s m jt h 。 c 毫：泠、 尊b 和e t i c _ e d i bb e t t e 竹 叶1 = n 坤觚i ：= “2 ”1 ，、 、 t i t l e ：哂e n ta d v a n c e i nc a r dp u n c h i n g g r l ：h t t 最”- p a p e r l p s 在查询q i 中，符号x ( p r i m e 操作) 表示返回x 的第一个子树( s u b t r e e ) 。符号表示 字符串匹配操作。xi nc s p a p e r s 表示x 是c s p a p e r s 的简单树( s i m p l et r e e ) 。而s e l e c t - f r o m w h e r e 语句的操作过程如下：对于f r o m 子句中的每一个变量实例，先检查w h e r e 子旬中的条件： 如果条件为真，则计算s e l e c t 子句中的查询并返回查询结果。 在w e b o q l 中对于超树还有下列几个特殊操作： 1 拼接( c o n c a t e n a t e ) ：拼接操作是将两棵超树的根合并起来，用符号+ 表示。 2 。头( h e a d ) ：返同超树的第一棵简单树，用符号& 表示。头操作的一个扩展形式是 返回超树的前n 棵简单树。 3 尾( t a i l ) ：返同超树除去第一棵简单树后所剩的那部分，用符号! 表示。尾操作的 一个扩展形式是返回超树除去前n 棵简单树后所剩的那部分。 4 悬挂( h a n g ) ：悬挂操作有两个参数：第一个参数是一个记录，第二个参数是一 棵超树。悬挂操作的含义是把表示该记录的一段弧与该超树相连接。 w e b o q l 的w e b 重构 使用上述一些操作可以完成对给定w e b 下的超树重构。w e b o q l 不但可以重构超树， 还可以重构w e b ，即把一个w e b 映射到另外一个w e b 。在w e b o q l 中w e b 重构操作是通 过s e l e c t f r o m - w h e r e 语句中的a s 子句体现的。例如查询： 9 0 八甜 。馓 余黑一 蕊八q 戈 “蝴蝴 黢一 姣i r 苎主童些塑兰翌垫查塑竖! 塑! 坚! 奎塑 一苎墼生型型曼翌苎壅塑墨! 壅! ! 堕 s e l e c t y t i t l e ，y u r l - ss c h e m a f r o mx i nc s p a p c r s y i nx w h e r e y a u t h o r s s m i t h ” 在上述查询中a ss c h e m a 将会把查询结果组成一个新的w e b 模式。而查询 将为每一个研究组创建一个新的页面；每一个页面都包含了相应研究小组的论文情况 有了上述的查询语言和重构语法，w e b o q l 就可以将一个h t m l 文档映射为一棵超树： 超树中的每一段弧都对应于每一对标识符( t a g ) 之间包含的文字( 例如 和 之间的文字) ，或者那些不成对的标识符的文字( 例如 ) ，或者不包含在标识符之间的 文字。对应于标识符 的弧是外部弧，其他弧是内部弧。内部弧具有的属性是：s o u r c e ， t e x t 和t a g ；外部弧还包括另外一个属性：u r l 。有了这样的映射关系和w e b o q l 的查询语 言，人们就可以对w e b 进行查询和重构操作了。另外为了查询方便，w e b o q l 还引入了导 航模式( n a v i g a t i o np a t t e r n ) 和尾变量( t a i lv a r i a b l e ) 的概念，由于篇幅的关系，这里就不加以详 细阐述了。 2 3 实用搜索引擎介绍 2 3 1 概述 今天，i n t e r a c t 上的数据已经可以说是泛滥成灾了。人们面临的问题已经不是需要的信 息在i n t e r a c t 上是否存在，而是如何既快叉准确的找到这些信息。于是人们提出了搜索引擎 ( s e a r c he n g i n e ) 的概念，来帮助用户找到所需要的信息。最初，人们试图采用普通的文本 检索的方法来搜索i n t e r n e t ，他们采用了对w e b 页面建立索引，根据用户输入关键词找到包 含该关键词的页面的方法。并且他们认为i n t e r a c t 上的搜索引擎应该和普通的文本检索一样， 需要尽可能多的返回符合查询的结果。但是，实际情况并非如此，撇开图像、视频等多媒体 信息不谈，就是一般的文本搜索引擎也和普通的文本检索有着本质的区别。因为i n t e r a c t 是 一个极其巨大的、分布的、动态变化和不断增长的资源库。建立搜索引擎必须考虑到这些特 性而不能简单的使用传统的文本检索的研究成果。例如，实用搜索引擎必须要考虑到网络 带宽，如何定期更新索引结构以保证与i n t e r a c t 的变化尽量同步等问题。而且搜索引擎用户 的要求也与文本检索用户的要求有着很大的区别，前者并不需要得到所有符合查询的结果。 而是更倾向于要求最相关的信息能出现在返回结果的最前面。 现在，世界上已经出现了几百个搜索引擎，它们的特点各不相同。在本节中我们将先 对其中比较有特点的儿个进行简单的介绍，最后对一个著名的搜索引擎g o o g l e 进行较为详 细的介绍。 表2 1 列出了若干搜索引擎的查询特性和具有该特性的一些著名的搜索引擎 ( 【a l t a v i s t a t c 4 】t 【d o g p i l e 】， e x c i t e 】，【h o t b o t 】，【l x q u i c k ，r n b c i 】， n o r t e m l i g h t ， p r o f u s i o n ，【r a g i n g tf w e b c r a w l e r ，【m s n ，【g o o g l e ，f l y c o s ，【s u r f w a x ，f a s k j e e v e s ， 【n a m e d r o p p e r s 】，【f o s s i c k 等) 1 0 墨鱼鉴笙兰翌塾查塑坠! 塑兰坠奎塑竺墅壁坚型 布尔操作 a i t a v i s t aa d v a n c e ds e a r c hi c 4i d o g p i l ei e x c i t eih o t b o tl h o t b o t s u p e r s e a r c h f i x q u i c km e t a s e a r e h 1n b c ip o w e rs e a r c hi n o m m l i g h ti p r o f u s i o n ir a g i n g s e a r c h ( 高级搜索) lw e b c m w l e r 可使用括号的完全布 a l t a v i s t aa d v a n c e ds e a r c hic 4i e x c i t eih o t b o tlh o t b o ts u p e r s e a r c