（管理科学与工程专业论文）基于DOM树的web新闻正文抽取技术的研究与实现.pdf

摘要 摘要 随着i n t e r n e t 的发展，目前的网络已经是一个巨大的数据存储仓库。w e b 新 闻是现代人们获取信息的重要源泉。但是互联网中的信息与噪音几乎是并存的。 为了从这个巨大的数据存储仓库中获得相关的信息，国内外已经做了很多研究。 目前通用的抽取网页新闻正文的方法主要有两种：一种是过滤网页中的噪音，另 一种是直接定位网页正文内容。在这篇文章中综合使用这两种方法来抽取网页新 闻的正文。 由于网页自身的特征，每个网页都可以转化为一棵d o m ( d o c u m e n t0 b j e c t m o d e l ) 树。所以对网页的操作可以转化为对树的操作。s t m ( s i m p l et r e em a t c h i n g ) 算法是计算两个树相似度的传统方法，这里对s t m 算法进行改进使其可以对共 享公共抽取路径的网页进行自动聚类。本文通过网页分块和网页信息化的度量来 定位主文本信息的位置。本文的方法可应用在结构化的网页。本文使用自己的算 法开发了一个基于在线新闻的正文抽取系统。本文的实验是基于在线的新闻网 站，结果也证实这个算法比r t d m ( r e s t r i c t e dt o p d o w nm a p p i n g ) 算法有效。 关键词：网页简单树匹配d o m 树公共抽取路径 a b s t r e c t a b s t r a c t r e c e n t l y ，w i t ht h ed e v e l o p m e n to fi n t e r n e t ，t h ew e bh a sb e e nt h ed a t ar e p o s i t o r y w e bn e w si sa ni m p o r t a n ts o u r c eo fp e o p l e sa c c e s st oi n f o r m a t i o n h o w e v e r ，t h e i n f o r m a t i o na l m o s tc o e x i s t sw i t ht h en o i s e i no r d e rt oo b t a i nt h er e l e v a n t i n f o r m a t i o nf r o mt h er e p o s i t o r y , m a n yr e s e a r c h e sh a v e b e e nm a d e t h et y p i c a l f u n c t i o n so fw e bn e w se x t r a c t i o ni st ol o c a t et h eu s e f u lc o n t e n tt e x ta n df i l t e rt h e n o i s e s i nt h i sp a p e r w ei n t e g r a t e dt h et w of u n c t i o n st oe x t r a c tt h eb o yo fw e bn e w s a st h ew e bp a g e so w nc h a r a c t e r i s t i c s ，e a c hp a g e sc a nt r a n s f o r m e di n t od o m ( d o c u m e n to b j e c tm o d e l ) t r e e t h e r e f o r e ，t h eo p e r a t i o no fw e bp a g ec a n b et r a n s l a t e d i n t ot h ea c t i o no nt h et r e e s t m ( s i m p l et r e em a t c h i n g ) a l g o r i t h mi sat r a d i t i o n a l m e t h o dt h a tc a l lc a l c u l a t et h es i m i l a r i t yb e t w e e nt w ot r e e s i nt h i sp a p e r ，w ei m p r o v e t h es t ma l g o r i t h mt oc l u s t e rt h ep a g e sw h i c hs h a r ec o m m o ne x t r a c t i n gp a t h i nt h i s p a p e r w e bp a g eb l o c ka n dp a g e so fi n f o r m a t i o nm e a s u r ea r et a k e nt oa u t o m a t i c a l l y e x t r a c tl o c a t i o no fm a i nt e x tp a s s a g e s t h ea p p r o a c hc a na p p l yt os t r u c t u r a lw e b p a g e s m o r e o v e r , w ed e v e l o p e da l le x t r a c t i n gs y s t e mb yu s i n go u ra l g o r i t h m e x p e d m e n t s a r ed o n eo v e rs e v e r a li m p o r t a n to n - l i n en e w ss i t e sa n de x p e r i m e n t a lr e s u l t so no u r e x t r a c t i n gs y s t e ms h o wt h a tt h ea p p r o a c hc a l la c h i e v eh i g h e re x t r a c t i o na c c u r a c yt h a n r t d ma l g o r i t h m k e yw o r d s ：w e bp a g e s ，s i m p l et r e em a t c h i n g ，d o mt r e e ，c o m m o ne x t r a c t i n gp a t h 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的成 果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或撰写 过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作了明确 的说明。 作者签名：签字日期： 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学拥 有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构送交 论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。本人 提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 口公开口保密( 年) 作者签名： 签字日期： 导师签名： 签字日期： 皂之季 第1 章绪论 第1 章绪论 1 1本文的选题背景 随着互联网的发展，互联网的信息量成几何级数增长。人们获取新闻的主要 方式自然也由传统报纸转变为网络或者手机等工具。只要打开相关网站的相关网 页就可以阅读相关的内容。但是网页上展示给人们的信息十分的繁杂。除了人们 想阅览到的信息外还有很多如导航信息，广告和其它与主内容不相关的信息。许 多读者并不希望看到这些不相关的信息。特别在按流量计费的时候，读者更不希 望任何不相关的信息被加载进来。因此如何抽取网页新闻正文成为一个国内外研 究的热点。 目前许多新闻网站都是预先设计一个显示模板，然后从后台数据库取相关数 据来填充模板。因为有相同的模板，所以来自同一个新闻网站的网页结构几乎完 全相同。因此很多研究试图去检测和发现模板，通过分析模板来得到要抽取的信 息。检测模板的方法也多种多样。而另一些研究试图不去考虑模板使用其它的方 法来抽取信息。但是在实际工作中各种各样的噪声如：导航信息、广告信息、版 权信息、关于我们信息等等，严重影响了网页新闻正文的抽取。本文就是通过研 究新闻网站的模板结构，来抽取相关的正文信息。 1 2 国内外研究现状及存在问题 如何从网页中抽取出相关信息国内外已经做了很多研究工作。c a l i f f ( 1 9 9 7 ) 、d a y n ef r e i t a g ( 1 9 9 8 ) 和s o d e r l a n d ( 1 9 9 9 ) 分别提出了基于自然语言 的抽取方法，此方法是把传统的信息抽取技术直接应用在网页上。它主要是通过 语句之间的关系来建立抽取规则，然后根据语法和语义来确定目标信息的位置。 这种方法的主要缺点是没有考虑网页的结构特征，不能抽取复杂对象。s u d a r s h a n c h a w a t h ( 1 9 9 4 ) 、k u s h m e r i c k ( 1 9 9 7 ) 、i o n m u t e a ( 1 9 9 8 ) 、a m a n d as a h u g n e t ( 1 9 9 9 ) 、k u s h m e r i c k ( 2 0 0 0 ) 和m u s l e a ( 2 0 0 2 ) 使用w r a p p e r 来抽取网页信 息内容。这种方法可以通过归纳的方法对文档信息进行自动抽取，但是它只能针 对特定的标签进行抽取，所以扩展性比较差。n e c h e s ( 1 9 9 1 ) 、g r u b e r ( 1 9 9 3 ) 、 b o r s t ( 1 9 9 7 ) 和s t u d e r ( 1 9 9 8 ) 使用基于o n t o l o g y 方法，依靠数据本身的描 述来实现抽取工作。这种方法的主要缺点是需要领域专家参与，扩展性也比较差。 由于每个网页可以通过网页解析工具解析成一棵树，所以r e i s ( 2 0 0 4 ) 提出了使用 r t d m ( r e s t r i c t e dt o p - d o w nm a p p i n g ) 算法来计算两个d o m ( d o c u m e n to b j e c t 第1 章绪论 m o d e l ) 树之间的距离来对网页进行聚类分析。r t d m 算法是建立在树编辑距离 ( t r e ee d i td i s t a n c e ) ( t a ik u oc h u n g ，1 9 7 9 ) 基础之上。由于它把树的编 辑操作都限定在叶子部分，所以在一定程度上比树编辑距离简单。r t d m 算法不 但可以从一个给定的网站中抽取相关的正文，而且可以获得整个网站内容和过滤 无用的信息。l a n y ( 2 0 0 3 ) 介绍了一种叫做s s t ( s i t es t y l et r e e ) 树来获取正 文。但是使用这种方法获取的正文中也可能包含噪音。y e o n j u n g k ( 2 0 0 7 ) 修改 了s t m ( s i m p l et r e em a t c h i n g ) 算法，使用信息值为每个节点增加了权重。然 而本文认为当相似度为1 0 0 时这种方法不能检测任何网页。y a n g s h , l i u h l ， h o n ，y b ( 2 0 0 7 ) 使用统计，结构，可视布局等方法来检测模板。很多研究者也试图 通过对网页进行分块或者通过模仿人类的视觉来抽取信息。s h u y i z ，r u i h u a s ， j i r o n g w ( 2 0 0 7 ) 贝l j 提出一种模拟人类行为的方式来抽取正文，而不是依靠模板。 d o n g u i n c ( 2 0 0 8 ) 使用信息量来检测一个论坛中提交内容与评论内容之间的边 界。它使用了可视化信息与有效文本信息来定位正文。但是在实验中发现由于空 白区域或者其它标记可能影响文本的抽取结果。d e n g c ( 2 0 0 3 ) 提出v i p s ( v i s i o n - b a s e dp a g es e g m e n t a t i o n ) 算法，主要是在视觉的基础上来抽取语义结 构。s a n d i p d ，p r a s e n j i tm i t r a ，c l e eg ( 2 0 0 5 ) 对网页进行分块，然后通过判断一 个块在多个网页中出现的次数在检测非正文的块。s a n d i p d ，p r a s e n j i tm i t r a ， c l e eg ( 2 0 0 8 ) 根据标签的开始和结束，使用堆来帮组对网页进行分块。l i n ，s h ， h o ，j m ( 2 0 0 2 ) 首先把页面分成块后，然后为每个块建立向量，最后通过向量来 抽取网页信息。 关于信息的抽取，很多研究者做了很多工作。但是面临的问题是，如何高效、 迅速、自动、准确的去抽取信息，且抽取方法必须有很好的适应性和扩展性。 1 3 本论文的主要工作和内容安排 本文研究的对象是新闻网页，介绍了如何通过聚类分析处理来对网页新闻的 正文进行自动化抽取。文中使用改进过的简单树匹配算法s t m 计算两个树之间 的相似度，从而对网页进行聚类。r t d m 算法虽然把对树的编辑操作都限定在叶 子部分，但是它仍然需要比较两棵树的所有节点。由于来自同一网站的网页都有 一些共同的结构特征。所以计算两个网页的相似度没有必要去匹配两棵树的所有 节点。本文构造的简单d o m 树都只包含 标签的直接孩子，所以本文的 s t m 算法的时间复杂度远小于r t d m 算法。本文还发现在相同类中的每个页面 都有一个相同的抽取路径。因此文中设计了一个高效的算法来检测出每个类的公 共抽取路径。这个路径开始于 标签，同类中的所有网页都共享这个抽取路 径。这篇文章的主要贡献是：1 构造了一个简单的d o m 树。2 修改了s t m 算法 2 第1 章绪论 并用其来对网页聚类。3 使用块信息有效性来度量哪个块是正文内容并找出公共 的抽取路径。网页新闻正文的抽取过程大致如下：首先通过h t m lp a r s e r 对网页 进行解析，从而生成d o m 树。然后使用改进的s t m 算法对网页进行聚类。接着使 用块信息有效性度量方法找出样本页的抽取路径。这个抽取路径就是公共抽取路 径。本文还在阐述的理论基础之上使用j 2 e e 技术开发一个新闻正文抽取系统。 本文的组织结构安排如下： 第一章为绪论部分，主要介绍了研究背景和国内外的研究现状。 第二章介绍了网页新闻正文抽取的一些基础理论知识。 第三章介绍了网页分块和网页信息度量的概念。 第四章是论文的核心部分，介绍了基于d o m 树的聚类的过程算法和公共抽取 路径生成和表示。 第五章根据以上章节的理论阐述对基于d o m 树的网页新闻正文抽取系统分 进行了设计与实现，并分析了实验结果。 1 4 本章小结 本章介绍了网页新闻正文抽取的研究背景以及国内外的研究现状，并说明了 本文所做的工作和文章结构安排。 3 第2 章理论基础 第2 章理论基础 2 1 网页的基本结构 早期的网页都是静态网页，用户通过浏览器使用h t t p 协议向服务器发送请 求，服务器根据用户的请求把相应数据发送给浏览器，浏览器然后把数据进行解 析展示给用户。网页新闻就是静态的网页。静态的网页主要由h t m l 语言构成。 由于w e b 2 0 时代的到来，网页向动态化发展。所以为了增强客户端与服务器的 交互性，h t m l 语言中嵌入了很多如j a v a s c r i p t ，v b s c r i p t 的脚本语言和j s p ，a s p 和p h p 等编程语言。各种各样的自定义标签也应运而生。 2 1 1h t m l m 慨( h y p e rt e x tm a r k u pl a n g u a g e ) 语言即超文本标记语言或超文本链接 标示语言。它是由欧洲物理量子实验室蒂姆伯纳斯李在1 9 8 9 年发明的，1 9 9 1 年它定义了h t m l 语言的第一个规范。后来w 3 c ( w o r l dw i d ew e bc o n s o r t i u m ) ( h t t p ：w w w w 3 c o r g ) 组织把h t m l 作为在互联网上发布信息的语言规范。h t m l 文本是由h t m l 命令组成的描述性文本，h t m l 命令可以说明文字，图形，动画， 声音，表格，链接等。h t m l 的结构包括头部( h e a d ) ，主体( b o d y ) 两大部分， 其中头部描述浏览器所需的信息，而主体则包含所要说明的具体内容。h t m l 标 签分为单标签和双标签两种。双标签就是使用一个标签如 贝u 必须以另一个 标签 结束，单标签指的是只需一个标签就可以表示，如 标签。h t m l 页面以d o c t y p e 开始，它声明文档的类型，且它之前不能有任何内容( 包括换行 符和空格) ，否则将使文档声明无效，接着是 标签，以 结束。在它 们之间，整个页面有两部分一一标题和正文。标题一般放在 和 标签之间。正文放在 和 之间。页面上显示的任何东西都包含在这 两个标签之中。 下面给出一个典型的网页的h t m l 结构： i i 定义了文档类型 h t m l 开始标签 头部开始标签 标题 标题部分，显示在网页左上方 头部结束标签 内容部分 4 第2 章理论基础 h t m l 结束标签 在上面的示例中， 是文档类型标签，它指定了浏览器文档使的 h t m l 标签以及标签之间的嵌套关系， 位于h t m l 文档开头，在 标签之前。 标签用于h t m l 文档的最前边，主要用来标识h t m l 文档的开始。 中的 “h t m l 说明的是文档类型的名称：“p u b l i c 表明所依赖的d t d 文档对任何人 公开： v e r s i o nn a m e 疗说明h t m l 版本名称；“u r l 说明h t m l 语言的定义规范 在网络上的位置。 表示h t m l 文档的结束。网页中的所有内容都要放在 之间。 定义了h t 乩文档的头部，在此标签之间可 以使用 等标签。 之间的内容 不在浏览器的文档窗口中显示出来。 只能放在 中间的文本显示在浏览器的标题栏部分。 定义了h t m l 文档的主体 部分，在 之间放置的是实际要显示的文本内容和其它用于控制文 本显示方式的标签和脚本。其中每个标签都有一些公共属性，比如c l a s s 、n a m e 、 i d 、s t y l e 等。 h t m l 标签经常是嵌套关系，比如h t m l 标签的元素体部分又包含h e a d 和b o d y 标签，而h e a d 标签的元素体部分又包含t i t l e 标签。实际上，一个规范的页面 的代码往往对应于一颗树型结构，h t m l 标签为树根，各个不含任何标签的文本 块成为该树形的各个叶节点。标记有三类意义：结构、语义和样式。结构将文档 组织成树型结构。语义将单个的元素与外部的实际事物联系起来。而样式的作用 是如何显示因素和布局网页。 2 。1 。2x m l 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 t m l 一样， 都是s g m l ( s t a n d a r dg e n e r a l i z e dm a r k u pl a n g u a g e ，标准通用标记语言) ，它是 由w 3 c 在1 9 9 8 年2 月发布的一种标准。x m l 是i n t e r n e t 环境中跨平台的，依赖于内 容的技术，是当前处理结构化文档信息的有力工具。扩展标记语言x m l 是一种简 单的数据存储语言，使用一系列简单的标记描述数据，而这些标记可以用方便的 方式建立，虽然x m l 占用的空间比二进制数据要占用更多的空间，但x m l 极其简单 易于掌握和使用。它与h t m l 不同的是不需要关心数据的显示或者布局。下面给出 一个x m l 的例子： 定义了文档的解析规则 文档开始元素 文档元素子元素 5 第2 章理论基础 王小明 文档元素子元素 1 6 男 王小红 17 女 文档结束元素 从上面可以看出来x m l 允许开发人员自定义标签。x m l 可以转化成相应的 h t m l ，来适应当前浏览器的需求，所以它可以被应用在网络传输上。x m l 与h t m l 的不同主要有一下几点： ( 1 ) x m l 的扩展性强于h t m l 。所以x m l 的自定义它可以提供更多的数据操作。 h t m l 只适用于静态网页，而在交互式的动态网页中要求过多的数据操作，x m l 显 得更加适用。 ( 2 ) x m l 的语法要求比h t m l 严格。它要求开始标签和结束标签必须匹配，在 h t 儿中开始标签与结束标签不同时，不会影响它的显示功能；嵌套标签之间不可 以再相互嵌套；x m l 还区分大小写，而h t m l 则是不区分大小写的。 2 1 3c s s c s s ( c a s c a d i n gs t y l es h e e t s ) 即层叠式样表，主要负责的是h t m l 如何显示， 式样通常存储在式样表中，也可以在h t m l 中直接编写。它是哈坤在1 9 9 4 年提出来 的。1 9 9 7 年w 3 c 组织了专门的工作组来管理c s s ，并在以后的时间里发布了它的 许多版本。式样的使用给网页带来了很多好处：1 使表现与内容相互分离，可以 把c s s 单独的放置在外部文件里，而网页中只存放文本信息即可。2 提高页面的 浏览速度，使用式样避免了浏览器在加载时编译大量的网页标签。3 易于维护和 改版，当要改变显示时，只须修改特定的式样文件即可。在h t m l 中可以通过 来引入外部c s s ，在 x m l d p 通过 当在h t m l 文档直接编写c s s 时，只需要在的 和 标记之 间插入一个 块对象。定义方式如下： 文档标题 6 第2 章理论基础 其中b o d y f o n t ：1 0 p t ；c o l o r = r e d ； 直接修饰b o d y 标签，意思是b o d y 标签 的字体大小为1o p t ，颜色为红色。 表示t a b l e 标签引用t a b l e c l a s s t e x t a l i g n ：c e n t e r 的式样，使得t a b l e 中的文本都剧中。 在很多网页中都有各式各样的c s s 代码与h t m l 语言结合在一起，来布局 和装饰网页。 2 2h t m l 与x m l 的解析 本文使用h t m l p a r s e r 作为h t m l 页面的解析工具，由于w e b 上的页面绝大多数是 由h t m l 语言来描述。这些大量的h t m l 文档大部分是手工生成，因此时常存在着语 法问题。解析工具解析这些带有问题的页面时有时候错误。因此，在对h t m l 页面 进行解析前，一般都需要对h t m l 页面进行清洗。h t m l p a r s e r 是一个j a v a 编写的 h t m l 解析库，并可以高速的解析h t m l 。它可以通过v i s i t o r 模式把h t m l 页面解析 为n o d e ，a b s t r a c t n o d e 和t a g 等对象。n o d e 定义了页面结构和获取父、子、兄弟 节点的方法。a b s t r a c t n o d e 是n o d e 的一个实现类。t a g 主要作用是进行具体分析。 也可以通过h t m l p a r s e r 把h t m l 页面转化为语法严格的x m l 格式的数据。接下来就 是讨论如何对x m l 进行解析。 将x m l 文档转化为d o m 树的过程就是解析。任何一个x m l 文档都可以解析成相 应的d o m 树，解析后的d o m 树节点包含x m l 文档的内容，每个d o m 树的内部节点都对 应x m l 中的标签。在一般情况下，都是通过对d o m 树的处理来处理x m l 文档。根据 从x m l 中获取数据的方式和最终所得到的数据模型的不同，x m l 解析技术大致可分 为以下四类：1 ) 面向文档的流式解析；2 ) 面向文档的对象式解析；3 ) 面向文档的 指针式解析；4 ) 面向应用的对象式解析；这四类解析技术适用于不同的应用需求， 它们有着各自的优缺点。针对具体的应用需求，选择合适的解析技术，往往能够 7 第2 章理论基础 减少内存消耗，缩短处理时间，简化获取数据过程，提高应用系统的整体性能。 2 2 1面向文档的流式解析技术 流式解析是一种基于事件的顺序解析过程，解析器有顺序地读取) ( m l 文档， 产生一个对应的事件流，并向事件处理程序发送所捕获的各种事件，如标签元素 开始和标签元素结束等事件，而事件处理程序则通过不同方法来实现的。 流式解析是将x m l 文档作为一个数据流来处理，因此，它能够立即读取数据， 而不需要读取所有的文档。由于事先不需要将整个文档一次加载到内存中，所以 在处理大型文档时具有较好的时间和空间效率。但是它也存在这一些问题，首先 它不支持随机访问，其次流式处理程序较为复杂，开发人员在开发时需要负责大 量的操作。并且由于处理程序没有以任何方式存储数据，所以在更改数据和移动 数据时候变得很分困难。流式解析方式一般分为两种，臣p s a x 和s t a x 。 s a x ( s i m p l ea p if o rx m l ) 是一种推式解析方式，它通过解析器控制着读循 环，在文档结束之前控制权不会返回给应用程序。s a x 是基于事件驱动的，o p s a x 解析器在读取x m l 文档的过程中生成一个事件流，并且每个事件都是通过回调来 处理程序中相应的方法。比如元素开始和结束标签，元素内容，实体，语法分析 错误等事件。s a x 中的核心事件处理程序实现了c o n t e n t h a n d l e r 接口。此接口中 定义了处理与x m l 文档本身关联的事件的方法，如s t a r t d o c u m e n t 、e n d o o c u m e n t 、 s t a r t e l e m e n t 、e n d e l e m e n t 、c h a r a c t e r s 等，s a x 解析技术在解析过程中，解析 器从读取文档开始到读取文档结束，中间是无法停止的。即使找到要找的数据， 也无法停止。如果中间发生异常或者其它原因使解析终止，那么解析器将无法继 续进行解析。 s t a x ( s t r e a m i n ga p if o rx m l ) 是一种拉式解析方式，应用程序控制着读循 环，应用程序负责反复调用解析器来获取下一个事件，直到文档结束。但是，拉 分析由应用程序进行调整；因此，分析事件是由应用程序生成的。s t a x 在分析时 可以跳过元素并且分析多个文档。可以借助s t a x ，在分析) ( m l 文档时生成分析事 件。s t a x 和s a x 对同样的x m l 文档所获得事件类型基本上是相同，但是s t a x 包含了 两套处理x i l 的a p i 。它们分别是基于指针的a p i 和基于迭代器的a p i 。基于指针的 a p l 只是简单的返回事件，此时事件用数值形式来表示。这是一种低层a p i ，所有 的状态信息直接从流读取器获得，不需要额外地创建对象。因此占据较少的内存， 拥有较高的效率。而基于迭代器的a p i 贝j j 以对象方式返回事件，是一种较为高级 的a p i ，每个事件对象都封装了它所表示的特定x m l 结构固有的信息，因此可直接 利用其方法获得属于该结构的信息，但也需要额外的对象创建开销。相对于基于 指针的a p i ，基于迭代器的a p i 具有更多的面向对象特征，因此更便于应用于模块 化的体系结构。s t a x 也是用j a v a 定义的，其s t a x i 0 于2 0 0 4 年3 月发布，并且成为 r 第2 章理论基础 了j s r - 1 7 3 规范，最新版本为2 0 0 6 年6 月发布的s t a x l 2 。 这两种解析方式的主要区别是由解析器，还是由应用程序控制读入文件的循 环。 2 2 2 面向文档的对象式解析技术 由于流式解析方式没有对x m l 文档建模所以无法更改数据，也不支持随机访 问特性。使得应用程序很难对x m l 文档进行修改、添加和删除等编辑操作。为了 解决这些问题，产生了基于d o m o p 面向文档的对象式解析技术。 d o m 是用与平台和语言无关的方式对x m l 文档进行建模的官方w 3 c 标准，其目 标是提供一个可以通用于各种程序语言、操作系统和应用程序的接口。d o m 作为 一种对象式解析技术，定义了层次化对象模型来表示x m l 文档。即为x m l 语法中的 每个概念( 如元素，属性，实体，文档等) 定义对应的类，而解析器在读入x m l 文 档的时候，会建立x m l 语法和类之间的一一映射。实际上，d o m 的层次化对象模型 是一个树形结构，它将一个x m l 文档看作一棵节点树，每个节点代表一个x m l 文档 中的元素。d o m 的基本节点对象有5 个：( 1 ) d o c u m e n t 对象：是树的最高节点，也 是对整个文档操作的入口；( 2 ) e l e m e n t 和a t t r 对象：对文档中元素和元素属性的 映射；( 3 ) t e x t 对象：作为e l e m e n t 和a t t r 对象的子节点，代表了元素或属性的文 本内容；( 4 ) n o d e l i s t 对象：对节点按指定的方式进行遍历。利用d o m 在内存中建 立的完整的x m l 文档的树形结构，开发人员就可以方便的对x m l 文档进行一系列操 作，如遍历、增加、删除、修改文档内容等，且具有良好的导航能力。同时d o m 所具有的对象特性也非常便于面向对象编程。然而，由于d o m 在使用数据前需要 完整的遍历x m l 文档，在内存中构建树形结构表示，因此需要消耗大量的内存， 尤其是对于大型文档，性能下降的很快。而且必须一次解析整个x m l 文档，不可 能只做部分解析，当只关注x m l 文档的小部分数据时，效率很低。 2 2 3 面向文档的指针式解析技术 上面面向文档的流式解析效率较高，但易用性差，面向对象式解析易用性强， 却效率较低。其效率问题主要是在解析时，提取一部分源文件，然后在内存中进 行解析。这种解析方法要大量的创建和销毁对象，在d o m 中每一次改动都需要将 d o m 模型重新完整的解析，这使得效率变的低下。面向文档的指针式解析技术 v t d x m l ( v i r t u a lt o k e nd e s c r i p t o r 一) ( m l ) 解决了这个问题，它是一种不需要提 取x m l ，所以解决了d o m 占用内存的问题。它还提供了对d o m 快速的解析与遍历。 v t d ( v i r t u a lt o k e nd e s c r i p t o r ) 是一个6 4 b i t s 长度的虚拟令牌描述符，它记录 了令牌的类型、嵌套深度、长度、深度以及令牌开始偏移量等信息。v t d 是实现 无提取解析的关键，它类似于x m l 文档中元素的指针，通过它可以快速定位到某 9 第2 章理论基础 个元素。 2 2 4 面向应用的对象式解析技术 以上三种解析技术都是从x m l 的角度来处理文档和建立模型，这适用于关心 文档的x m l 结构的应用程来说是适用的，但对文档数据内容理解有些不够。面向 应用的对象式解析可以使应用程序在很大程度上忽略x m l 文档的实际结构，而直 接使用文档的数据内容。 2 3 正则表达式与网页的清洗 一个正则表达式( r e g u l a re x p r e s s i o n ) ，就是用某种模式去匹配一类字符串 的一个公式。正则表达式被各种文本编辑软件、类库、脚本工具广泛的支持，而 且像m i c r o s o f t 的v i s u a lc + + ，s u n 的n e t b e a n s 这种交互式i d e 也开始支持它了。 一般看来，一个正则表达式就是一个普通的查找串。它是由普通字符和元字符组 成的。普通字符包括大小写字母和数字，元字符一般是有规定的。例如，正则表 达式s t u d e n t ”中没有包含任何元字符，它可以匹配”s t u d e n t ”和”0 2 7 s t u d e n t ” 等字符串，但是不能匹配”s t u d e n t 。要用好正则表达式，就必须得了解它的一 些表示意思。下表列出了所有的元字符以及他们所代表的意思。 元字符( ) 匹配任何单个字符。例如正则表达式t c 匹配这些字符串：t a c 、 t b c 、a c e ，但是不匹配c b d 。 元字符( $ ) 匹配行结束符。例如正则表达式s t u d e n t s 能够匹配字符串“h e s as t u d e n t 的末尾，但是不能匹配字符串“t h e ya r es t u d e n t s 刀。 元字符( ) 匹配一行的开始。例如正则表达式h ei s l e 够匹配字符串“h ei sa s t u d e n t 的开始，但是不能匹配“s h ea n dh ea l l 。 元字符( 木) 匹配o 或者多个正好在它之前的那个字符。 元字符( ) 是引用符，用来将这里列出的这些元字符当作普通的字符来匹配。 元字符( c l - c 2 ) 匹配括号中的任何一个字符。 元字符( ) 将( 和) 之间的表达式定义为组，并把将匹配这个表达式的字符保 存到一个临时区域，一般一个正则表达式中最多可以保存9 个，可以用1 到9 的符 号来引用。 元字符( i ) 将两个匹配条件进行逻辑“或 运算。 元字符( + ) 匹配1 或多个正好在它之前的那个字符。 元字符( ? ) 匹配0 或者1 个正好在它之前的那个字符。 元字符( f i ) 匹配指定数目的字符，这些字符是在它之前的表达式定义的。 在本文中使用下列表达式来过滤w e b 页面中妨碍网页解析的数据。比如使用 】0 第2 章理论基础 正则表达式 4 ? s s $ ? 4 来过 滤网页中的s c r i p t 内容；使用正则表达式 ” ? s s ? “ 来过滤网页中的n o s c r i p t l 内容；使用正则表达式 ? s s ? ”来过滤 网页中的s t y e 内容。 2 4 新闻网页的结构特点与d o m 树 新闻网页除了具有上述一般用页的特点外还有自身的一些特点。目前的新闻 嗣页一般都是主题型网页布局，所谓布局就是在页面上划分出不同的区域，按照 设计的原则和方法，把不同的内容放置到不同的位置上，并通过色彩调和出不同 的网页基调，使网页内容形成一个有机的整体充分表达出网页主体的过程。所 谓主题型网页布局就是指网页通常通过成段的文字描述一个或多个主题虽然偶 尔也会在文字部分出现图片和超链接，但这些图片和超链接并不是网页的主体。 除此之外大多数的新闻网站的网页结构都是出自相同的模板，所以来自同一个网 站的新闻网页都有相同的显示规律。比如y a h o o 新闻网页，一般顶都放置的是导 航信息，左边放置的是其它新闻的连接，下部是相关新闻的连接等等。这些网页 都具有一个相同的d 叫树结构和相同的网页布局。网页的这种结构特征决定了网 页新闻正文的抽取可以借助这些相似或者相同的d o m 树。 懿i ! ! 。_ = 皇。 i 一瞳 啊置 鲞毒 露 i t t a 吣【r 1e ；1 【：0r d e 龇im 一 n d i v ：d 一一y = 一b o ：d _ a i v 州c a n o ” d l v ：d ；1 v n w = a 口” dr v ：$ 2yo = ”z 一n d b ” ec c i o 托8 i “a m c l y l 自；。b 0r d er n y l et e 】 d i v ：g tr e t 旷) c c 唧x e 二c 0 围2 1y a b 。o 网页与其对应的d o m 料 第2 章理论基础 图2 1 给出一个网页集合的d o m 树结构和网页标签的名称与部分属性，其代码 如下： 内容 内容 内容 内容 内容 内容 内 容 d o m 臣p 文档对象模型。根据w 3 c ( h t t p ：嗍w 3 o r g 1 ) 0 l d ) 的d o m 规范，d o m 是一 种与平台，语言无关的接口。可以通过程序和脚本动态地访问和更新其内容，结 构和文档式样。因为d o m 的节点是以层次结构组织的，所以它是基于树的。这种 基于树的层次结构一旦建立，就可以使用程序或者脚本通过导航路径在树中查询 到特定的内容信息。 2 5网页信息抽取的概念与技术 2 5 1网页信息抽取的概念 网页信息抽取属于w e b 数据挖掘的领域，w e b 数据挖掘就是把数据挖掘的理 论与技术应用在w e b 上，从i n t e r n e t 上的海量资源中抽取用户感兴趣的知识或 者模式。它涉及到数据挖掘技术，w e b 技术，计算机科学，和信息学多个领域。 如图2 2 所示一个网页信息抽取的例子： 1 2 第2 章理论基础 围2 2 一个网页信息抽取的例子 信息抽取i e ( i n f o r m a t i o ne x t r a c t i o n ) 是把文本里包含的信息进行结构化 处理或者从一般的自然语言文本中直接抽取信息，同时把信息用固定的结构格 式表示出来。信息抽取的研究工作是从2 0 世纪6 0 年代中期开始的。它的主要任 务就是从各种各样的文档中抽取出主要信息点，然后以统一的形式显示，以便信 息查询、文本挖掘、知识发现和信息比较等应用。信息抽取不是去分析所有的文 档，而是找出文档中的相关部分来进行分析处理。近些年来，信息抽取己经成为 自然语言处理领域的一个重要分支，主要涉及自然语意理解、篇章分析与推理、 多语言文本处理、w e b 信息抽取等自然语言研究领域。通过系统化、大规模地定 量研究和评测推动了自然语言处理研究的发展，促进了自然语言处理研究与应用 的紧密结合。信息抽取技术主要应用在搜索引擎、网络信息过滤和信息安全、推 荐系统，意见挖掘系统、机器翻译、文本日志挖掘、企业智能决策系统等。随着 i n t e r n e t 的发展互联网上存在着大量的各式各样的文档，信息抽取的研究开 始转向w e b 信息抽取。这就促使了w 曲信息抽取技术的飞快发展。 w e b 信息抽取( w e bi n f o r m a t i o ne x t r a c t i o n ) 简称w e bi e ，就是把w e b 信息 作为信息塬的信息抽取( 陈玉芳2 0 0 4 ) 。w e b 信息主要是由h t m l 网页组成的，而且 里面嵌入了很多其它的语占或者对象。由于人们对视觉美观的需要，所以网页的 布局多种多样，网页的信息展示也十分杂乱，不同的网站没有固定的显示格式与 模式。如何处理w e b 上的海量信息变的十分困难。这也就是为什么人们常常感慨 数据多，信息少的原因。w e b 信息抽取就是研究如何从w e b 海量信息中提取出用户 感兴趣的信息和知识，并用一种结构化和语义清晰的模式显示出来。w 曲i e 和i r ( i n f o r m a t i o nr e t r i e v a l ) 有本质的区别，i r 是根据用户的查询请求从文档库 l3 第2 章理论基础 中查询出相关的信息内容，同时尽可能提出不相关的文档。搜索引擎就是i r 在w e b 上的应用。它返回是是很多页面集合。而w e bi e 是从文档中抽取出相关的信息内 容。w e b 信息抽取的评价指标有：1 召回率( r e c a l l ) ，有多少信息被正确的抽 取出来。2 准确率( p r e c i s i o n ) ，度量的是抽取出的信息有多少是正确的。本 文采用一些相反的指标来度量如：1 没有抽取率，度量有多少信息没有被抽取出 来。2 错误抽取率度量有多少信息被错误的抽取。 2 5 2 网页信息抽取的技术 实现w e b 信息抽取的技术多种多样，主要有以下几种： 1 基于自然语言的抽取方法 基于自然语言( n a t u r el a n g u a g e ) 理解的方法采用了基于语法和语义来实现 对信息的抽取。即把文本划分成子句，然后利用子句结构，短语和子句间的关系 来建立抽取规则。这些规则可以通过语法和语义上的约束来定位要抽取的信息。 主要有三种工具c a l i f f ( 1 9 9 7 ) 提出r a p i e r ( r o b u s ta u t o m a t e dp r o d u c t i o no f i n f o r m a t i o ne x t r a c t i o nr u l e s ) 、d a y n ef r e i t a g ( 1 9 9 8 ) 提出s r v ( s e q u e n c er u l e s w i