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

面向d e e pw e b 的对象检索关键技术研究 中文摘要 面向d e e pw e b 的对象检索关键技术研究 中文摘要 随着w e b 规模日益扩大，网络已经成为一个巨大的信息资源库。网络中包含了各 种类型的对象信息，其中很大一部分信息被“深藏于各类在线数据库中，用户只能 通过向接口提交查询来获取信息，这类信息被称为d e e pw e b 。如果这些对象信息能 够被集成起来，提供对象级的检索服务，用户就能够快速、准确地找到所需信息。 本文对面向d e e pw e b 的对象检索关键技术进行了分析研究，并提出了相关的算 法和模型。主要研究工作包括： ( 1 ) 采用聚焦爬虫技术处理d e e pw e b 数据源发现问题，提出了一个面向查询接 口的聚焦爬虫框架及算法。 ( 2 ) 。研究了基于u r l 模式和基于关键词查询的w e b 数据库内容获取方法。介绍了 利用文档对象模型和正则表达式来抽取网页中的对象信息。 ( 3 ) 对w e b 对象的变化规律进行了建模，提出要根据对象的平均变化频率，确定 本地数据的同步频率。 ( 4 ) 提出了一种混合对象匹配模型，该模型考虑了数据抽取中的多级错误，将对 象属性抽取准确率作为参数来平衡结构化和非结构化的相似度计算方法。 ( 5 ) 参与设计并实现了一个面向d e e pw e b 的对象检索平台。 此外，本文还对文中提出的方法和技术进行了实验，通过对实验结果的分析进一 步证明本文提出的技术方法是行之有效的。 关键词：d e e pw e b ，聚焦爬虫，泊松过程，对象匹配，对象排序，数据集成 作者：林超 指导老师：崔志明( 教授) a b s t r a c tr e s e a r c h0 1 1d e e pw e bo r i e n t e do b j e c t - l e v e li n f o r m a t i o nr e t r i e v a l r e s e a r c ho nd e e pw e bo r i e n t e do b je c t - - l e v e l i n f o r m a t i o nretrievalationr e t r i e v a l a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e r n e t ，w e bh a sb e c o m eal a r g ed e p o s i t o r yo fi n f o r m a t i o n t h e r ea r ev a r i o u sk i n d so fo b j e c t so nt h ew e b ，l a r g ep e r c e n t a g eo fw h i c ha l eh i d d e nd e e p l y i nv a r i e dk i n d so fo n l i n ed a t a b a s e s u s e r sh a v et of i l lo u tf o r m sa n ds u b m i tq u e r yt oo b t a i n t h ed a t a w ec a l lt h e ma sd e e pw e b i ft h e s ei n f o r m a t i o nc a l lb ei n t e g r a t e da n dp r o v i d e o b j e c t - l e v e li n f o r m a t i o nr e t r i e v a l ，u s e r sc a nf i n dw h a tt h e yw a n tm o r ee f f i c i e n t l y t h i st h e s i sd o e sr e s e a r c h e so nk e yt e c h n o l o g i e sa b o u td e e pw e bo r i e n t e do b j e c t - l e v e l i n f o r m a t i o nr e t r i e v a la n dp r o p o s e sr e l a t e da l g o r i t h m sa n dm o d e l s t h em a i nw o r ki n c l u d e s ： ( 1 ) u s ef o c u s e dc r a w l i n gt e c h n o l o g yt od e a l 埘t ht h ep r o b l e mo fd e e pw e bs o u r c e d i s c o v e r y p r o p o s ef r a m e w o r k a n da l g o r i t h mo fs e a r c hi n t e r f a c e so r i e n t e df o c u s e dc r a w l e r ( 2 ) r e s e a r c hm e t h o d sb a s e do nu r ls c h e m aa n dq u e r yt oo b t a i nd a t a b a s ec o n t e n t i n t r o d u c em e t h o d st oe x t r a c to b j e c ti n f o r m a t i o nb yd o ma n dr e g u l a re x p r e s s i o n ( 3 ) m o d e lt h er u l e so fh o ww e bo b j e c t sc h a n g e p r o p o s et h a tt h es y n c h r o n i z a t i o n f r e q u e n c ys h o u l d b ed e c i d e da c c o r d i n gt ot h ea v e r a g ec h a n g ef r e q u e n c yo ft h eo b j e c t ( 4 ) p r o p o s eah y b r i do b j e c tm a t c h i n gm o d e l 。t h i sm o d e lc o n s i d e r sm u l t i l e v e le l l o r si n d a t ae x t r a c t i o na n du s e sp r e c i s i o no fa t t r i b u t ee x t r a c t i o nt ob a l a n c es t r u c t u r e da n d u n s t r u c t u r e df e a t u r e so fo b j e c t si no b j e c tm a t c h i n g ( 5 ) p a r t i c i p a t ei nt h ed e s i g na n dd e v e l o p m e n to fp l a t f o r mo fd e e pw e bo r i e n t e d o b j e c t - l e v e li n f o r m a t i o nr e t r i e v a l m o r e o v e r , t h i st h e s i sa l s op e r f o r m se x p e r i m e n t so nt h em e t h o d sm e n t i o n e d e x p e r i m e n t ss h o wt h e s em e t h o d sa r ee f f e c t i v e k e y w o r d s ：d e e pw e b ，f o c u s e dc r a w l i n g ，p o i s s o np r o c e s s ，o b j e c tm a t c h i n g ， o b j e c tr a n k i n g ，d a t ai n t e g r a t i o n w r i t t e nb yl i nc h a o s u p e r v i s e db yc u iz h i m i n g i i 图表目录 图2 1 d e e pw e b 查询接口聚焦爬虫系统框架5 图2 - 2 查询接口聚焦爬行实验结果9 图3 - 1中国图书网图书一级分类目录1 1 图3 - 2 单属性查询接口和多属性查询接口1 2 图3 - 3 基于查询的数据库内容获取方法流程1 2 图3 - 4h t m l 代码片段及其d o m 树1 5 图3 - 5 图书页面数据抽取实例1 6 图3 - 6 平均变化频率属于各时间段内的对象比例1 9 图3 - 7 平均变化间隔为1 0 天的w e b 对象变化规律2 0 图4 - 1d e e pw e b 查询结果页面2 4 图4 - 2d e e pw e b 信息集成的流程2 4 图4 - 3 各对象匹配模型的平均准确率2 7 图4 - 4 不同抽取准确率下的匹配模型准确率2 8 图6 - 1面向d e e pw e b 的对象检索平台系统框架3 3 图6 - 2 聚焦爬虫参数的图形化配置3 4 图6 - 3图书信息抽取结果文件示例3 5 图6 4l u c e n e 工具包结构3 7 图6 5 服务定制模块界面3 8 图6 - 6图书集成检索引擎运行界面3 9 表2 - 1面向查询接口的聚焦爬行算法7 表3 - 1 对象信息抽取实验数据源1 6 表3 - 2 对象信息抽取实验结果1 7 表3 - 3 搜集的w e b 对象数据集概览1 9 表3 - 4 平均变化频率属于各时间段内的对象个数( 单位：个) 1 9 表4 - 1 三个不同抽取器的抽取准确率2 7 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体已经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均已在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名：型迭日 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签名：尘挫日 导师签名 强：勘8 s 混 日期：銎竺翌墨：兰i 锣 面向d e e pw e b 的对象检索关键技术研究 第1 章引言 1 1 研究背景和意义 第1 章引言 随着w e b 规模日益扩大、信息量以惊人的速度增长，网络已经成为一个巨大的 信息资源库。网络中包含了各种类型的对象信息，例如产品、论文、组织机构等信息。 传统的搜索引擎如g o o s e 、b s j d u 等通过接收用户提交的查询关键字，返回一组相关 的页面。用户必须花费大量的时间在这些网页中寻找他们需要的对象信息，因此利用 传统搜索引擎来检索这些对象效率不高。但是如果网络中的对象信息能够被抽取、按 领域集成起来，提供“对象级”的检索服务，用户就能够快速、准确地找到所需信息。 近几年，w e b 正在迅速地“深化”【l 】。i n t e m e t 上有大量页面是由后台数据库动 态产生，这部分信息不能直接通过静态链接获取，只能通过填写表单提交查询来获取。 由于传统的爬虫( c r a w l e r ) 不具有填写表单的能力，抓取不到这些内容。因此，现 有的搜索引擎搜索不出这部分页面信息，从而导致这部分信息对用户是隐藏、不可见 的，我们称之为d e e pw e b ( 又称为i n v i s i b l ew e b ，h i d d e nw e b ) 。研究表明，网络 上至少有4 3 ，0 0 0 9 6 ，0 0 0 个d e e pw e b 站点，d e e pw e b 页面信息是s u r f a c ew e b 信 息的5 5 0 倍【l l 。此外，d e e pw e b 还有结构性好、价值高、主题专一等特性，因此得 到了越来越多的关注，也日益成为研究热点。 实现大规模d e e pw e b 数据的集成是提供对象级的检索服务的前提。由于w e b 数据库的异构性和自主性，如何从各个w e b 数据库中获取、集成对象信息成为一项 非常具有挑战性的工作。 1 2 国内外研究现状 对d e e pw e b 数据资源进行大规模的利用，从原理上来分主要有如下三种方法： 1 基于分类目录的方法。国外仅有b f i g h t p l a n e t l 2 1 、i n v i s i b l e w e b t 3 1 等公司生产相 关产品，他们把d e e pw e b 查询接口按其所属类别进行分类，用户可以根据类别找到 所需要的查询接口。由于这种方法对查询接口的分类进行严格区分，通常还采用多层 次的分类方式，所以需要较多的人工干预，自动化程度不高。目前国内外还没有针对 第1 章引言面向d e e pw e b 的对象检索关键技术研究 中文d e e pw e b 查询接口的分类目录。 2 基于全局查询模式的方法。从分布式数据库角度来说，所谓全局模式( g l o b a l s c h e m a ) 就是把现有的各个分布的数据库的模式集成起来，将公用的数据定义整合， 并解决对同一个数据的不同表示方法之间的冲突问题。具体实现和元搜索引擎类似， 即在每个领域中，提供给用户一个全局的查询接口。这个接口接收用户的查询，并把 查询派发到各个成员接口进行查询，然后把从各个成员数据库中得到的结果组合起 来，返回给用户。采用这种方法的典型系统有m e t a q u e r i e r 4 j 、w i s e i n t e g r a t o r 5 1 。在 这种架构方式下，涉及到的具体技术主要包括：接口属性的抽取、模式匹配、查询派 发、分类和聚类、查询结果集成等。 3 在本地集成w e b 数据库内容的方法。这种方法首先自动获取w e b 数据库的 内容，接着利用信息抽取技术抽取所需信息，最后把数据集成到本地数据库中供用户 检索。该方法与上述两种方法的最大区别在于：上述两种方法的数据信息分布在各地 的w e b 数据库中，它们是自治的、异构的。用户查询时在线地从各w e b 数据库获取 信息。而本方法需要把w e b 数据库中的对象数据尽可能多的下载集成到本地数据库 中，并对这些数据进行管理，用户查询的结果也来自本地数据库。在文献 6 】 7 】 8 中， 研究了这种架构方式。国内外已有一些学者对其中的具体技术进行了初步研究，包括 d e e pw e b 数据源发现、w e b 数据库内容获取、信息抽取、对象匹配、排序技术等。 各部分技术的具体研究情况将在后续章节作进一步的介绍。文本所研究的面向d e e p w e b 的对象检索关键技术都是在这种架构下进行的。 1 3 本文组织 本文共分为7 章： 第1 章介绍了研究背景及意义、国内外研究现状以及本文的结构安排。 第2 章研究了d e e pw e b 数据源发现问题，提出了一个面向查询接口的聚焦爬虫 框架及算法。 第3 章研究了基于u r l 模式和基于关键词查询的w e b 数据库内容获取方法、利 用d o m 模型和正则表达式来抽取对象数据、以及对象信息的同步等问题。 第4 章研究了对象匹配技术，并提出了一种混合对象匹配模型。 2 面向d e e pw e b 的对象检索关键技术研究第1 章引言 第5 章叙述了一种查询结果页面中的对象排序技术。 第6 章详细介绍了面向d e e pw e b 的对象检索平台的框架及功能模块。 第7 章总结了本文所做的工作，说明了工作的特色与创新之处，并对今后的工作 进行了展望。 第2 章面向查询接口的聚焦爬虫 面向d e e pw e b 的对象检索关键技术研究 第2 章面向查询接口的聚焦爬虫 2 1 聚焦爬虫技术 爬虫程序是指会自动地、永不停止地在网络上搜集网页的程序，它是搜索引擎的 一个重要组成部分。传统搜索引擎的爬虫采用宽度优先或者深度优先策略，尽可能多 的抓取网页。而聚焦爬虫的作用是跟踪网络上的链接，有选择的抓取和某一主题相关 的内容。它根据一定的网页分析算法过滤与主题无关的链接，保留有用的链接并将其 放入等待抓取的u r l 队列。然后，它将根据一定的搜索策略从队列中优先选择最有 价值的链接进行访问，并重复上述过程。一类方法根据文档间链接关系来计算链接的 价值，例如p a g e r a n k 算法、h i t s 】算法。另一类方法根据主题与页面内容、链接信 息的相关性大小来评价链接的重要性。例如b e s t - f i r s t 算法，利用向量空间模型计算页 面向量与主题向量的相似度，两者相似度越高，则认为该页面中链接的价值就越高。 还有一些学者除了考虑页面或链接本身的特征以外，还考虑了通向目标页面路径上的 特征。r e n n i e 等使用了强化学( r e i n f o r c e m e n tl e a n l i n g ) 的方法来改善爬虫的效率【翻， 其根据链接q 值的不同，把链接划分到多个( = 3 ) 不同的组里。而处于中间几组的 那些链接，就有相应的未来回报价值。d i l i g e n t i 采用了语境图4 ( c o n t e x tg r a p h ) 方法 来提高效率【1 3 】。这种方法的着眼点在于网络中页面离目标页面的远近是不同的，由此 形成了层次关系。最内层( 第0 层) 是属于该主题的一些典型的页面集合( 种子页面) ， 然后通过搜索引擎提供的查找链接功能来查找指向最内层页面的所有页面集合，把它 作为第1 层。接着把第1 层页面放入搜索引擎中去收集第2 层的页面，以此类推，直 到达到某个预先指定的层次。对于一个新的链接，利用前面几层信息训练好的分类器 判断该页面属于哪个层次，由此确定该链接的价值大小。 2 2 查询接口聚焦爬虫设计 为了能够对d e e pw e b 资源进行大规模集成检索，首先我们必须去发现、搜集这 些资源。但是w e b 具有规模大、变化快等特点，如何去自动的发现、搜集w e b 数据 4 面向d e e p w e b 的对象检索关键技术研究 第2 章面向查询接口的聚焦爬虫 库的查询接1 3 是一个重要问题。由于查询接口在网络上的分布非常稀疏，而计算资源 是有限的，面向查询接口的聚焦爬虫的作用就是采用一定的策略，跟踪有价值的网页 链接，过滤大量无用的链接，从而高效率的发现和搜集特定领域内的查询接口。 2 2 1 系统框架 为了处理网络上表单分布很稀疏的问题，我们通过以下方法让爬虫忽略没有价值 的路径：爬行针对一个特定的主题；学习指向含有查询接口的页面的链接、路径特征； 使用合适的爬行停止条件。d e e pw e b 查询接1 2 1 聚焦爬虫的系统框架如图2 1 所示。 爬虫利用“页面分类器 和“链接分类器”来指导爬行。“页面分类器 用来把页面 分入某一主题。它使用如下策略：当爬虫新抓取一个页面p ，如果p 属于当前主题， 该页面内的表单和链接被抽取出来。“链接分类器 被用来识别那些有价值的链接， 它们直接指向含有查询接口的页面或者经过若干步可以到达含有查询接口的页面。 “链接分类器 检查来自当前主题页面中的链接，并把属于当前站点的链接加入到“当 前站点链接队列 ，否则如果链接指向其他站点，它所在站点的首页地址会被加入“外 部站点根链接队列”。如果“外部站点根链接队列”中已包含该首页地址，则只需调 整其权重。“表单分类器”用来剔除无效的表单。如果一个表单被“表单分类器 判 定为查询接1 2 1 ，则该表单被加入到“d e e pw e b 数据源”库中存放。 图2 - 1d e e pw e b 查询接1 2 1 聚焦爬虫系统框架 第2 章面向查询接口的聚焦爬虫面向d e e pw e b 的对象检索关键技术研究 2 2 2 链接分类器 目前有许多成熟的文本自动分类方法【6 3 】，包括概率模型方法，关系学习方法，支 持向量机方法等。其一般过程都是通过对已经分好类的一组训练文本的学习来自动创 建分类器，通过有指导的学习对测试文本进行分类。我们使用了朴素贝叶斯分类算法 来分类链接特征。朴素贝叶斯分类器( n a i v eb a y e sc l a s s i f i e r ) 假定特征向量的各分 量间相对于决策变量是独立的。对于特征向量为x = 【x l ，x 2 ，x d 】1 。的测试样本，它属于 第c i 类的概率按下式计算： d e ( c ，lx ) = e ( c ，) p ( x ) 兀p ( x ，i c i ) ( 2 - 1 ) 1 = 1 其中p ( c i i x ) 代表x 属于类c a 的概率。对每一个类别都计算上式的概率，最终的识别结 果是使概率值最大的那个类。在系统中，“链接分类器”依据链接的特征来发现有价 值的链接。特征主要是锚文本及链接上下文文本、u r l 地址、链接中的图片地址。经 观察，很多链接中用图片代替了锚文本，所以我们把图片的地址信息也考虑进去，从 而提高分类结果的精确性。把上述信息经过分词并统计词频后，就得到了该链接的特 征向量x 。 2 2 3 页面分类器 “页面分类器 采用了朴素贝叶斯分类算法。先用收集的各领域文本训练分类 器。然后当爬虫返回一个页面p ，“页面分类器”分析页面，并且计算该页面属于当前 主题的分值。如果分值大于某个阈值，爬虫认为该页面与当前主题相关。 2 2 4 表单分类器 因为我们要发现d e e pw e b 数据源，所以我们要过滤掉那些不是查询接口的表单， 例如：登陆注册、订购商品表单。“表单分类器 利用了c 4 5 决策树算法f 6 3 1 ，用来 判断表单是否是查询接口。据研究，决策树算法在查询接口判定中错误率是最低的【1 9 1 。 2 2 5 聚焦爬虫算法 6 面向d e e p w e b 的对象检索关键技术研究 第2 章面向查询接口的聚焦爬虫 面向查询接口的聚焦爬行算法如表2 1 所示。待访问的链接存放在“当前站点链 接队列 和“外部站点根链接队列”中，已访问的链接存放在已访问队列中。 表2 - 1 面向查询接口的聚焦爬行算法 耢久： s i t e u r l q u e u e 一外部站点根链接队列 l o c a l u r l q u e u e 一当前站点链接队列 输出t d e e p w e b s o u r c e s d b d e 印w e b 数据源集合库 l ：b e g i n 2 ：把若干种子u i 也加入s i t e u r l q u e u e 3 ：按权重由高到低对s i t e u r l q u e u e 排序 4 ：t e m p l i n k 卜移除s i t e u r l q u e u e 中第一个链接，把它放到l o c a l u r l q u e u e r 扣 5 ：w h i l e ( 不符合爬行停止条件时) d o 6 ：l i n k 卜移除l o c a l u r l q u p “g 中的第一个链接 7 ： v i s i t e d 卜l i n k v i s i t e d 是已经访问过的链接队列 8 ：p a g e + - 下载砌七对应的页面 9 ： 用页面分类器判断p a g e 是否属于当前主题 1 0 ： i f ( p a g e 不属于当前主题) 1 1 ： 跳转至第6 行 1 2 ：e n d i f 1 3 ： 抽取p 昭p 中的d e e pw e b 查询接口，并把它加入d e e p w e b s o u r c e s d b 中 1 4 ： u r l l i s t 卜分析并抽取出p a g e 所有的链接 1 5 ： f o r ( u r l l 豇t 中的每个链接功d o 1 6 ： i f ( 矗的深度 3 ) 1 7 ： 跳转至第1 5 行，处理下一个 1 8 ：e n d i f 1 9 ： i n f o 卜抽取与链接，f 相关信息 2 0 ： s c o r e 卜用链接分类器给i n f o 评分 2 1 ： i f ( s c o r e 阈值岛) 2 2 ： i f ( 1 i 不属于当前站点) 2 3 ： 把l i 所在站点的首页地址加到黜g u r q 甜g “e 中，并更新该站 点的权重 2 4 ： e l s e 2 5 ： 把砌入到l o c a l u r l q u e u e r p 2 6 ：e n d i f 2 7 ：e n d i f 2 8 ：e n d f o r 2 9 ：对l o c a l u r l q u e u e 和s i t e u r l q u e u e 内链接按价值大小重新排序 3 0 ：i f ( l o c a l u r l q u e u e 为空) 3 l ： 跳转至第4 行 3 2 ：e n d i f 3 3 ：r e p e a t 3 4 ：e n d 当判断一个链接是否要放入待访问链接队列时，我们要考虑以下三个问题：1 该链 接的深度是否小于等于3 ( 因为9 t 6 的d e e pw e b 查询接口所在页面的深度小于等 7 第2 章面向查询接口的聚焦爬虫 面向d e e pw e b 的对象检索关键技术研究 于3 【1 1 ) 。2 该链接所在页面的内容是否与当前主题相关。如果页面内容与主题无 关，则不考虑其中的链接。3 该链接直接或间接地指向含表单页面的概率是否大于 阈值03 。爬虫对当前站点的爬行何时停止也是一个重要的问题。因为据统计，一个 站点平均含有4 2 个查询接i z l ，如果一个站点抓取的页面数超过了阈值0l ，或者已 获取了超过预定义数目的查询接口数，对该站点链接的爬行就可以终止了。 2 3 实验及分析 2 3 1 收集训练数据 以j o b 领域为例，说明“链接分类器”的训练集的采集方法：对一些有代表性的 求职网站，手工提取站点页面中各个链接相关信息( 包括锚文本及链接周围文本、u r l 地址、链接包含的图片地址等) 。并根据该链接是否指向包含查询接口的页面把信息 分别存入j o kh a v e f o r m t x t 和i o kn o f o r m t x t 。同时要注意以下几点问题：1 人工收 集训练集时，有一些明显的噪音信息，要剔除掉。2 在每个主题爬行时，当前站点内 及外部站点的链接都要处理。这增强了系统的可扩展性。3 当爬行了一段时间以后， 随着待访问链接队列中链接数量成几何级增长，内存消耗相当快，c p u 利用率变得 很低。所以要限制相关数据结构占用内存的容量，当其容量大于一定数值时要把数据 利用持久化技术( s e f i a l i z a t i o n ) 写到磁盘上。 2 3 2 实验结果 我们选取三个领域( a u t o m o b i l e 、j o b 和h o u s i n g ) ，分别采用b e s t - f i r s t 策略和 我们的爬行策略( d wf o c u s e d ) 进行爬行。本实验中，我们把控制爬行停止的两个阈值 分别设为5 、1 0 0 ，即当某站点已发现的不同的查询接口数多于5 或下载的页面数大 于1 0 0 时，该站点中的链接就不再处理了。实验结果如图2 2 所示，横坐标是爬虫下 载的网页数量，而纵坐标代表在这些网页中含有的查询接口数量。可以看到我们的爬 行策略取得了比较好的效果，大大提高了爬行的效率。 2 4 本章小结 8 面向d e 印w 曲的对象检索关键技术研究 第2 章面向查询接口的聚焦爬虫 本章采用聚焦爬虫技术处理d e e pw e b 数据源发现问题，提出了一个面向查询接 口聚焦爬虫框架。它把待抓取链接队列细分为“当前站点链接队列 和“外部站点根 链接队列 ，这样可以获得页面在该站点内的深度信息，避免抓取大量无关的页面。 实验结果表明该策略是高效的。今后，我们打算考虑更多的信息( 例如d o m 树中的 信息) ，我们还将利用并行分布式技术来进一步提高爬虫系统的性能，以适应更大规 模爬行的需求 a m o m o b f l e 3 5 0 0 一 n j u u u ， 藏2 5 0 0 2 0 0 0 “ 端1 5 0 0 膏。 曩1 0 0 0 j ， 榭 5 0 0 。 n q 矿，矿，测一。b 览e s t 亿- f i 。r s t 。j 下袭页面数 j o b 3 5 3 0 0 0 2 5 0 0 凝f - 2 0 0 0 鞘1 5 0 0 。， 震l o o o 相5 0 0 广 0。 毋毋爹毋萝 + b e s t n i s l _ - d wf o c u s e d 下载页面致 h o u s i n g 4 0 0 0 j a u u ， 3 0 0 0 藏2 5 0 0 口2 0 0 0 穗r - ， _ b u u 。 基0 0 0 - -cnn。1 _ a u u 幺7 。 0 爷扩扩扩二一b 吐e s t - 一f i r s t 下载页面敷 图2 - 2 查询接口聚焦爬行实验结果 9 第3 章w e b 数据库内容获取及信息抽取技术 面向d e e p w e b 的对象检索关键技术研究 第3 章w e b 数据库内容获取及信息抽取技术 3 1w e b 数据库内容获取方法 d e e pw e b 数据库中包含了大量高质量的结构化对象信息。但由于这些数据库是 自主的，我们无法把这些数据直接迁移到本地数据库中。所以我们必须采用一定的技 术把这些对象信息采集下来，并存放到本地数据库中。已经有一些学者对此问题进行 了研究。文献 2 0 】针对文本数据库，提出了自动生成查询的理论框架及生成查询的策 略，并对数据库内容获取问题进行了形式化处理。文献 2 1 1 研究了结构化数据库环境 下如何高效的生成查询项。它用“属性值”图来描述数据库，并把数据库内容获取 问题转变为对“属性值”图的遍历问题。文献 2 2 1 提出了基于图模型的数据库采样方 法，通过查询接口从数据库中增量的方式获取近似随机的样本，并用保存在本地的记 录生成下一次的查询。 本文对两种w e b 数据库内容获取方法进行了研究：基于u r l 模式的内容获取方 法和基于查询的内容获取方法。 3 1 1 基于u r l 模式的方法 网页模板规律告诉我们在同一个网站上属于同一主题的页面的u r l 有着很强相 似性，也就是说u r l 遵循一定的模式。比如在图书电子商务网站中国图书网 ( h t t p ：w w w b o o k s c h i n a c o r n ) 上，里面所有包含图书信息的网页地址都符合统一的 模式：“h t t p ：w w w b o o k s c h i n a c o m o 9 】+ h t m ”，其中“ 0 - 9 + ”代表若干位连续阿 拉伯数字。有了这个模式，就可以得到包含图书信息的网页地址集合，并利用爬虫程 序把所有页面抓取下来。 我们观察网站还发现这样的规律：网站基本上有两种页面组成：目录页面和内容 页面。例如在电子商务网站里有分类导航页面和商品页面。分类导航页面就是目录页 面，包含大量指向内容页面的链接，例如图3 1 是中国图书网的图书一级分类目录页。 而商品页面是内容页面，包含商品的具体信息。 1 0 面向d e e pw e b 的对象检索关键技术研究第3 章w e b 数据库内容获取及信息抽取技术 通过u r l 模式获取w e b 数据库内容方法的优点在于：可以无遗漏的获取数据库 中所有内容，而且效率很高。但这种方法的局限性是：如果w e b 数据库没有提供分 类目录，或者当没有一个统一的u r l 模式可以描述包含对象信息的页面，则该方法 很难甚至无法实施。 。e 1 n n 6 ：吲f 舢暇口一一一t t c 蛐 文件逆)蝙辑遥)查看凹收穗工且嘎)帮助趔) 静 0 后退，0 。固固孙r 户搜索收藏天。当，法国- l o 地址o ：韵h t t p ，b 。k h i c b 。h k l n d ，：o r t - v ：臼转到 i 5 = 攫 罗一 l k 中b o o 国k s c 图h i “a 书, c o 网m ：竺芝? 冀篓? ： 7 中团母书网台：育分站鳍委疆蠹图菇强i i 醇润西汪；纛茬裾员茹b 藉函心一 固霉毫离漠南羲茬蠢孬 ；雾勇书名 目书名：t 麓薹。h 面绍鹫紊瞄奎溺箬爰5 舂挢茴莩 宗教、术数 ! 医药卫生西医学、预防医学 中国笤掌 基医学 外国暂学 内利擘 一一绅学 ：，二抖! 国i n f e r r e r 图3 - 1 中国图书网图书一级分类目录 3 1 2 基于关键词查询的方法 d e e pw e b 查询接口根据其包含的查询条件的个数可以分为两类：单属性查询接 口和多属性查询接i s ，分别如图3 2 ( a ) 、( b ) 所示。 基于查询的数据库内容获取方法的一般工作流程如图3 3 所示：选取查询词，填 写表单提交查询，系统会返回符合条件的结果页面。不断重复上述步骤，直到所有可 能的查询都递交完毕或者到达一定的查询停止条件。 在查询关键词的选择上，主要有以下三种策略：1 随机选择。从字典或者文档 集产生的术语集中，每次随机的选择一个关键词，然后提交查询。这种方法的缺点是 随机选择的词可能和数据库中的内容根本不属于同一主题或者相关性极小，因此得到 的结果也可能是很差的。2 根据词频高低选择。在字典或者术语集中，按术语的词 频由高到低的顺序排列，依次作为关键词提交。这种策略基于如下假设：在字典或者 术语集中出现频率高的词语，在w e b 数据库中匹配到的记录数多的可能性也比较大。 1 1 第3 章w e b 数据库内容获取及信息抽取技术 面向d e e pw e b 的对象检索关键技术研究 但这种假设忽略了如下事实：即d e e pw e b 数据库通常是主题单一的，所以一般情况 下出现频率高的词语在特定领域里可能出现频率会很低。3 自适应的关键词选择策 略。这种策略分析本地数据库中已获取的数据内容，通过推导得到下一个最优的关键 词，这个关键词能返回较多的新记录。此策略的目的是希望通过不断发现最优的关键 词，从而通过最少次数的查询，获得尽可能多的w e b 数据库内容。 图书橙索组合查找， t - l = = = = = = = = = = = ( b ) 图3 - 2 单属性查询接口和多属性查询接口 策略1 及策略2 实现起来比较简单，但效果不够好。本文采用自适应的关键词选 取策略。此策略适用于图3 2 所示的单属性查询接口及多属性查询接口，区别仅在于 向后者提交的关键词需要与相应的属性对应起来，而且查询项由一个或者多个不同属 性上的值构成。 图3 3 基于查询的数据库内容获取方法流程 面向d e e pw e b 的对象检索关键技术研究第3 章w e b 数据库内容获取及信息抽取技术 定义一个查询项q i 的价值为f 2 0 】： 喇= 涨 ( 3 1 ) 其中p n e w ( q i ) 代表提交查询q i 后预计能得到的新记录个数占数据库总记录数的比例。 在假设各查询项之间互相独立的前提下，满足如下关系1 2 0 1 ： ? p n e w ( q , ) = p ( q iv v q j ) 一p ( q lv v q t 1 ) = p ( q i ) 一p ( q lv v g f 1 ) p ( q jlq lv v q l 一1 )( 3 - 2 ) 其中p ( q i ) 代表w e b 数据库中与q i 匹配的记录个数占数据库总记录数的比例，若假设 各查询项互相独立，可通过p ( 仍i q lv v q j 1 ) 估算。p ( q lv v q h ) 是查询项 q l ，q 2 ，q i 1 都提交以后得到的总记录数占数据库总记录数的比例，即本地已获取的该 w e b 数据库的记录百分比。项p ( q ，iq 1v vq f 1 ) 可以通过统计q i 在q l ，q 2 ，q i 1 返回 的文档中出现的比率来估算。c o s t ( q i ) 是提交查询q i 的代价，由查询消耗的网络带宽 衡量，具体可由下式计算： c o s t ( q i ) = p ( q i ) k ( 3 - 3 ) p ( q i ) 含义同上。而k 代表每个结果页面能显示的最大记录数。 因此，在每次提交查询之前，我们计算各候选查询项的价值p e r f o r m ( q i ) ，并把取 得最大价值的查询项向接口提交。 在图3 3 中，查询提交终止的条件主要依据几个原则：1 如果知道或者可以估算 出w e b 数据库中记录的总数，那么当累计得到的记录数达到或者接近总数时，可以 停止查询了。2 如果数据库中的记录总数无法估计，则当最近几次查询得到的新记 录数都小于一定的阈值，则停止查询。 从w e b 数据库获取的内容以网页的形式存在，因此必须借助于下文将要介绍的 信息抽取技术把需要的信息抽取出来。 3 2 对象信息抽取技术 3 2 1w e b 信息抽取概述 第3 章w e b 数据库内容获取及信息抽取技术面向d e e pw e b 的对象检索关键技术研究 从网页中抽取信息的工作通常由一种叫做“包装器”( w r a p p e r ) 的程序完成。 包装器是一个程序，用于从特定的信息源中抽取相关内容，并以特定形式加以表示。 在因特网环境下，包装器的目的是把网页中储存的信息用结构化的形式储存起来，以 方便进一步的处理。 包装器可以用手工方式产生，如文献【2 4 】介绍的包装器需要一个规则配置文件， 其中记录了抽取规则，该文件需要人工书写。 由于手工方式的抽取技术费时费力，且难以维护，所以它的应用受到了极大的限 制。为解决此问题，有些学者引入了本体和机器学习的方法，如启发式规则、聚类、 归纳学习等，从而实现了半自动、全自动的数据抽取。文献【6 0 】介绍了系统b y u ，它 事先需要由领域专家采用人工方式书写某一领域的o n t o l o g y 。系统根据边界分割符和 启发信息将源文档分割为多个描述某一事物不同实例的文本块，然后根据o n t o l o g y 中的描述信息产生抽取规则，对每个文本块进行抽取获得各语义项的值。但是 o n t o l o g y 需要领域专家花费大量的时间来建立，故使用不便。文献 3 8 t u 用了页面呈 现时的视觉特征及标签树的结构信息来自动生成封装器。文献 2 9 】通过计算d o m 树 中子树的“新奇度”来发现数据块，进而自动的抽取出对象数据，并推导出某领域的 对象模式。文献【3 4 】基于微软亚洲研究院提出的v i p s 算法，把网页转化为视觉信息 块树，并定位数据区域、得到记录信息。 3 2 2 文档对象模型 d o m ( d o c u m e n to b j e c tm o d e l ，文档对象模型) f 6 1 j 是一种供h t m l 和x m l 文档使 用的应用程序编程接i ( a p i ) ，定义了文档的逻辑结构以及访问和操作文档中各个部 分的标准方法。d o m 树是文档的逻辑表示，其结构简单清晰，意义表述明确，形成 一种层次化的树结构。它包括根元素和各类节点。结点是文档对象模型中最基本的对 象，结点通过继承关系形成一棵d o m 树。图3 4 是一个h t m l 代码片段及其对应的 d o m 树结构。 3 2 3 正则表达式 正则表达式就是由普通字符( 例如字符a z ) 以及特殊字符( 称为元字符) 组成 1 4 面向d e e pw e b 的对象检索关键技术研究 第3 章w e b 数据库内容获取及信息抽取技术 的文字模式。该模式描述在查找文字主体时待匹配的一个或多个字符串。例如表达式 “1 3 d 9 )