大规模网页模块识别与信息提取系统设计与实现北京大学本科生毕业论文.docx

大规模网页模块识别与信息提取系统设计与实现北京大学本科生毕业论文.docx

《大规模网页模块识别与信息提取系统设计与实现北京大学本科生毕业论文.docx》由会员分享，可在线阅读，更多相关《大规模网页模块识别与信息提取系统设计与实现北京大学本科生毕业论文.docx（42页珍藏版）》请在冰点文库上搜索。

大规模网页模块识别与信息提取系统设计与实现北京大学本科生毕业论文

本科生毕业论文

题目：

（中文）大规模网页模块识别与信息提取系统设计与实现

（英文）DesignandImplementationofLargeScaleWebTemplateDetectionandInformationExtractionSystem

姓名：

学号：

院系：

专业：

指导教师：

摘要

本文提出了一套基于语义的网页分块和主题内容信息提取算法，在天网搜索引擎预处理模块中将其实现，并且在SEWM2008会议中，以这套算法为框架，组织了主题型网页识别和网页主题内容信息块提取两个中文Web信息检索评测项目。

在这套算法的基础上，基于天网文件系统与Map-Reduce计算平台，实现了分布式的网页块级别QuarkRank算法，改进了PageRank算法的效果。

实际检验表明，该套算法具有很好的适应性与可扩展性，并达到了很高的精度和召回率。

关键词：

网页分块信息提取评测Map-ReducePageRank

Abstract

Thispaperpresentsasemanticweb-pageblockingandinformationextractionofthematiccontentalgorithm,whichisachievedinthepretreatmentmoduleofTianWangsearchengine,andinSEWM2008meeting,usingthisalgorithm,weorganizedtwoChineseWebInformationRetrievalEvaluationProjects,whicharetheme-basedWebpageidentificationandblockextractionoftheinformationthemecontent.Inthismethod,basedonTianWangfilesystemandtheMap-Reducecomputingplatform,thispaperreportsthedistributedblock-levelQuarkRankalgorithm,whichimprovestheresultofPageRankalgorithm.Theactualtestshowedthatthisalgorithmisgoodatadaptabilityandscalability,andreachesaveryhighprecisionandrecall.

Keywords:

Web-PageBlocking,InformationExtraction,Evaluation,Map-Reduce,PageRank

第1章序言

信息时代，非Web无以制胜。

互联网的高速发展，改变了我们的生活方式，打破了我们的时空界限，重塑着我们的社会形态。

经济、政治、学习、工作、生活、娱乐等等各个层面都在Web网络中激荡起伏，深刻地影响着人类的未来。

而Web网络的灵魂，就是流动在其中的无穷无尽的信息。

Web2.0的意义就在于网络内容的提供方从商人和专业人员转变为网络上的每一个普通用户，从而几何级数地增长了Web的信息量。

然而信息量的增大，随着而来的就是存储成本的增大和信息提取难度的增大，如何有效的获取和整合Web信息成为大家面对的共同课题。

传统意义上，整个Web网络就是由无数的Web页面而构成，它们是网络信息存储和提取的基本单位，获取了这些Web页面就相当于获取了Web信息内容。

但是把整个页面作为最基本的信息处理单位有一些不合理之处。

首先是因为Web页面中信息量的分布非常不均匀，有主题内容，也有广告，导航栏，版权信息，装饰信息，以及在大量网页中重复出现的部分，它们自身的信息含量千差万别。

当网页浏览者刚打开一个新页面的时候，如果之前没有浏览过类似页面，就会目不暇接，眼花缭乱，有无所适从的感觉，必须仔细探寻一番才能定位到这个页面的要害；如果之前浏览过类似页面，比如常上这个网站，那么通常浏览者就已经训练出一种直觉或者说是条件反射，他会立刻定位到他所想要浏览的部分，从而忽略掉页面中的其他部分。

其次还因为现在很多Web页面是动态更新的，比如博客页面或者论坛讨论帖，它们的更新是以一个一个网页块的形式进行的，更新时页面上大部分内容并没有变化，如果仍然以整个页面为处理单位，则不可避免地存在效率损失和定义的混淆。

这些情况促使我们反思以整个页面为基本信息单元的做法不仅不尽合理，一定程度上甚至已经损害了网络浏览者的用户体验，妨碍了网络信息提取的效率。

解决这个问题的办法其实有两种思路。

第一种就是从信息的产生方那儿就不再提供网页式的信息，而改为直接提供网页块或者文字段式的信息。

