（计算机应用技术专业论文）基于网格的web信息抽取技术的研究与实现.pdf

土摘篮 基于网格的w e b 信息抽取技术的研究与实现 中文摘要 w e b 文档往往用各种复杂的h t , i l 标记来包装内部数据，但这种方式 给应用系统直接使用w e b 文档中的数据带来了困难。w e b 信息抽取是处理 海量数据且需要各种复杂算法支持的一种技术，因此它在一般平台上的 工作效率不是很好。网格能为复杂应用提供分布式并行环境，它面向服 务的开放式结构能提高应用的灵活性和代码重用率。因此，结合网格技 术来开发一个自动的w e b 信息抽取应用有着非常重要的意义。 本文首先介绍了w e b 信息抽取的有关技术，分析了自动抽取系统 r o a d r u n n e r 的算法和优缺点；接着，介绍了网格的相关知识，重点研究 网格应用的特性。在这之后，本文重点解决两个问题：如何自动抽取w e b 信息和如何在网格中实现。在第一阶段，本文通过有效的启发规则解决 自动获取一批相似页面的问题，提出并实现了二级页面噪声处理的方案 和算法，完成了自动归纳抽取规则的算法，并最终实现了一个完整的面 向数据密集型页面的w e b 信息抽取系统。在第二阶段，本文首先分析了 w e b 抽取应用的可并行化部分，给出了相应的网格应用模型和编程模式， 安装和配置了网格平台，开发和部署了一组相应的服务，并最终结合j a v a 多线程技术解决了抽取应用的并行化问题。 本课题主要有两方面的意义：从w e b 信息抽取方面来看，能提高抽 取系统的自动化程度和数据抽取精度；从网格应用方面来看，通过j a v a 线程和网格服务相结合的方式能有效改善传统应用的运行效率，并为网 格应用开发提供了一种新的实现思路。 关键词：w e b 信息抽取相似页面噪声处理，网格应用，g t 4 作者：贡正仙 指导老师：朱巧明 !卜k 皇坠竺一 ! ! ! ! ! ! 塑! 竺! ! ! ! ! ! 竺21 1 竺! ! 里! ! ! ! ! ! 型! ! ! ! 鱼! 尘! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ! ：! ! ! 竺! ! ! 型! ! 鱼! ! t h er e s e a r c ha n di m p l e m e n t a t i o no faw e bi n f o r m a t i o n e x t r a c t i o ns y s t e mb a s e do ng r i d a b s t r a c t t h ed a t ae x i s t i n gi nw e bd o c u m e n t sa r eu s u a l l yw r a p p e db yam a s so f h t m ll a b e l s ，w h i c hb r i n g st r o u b l et oa p p l i c a t i o ns y s t e m st h a t d i r e c t l yu s e d a t ai nw e bd o c u m e n t s w e bi n f o r m a t i o ne x t r a c t i o nf a c e sm a g n a n i m i t yd a t a a n dd e p e n d so nal o to fc o m p l e xa l g o r i t h m s ，w h i c hr e s u l t si np o o rw o r k e f f i c i e n c y o t lc o m m o n p l a t f o r m g d d c a l lo f f e rd i s t r i b u t e d p a r a l l e l e n v i r o n m e n t ，w h o s es e r v i c e o r i e n t e do p e na r c h i t e c t u r er a i s e sf l e x i b i l i t yo f a p p l i c a t i o na n dc o d er e u s er a t e s or e s e a r c ha n dd e v e l o p i n ga na u t o m a t i cw e b i n f o r m a t i o ne x t r a c t i o na p p l i c a t i o nb a s e do ng r i di sav e r y i m p o r t a n ta n d s i g n i f i c a n tt a s k t h et h e s i si n t r o d u c e sr e l a t e dt e c h n i q u e so fw e bi n f o r m a t i o ne x t r a c t i o n a n da n a l y s e st h e a l g o r i t h ma d o p t e db yr o a d r u n n e r , w h i c hi sa ne x c e l l e n t a u t o m a t i cw e bi n f o r m a t i o ne x t r a c t i o ns y s t e m t h e nt h et h e s i sp r e s e n t sr e l a t e d w o r ko f g r i d ，f o c u s i n go nr e s e a r c h i n gt h ec h a r a c t e r i s t i co f g r i da p p l i c a t i o n i nt h e f o l l o w i n gs e c t i o n s ，t h et h e s i ss o l v e st h et w op r o b l e m s ：o n ei sh o wt o e x t r a c tw e bi n f o r m a t i o na u t o m a t i c a l l ya n da n o t h e ri sh o wt oi m p l e m e n ti to n g r i dp l a t f o r m i nt h ef i r s tp a r t ，t h et h e s i ss o l v e st h ep r o b l e mo fa u t o m a t i c a l l y o b t a i n i n g as e to fs i m i l a rp a g e st h r o u g hs o m ee f f e c t i v e h e u r i s t i cr u l e s ，a n d p u t sf o r w a r dt w oa l g o r i t h m sr e s p e c t i v e l ya i m i n ga tt w o s t a g e dc l e a n i n gw e b n o i s yi n f o r m a t i o na n dd e d u c i n ge x t r a c t i o nr u l e sa u t o m a t i c a l l y i nt h es e c o n d p a r t ，t h i st h e s i sa n a l y s e sp a r a l l e l e n a b l e dp a r t s o ft h ew e be x t r a c t i o n a p p l i c a t i o n ，g i v e s t h e c o r r e s p o n d i n g g r i d a p p l i c a t i o n m o d e la n d p r o g r a m m i n gm o d e ，i n t r o d u c e sh o wt oi n s t a l la n dc o n f i g u r et h eg r i dp l a t f o r m ， d e s c r i b e st h ed e t a i l e ds t e p so fd e v e l o p i n ga n dd e p l o y i n gas e to ls e r v i c e s ，a n d d e d i c t sh o wt oi m p l e m e n tp a r a l l e l i s m f o rt h ew e bi n f o r m a t i o ne x 觚c t l o n a p p l i c a t i o nb yj a v a m u l t i - t h r e a dt e c h n i q u e t h e r ea r et w oc o n t r i b u t i o n s i n t h i sr e s e a r c h f i r s t l y ，i th e i g h t e n s a u t o m a t i cd e g r e ea n dd a t ap r e c i s i o n f o rt h ew e bi n f o r m a t i o ne x t r a c t i o n s e c o n d l v ，i ti m p r o v e st h ea p p l i c a t i o n w o r ke f f i c i e n c yr e c u r r i n gt o g r i d t e c h n i q u e sa n do f f e r san e w i d e af o rg r i d e n a b l e da p p l i c a t i o nd e v e l o p m e n t k e y w o r d s ：w e b i n f o r m a t i o ne x t r a c t i o n ，s i m i l a r w e bp a g e s ，w e bn o i s y i n f o r m a t i o np r o c e s s i n g g r i da p p l i c a t i o n ，g t 4 w r i t t e nb yg o n gz h e n g x i a n s u p e r v i s e db yz h uq i a o m i n g i i i 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郏币声明：所提交的学位论文是本人在导师的指导卜独立 进行研究工 1 jj 折取得的成果。除文中已经注明l jj j l j 的内容外，木论文 小含其他个人j 哎北体已经发我或撰写过的研究成果，也卅i 岔为铁得苏 州大学或其它教育机构的学位让辂而使用过的材料。对本文的研究作 m 重要贡献的个人_ 千( j 壤体，均己在文中以明确力式标明。木人承担术 j 皂i 蝈的法律r 仔。 研究生签名：么兰! 塾 日 期：2 理：皇：加 学位论文使用授权声明 券州人学、r ，隔科学技术信息研究所、1 1 | l 家i 习书馆、消1 # 大：譬论 义合作爿5 、q 社科院立献 i 息情报h 心有权保留本人所送交学位论 义的复印件年| 【i 乜f 文档，可以_ = j 乇用影印、绵印或其他复制手段保存论 义。本人电子文档的内容年纸质论文的内容柏一致。除神i 保密期内的 侏晰绝文外，允许论文铍阋和借阅可以公布( 包括刊登) 论史的 全部或部分内棒。论文的公枷( 包括刊迸) 授权苏州大学学能办办理。 砂 究：l ! 签幺： 日 划：一 导 | 1 j 签名： 基于问格的w e b 信息抽墩技术的研究与实现 第一章引言 1 1 课题提出 第一章引言 迄今为止，w e b 是世界上最密集的信息来源，蕴藏着丰富的具有潜在 价值的知识。目前，w e b 数据大都以h t 札形式展示，但这种半结构化的展 示形式缺乏对数据的描述，没有清晰的语义和明确的模式，因此应用程 序就无法直接解析并利用w e b 上的海量信息。为了增强w e b 数据的可用性， 产生t w e b 信息抽取技术“1 。这种技术通过对特定网页的结构和数据项特 征进行分析，可以将网页预定义数据抽取出来，并为其增加一定的语义 和模式信息。w e b 抽取为应用程序再利用w e b 中的数据提供了可能，因此 有着明显的优势和广阔的前景，是当今多个领域的研究热点。w e b 信息抽 取具有下面两个特点： 第一，它处理的对象是海量信息，这些信息所处平台是异构的，信 息本身也是形态各异并被不断更新； 第二，目前w e b 文档大多是半结构化的，缺乏语义连续性和相关性， 在对w e b 文档进行深层次处理时，需要用到一些时空复杂度较高的处理算 法和技术。 解决以上问题的一个重要途径是需要高性能的存储资源和计算资 源。 网格心1 技术的研究开始于2 0 世纪9 0 年代，发展到今天已被认为是继 i n t e r n e t 和w e b 之后的第三次信息技术浪潮。网格技术与传统分布式技术 的主要区别在于：在没有集中控制机制的情况下，通过对计算资源进行 大规模共享，满足应用对高性能计算的要求。网格技术充分实现了资源 共享，并且这种共享是动态的、柔性的和协作式的。网格技术不仅能提 高计算的工作效率，而且更充分地利用了闲置的资源，因此，在网格平 台上研究w e b 信息抽取是一个很自然的课题，具有很重要的意义。 本课题首先希望实现一个自动程度较高的w e b 信息抽取系统，然后针 第章引言 基于网格的w e b 信息抽取技术的研究与实现 对w e b 抽取应用的特点，找到一种能在网格平台上运转的实施方案，并最 终实现一个基于网格的w e b 信息抽取系统。 1 2 课题内容 1 2 1 课题内容 本课题受江苏省自然科学基金( b k 2 0 0 3 0 3 0 ) 、江苏省高技术研究项 目( b g 2 0 0 5 0 2 0 ) 和江苏省教育厅自然基金( 0 4 k k b 3 2 0 1 3 4 ) 资助。课 题主要内容如下： 1 研究和实现一个自动的w e b 信息抽取系统 这是本课题的重点，具体分三步展开：一、分析比较前人的方法， 研究r o a d r u n n e r t 3 】的实现算法和优缺点，提出本课题的自动抽取方案： 二、根据方案提出相应的算法和解决方法，具体实现方案；三、通过实 验证明抽取系统的工作效率和正确性。 2 构建和配置网格环境 安装g l o b u st o o l k i t n l ( 简称g t ) ，研究g t 工作机制和关键模块，根 据网格应用的需求部署网格节点并做相应配置。 3 研究和实现网格平台上的应用 这是本课题的另一个重点，这一阶段要解决四方面内容：一、根据 网格的分布并行特征，分析w e b 信息抽取应用并找到应用并行方案；二、 根据并行方案设计网格应用模型并选择合适的网格编程模式；三、利用 j a v ac o gk i t 5 】在网格平台上实现w 曲信息抽取应用；四、通过实验说明 应用在网格平台上的优势。 1 2 2 本人工作 除了建立网格平台的工作与同组同学共同完成外，课题的整体设计 和实现均由本人独立完成。 基于删格的w e b 信息抽取技术的研究与实现第一章塑 1 3 课题意义和创新性 1 w e b 信息抽取方面 w e b 信息抽取是w e b 数据挖掘中的一个重要环节，通过提高它的自 动化程度和抽取精度，不仅能方便用户从w e b 上获取有效信息，而且能 为目前一些专门提供信息类服务的应用( 比如搜索引擎，商品比价) 提 供大量的数据，因此具有非常高的实用价值。 2 网格应用方面 此项课题的研究，将为网格应用开发提供切实可行的方案和宝贵的 实践经验，有助于推广网格技术和提高网格技术在应用中的影响。 总之，这项课题的研究能有效地推广网格技术，对广域分布的海量 数据进行高效和协作的处理和分析，给科学研究领域、经济领域和社会生 活带来巨大的价值。 1 4 本文组织 第一章对本课题做整体介绍，包括课题的提出、内容和意义、以 及本人所做的工作。 第二章相关知识研究。首先对w e b 信息抽取进行综述，重点研究 r o a d r u n n e r 采用的算法及其优缺点；然后介绍网格的相关知识，研究网 格的应用特性。 第三章阐述w e b 信息抽取技术的实现部分。这一章设计了w e b 信 息抽取系统的总体流程，并从自动获取页面、处理噪声、自动归纳规则、 抽取数据等关键技术出发详细描述在此领域做的重要工作，最后给出w e b 信息抽取的相关实验数据。 第四章设计和实现网格平台上的w e b 信息抽取应用。首先提出设 计目标，然后根据应用特点分析应用可并行化部分，提出此应用的网格 应用模型和编程模式，建立和配置网格环境，定义和发布一系列的相关 服务，结合j a v a 线程和网格服务实现应用，最后给出基于网格的w e b 抽 取应用的实验结果。 第五章总结本课题的研究成果，并讨论下一步的工作要点。 1 第章j f i l 燕l 辨究练述基于网格的w e b 信息抽取技术的研究与赛现 第二章相关研究综述 21w e b 信息抽取技术综述 随着i n t e r n e t 的日益普及，w w 为人们提供了大量的w e b 文档，这些 文档按照所含主体内容的特征可分为文本型、数据型和多媒体型。其中 数据型页面往往借助脚本程序先从数据库中获得一批数据，然后根据显 示需要为数据封装上h t m l 标记后形成。数据型页面包含的丰富数据对于 专门提供信息服务的应用非常有用，但是，网页主要是供浏览的，而不 是用来供操纵和使用数据的，因此，网页开发者在开发时根本不需要考 虑h t m l 标记的语义。正是由于这个原因。页面中的数据很难被应用程序 直接使用。因此，将数据从网页中抽取出来并且将它们传递给应用程序 依然是一个复杂、困难但又有意义的任务。 2 1 1 w e b 信息抽取难点 与普通的纯文本文件相比，w e b 文档有着鲜明的特点，这些特点给抽 取工作带来了较大的困难，主要表现在： ( 1 ) 网页具有动态性。网页内容经常更新：为了使网页更具吸引力， 网页的表现形式也会发生变化。网页的动态性要求页面包装器具有较高 的健壮性。 ( 2 ) 网页内容缺乏语义信息。h t f l 标记是为了展示数据，而不是对 数据本身的描述，因此通过h t m l 标签定位到特定数据是不可行的。 ( 3 ) 网页的结构复杂。由于页面技术的发展，各种动画和特效被加 入了页面。页匝结构也由简单的平面型转向复杂的多层嵌套类型。另外， 由于展示的需要，一个页面往往还会被分割成若干块。 ( 4 ) 网页主题多样。一个页面可能会表示多个主题内容。另外，由 于商业需要，网页中还不得不加入一些广告、友情链接、搜索引擎等元 素，这些元素会极大地干扰页面抽取的效率和精度。 4 基十喇格的w e b 信息抽取技术的研究与实现第二章相关研究综述 w e b 文档的特殊性给抽取工作带来了很大的挑战，显然，一个好的页 面抽取系统要尽可能少地受这些特殊性的影响。 2 1 2w e b 抽取技术现状 将数据从网页中抽取出来通常采用w r a p p e r m e d i a t o r 嵋1 ( 包装器中介 器) 模式。如图2 1 所示，w r a p p e r m e d i a t o r 主要包括下面几个步骤：网 页获取、网页预处理、网页数据抽取、数据集成。这种模式不将各数据 源的数据集中存放，数据仍存在局部数据源中，通过为各数据源定制 w r a p p e r 从而对数据进行抽取转换，最后再通过m e d i a t o r 将结果集成起来 提供给用户。w r a p p e r 和m e d i a t o r 都非常重要，但目前的研究还是侧重于 前者。w r a p p e r 是一个能够将数据从h t m l 网页中抽取出来并且将它们还原 为结构化数据的软件程序。w r a p p e r 通常由抽取规则和抽取器两部分构 成。抽取规则主要描述网页结构、数据项位置、抽取步骤、转换规则、 输出方式等；抽取器用来执行抽取规则产生结果数据。 衙 黟噼毯哐羚 图2 1w e b 抽取一般流程 用户 w r a p p e r 的发展经历了手工编写、半自动化生成和正在研究的全自动 化生成三个阶段。目前，一些针对特定领域的页面信息抽取集成软件( 像 n e w s b o t ”1 ，s h o p b o t ”3 等) 已投入了商业应用，给人们的生活带来了很大 的方便。 1 国外代表技术 w e b 信息抽取的研究起源于国外，发展到今天，已经积累了多种方 法和经验。下面将简要介绍几类代表技术。 ( 1 ) 采用自然语言处理的方法。这类方法将w e b 文档视作文本进行 处理。它首先过滤掉w e b 页面的h t m l 标记，然后采用词性标注和句法分析 等方法建立短语和语句元素间的关联。代表工具有r a p i e r 凹3 和w h i s k “。 第二章柑关研究综述基于网格的w e b 信息抽取技术的研究与实现 这种方式的信息抽取将忽略w e b 文档的本身层次结构，如果w e b 文档是由 多个主题块构成的，那么不进行先期的页面分块和主题分析等工作就直 接过滤h t m l 标记，必定导致抽取的失败。因此，这种方法适用于含有大 量文本块的w e b 页面。 ( 2 ) 基于机器学习的方法。这类方法通过对人为标记的样本自动学 习来获得抽取规则。与采用自然语言处理的方法不同，它不依赖语法约 束，而是通过对感兴趣的语义项的左右边界的描述来定位语义项，注重 的是描绘数据的格式特性。主要工具有w i e n “”和s t a l k e r “”。w i e n 必须依 靠紧挨着数据前的分隔符来定位数据，不能抽取复杂格式的数据。 s t a l k e r 弓 入嵌入式分类树( e m b e d d e dc a t a l o gt r e e ) 来表示复杂格式 的数据，能实现层次的信息抽取。基于机器学习的抽取工具需要用户提 供大量的样本实例。 ( 3 ) w e b 查询技术。目前w e b 上的查询主要基于搜索引擎的关键词索 引技术，这种技术存在一些不足：查询结果的重复页面多：查询结果的 格式重构能力弱；无法进行页面间连接的查询。因此，这方面的研究侧 重于提供功能更强大的w e b 查询和重构语言，如w e b s q l n ”，w 3 q l “们等。其 中l o r e 系统的d a t a g u i d e “”为半结构化数据查询提供了一个交互式用户 界面，帮助用户利用抽取出来的模式构造查询。 ( 4 ) 基于h t m l 结构的方法。基于h t m l 结构的抽取一般需将w e b 文档 解析成一棵反映h t m l 标记层次的倒置树，然后通过自动或半自动的方式 产生抽取规则。这种方式很大程度地依赖页面结构，页面结构变化了， 则会造成抽取规则的失效。但如果归纳抽取规则的算法效率比较高，那 么在每次抽取前，通过极短的时间先动态获得规则，再进行数据抽取， 这种方法还是非常可靠的。w 4 f “6 1 和x w r a p 是采用这种方法进行半自动 信息抽取的典型工具；r o a d r u n n e r 。1 和i e p a d 通过这种方法已经基本实 现了自动抽取。用这类方法进行信息抽取自动化程度较高，但抽取结果 粒度较粗。在后面章节，本文将仔细分析r o a d r u n n e r 系统。 ( 5 ) 基于o n t o l o g y 的方法。这类方法利用对数据本身的描述信息实 现抽取，对网页结构的依赖较少。文献 1 9 实现的信息抽取工具采用了 基于f q 格的w e b 信息抽墩技术的研究与实现 第二章柑关研究综述 这种方法。该系统构造的本体对感兴趣数据进行了定义，包括关系、词 条和语境关键词。构造本体需要由领域知识专家事先花费很长的时间才 能完成。另外，从理论上说，如果本体涵盖的知识足够丰富与正确，那 么建立其上的抽取工具可以完全自动地工作，但是一旦本体的定义不能 满足要求或不正确( 有些信息是很难给出对应的o n t o l o g y ) ，它的准确率 将大大降低。 ( 6 ) 基于页面视觉特征的方法。文献 2 0 提出了一种基于视觉特征 的解析方法，并把它用在t t r e c2 0 0 3 的评测中，取得了较好的效果。因 为h t m l 标记不仅用来组织内容，还用来表示页面的外观。字体的大小和 颜色、段落的长短、数据所处区域等视觉特征能对页面解析提供很好的 线索。这种方法在一定程度上满足了复杂页面对算法的要求，但由于视 觉特征的复杂性，运用的启发规则往往非常多，一条规则的加入会对已 经成功分析的页面产生影响。 从以上分析来看，虽然w e b 信息抽取技术已经发展到了自动化阶段， 但抽取规则的适应性较差、缺乏健壮性仍然是现有信息抽取技术所面临 的问题。性能较好的信息抽取系统，其规则的制定需要用户的大量参与， 自动化程度不高：而自动化程度较高的信息抽取系统，抽取数据的准确 率较低，实用性较差。 2 国内发展状况 国内的w e b 信息抽取技术起步较晚，但由于借鉴了国外的研究成果和 经验总结，目前也取得了很大的进展。很多研究机构都实现了自己的信 息抽取系统。比如河北大学的基于样本实例的抽取系统阻“；中国人民大 学的基于预定义模式的包装器。“；中国科学技术大学的基于x m l 的网页信 息抽取暖副等。 最近几年，国内除了研究这些相对完整的信息抽取系统之外，还大 力研究跟信息抽取相关的一些技术，比如，页面分块妇们和主题分析。”等 技术能使w e b 抽取技术适应更复杂的页面；页面噪声处理技术踞”能有效提 高抽取结果的精度等。 第二：章相关研究综述基于网格的w e b 信息抽取技术的研究与实现 2 1 3r o a d r u n n e r 系统 本课题建立的信息抽取系统最终要工作在网格平台，由于网格应用 的特殊性，本文尤为关注能自动进行w e b 信息抽取的技术。i e p a d “8 1 和 r o a d r u n n e r 1 都能实现w e b 信息的自动化抽取。其中，i e p a d 通过构造p a t 树来发现频繁出现的连续标记来定位和抽取数据，i e p a d 只适用于有限的 数据模式( 比如，搜索引擎) ，不包含嵌套结构的记录：而r o a d r u n n e r 相比之下更具优势。 1 r o a d r u n n e r 系统优势 r o a d r u n n e r 的出现标志着页面包装器已经进入了自动化阶段。 r o a d r u n n e r 通过比较给定的两个( 或多个) 相似页面，根据h t m l 标记的不 匹配，归纳出页面数据的分布规律；根据对应位置文本串的不同，推测 出需要抽取的数据位置；然后把数据分布规律和数据抽取位置合并成一 个总的抽取模式；最后用一个类正则表达式表示这个模式从而获得抽取 规则。 r o a d r u n n e r 信息抽取技术实质是基于h t m l 结构的，基于h t m l 结构 抽取数据时的有一定的劣势，但r o a d r u n n e r 为何还具有这么大的影响 力? 原因主要有三点： 第一，它抽取数据不需要先验知识，因此通用性较高； 第二，它借助于2 个相似页面的自动对比获取规则和数据，在这个 过程中完全不需要人工参与，因此自动化程度较高； 第三，归纳规则时间极短。当抽取页面的结构或内容变化而导致前 次获取的规则失效时，可以很快再归纳出新的规则。 总之，r o a d r u n n e r 推动了w e b 信息抽取技术的发展，具有很大的参 考价值。 2 r o a d r u n n e r 核心算法 r o a d r u n n e r 针对的是数据密集型页面，它采用的a c m e 0 1 算法思想如 下：接受2 个相似页面，一个作为样本，另一个作为页面包装器( 即抽 取规则，此规则最终以类似正则表达式的u f r e 1 表达式表示) 。r o a d r u n n e r 基于网格的w e b 信息抽取技术的研究与实现 先符号化( t o k e n i z e ) 这2 个相似页面，然后通过字符串不匹配和标记不 匹配来归纳规则。因为是相似的数据密集型页面，字符串不匹配将表示 这个字符串对应于数据库的某个字段；标记不匹配，首先要判断是否存 在迭代项( 即重复项+ ，也可认为是一条记录) ，若不是迭代项，需要进 一步判断是否存在可选项( ? ) 。 利用文献 3 中一个例子来描述这个算法。图2 2 左边的w r a p p e r 是 其中一个相似页面，被称作包装器页；s a m p l e 是另一个相似页面，在此 图2 2a c m e 算法 ： 撑p c d a t a i ( ) ? ： ( ( l i t i t l e # p c d a t a ) + 被当作了样本页。从w r a p p e r 页的第1 行开始进行两页的字符比较( 代 表页面h t m l 标记，其余为字符串) 。扫描到w r a p p e r 页第3 行时，发现 此处存在字符串不匹配，把包装器页的j o h n 用# p c d a t a 代替，表示此处 存在变化的数据，可能对应数据库字段，需要进行数据抽取。扫描到 w r a p p e r 页的第5 行时，发现了标记不匹配。r o a d r u n n e r 首先判断这里 是否存在一个迭代项，往前回溯后发现不存在迭代项，则进一步判断这 是不是一个可选项( 这个可选项可能位于样本页，也可能在包装器页) ， 这时，程序同时在两个页面进行粗略扫描，发现 是位于样本页的可 选项，所以需把此标记插入到包装器页面，并用? 表示它是一个可选项。 接着样本页指针后移，继续比较这两个页面。当扫描到w r a p p e r 页的第 1 0 行时，又发现了标记不匹配，因为w r a p p e r 页将结束，所以从s a m p l e 页往前回溯去判断是否存在迭代项。r o a d r u n n e r 回溯判断迭代项的步骤 如下：它把s a m p l e 页的第1 l 行分别与自身的第1 0 、9 、8 行比较，直到 第二章柑关研究综述基于网格的w e b 信息抽取技术的研究与实现 定位到自身的第7 行，才归纳出存在一个迭代项，然后，它把w r a p p e r 页对应的区域用迭代项符号表示出来。包装器( w r a p p e r ) 页面最终内容如 图2 2 的虚框所示。 3 r o a d r u n n e r 的局限 通过分析r o a d r u n n e r 的工作机制和算法，发现它虽然非常优秀，但 它仍然存在很多局限。 第一，r o a d r u n n e r 把h t m l 当作序列化的字符串来处理，这使得回溯 时，搜索空间很大，很容易出现错误。文献 2 7 2 8 指出h t m l 标记正确 的w e b 页可以用树结构表示，因此这两个文献阐述了如何把a c m e 算法改 造成基于树型结构的算法，重点放在了建树的过程，并没有对a c m e 算 法做实质性地改动。 第二，r o a d r u n n e r 比较的对象是整个网页，在此之前，并没有对页面 进行噪声处理，因此导致了很多无关的信息被抽取出来，影响了抽取效 率和精度。 第三，a c m e 算法不够完善。在抽取过程中，比较的两页必须具有不 同的记录数目，如果图2 2 所示的包装器页与样本页都有2 本书，虽然该 算法最终也能抽取出数据，但它却不能正确归纳出迭代项。抽取规则的 不正确，将会导致后期数据存储的错误。作者用如图2 3 的2 个相似页面 ( 这两个页面记录数相同都为2 0 ) 测试了r o a d r u n n e r 系统，发现它抽取 出来的页面结果如图2 4 所示。每个页面原有6 个字段2 0 行记录，它抽 取出的数据却表现成6 2 0 = 1 2 0 个字段，只有一行记录。 丛1 i 网格的w e b 信息抽取技术的研究与实现 第二章相关研究综述 图2 3 新浪房产页面 图2 4r r 错误的抽取规则 第四，不能够自动获取相似页面。r o a d r u n n e r 能进行自动抽取的重 要前提是至少需要2 个相似页面，然后，它将利用这两个页面自动归纳 抽取规则。但是作者认为，获取规则的最终目的是利用它来抽取一类页 面中的数据，因此相似页面应该不止2 个，而应该是一批。r o a d r u n n e r 箱二章相关研究综述基于网格的w e b 信息抽取技术的研究与实现 并没有解决如何自动获得这2 个相似页面以及跟它们属于同类的一批页 面。r o a d r u n n e r 的作者只在文献 3 中指出“可以通过人工或页面聚类技 术来获取相似页面”。 r o a d r u n n e r 前面两条不足将影响系统的执行效率和抽取结果的精度； 最后一条不足将影响整个系统的自动化程度；第三条属于算法的不完善， 不仅局限了系统的通用性，而且将会严重影响后期数据的再利用。 在分析和研究r o a d r u n n e r 的优势和不足的过程中，作者得到了很多 灵感和启示。本课题将针对r o a d r u n n e r 的这些特点，设计并实现一个自 动化程度较高的w 曲信息抽取系统。 2 1 4 本节小结 手工编写w r a p p e r 的方式费时费力，容易出错，而且难以维护( 站点 结构变化后，所有代码就得重新编写) 。为了解决这个问题，人们提出并 实现了各种半自动或自动化的方法进行页面数据的抽取。随着页面技术 的发展，w e b 页面具有了更多新的特性，使得w e b 信息抽取难度也加大 了，但r o a d r u n n e r 却能对一类页面进行自动的信息抽取，在仔细分析了 它的算法之后，发现它也存在很多改进之处，这些研究为作者设计自己 的抽取系统提供了很多启示。 2 2 网格技术研究 目前，网格的研究已经从美国推广到了世界各个大洲，各个国家和 地区都投入了大量的资金进行网格技术研究和网格基础设施建设。网格 的发展目标心1 是要将整个互联网整合成为巨大的超级虚拟计算机，对计算 资源、存储资源、数据资源、通信资源、软件资源、信息资源等进行全 面共享，为用户提供科学计算、数据存储、信息获取、远程控制等各种 高性能网络服务，最大限度地提高网络资源利用率。 蟾于网格的w e b 信息舢取技术的研究写实现 第二章相关研究综述 2 2 1 网格概念与特点 网格：一种未来计算基础设施蓝图心”一书把网格描述为：“网格 是构筑在互联网上的组新兴技术，它将互联网、计算机、大型数据库、 传感器、远程设备融为一体，为科研人员和普通用户提供更多的资源、 功能以及服务。” 网格作为一种新的计算基础设施，具有如下的重要特点晗 划： ( 1 ) 分布性。网格资源在地理位置上是分布的，这些资源可能是计 算资源，存储资源，数据资源，设备仪器资源等，分布在地理位置不同 的许多地方。 ( 2 ) 异构性。组成网格的资源是异构的，有不同类型的计算机，不 同的计算方式，不同的计算接口，不同的系统架构；同样对于存储资源 和其它资源也面临这样的问题。 ( 3 ) 自治性。网格资源的拥有者对资源具有最高级别的管理权限， 网格允许资源拥有者对其资源有自主的管理能力，但同时这些资源根据 一定的约束和规则接受网格的统一管理，实现资源的共享和互操作。 ( 4 ) 动态型。网格资源可以动态地加入或者退出网格，另外资源的 性能情况也可能发生较大的变化，使得供网格使用的资源也会发生相应 的变化。 ( 5 ) 自相似性。网格的局部和整体之间存在着一定的相似性，网格 的构建通过小的局部网格可以形成更大的网格，其构成方式具有相似性。 2 2 2 网格体系结构 网格体系结构是关于怎样建造网格的一种技术。它给出了网格的基 本组成和功能，描述了网格各个组成部分的关系以及它们集成的方式或 方法，刻画了支持网格有效运转的机制。目前，网格体系结构的发展经 历了元计算、网格计算、多层网格体系结构。们( 五层沙漏结构) 、开放 网格服务结构啪3 ( o p e ng r i ds e r v i c ea r c h i t e c t u r e ，o g s a ) 和w e b 服务资 源框架”“( w e bs e r v i c er e s o u r c ef r a m e w o r k ，w s r f ) 5 个阶段。 l3 基于网格的w e b 信息抽取技术的研究与实现 五层沙漏结构是一种影响广泛的结构，它侧重于定性的描述而不是 具体的协议定义。五层沙漏结构对该结构中各部分组件的通用要求进行 定义，将这些组件形成一定的层次关系，每一层的组件具有相同的特征， 上层组件可以在任何一个底层组件的基础上建造。 厂百蕊两 广顶冈厂面冈厂西藤丙 广西噩丙 e n a b l e de n a b l e dl | e n a b l e d e n a b l e d | | e n a b l e d 安全i l 数据库| | 文件系统| l 目录| |信息 o g s ae n a b l e d f o g s ae n a b l e d f o g s ae n a b l e d 服务| |存储网络 图2 5o g s a 架构 o g s a 是在“五层沙漏结构”的基础上，结合w e bs e r v i c e 提出来的面 向服务的网格层次结构，如图2 5 。相对于五层沙漏结构，o g s a 强调以“服 务”为中心。在五层沙漏结构中也突出了“服务”的概念，但主要是指 被共享的各种物理资源。在o g s a 中，服务所指的内容非常广泛，包括各 种计算资源、存储资源、数据资源、信息资源、软件资源等。开放网格 服务基础设施( o p e ng r i ds e r v i c e si n f r a s t r u c t u r e ，o g s i ) 是o g s a b 艮务 的实施标准，它引入了有状态w e b h 匣务的观念并定义了一些方法，但o g s i 过分强调网格服务s u w e b 月e 务的差别，导致了两者不能更好地融合在一 起。 为试图解决o g s i 和w e b 服务之间存在的矛盾，2 0 0 4 年1 月提出了w e b e 务资源框架( w e bs e r v i c e sr e s o u r c ef r a m e w o r k ，w s r f ) 。w s r f 的最终 目的是要阐明如何把“状态”加入到w e b 服务中。它提出的w e b 服务资源 ( w e bs e r v i c er e s o u r c e ，w s r e s o u r c e ) 实质是w e b j e 务和状态资源的 组合体。在w s r f 标准中，状态资源是作为服务消息交换执行的数据上下 文，个服务可以对应多个状态资源，一个状态资源可以对应多个服务。 一 高级服务 一 基于刚格的w e b 信息抽取技术的研究与实现第二章柏关研究综述 w s r f 明确定义了使用w e b 服务来访问有状态资源的一系列规范，这些规范 描述了如何定义有状态资源，如何将资源与w e b 服务相关联，以及如何通 过w e b 服务接口来访问w e b 服务资源的状态等，并对w s - r e s o u r c e 定义了分 组和寻址的相关机制。 o g s i 和w s r f 有效补充了网络服务所缺少的关键功能：能够创建、使 用、探察、发现和管理有状态资源。 g l o b u st o o l k i t ”1 ( g t ) 是由g l o b u s 项目组成员联合开发的标准工具 包，用于建立网格系统和开发网格软件。g t 随着网格体系结构的发展， 经历了g t 2 、g t 3 ( 基于o g s i ) 、g t 4 ( 基于w s r f ) 。尽管目前网格平台还没有 形成正式的标准，g t 已成为事实上的网格标准。一些重要的公司，包括 i b m 、m i c r o s o f t 、c o m p a q 、g r a y 、s g i 、s u n 等公开宣布支持g t 。目前大 多数网格项目都是基于g t 所提供的协议及服务建设的，例如美国的物理 网格g r i p h y n 、欧洲的数据网格d a t a g r i d 、荷兰的集群计算机网格d a s 一2 等。 1 g t 4 核心模块 g t 4 包括s e c u r i t y 、d a t am a n a g e m e n t 、e x e c u t i o nm a n a g e m e n t 、 i n f o r m a t i o ns e r v i c e 和c o m m o nr u n t i m e 5 个核心模块口“。g t 4 在这些核 心模块中提供了大量的基础服务，可以使网格用户方便地开发自己的服 务和完整的网格应用。 ( 1 ) 网格安全( s e c u r i t y ) 建立在公钥基础设施( p u b l i ck e y i n f r a s t r u c t u r e ，p k i ) 之上的。p k i 系统是一种信任层次系统，参与其中 的实体通过其持有的证书实现身份的标识和确认。公钥的认证一般遵从 x 5 0 9 标准。对于基于g l o b u s 的安全网格服务和客户端而言，这意味着 所有参与的实体( 包括服务和客户端) 都要具备一个符合x 5 0 9 格式的身 份标识。g t 4 已在消息级安全中实现了两个标准：w s s e c u r i t y 和 w s s e c u r e c o n v e r s a t i o n 。这两个标准提供