（计算机科学与技术专业论文）半结构化网页的信息抽取技术研究.pdf

l r q 。- y t h er e s e a r c ho fs e m i - - s t r u c t u r e dw e bp a g e s 一一 1 n o i n f o r m a t i o ne x t r a c t i o n at h e s i ss u b m i t t e df o r t h ed e g r e eo fm a s t e r c a n d i d a t e ：z h um e i l i a n s u p e r v i s o r ：p r o f l ic u n h e c o l l e g eo fc o m p u t e r & c o m m u n i c a t i o ne n g i n e e r i n g c h i n au n i v e r s i t yo fp e t r o l e u m ( e a s tc h i n a ) 们 删7m 5m 7 舢8m 1胛y 关于学位论文的独创性声明 本人郑重声明：所呈交的论文是本人在指导教师指导下独立进行研究工作所取得的 成果，论文中有关资料和数据是实事求是的。尽我所知，除文中已经加以标注和致谢外， 本论文不包含其他人已经发表或撰写的研究成果，也不包含本人或他人为获得中国石油 大学( 华东) 或其它教育机构的学位或学历证书而使用过的材料。与我一同工作的同志 对研究所做的任何贡献均已在论文中作出了明确的说明。 若有不实之处，本人愿意承担相关法律责任。 学位论文作者签名：日期：驴7 f 年5 月z 驴日 学位论文使用授权书 本人完全同意中国石油大学( 华东) 有权使用本学位论文( 包括但不限于其印刷版 和电子版) ，使用方式包括但不限于：保留学位论文，按规定向国家有关部门( 机构) 送交学位论文，以学术交流为目的赠送和交换学位论文，允许学位论文被查阅、借阅和 复印，将学位论文的全部或部分内容编入有关数据库进行检索，采用影印、缩印或其他 复制手段保存学位论文。 保密学位论文在解密后的使用授权同上。 学位论文作者签 指导教师签名： 日期：力州年岁月砺同 日期：砌i f 年岁月贸日 摘要 随着国际互联网的迅猛发展，网络已经成为人们发布和获取信息的一个重要平台。 目前，大部分网页都是通过服务器根据请求从后台数据库中查询相关数据，然后展示到 一个列表页面当中。这些页面一般都是由特定的入口查询获得的，而且网页中的数据很 难被其它应用程序直接利用。因此如何自动抽取这些页面中的重要信息就变得非常重 要。 介绍了网页信息抽取技术的概念，要解决的主要问题以及相关技术，分析了常用的 网页信息抽取算法及优缺点。针对现有方法对主数据区域的定位不准确的问题，将最大 扇出子树法、最大内容量增大法和最大标记量法三种启发式规则相结合，定位网页的主 数据区域。在数据记录分离的过程中，现有方法需要对所有子树进行相似度判断，算法 效率较低，针对这一问题，提出了一种基于树编辑距离的聚类算法，增加了聚类算法， 减少了予树的比较次数，提高了算法效率。同时采用树编辑距离表示子树之间的相似度， 更符合网页的层次结构，算法准确率更高。聚类后得到数据记录的候选分割方案，给出 了类之问相似度的计算公式，获得最高相似度的分割方案即为数据记录的最佳切分方 法。最后采用了星比对算法，对数据记录的属性进行抽取。 实验表明，本文方法的自动化程度较高，并且具有较高的效率，数据记录抽取和属 性抽取都较为准确。 关键词：网页信息抽取，数据记录，树编辑距离，聚类算法 t h er e s e a r c ho fs e m i s t r u c t u r e dw e bp a g e si n f o r m a t i o ne x t r a c t i o n z h um e i l i a n ( c o m p u t e rs i c e n c ea n dt e c h n o l o g y ) d i r e c t e db yp r o f l ic u n h e a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to ft h ei n t e r n e t ，t h en e t w o r kh a sb e c o m e0 , 1 1 i m p o r t a n t p l a t f o r mf o rp e o p l e t oi s s u ea n da c c e s si n f o r m a t i o n c u r r e n t l y , t h en u m b e ro fr e s o u r c e s a c c e s s i b l ei nd y n a m i c a l l yg e n e r a t e dw e bs i t e sr e s u l t i n gf r o mu n d e r l y i n gd a t a b a s e sg r o w s d y n a m i c a l l y , s u c ha s t h el i s to fg o o d sp a g e s t h e s ep a g e sa r eg e n e r a l l yo b t a i n e db ya p a r t i c u l a rq u e r yi n t e r f a c e ，a n dt h e y a r ed i f f i c u l tt ou s ef o ro t h e ra p p l i c a t i o n sd i r e c t l y t h e r e f o r e h o wt oe x t r a c ti n f o r m a t i o nf r o mt h e s ep a g e sb e c o m e sv e r yi m p o r t a n t t h i sp a p e r s t u d i e sh o wt oe x t r a c ti n f o r m a t i o nf r o mt h e s es e m i - s t r u c t u r e dp a g e s i n t r o d u c e dt h ec o n c e p to fw e bi n f o r m a t i o ne x t r a c t i o n ，t h em a i np r o b l e m sa n dr e l a t e d t e c h n o l o g i e s ，a n a l y z e dt h ew e bi n f o r m a t i o ne x t r a c t i o na l g o r i t h m sa n dt h ea d v a n t a g e sa n d d i s a d v a n t a g e s t os o l v et h ee x i s t i n gm e t h o d s c a nn o tf i n dt h em a i nd a t ar e g i o nv e r ya c c u r a t e p r o b l e m ，c o m b i n e dt h r e eh e u r i s t i cm e t h o d sw h i c h a l eh i g h e s tf a n o u t ，l a r g e s ts i z ei n c r e a s ea n d l a r g e s tt a gc o u n tt of i n dt h em a i nd a t ar e g i o n w h e nd i v i d i n gt h ed a t ar e c o r d s ，a l le x i s t i n g m e t h o d sn e e dt oc o m p u t et h es i m i l a r i t yo fs u b t r e e s ，t h ee f f i c i e n to ft h e s ea l g o r i t h m s i sn o t v e r yw e l l ，t os o l v et h i sp r o b l e m ，p r o p o s e dt h et r e e e d i td i s t a n c ec l u s t e r i n ga l g o r i t h m ，t h e c l u s t e r i n ga l g o r i t h mr e d u c e dt h en u m b e r o fc o m p a r i s o n ss u b t r e et oi m p r o v et h ee f f i c i e n c yo f t h ea l g o r i t h m a tt h es a m et i m eu s i n gt h et r e ee d i td i s t a n c et or e p r e s e n tt h es i m i l a r i t yo f s u b t r e e s ，t h ea l g o r i t h mg e t sah i g h e ra c c u r a c y a f t e rc l u s t e r i n go b t a i nt h ec a n d i d a t ed i v i d e l i s t s ，g i v e saf o r m u l at oc h o o s et h eb e s ts e g m e n ts c h e m e u s e dm a s t e ra l i g n m e n ta l g o r i t h m t o e x t r a c tt h ea t t r i b u t e so ft h ed a t ar e c o r d s e x p e r i m e n t ss h o wt h a to u rm e t h o dh a sah i g h e rd e g r e eo fa u t o m a t i o na n dh i g h e r e f f i c i e n c y t h r o u g ht h er e a lw e bp a g e st e s t ，0 1 1 1 m e t h o dh a s ah i g h e ra c c u r a c y k e y w o r d s ：w e bp a g ei n f o r m a t i o ne x t r a c t i o n ，d a t ar e c o r d s ，t r e ee d i td i s t a n c e ，c l u s t e r a l g o r i t h m 目录 第一章前言1 1 1 课题背景与意义。1 1 2 国内外研究现状2 1 3 论文研究内容6 1 4 论文组织结构。7 第二章网页信息抽取技术综述9 2 1 网页信息抽取技术概念9 2 2 网页信息抽取要解决的主要问题9 2 3 网页信息抽取的关键技术l o 2 3 1d o m 模型。1o 2 - 3 2 树编辑距离1 1 2 3 3h t m l p a r s e r 技术1 2 2 4 网页信息抽取技术分类1 3 2 4 1 手工构造的抽取系统1 4 2 4 2 基于监督的抽取系统1 5 2 4 3 基于半监督的抽取系统1 6 2 4 4 无监督的抽取系统1 6 2 5 信息抽取评价标准1 6 2 6 本章小结1 7 第三章基于树编辑距离聚类算法的网页信息抽取18 3 1 网页预处理18 3 2 主数据区域发现1 9 3 3 数据记录的分离2 1 3 3 1 简单树匹配算法2 l 3 3 2 聚类算法2 4 3 3 3 选择最佳分割方案一2 6 3 5 本章小结2 6 第四章数据记录属性抽取。2 8 4 。1 序列比对算法简介一2 8 4 1 1 序列比对问题的起源一2 8 4 1 2 序列比对问题定义2 8 4 1 3 序列比对算法分类2 8 4 2 抽取数据记录属性3 1 4 6 本章小结一3 2 第五章实验系统设计3 3 5 1 开发工具以及实验环境3 3 5 2 信息抽取系统设计3 3 5 2 1 网页预处理模块一3 4 5 2 2 主数据区域定位模块3 4 5 2 3 数据记录分离模块3 4 5 2 4 数据记录属性抽取模块3 6 5 2 5 实验运行结果及分析。3 7 5 3 基于l u c e n e 的简单搜索引擎4 0 5 3 1l u c e n e 简介。4 0 5 3 2 本文所用插件简介4 l 5 4 本章小结4 3 总结4 4 主要工作4 4 主要创新点4 5 存在的问题及未来的方向4 5 参考文献4 6 在学期l 、日j 的研究成果5 0 堑定谢51 中国石油大学( 华东) 硕十学位论文 1 1 课题背景与意义 第一章前言 随着国际互联网的迅猛发展，网络上的资料越来越多，对于用户来讲，很难找到自 己需要的信息。搜索引擎便应运而生，搜索引擎对网络上的资料进行索引，能够使网络 使用者尽快的找到所需的资料，节省了用户在搜索上所用的时间。因此，具有搜索功能 的网站常常被作为入门网站。但是搜索引擎主要是对资料进行索引，如果想要对网上的 资料做更有效的应用，还需要更进一步的整合相关资料，给用户提供整合性的服务，于 是便有了网络信息集成的概念。 毫无疑问地，互联网是现在全球最大的信息库，如果可以将各个相关网站上的资料 加以收集、分析，这些整合后的信息就能够提供更专业的服务，例如网络购物者能够从 众多的网上商店中找到自己需要的多种商品，而且能够对这些商品的功能、效果和价格 进行比较；或者能够把网络上的各种各样的招聘信息汇集起来，构成一个功能强大的搜 索工具，方便求职的人员来使用；另外，能够集成多个供应商的供货信息，让用户可以 自由选择最适合自己要求的供应商。 网络信息集成的重点就是网页信息抽取，所谓的网页信息抽取，就是从网页所包含 的无结构或半结构的信息中识别用户感兴趣的数据【l 】，并将其转化为更为结构化、语义 更为清晰的格式。 成功的网页信息抽取系统将把互联网变成巨大的数据库。网页信息抽取为许多网络 信息处理应用领域包括网络数据挖掘、网络信息检索等提供了有益的基础。比如网页信 息抽取为网络数据增加了语义和模式信息，极大地方便了网络数据挖掘，还有网页信息 抽取使用户在网络信息检索中能直接定位到感兴趣的信息点，加快了人们获取信息的速 度。总之，网页信息抽取为海量的网络信息的再利用提供了可能，因此有着明显的优势 和，1 。阔的应用前景，是当今研究的热点。 本课题旨在对半结构化网页的信息抽取技术进行研究，针对目i j i 抽取技术主数据区 域定位不够准确以及算法效率较低等问题提出自己的改进策略，并将改进后的算法应用 到信息抽取系统中，提高算法的准确率和效率。 第一章前言 1 2 国内外研究现状 信息抽取的最初始的研究，一般认为是从2 0 世纪6 0 年代中期的从自然语言文本中获 取结构化的信息。当时的两个代表性的研究是美国纽约大学开展的l i n g u i s t i cs t r i n g 项目 和耶鲁大学r o g e rs c h a n k 及其同事开展的有关故事理解的研究，他的学生设计并实现了 一个根据故事脚本理论建立的一个l e 系统，这个系统命名为f r u m p 系统。 其q b l i n g u i s t i cs t r i n g 项目开始于6 0 年代中期，一直延续到了8 0 年代。这个项目的主 要研究内容是建立一个大规模的英语计算语法，项目主要应用到医疗领域当中。从医院 的出院记录和x 光报告中抽取信息格式，也就是现在所说的模板。 f r u m p 系统，主要从新闻报道中抽取信息，内容涉及很多场景和领域，采用的是 期望驱动和数据驱动相结合的处理方法。 2 0 世纪8 0 年代，信息消解系列会议召开1 2 ，信息抽取得到了蓬勃的发展，信息抽取 研究逐渐成为了自然语言处理领域的一个非常重要的分支，并一直向前发展。 网页的数据通常都是通过h t m l 语言的方式来展现的，然而h t m l 语言在初始设计 的时候并不是为了存储数据，而是供浏览器解析并以w 曲页面的形式展示给用户的，能 够方便用户通过浏览器浏览信息。因此，尽管h t m l 语言是一种标记语言，但是它所定 义的标签以及文档结构都是为了显示的需要，并没有真正语义上的含义。因此对于网页 信息抽取的研究，就需要通过包装器，从h t m l 文档中得到有意的数据内容，并将其转 化为适合计算机处理的形式。 现在利用包装器技术来抽取网页信息的基本思路是：首先根据h t m l 文档特点以及 用户抽耿的需求，制定一系列的抽取规则，然后在抽取规则的指导下，包装器从特定的 网页中将数据抽取出来。抽取规则是基于h t m l 文档的，对于h t m l 文档有两种看待方 式：一种是将h t m l 文档看作字符流；另一种是将h t m l 文档看作d o m 树结构。相应地， 抽取规则分为两种，基于分界符和基于树路径。 基于分界符的规则最简单的就是给出数据项的开始和结束的分界符，我们可以假设 一个数据项开始舰则是“s k i p t o ( ) ”，它的结束规则是“s k i p t o ( ) 。这条规则的 意思就是说从文档的开始忽略掉所有的字符，一直到找到标签“ ”，然后找到标签 “ 。两个标签的中间部分就是我们所要抽取的数据部分。此外，除h t m l 标签外， 特征字符、标点符号等也能够作为分界符。此算法的改进算法主要有：采用正向和反向 2 中国石油大学( 华东) 硕十学位论文 抽取相结合的方法，以及有限状态自动机的方式等。总之，这种方法主要是将h t m l 页 面源码看成是字符串，通过定义分界符来划分数据项，从而抽取出用户所需要的正确的 数据。 基于树路径的抽取规则，将h t m l 源码看作是一棵树结构，用户需要的数据都存储 在树节点当中。基于这种规则来进行抽取时，首先将h t m l 源码转化为树结构，然后再 通过规则中的路径，搜索树中的相应节点，获得数据。 对于h t m l 文档的抽取，都需要使用不同的抽取的规则，不管是使用基于分界符的 规则还是使用基于树路径的规则，每一个特定的信息源都需要有相应的抽取规则。本文 采用类似于树路径的抽取方法，把h t m l 文档看作一棵树结构。 前人已经进行了很多网页信息抽取方法的研究。2 0 0 1 年，由v a l t e rc r e s c e n z i 等人提 出的r o a d r u n n e r l 3 1 方法，这种方法主要适用于有数据库查询产生的页面，这些页面的数 据结构具有相似性，网页都是由相同的模板生成的。它通过比较相似的页面归纳得到网 页模板，这些模板就是抽取规则，使用正则表达式来描述模板。 r o a d r u n n e r 方法的基本思想是：比较同一类网页中的两个或者多个给定样本页面， 归纳得到正则表达式，对于不同的文本字符，表示为# p c d a t a ，这样就能够生成网页 所包含的数据模式，通过得到的正则表达式来抽取这类型网页的数据信息。r o a d r u n n e r 方法假定所有标签都是由模板产生的，同时没有关系数据，然而这两个假设在很多的情 况下并不成立。而且它把网页源码看作是字符串，逐个进行比较，并采用了多种复杂的 启发式算法和归纳模式。因此这种方法很敏感，只要网页存在不符合假设条件或者不符 合启发式规则的地方，归纳就会失败。 2 0 0 3 年吐t a r v i n da r a s u 和h e c t o rg a r c i a - m o l i n a 提出i 筝j e x a l g 4 方法，使用了类似的模 型，但是归纳方式不一样。这种方法不是逐个比较页面的标签，而是统计最大频繁的连 续标记组。把这些标记组成为模板的字符串模式，假设每个模板的标记组都是唯一的， 而且每种类型会出现多次，数据值之间存在分隔符，即每个模板有相应的字符串模式。 这种方法l 卜r o a d r u n n e r 要健壮一些，但是仍然很敏感，而且假设也会经常失效。 上面的两种方法都是将h t m l 文档视为字符流，完全忽略了h t m l 的d o m 结构。因 此算法极为复杂而且很敏感，效果也不是很好。归纳出来的模式也不健壮，只要网页稍 作微小的变动，模式就会失效。而且，这种模式很难人为修改和创建。 第一章前言 2 0 0 1 年，l i n gl i u 等人提出- r x w r a v t 5 】方法，该方法是一个基于树路径的半自动化 的w r a p p e r 生成器，它首先获取网页源码的树结构，而后利用源码当中的一些特定的标 签和它们被用作数据表现时的含义，作为启发式规贝0 。通过这些启发式的规则，就能够 自动查找出关键信息，最后生成包装器。用户可以只通过几次简单的点击就能够获得一 个网站的包装器，这种方法的自动化程度较高。但是，由于很多站点并不符合特定的启 发式规则，而且对于大部分信息抽取任务，简单的几次点击和启发式搜索不能够准确捕 捉到用，的需求，所以在实际应用中包装器的效果并不十分理想。另外，由于产生的包 装器是h q j a v m 弋码描述的，这就使得包装器的修改和维护都很困难。 2 0 0 3 年，由c h i a - h u ic h a n g 等人提出的i e p a d l 6 】方法通过构造p a t 树来发现频繁出现 的连续标记来定位和抽取数据。这种方法的特点在于：第一，完全不需要人工标注的训 练实例来发现数据记录的边界；第二，发现的模式能够推广到同一个数据源的不同查询 请求结果的页面中。但是，这种方法是一种半自动的方法，需要用户标注抽取模式。而 且，这种方法只适用于有限的数据模式，不包含嵌套结构的记录。比如它们的实验对象 搜索引擎。由于并不是所有重复出现的模式都包含有用的数据，i e p a d 使用了各种 启发式来进行标识。 同年，由b i n gl i u 等人提出的m d r 7 1 方法，是第一个完全不需要用户参与自动抽取 信息的系统，这种方法基于两个特征：( 1 ) 一组相似的结构化数据记录可以看成一个相似 对象的集合，这些对象在页面中常被放在一片邻近的区域中，该区域称为数据区域( d a t a r e g i o n ) ，且每个对象的h t m l 标签是相似的。( 2 ) 一个网页中的h t m l 标签的内嵌结构 很自然地构成一棵标签树。在一片特定区域中的一组相似的数据记录，在标签树中往往 具有相同的父节点。 给定一个网页，m d r 方法的抽取流程如下：首先建立h t m l 标签树；然后基于标签 树和字符串比较算法找到页面中的数据区域；最后从每个数据区域中分离出每一条数据 记录。这种方法虽然自动程度很高，能够处理不连续的数据，但是它不能够有效处理网 页中有嵌套结构的数据。 2 0 0 5 年，哇i y a n h o n gz h a i 和b i n g “u 提出的d e p t a l 8 j 方法是对m d r 方法的一种改进。 这种方法包括两步：( 1 ) 识别出网页中的数据记录；( 2 ) 比较并抽取出数据记录当中的数 据项。第一步中作者提出了应用h t m l 网页的视觉信息来产生d o m 树的方法，第二步中 4 中国石油大学( 华东) 硕上学位论文 提出利用p a r t i a lt r e ea l i g n m e n t 算法进行字符串比较，抽取出有用信息。这种方法抽取成 功与否依赖于启发式信息，但是并不是所有的页面都能够符合这些启发式的规则，所以 对于某些页面抽取的准确率不高。而且这种方法计算编辑距离的效率较低。 同年，f l j h o n g k 吼z h a o 等人在文献【9 】中提出了一种基于视觉的网页数据项抽取方 法，能够生成包装器，得到相当全面的信息。但是，包装器生成算法需要站内众多网页 作为输入，导致整个抽取方法的效率和灵活性不高，而且这种方法主要针对搜索引擎的 返回结果页面，适应性不强。 针对这个问题，2 0 0 8 年m a n u e la l v a r e z 等在文献【1 0 】中提出了能够自动抽取数据记 录，挖掘数据区域的信息抽取方法。采用了一种生成模型来获得半结构网页的主要特征。 这种方法需要输入一个包含数据记录列表的网页，通过三个主要步骤来抽取网页中的信 息：第一步，识别出网页的数据区域；第二步，选择一个自动相似度最高的候选分块方 法将数据记录分块；第三步，应用序列比对算法抽取出数据记录属性值。但是这种方法 无法对不连续的数据进行处理，而且算法的执行效率不高。 在国内，近几年也有很多相关工作。2 0 0 5 年，朱明等提出了基于记录子树的最大相 似度发现记录模式【1 1 1 的思想，该方法能够在同类记录的表现模式存在差异的情况下，正 确识别出数据记录。算法会将自动发现同一个网页中的多条数据记录模板问题，转化为 从两个字符串当中找到最大相似子序列的问题。如果相似度超过一定的阈值，就认定两 棵子树属于同一类型的数据记录，这样就有效的解决了同类记录存在差异是数据记录的 自动抽取问题。该方法对于常见的沦文检索网站具有较好的效率和准确率。 2 0 0 6 年，张慧颖和曲著伟针对查询相关的w e b 页面的特点，提出了一种基于d o m 子 树匹配的交互式w e b 数据抽取方法【1 2 】。查询相关的w e b 页面中的数据记录之间具有极高 的代码结构相似性，w e b 数据记录对应的d o m 子树之间自然也就具有很高的结构相似 性。 2 0 0 7 年，邵辉和李芳提出了一种新的基于树模型的信息抽取方法一d e t m l l 3 】。该 方法利用网页的树形结构，采用了树编辑距离模型以及树归并算法进行数据记录的定位 和抽取。首先将网页转化为标签树的形式，然后利用树编辑距离定位和分割网页当中的 数据记录，并且将数据记录生成树结构。最后采用a l i g n 算法生成包装器。算法的自动化 程度很高，对于动态网页具有良好的效果。但是这种方法没有利用语义信息，仅仅是利 第一章前言 用网页的结构，抽取的范围不广，只能对动态网页进行抽取。 2 0 0 8 年，梅雪等人在分析总结前人工作的基础上，提出了一种全自动化生成网页信 息抽取w r a p p e r 的方法【1 4 】。该方法利用网页模板的层次化、结构化的特点，充分运用网 页链接分类算法以及网页结构分离方法，抽取网页当中的各个信息块，同时输出相应的 包装器。应用所生成的包装器能够对同类型的网页进行自动信息抽取，但是该方法实现 比较复杂，且适应性不强。 2 0 0 9 年，王晓斌等人提出了一种自动粒度选择的半结构化页面信息抽取方法f 1 5 】，半 结构化页面的数据汜录的结构存在相似性，这种相似性表现为在先序遍历d o m 树生成 的标记序列当中的重复出现的模式，所以能够利用后缀树对数据记录进行抽取。该方法 通过后缀树产生重复模式，再从中选出最大重复和串联重复来构成候选的模式集，而后 通过特征参数给定两个粒度相应的最佳模式集，追后还引入抽取结果规则度参数，进行 综合评价。最终来确定抽取模式，从而完成数据记录的自动抽取，但是这种方法抽取的 准确率不高。 综上，在网页信息抽取领域，已经有大量的研究工作，包括手工构造方法、基于半 监督的抽取系统、无监督的抽取系统等，但是这些方法都存在一些不足，首先在网页主 数据区域定位时算法准确率不高，造成后面的部分准确率降低；在数据记录抽取时，需 要将所有予树进行相似度比较，算法用时较长等问题，本文旨在提高网页信息抽取算法 的准确率以及算法的执行效率。 1 3 论文研究内容 本文的研究对象足列表页面，这种网页的特点就是网页当中通常都会包含多个结构 相似和模板相同的记录项。数据记录就比如是商品的一条信息，数据记录的属性就是商 品的名称、价格以及地区等信息。如图1 1 所示：页面当中的每一条笔记本信息都是一 条数据记录，其中笔记本的名称、价格、库存状态等都是数据记录的属性。 论文的主要工作内容如下： ( 1 ) 数据区域识别问题 数据区域就是指网页中包含数据记录最多的一部分区域，一个网页可以有多个数据 区域，也可以只有一个数据区域。本课题大体思路足：将三种启发式规则相结合，找出 6 中困石油大学( 华东) 硕二l 学位论文 数据区域的根节点。 ( 2 ) 记录的抽取问题 网页中一般都包含多条记录，要对记录进行进步的细化处理，要将多条的记录切 分成一个个的单条记录，这个过程被称为记录的抽取。通过利用上一步找出的数据区域 的根节点，找到该节点的直接后继，组合分析出各种候选分割方案，最后经过一系列计 算找出最佳的分割方案，分割方案中的每一条就会作为一条数据记录抽取出来。 ( 3 ) 数据记录属性的抽取 一个记录一般由若干个属性组成【1 6 1 ，为了能够将记录变成结构化的信息，我们需要 从记录中把不同的属性值分别抽取出来，并且给它们标注上正确的属性名，这样，抽取 出的属性值j 。能成为有意义的信息，加以利用。数据属性的抽取主要是采用字符串序列 比对算法，这种算法首先找出一个主串，即最长的字符串，比对字符串集合，通过不断 的替换删除，最终得到一个不再变化的字符串，即为所求。 1 4 论文组织结构 图1 1 一个三条记录的网页 f i g l - 1a ne x a m p l e ：t h r e er e c r o d s 论文共分六章，具体结构如下： 第一章“前言”，给出了网页信息抽取技术的研究背景、意义。分析了国内外的研 究现状，介绍了论文的主要研究内容，最后指出了论文的组织结构。 7 第一章前言 第二章“网页信息抽取技术综述 ，介绍了网页信息抽取技术的定义、要解决的主 要问题、关键技术、网页信息抽取技术的分类，以及网页信息抽取技术的评价标准。 第三章“基于树编辑距离聚类算法的信息抽取”，介绍了本文的研究方法基于树编 辑距离聚类算法的网页信息抽取方法。 第四章“数据记录属性抽取”，介绍了采用星比对算法，抽取数据记录属性。 第五章“实验系统设计”介绍了本文的实验系统的设计，分析了实验的结果，最后 将实验结果应用到搭建的一个简单的搜索平台当中，实现抽取数据的再次利用。 最后，“总结”总结了全文的内容，给出了论文的主要工作、创新点、所存在的不 足和未来研究的方向。 8 中国石油大学( 华东) 硕二f ：学位论文 第二章网页信息抽取技术综述 2 1 网页信息抽取技术概念 网页信息抽取就是从网页集合当中抽取出需要的数据信息，并将这些数据用一种更 易于查询的数据模型表示。网页信息抽取的抽象描述【1 7 】为：对于一个给定的包含一系列 对象的网页s ，找出一个映射w ，这个映射能够将s 中的对象映射到一个数据集r 上， 同时它还必须能够从任何与网页s 相似的网页s 中识别并抽取数据( 两个网页的相似是 指网页的表示风格或者数据的描述方式一致或者类似，但是网页中包含不同的信息。) 。 其中，映射w 就是包装器，它是通过分析一定数量的样本网页而产生的，一个包装器 就是一个能够执行映射w 的程序。包装器产生之后，我们就利用该包装器对与样本网 页有相似结构的网页进行抽取。 2 2 网页信息抽取要解决的主要问题 对于网页信息抽取的研究有很多，思路各有不同，但是总体来讲，网页信息抽取要 解决的问题主要有以下几个： ( 1 ) 网页预处理。网页设计者为了增强网页的显示效果，会在源码中添加大量的与 信息无关的脚本代码，这些代码会给信息抽取带来比较大的干扰，因此我们在信息抽取 之前将其清除。另外，网页的h t m l 标签存在大量不严格符合编写规则的问题，如标签 嵌套混乱等，由于浏览器容错能力很强，这些错误大部分都不会影响到网页的正常显示， 但是对于抽取工作，这些都会对数据的正确抽取产生干扰，所以我们会使用一些工具来 纠正这些错误，规范h t m l 代码【1 引。这些都是网页预处理的内容。 ( 2 ) 确定目标信息所在区域。网页中除了一些不规范代码和脚本信息之外，还会有 一些噪音数据，包括网页导航、广告链接等。为了能够使抽取更准确，我们需要将这些 信息抛开，直接定位网页的重要信息所在的区域【7 1 ，即网页主数据区域。 ( 3 ) 记录的抽取。本文的研究对象是列表页面，网页中通常都包含多条记录，要对 记录进行细化处理，要将多条的记录分割成一个个的单条记录，这个过程被称为数据记 录的抽取。对于数据记录的抽取，需要确定数据区域的分割方案，这是网页信息抽取的 关键步骤。 ( 4 ) 记录属性的抽取。一条数据记录一般会有若干个属性【1 8 】，为了使抽取出的数据记 9 第二章嘲页信息抽取技术综述 录变为结构化的信息，需要从数据记录当中，将不同的属性值抽取出来。只有结构化的 信息才能够更方便的为人们所利用。 根据几个主要问题，网页信息抽取的流程如图2 1 所示。 ，一一一- 一 一- 图2 1 网页信息抽取的流程图 f i 9 2 - 1t h ef l o wc h a r to fi n f o r m a t i o ne x t r a c t i o n 在这几个问题中，对于问题( 1 ) 目前有很多的软件工具可以用来完成这个任务，现在 的网页信息抽取方法主要关注的是后面3 个问题。 2 3 网页信息抽取的关键技术 本节详细介绍本文研究的信息抽取方法涉及到的d o m 模型、树编辑距离技术以及 h t m l p a r s e r 技术。 2 3 1d o m 模型 d o m 是d o c u m e n to b j e c tm o d e l 文档对象模型的缩写。根据w 3 c ( w o r l dw i d ew e b c o n s o r t i u m ) d o m 规划1 9 1 ，它是一种接口，并且具有与浏览器、平台、语言无关的特性， 它的出现使得我们能够方便的访问页面其它的标准组件。简单来讲，d o m 解决了 n e t s c a p e 的j a v a s c r i p t 和m i c r o s o f t 的j s c r i p t 之间的冲突，使得w e b 设计者和开发者有一个标 准的方法，访问他们站点中的数据、脚本和表现层对象。 d o m 具有易用性强的优点，在使用时，将所有的x m l 文档信息都存入内存，遍历 简单，支持x p m h ，增强了易用性。但是d o m 也存在一些缺点，主要是效率低，解析的 速度慢，而且占用内存比较多，不能够用来解析大文件。 1 0 中国石油大学( 华东) 硕上学位论文 d o m 以层次结构来组织节点或者信息片段的集合。这样d o m 就允许开发人员在树 的导航中很快找到自己需要的信息。d o m 需要加载整个稳定并构造层次结构，然后才 可以进行下一步的工作。所以d o m 被认为是基于树或者基于对象的。 通常，h t m l 文档包括b o d y 、t i t l e 、h e a d 、t a b l e 、t r 、t d 等各种组件，而 且组件在文件中的顺序与显示顺序相同。d o m 通过对h t m l 文档解析，产生一个树形结 构，称为文件的树形逻辑结构或逻辑结构。 d o m 定义了a p i 允许其它程序浏览树形逻辑结构，并且提供存取、添加、修改和删 除节点的功能。使用树形结构有以下的优点： ( 1 ) 节点操作，添加、删除节点。 ( 2 ) 在标记树的结构上根据不同的需要导出或生成一种新的代表h t m l 文档某方面 特征的新的结构。 在d o m 接口规范中，有四个基本的接口：d o c u m e n t ，n o d e ，n o d e l i s t 和 n a m e d n o d e m a p 。在这四个基本接口中，d o c u m e n t 接口是对文档进行操作的入口，它是 从n o d e 接口继承过来的。n o d e 接口是其他大多数接口的父类，象d o c u m e t ，e l e m e n t ， a t t r i b u t e ，t e x t ，c o m m e n t 等接口都是从n o d e 接口继承过来的。n o d e l i s t 接口是一个节点 的集合，它包含了某个节点中的所有子节点。n a m e d n o d e m a p 接口也是一个节点的集合， 通过该接口，可以建立节点名和节点之间的一一映射关系，从而利用节点名可以直接访 问特定的节点。 2 3 2 树编辑距离 文章引入树编辑距离来计算子树问的相似度，为了便于理解，首先给出编辑距离的 定义。编辑距离记为d ( s l ，s 2 ) ，其中s l ，s 2 为字符串。编辑距离被定义为使s l 和s 2 成为相 刚字符串需要的操作的最小次数。其中操作包括：插入、删除和替换。 我们将网页看作是一个树结构，抽取其中的数据记录，就需要识别网页当中结构相 似的内容块，为了比较网页结构的相似性，就需要对网页中不同子树的相似性给出一个 定量描述。这里我们就采用了树编辑距离来表示这种子树之间的相似性。 首先，介绍一下字符串编辑距离的概念。编辑距离，又称l e v e n s h t e i n 距离，是指两 个字符串，由一个转化为另一个所需要的最少的操作次数。这里的操作可以包括：替换， 插入和删除。 例如：将s t r i n g 一字转成m o r i n g ： 第二章网页信息抽取技术综述 s t r i n g ( k _ s ) r a t t i n g s t r i n g ( t 叶o ) m o r i n g s t r i n g ( n _ ) m o r n i n g 俄罗斯科学家v l a d i m i rl e v e n s h t e i n 在1 9 6 5 年提出这个概念。主要用于描述两个字符 串之间的差异。 树编辑距离的定义类似于字符串编辑距离定义【2 0 1 。树编辑距离就是指，给定两棵树， 树a 和树b ，两棵树的编辑距离就是指两棵树之间相互转化所需的操作的最少次数。这 里操作包括节点的删除、插入和替换，另外我们给每种操作赋一个权值。 计算两棵树的树编辑距离，主要就是要找出两棵树之间的一个权值最小的映射，这 个映射可以有如下的定义： 假定x 是一棵树，x t i l 是树x 中第，个子节点。那么t l 和t 2 之间的映射m 是满足 以下条件的有序数对( 奶的集合 对于任何( a i ，b 1 ) ，( a 2 ，b 2 ) ( 1 ) a l = a 2 当且仪当b l = b 2 ( 2 ) t l | a l j 是t 1t a 2 l 姚邻节点当且仅当t 2 i b q 是t 2 b 2 1 1 魁邻节点 ( 3 ) 7 f 1 t a l l 是t 1 【删的父节点当且仅当t 2 i b h 是t 2 【b 2 j 的父节点 上面的( 1 ) 主要保证了所有的节点在映射当中不会重