最常见的例子就是RSS（聚合内容，ReallySimpleSyndication），博客或者新闻的提供方省去了浏览者访问网站查看更新的麻烦，直接将精简后的网页块或者文字段发送给RSS的订阅方。

第二种则更为普适，就是细分网页中的信息单元，也就是给网页分块，在网页分块的基础上存储和提取Web页面的语义信息。

基于网页分块的Web页面的语义信息提取在很多方面都有应用。

比如，在常规搜索引擎中，可以以网页分块为基础去除网页中的噪音信息，识别出网页中的主题内容信息块，从而用提取出的主题内容信息来构建对这个页面的描述，完成网页分类、网页消重等应用。

还可以凭此改进搜索引擎的索引模块和检索模块的效率，比如改进TF/IDF和PageRank的算法（详见第五章）。

Web页面的语义分块另外一个重要用途在于移动终端访问互联网，比如手机和IPod等。

因为目前大部分的Web页面都是针对PC机设计的，要求有相对较大的屏幕。

而移动设备通常屏幕较小，计算能力有限，无法直接访问这些页面。

为了解决这个问题，要么是内容提供商手工编辑专门适用于移动设备的页面，要么就只有对页面进行语义分割，并在分割后的页面中选择信息量最高的语义块。

除此之外，Web页面的语义分块还可能对常规搜索引擎之外的其他信息检索系统有帮助。

比如类似于新闻人物追踪和历史新闻检索等应用，出于节约存储空间，提高检索精度，方便更新等目的，可以直接存储和操作网页中的主题内容语义块，而舍弃网页中其他与系统需求无关的语义块。

在这篇论文中，第二章介绍了本文的相关研究工作，包括常见的网页分块和信息提取算法、基于视觉的网页分块算法，以及网页分块的一个应用BlockLevelPageRank算法；第三章介绍了我实现的网页分块和主题信息提取算法——Quark算法；第四章介绍了Quark算法在SEWM2008中文Web信息检索评测项目中的实际检验；第五章介绍了在Quark算法基础上实现的一个分布式QuarkRank程序。

第六章是对本文的总结和工作展望。

第2章相关研究工作

2.1基于语义的网页信息提取算法

由于对Web页面有效分块之后可以极大地方便内容提取、数据挖掘、Web结构分析等各项Web信息检索领域的相关工作，所以早有很多研究人员前赴后继，就此展开了很多工作。

其中，基于语义信息对网页分块是最简便，也最基础的一种方法。

所谓语义信息，通常包括网页中包含的HTML标签信息，HTMLDOM树的结构信息，文字内容信息，超链接信息，以及其他通过统计或学习而得到的全局信息等等，也可以理解成为除了网页中的视觉信息之外的所有可以得到的信息。

通常基于语义的网页分块算法是和后续的网页主题内容提取结合在一起的，也就是在网页分块的过程中，同时完成了主题内容提取的工作，并且主要的注意点是在主题内容提取上，因此分块算法就比较简单，甚至不显式地分块，在此我们统称它们为网页信息提取算法。

总的来说，网页信息提取算法可以分为两类，一类属于网站级别（Site-Level），一类属于网页级别（Page-Level），当然也有将两类方法结合使用的算法。

Site-Level的算法顾名思义，就是分析一个网站或者网页集内部的所有网页，从中提取反复出现的模式，而一般来说，在多个网页里重复出现的模式（可理解为Dom-Tree子树）就是导航栏、广告等噪音信息了，单个网页中减去这些信息，剩下的就是主题信息内容。

关于Site-Level的研究一直在继续，WWW2008上就有一篇名为Webpagesectioningusingregex--basedtemplate[1]的论文使用正则表达式来提取重复模式，从而更适应网页间的细微变化，增加了Site-Level的召回率。

Page-Level的算法在处理大型网站的网页时效率常常不如Site-Level，但优势在于灵活，不受网页类型限制。

它只利用单个页面内部的信息，当然也可能会用到一些全局信息。

宾夕法尼亚州立大学2005年的论文[2]就是其中的典型。

这篇论文提出简化块与块之间的层次结构，直接提取一些原子块（AtomicBlock），诸如以list,table,link,object,frame,form等为根节点的html子树，来完成分块工作。

这一方法虽然简单而易于实现，但依赖于事先给出的原子块列表，同时忽略了原子块之间的嵌套链接问题。

在分块之后，它也只是简单计算了文字长度等几个变量来决定主题信息块。

合并Site-Level和Page-Level的方法也一直有人尝试。

WWW2007的论文Page-leveltemplatedetectionviaisotonicsmoothing[3]先利用一个Site-Level噪音模板提取器来构建训练集，然后对所有页面构建DOM树，为各节点提取分类特征，比如各节点的文本向量，各节点中链接的平均字数，各节点中链接文字所占比例等，最后利用以上训练集对测试集中每一个DOM树节点打分，经过等压平滑之后，判定每个DOM树节点的类型。

所以它是典型的先Site-Level，后Page-Level的方法。

2.2基于视觉的网页分块算法

基于语义的网页分块算法具有一些无法克服的先天性局限。

首先，HTML语言版本众多，一直没有有效统一，而且其语法规范很松散，一些不符合HTML规则的网页也能被完全识别，所以网页编写者在制作网页时相对随意，导致Web上的很多网页都没有完全遵循W3C规范；其次，IE、Firefox等浏览器各自为政，对HTML标签的识别不尽相同，IE甚至还特别为Office软件设计了特别的html标签以辅助显示，这些都增加了基于规则分块的复杂性。

在实际编程中，就必须得借助一些HTML规范工具如tidy等来修正DOM树结构的错误，但个别中文网页仍然存在无法修正的情况。

而且DOM树最早引入是为了在浏览器中进行布局显示而不是进行Web页面的语义结构描述。

比如，即使DOM树中两个结点具有同一个父结点，那么这两个结点在语义上也不一定就是有联系的。

反之，两个在语义上有关系的结点却可能分布在DOM树的不同之处。

因此仅仅通过分析DOM树并不能完全获取Web页面的语义信息，所以依赖于DOM树的启发式规则算法存在先天不足。

而基于视觉的网页分块算法就弥补了这个不足。

它的原理来自于用户的实际观察体验，即用户并不关心Web页面的内部结构，而是使用一些视觉因素，比如背景颜色、字体颜色和大小、边框、逻辑块和逻辑块之间的间距等等来识别出页面中的语义块。

因此如果充分的使用Web页面的视觉信息，模拟人眼识别语义块的过程，并结合DOM树结构分析进行页面分块，则可以达到更好的效果。

微软亚洲研究院在其2003年的论文VIPS:

Avisionbasedpagesegmentationalgorithm[4]里首次提出了基于视觉的网页分块算法VIPS（Vision-basedpagesegmentation）。

VIPS算法充分利用了Web页面的布局特征（见图1），它有三个主要步骤：

首先从DOM树中以较小的粒度提取出所有可视标签块，并且给每个可视标签块计算出一个DOC（“一致性程度”，DegreeofCoherence）值来描述该块内部内容的相关性。

DOC的值越大，则表明该块内部的内容之间的联系越紧密，反之越松散。

第二步利用每个可视标签块的绝对位置和相对位置信息，检测

出它们之间的所有的分割条，包括水平和垂直方向。

最后基于这些分割条，利用更多的诸如颜色等视觉信息，重新构建Web页面的语义结构。

VIPS算法的优点十分明显，它充分利用了网页的视觉信息和结构信息，相对于传统的基于规则的分块算法来说，大大提高了分块的精确度。

但VIPS算法也有其局限性：

首先，提取网页视觉信息代价很高。

因为HTML语言本身并没有包含足够的视觉信息，所以网页真正显示出来的效果因浏览器，因操作系统，甚至因硬件而异。

为了得到网页的完整视觉信息，必须完全下载该网页所链接的CSS文件，JavaScript文件，图片文件等等，然后调用浏览器内核代码渲染这些网页文件，最后从浏览器内核代码的接口中得到每个HTML标签的视觉信息。

整个步骤不仅耗时，而且十分依赖于浏览器内核代码。

网络上看到的一些VIPS算法实现都是调用了IECOM接口，而微软自身的实现是利用单独优化后的IE内核，他们都是基于Windows编程环境。

在Linux编程环境下，可以利用的只有Mozilla

（Firefox）浏览器的开源代码。

但Mozilla代码并没有针对网页视觉信息提取这一需求给出方便的使用接口，只有在其渲染完网页之后再截取视觉信息。

我们实验室的毛先领师兄曾经研究Mozilla代码，完成了这项艰苦的工作，但实验表明，提取一个网页的视觉信息所需时间超过1秒钟，不能满足搜索引擎等常规应用的使用要求。

其次，VIPS算法虽能改进分块精确度，但算法相对比较复杂，迭代轮数较多，而基于规则的分块算法却只用较少的迭代轮数。

2.3BlockLevelPageRank算法

在VIPS算法的分块基础上，微软2004年的论文Block-levelLinkAnalysis[5]中提出了BlockLevelPageRank（BLPR）算法。

之前的大多数链接分析算法都是以一个Web页面为Web图中的一个节点，而BLPR算法以网页中的语义块为原子节点，从链接结构和页面结构中提取出Page-to-Block，Block-to-Page关系矩阵，构建出新的Web语义图，并以此计算PageRank。

实验表明，BLPR改进了PageRank的质量。

2.3.1BlockLevelWebGraph

首先定义两个集合P和B。

P为所有网页的集合，P={p1,p2,…,pk}，k为网页总数。

B为所有语义块的集合，B={b1,b2,…,bn}，n为语义块总数。

对每个语义块来说，只有一个网页包含它，bi∈pj意味着语义块i包含于网页j。

而每个网页包含有多个语义块。

然后定义两个矩阵，block-to-page矩阵Z和page-to-block矩阵X。

在上述两个矩阵的基础之上，可以构建两个web图模型，即网页图GP（VP,EP,WP）和语义块图GB（VB,EB,WB）。

对这两个图来说，V是节点集合（节点分别是网页和语义块），E是连接两个节点的边的集合，而W是边的权值矩阵。

块页（block-to-page）矩阵Z的维数为n×k，定义如下：

Zij

⎧1/s

=⎨i

如果blocki中有链接指向pagej

⎩0否则

si是blocki所链接的网页总数。

Zij可以理解成是用户从blocki链接到

pagej的概率。

页块（page-to-block）矩阵X的维数为k×n，定义如下：

Xij

⎧1/s

=⎨i

如果blockj属于pagei

⎩0否则

si是pagei所包含的block总数。

上面的公式分配给pagei中的每一个block以相同的权值，显然是过于简化了，不能区分block的重要程度。

在BLPR算法中，采用了一个简单的block重要度区分的公式，即用block的文字多少和离整个页面中心点位置的远近来计算block的重要度。

每个block包含的文本长度越大，离页面中心点越近，则越重要。

改进后的X定义如

下：

Xij

⎧f

P

⎪

=⎨i

（bj）

如果blockj属于pagei

⎪⎩0否则

其中f函数给pagei中的每一个blockj赋予一个重要度权值。

函数值越大，则block越重要。

在BLPR的实现中函数f的定义如下：

fP（b）=β

pagep中blockb的大小

blockb的中心点到页面中心点的距离

其中β为正规化因子，使得对每个page，fp（b）的总和为1。

即

∑fP（b）=1

b∈p

fp（b）可以理解为是用户在浏览pagep的时候，关注blockb的可能性。

2.3.2PageGraph

传统的PageRank算法中PageGraph的权值矩阵计算十分简单，如果从pagei到pagej有链接的话，则WP（i,j）为1，反之为0。

然而在BLPR算法中，PageGraph需要体现出不同的语义块的重要程度的不同。

也就是说，当用户点击页面中的超链接时，更偏好选择重要的语义块中的URL。

所以在BLPR中，WP的定义为：

WP（α,β）=∑fα（b）Z（b,β）,

b∈α

α,β∈P

即WP

=XZ。

WP（α,β）可以理解为是从pageα开始，以pageα中包含的各语义块为媒介，跳转到pageβ的概率。

2.3.3BlockGraph

WB的定义为：

WB（a,b）=Z（a,β）X（β,b）,a,b∈B

即WB

=ZX。

WB（a,b）可以理解为用户从blocka开始，以包含blockb的pageβ为媒介，跳转到blockb的概率。

2.3.4BlockLevelPageRank

BlockLevelPageRank跟PageRank区别的实质在于，PageRank算法基于原始的只有1和0的PageGraph，而BLPR算法基于上面提到的GP。

BLPR算法的数学计算公式如下：

._.

（εU+（1-ε）M）Tp=p

其中p为结果向量，共n维，每一维代表一个网页的PageRank值。

ε为适配参数，以1-ε的概率，用户在当前页面中随机选择一个超链接，跳转到该链接指向的页面；以ε的概率，用户从所有网页中随机选择一个URL并跳转。

所以U为n×n的转换矩阵，它满足对所有的i，j，Uij=1/n。

而M也是n×n的转换矩阵，它是由上面提到的WP权值矩阵对每一行做归一化，令每一行的权值之和为1得到的。

p向量的值以马尔科夫链的形式循环计算下去，直到算法收敛。

BlockLevelPageRank比单纯的PageRank包含了更多的语义信息。

因为它的计算基于网页中各语义块的重要程度，噪音块、广告块中的超链接指向的网页的重要性显然不如导航块、正文块中的超链接所指向的网页，所以前者会被分配到较少的PageRank值，而后者则被分配到较多的PageRank值。

也就是说，网页中的无关信息区域在PageRank的计算过程中起的作用相对较小，所以BLPR的效果要优于单纯的PageRank。

第3章天网搜索引擎Quark模块

搜索引擎系统一般包括网页的抓取、预处理、存储、索引、检索等几个部分，其中预处理部分的作用是分析、处理原始网页数据如去除网页噪音，消除重复网页，计算PageRank，中文切词等等，并为后继模块提供统一的数据访问接口，规范数据管理，避免重复计算。

同时在天网搜索引擎平台中，基于功能扩展和实验室内部其他相关研究的需要，必须将对原始网页的处理部分单独出来，从而方便模块复用，统一代码管理，减少重复劳动。

在天网搜索引擎平台的搭建过程中，也包括了抓取、存储、分析（预处理）、索引、检索等模块，其中的分析模块接受成批量原始网页的输入，然后对每个网页调用Quark模块，进行网页分块、信息提取等工作，最后将处理后的数据存成TwDocView格式，再提供给下游模块。

我的毕业设计的主要工作，就是围绕Quark模块而展开。

从上面的介绍中可以看出，天网搜索引擎Quark模块有两个比较重要的特点：

1、可扩展性。

因为搜索引擎是一个比较庞大的系统，并且一直在不停的有新算法，新需求的加入，所以对数据的要求也会一直变化。

而基于对原始网页数据集中处理的原则，为了应对下游模块可能提取的新的数据访问需求，Quark模块必须具备良好的可扩展性，并且提供尽量多的各种类型的数据访问接口。

同时由于实验室人员的不固定性，代码的维护十分重要。

我自己在刚开始阅读旧有的天网搜索引擎相关代码的时候，就常有十分难懂的感觉，无法复用已有代码，只好自己重新编写。

而正由于Quark模块的可扩展性要求，所以它的代码的可阅读性也十分重要，在编写的过程中，我尽量注意了这一点，遵守了我们统一的代码规范。

2、独立性。

在我们实验室内部，除了搜索引擎之外，还有Web数据挖掘，Map-reduce应用等相关工作也可能需要使用对单个网页的处理和数据提取程序。

因此Quark模块必须能独立于搜索引擎代码之外单独编译运行，并且方便他人调用这部分代码。

基于上述两个特点，我初步实现了Quark模块。

该模块的类结构图如下：

1、图中右下及中间蓝色的部分为Quark模块的核心功能类，包括QuarkTree、QuarkElement、QuarkRecognizer、QuarkAnalyzer等四个类。

QuarkTree类的作用有两个，一个是以原始网页为输入，建立Html的DomTree；另一个是存储分好的网页块（在我们的系统中，每一个网页块就叫做一个Quark）并记录Quark与Quark之间的组织架构。

QuarkElement类指代一个Quark,即每个Quark自身就是一个QuarkElement类的对象。

QuarkRecognizer类肩负网页分块的重任，从网页中识别出所有语义块。

它依赖于前面的两个类。

QuarkAnalyzer类依赖于QuarkRecognizer类，它在分好的块的基础上，判断各个块的类型，提取正文信息。

这个类是整个Quark模块最核心的类，目前功能只是初步实现，还有很大的改进空间，将来也可以根据功能将其分割成多个类。

2、中上部绿色的部分为Quark模块的评测和演示类，包括QuarkEvaluation和QuarkHtmlBuilder两个类。

QuarkEvaluation类是评测类，用来评测Quark核心类的实现效果。

当前实现的是对网页正文信息提取的评测，评测需要接受人工标记的网页或网页集为输入。

评测算法的细节见后文。

QuarkHtmlBuilder类是演示类，用来查看Quark模块各步骤的实现效果。

目前可以查看网页分块的效果，也可以查看主题信息提取的效果。

3、最上面黄色的部分为Quark模块的应用类，包括QuarkRank、Qu