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

1、大规模网页模块识别与信息提取系统设计与实现北京大学本科生毕业论文 本科生毕业论文题目：(中文)大规模网页模块识别与信息提取系统设计与实现(英文 )Design and Implementation of Large Scale Web Template Detection and Information Extraction System姓 名： 学 号： 院 系： 专 业： 指导教师： 摘要本文提出了一套基于语义的网页分块和主题内容信息提取算法，在天网搜索引擎预处理模块中将其实现，并且在SEWM 2008 会议中，以这套算法为框架，组织了主题型网页识别和网页主题内容信息块提取两个中文Web

2、信息检索评测项目。在这套算法的基础上，基于天网文件系统与Map-Reduce 计算平台，实现了分布式的网页块级别QuarkRank 算法，改进了PageRank 算法的效果。实际检验表明，该套算法具有很好的适应性与可扩展性，并达到了很高的精度和召回率。关键词：网页分块信息提取评测Map-Reduce PageRankAbstractThis paper presents a semantic web-page blocking and information extraction of thematic content algorithm, which is achieved in the p

3、retreatment module of TianWang search engine, and in SEWM 2008 meeting, using this algorithm, we organized two Chinese Web Information Retrieval Evaluation Projects, which are theme-based Web page identification and block extraction of the information theme content. In this method, based on TianWang

4、file system and the Map-Reduce computing platform, this paper reports the distributed block-level QuarkRank algorithm, which improves the result of PageRank algorithm. The actual test showed that this algorithm is good at adaptability and scalability, and reaches a very high precision andrecall.Keyw

5、ords:Web-Page Blocking, Information Extraction, Evaluation, Map-Reduce, PageRank第1章 序言信息时代，非Web 无以制胜。互联网的高速发展，改变了我们的生活方式，打破了我们的时空界限，重塑着我们的社会形态。经济、政治、学习、工作、生活、娱乐等等各个层面都在Web 网络中激荡起伏，深刻地影响着人类的未来。而Web 网络的灵魂，就是流动在其中的无穷无尽的信息。Web2.0 的意义就在于网络内容的提供方从商人和专业人员转变为网络上的每一个普通用户，从而几何级数地增长了Web 的信息量。然而信息量的增大，随着而来的就是存储

6、成本的增大和信息提取难度的增大，如何有效的获取和整合Web 信息成为大家面对的共同课题。传统意义上，整个Web 网络就是由无数的Web 页面而构成，它们是网络信息存储和提取的基本单位，获取了这些Web 页面就相当于获取了Web 信息内容。但是把整个页面作为最基本的信息处理单位有一些不合理之处。首先是因为Web页面中信息量的分布非常不均匀，有主题内容，也有广告，导航栏，版权信息，装饰信息，以及在大量网页中重复出现的部分，它们自身的信息含量千差万别。当网页浏览者刚打开一个新页面的时候，如果之前没有浏览过类似页面，就会目不暇接，眼花缭乱，有无所适从的感觉，必须仔细探寻一番才能定位到这个页面的要害；如

7、果之前浏览过类似页面，比如常上这个网站，那么通常浏览者就已经训练出一种直觉或者说是条件反射，他会立刻定位到他所想要浏览的部分，从而忽略掉页面中的其他部分。其次还因为现在很多Web 页面是动态更新的，比如博客页面或者论坛讨论帖，它们的更新是以一个一个网页块的形式进行的，更新时页面上大部分内容并没有变化，如果仍然以整个页面为处理单位，则不可避免地存在效率损失和定义的混淆。这些情况促使我们反思以整个页面为基本信息单元的做法不仅不尽合理，一定程度上甚至已经损害了网络浏览者的用户体验，妨碍了网络信息提取的效率。解决这个问题的办法其实有两种思路。第一种就是从信息的产生方那儿就不再提供网页式的信息，而改为直

8、接提供网页块或者文字段式的信息。最常见的例子就是RSS（聚合内容，Really Simple Syndication），博客或者新闻的提供方省去了浏览者访问网站查看更新的麻烦，直接将精简后的网页块或者文字段发送给RSS 的订阅方。第二种则更为普适，就是细分网页中的信息单元，也就是给网页分块，在网页分块的基础上存储和提取Web 页面的语义信息。基于网页分块的Web 页面的语义信息提取在很多方面都有应用。比如，在常规搜索引擎中，可以以网页分块为基础去除网页中的噪音信息，识别出网页中的主题内容信息块，从而用提取出的主题内容信息来构建对这个页面的描述，完成网页分类、网页消重等应用。还可以凭此改进搜索引

9、擎的索引模块和检索模块的效率，比如改进TF/IDF 和PageRank 的算法（详见第五章）。Web 页面的语义分块另外一个重要用途在于移动终端访问互联网，比如手机和IPod 等。因为目前大部分的Web 页面都是针对PC 机设计的，要求有相对较大的屏幕。而移动设备通常屏幕较小，计算能力有限，无法直接访问这些页面。为了解决这个问题，要么是内容提供商手工编辑专门适用于移动设备的页面，要么就只有对页面进行语义分割，并在分割后的页面中选择信息量最高的语义块。除此之外，Web 页面的语义分块还可能对常规搜索引擎之外的其他信息检索系统有帮助。比如类似于新闻人物追踪和历史新闻检索等应用，出于节约存储空间，提

10、高检索精度，方便更新等目的，可以直接存储和操作网页中的主题内容语义块，而舍弃网页中其他与系统需求无关的语义块。在这篇论文中，第二章介绍了本文的相关研究工作，包括常见的网页分块和信息提取算法、基于视觉的网页分块算法，以及网页分块的一个应用Block Level PageRank算法；第三章介绍了我实现的网页分块和主题信息提取算法Quark 算法；第四章介绍了Quark 算法在SEWM2008 中文Web信息检索评测项目中的实际检验；第五章介绍了在Quark 算法基础上实现的一个分布式QuarkRank 程序。第六章是对本文的总结和工作展望。第2章 相关研究工作2.1 基于语义的网页信息提取算法由

11、于对Web 页面有效分块之后可以极大地方便内容提取、数据挖掘、Web 结构分析等各项Web 信息检索领域的相关工作，所以早有很多研究人员前赴后继，就此展开了很多工作。其中，基于语义信息对网页分块是最简便，也最基础的一种方法。所谓语义信息，通常包括网页中包含的HTML 标签信息，HTML DOM 树的结构信息，文字内容信息，超链接信息，以及其他通过统计或学习而得到的全局信息等等，也可以理解成为除了网页中的视觉信息之外的所有可以得到的信息。通常基于语义的网页分块算法是和后续的网页主题内容提取结合在一起的，也就是在网页分块的过程中，同时完成了主题内容提取的工作，并且主要的注意点是在主题内容提取上，因

12、此分块算法就比较简单，甚至不显式地分块，在此我们统称它们为网页信息提取算法。总的来说，网页信息提取算法可以分为两类，一类属于网站级别（Site-Level），一类属于网页级别（Page-Level），当然也有将两类方法结合使用的算法。Site-Level 的算法顾名思义，就是分析一个网站或者网页集内部的所有网页，从中提取反复出现的模式，而一般来说，在多个网页里重复出现的模式（可理解为Dom-Tree 子树）就是导航栏、广告等噪音信息了，单个网页中减去这些信息，剩下的就是主题信息内容。关于Site-Level 的研究一直在继续，WWW2008 上就有一篇名为Web page sectioning

13、 using regex-based template1的论文使用正则表达式来提取重复模式，从而更适应网页间的细微变化，增加了Site-Level 的召回率。Page-Level 的算法在处理大型网站的网页时效率常常不如Site-Level，但优势在于灵活，不受网页类型限制。它只利用单个页面内部的信息，当然也可能会用到一些全局信息。宾夕法尼亚州立大学2005 年的论文2就是其中的典型。这篇论文提出简化块与块之间的层次结构，直接提取一些原子块（Atomic Block），诸如以list, table, link, object, frame, form 等为根节点的html 子树，来完成分块工作

14、。这一方法虽然简单而易于实现，但依赖于事先给出的原子块列表，同时忽略了原子块之间的嵌套链接问题。在分块之后，它也只是简单计算了文字长度等几个变量来决定主题信息块。合并Site-Level 和Page-Level 的方法也一直有人尝试。WWW2007 的论文Page-level template detection via isotonic smoothing3先利用一个Site-Level 噪音模板提取器来构建训练集，然后对所有页面构建DOM 树，为各节点提取分类特征，比如各节点的文本向量，各节点中链接的平均字数，各节点中链接文字所占比例等，最后利用以上训练集对测试集中每一个DOM 树节点打分

15、，经过等压平滑之后，判定每个DOM 树节点的类型。所以它是典型的先Site-Level，后Page-Level 的方法。2.2 基于视觉的网页分块算法基于语义的网页分块算法具有一些无法克服的先天性局限。首先，HTML 语言版本众多，一直没有有效统一，而且其语法规范很松散，一些不符合HTML 规则的网页也能被完全识别，所以网页编写者在制作网页时相对随意，导致Web 上的很多网页都没有完全遵循W3C 规范；其次，IE、Firefox 等浏览器各自为政，对HTML 标签的识别不尽相同，IE 甚至还特别为Office 软件设计了特别的html 标签以辅助显示，这些都增加了基于规则分块的复杂性。在实际编

16、程中，就必须得借助一些HTML 规范工具如tidy 等来修正DOM 树结构的错误，但个别中文网页仍然存在无法修正的情况。而且DOM 树最早引入是为了在浏览器中进行布局显示而不是进行Web 页面的语义结构描述。比如，即使DOM 树中两个结点具有同一个父结点，那么这两个结点在语义上也不一定就是有联系的。反之，两个在语义上有关系的结点却可能分布在DOM 树的不同之处。因此仅仅通过分析DOM 树并不能完全获取Web 页面的语义信息，所以依赖于DOM 树的启发式规则算法存在先天不足。而基于视觉的网页分块算法就弥补了这个不足。它的原理来自于用户的实际观察体验，即用户并不关心Web 页面的内部结构，而是使用

17、一些视觉因素，比如背景颜色、字体颜色和大小、边框、逻辑块和逻辑块之间的间距等等来识别出页面中的语义块。因此如果充分的使用Web 页面的视觉信息，模拟人眼识别语义块的过程，并结合DOM 树结构分析进行页面分块，则可以达到更好的效果。微软亚洲研究院在其2003 年的论文VIPS: A vision based page segmentation algorithm4 里首次提出了基于视觉的网页分块算法VIPS(Vision-basedpage segmentation)。VIPS算法充分利用了Web页面的布局特征（见图1），它有三个主要步骤：首先从DOM 树中以较小的粒度提取出所有可视标签块，并且

18、给每个可视标签块计算出一个DOC（“一致性程度”，Degree of Coherence）值来描述该块内部内容的相关性。DOC 的值越大，则表明该块内部的内容之间的联系越紧密，反之越松散。第二步利用每个可视标签块的绝对位置和相对位置信息，检测出它们之间的所有的分割条，包括水平和垂直方向。最后基于这些分割条，利用更多的诸如颜色等视觉信息，重新构建Web 页面的语义结构。VIPS 算法的优点十分明显，它充分利用了网页的视觉信息和结构信息，相对于传统的基于规则的分块算法来说，大大提高了分块的精确度。但VIPS 算法也有其局限性：首先，提取网页视觉信息代价很高。因为HTML 语言本身并没有包含足够的视

19、觉信息，所以网页真正显示出来的效果因浏览器，因操作系统，甚至因硬件而异。为了得到网页的完整视觉信息，必须完全下载该网页所链接的CSS 文件，JavaScript 文件，图片文件等等，然后调用浏览器内核代码渲染这些网页文件，最后从浏览器内核代码的接口中得到每个HTML 标签的视觉信息。整个步骤不仅耗时，而且十分依赖于浏览器内核代码。网络上看到的一些VIPS 算法实现都是调用了IE COM 接口，而微软自身的实现是利用单独优化后的IE 内核，他们都是基于Windows 编程环境。在Linux 编程环境下，可以利用的只有Mozilla（Firefox）浏览器的开源代码。但Mozilla 代码并没有针

20、对网页视觉信息提取这一需求给出方便的使用接口，只有在其渲染完网页之后再截取视觉信息。我们实验室的毛先领师兄曾经研究Mozilla 代码，完成了这项艰苦的工作，但实验表明，提取一个网页的视觉信息所需时间超过1 秒钟，不能满足搜索引擎等常规应用的使用要求。其次，VIPS 算法虽能改进分块精确度，但算法相对比较复杂，迭代轮数较多，而基于规则的分块算法却只用较少的迭代轮数。2.3 Block Level PageRank算法在VIPS 算法的分块基础上，微软2004 年的论文Block-level Link Analysis5 中提出了Block Level PageRank(BLPR)算法。之前的大

21、多数链接分析算法都是以一个Web 页面为Web 图中的一个节点，而BLPR 算法以网页中的语义块为原子节点，从链接结构和页面结构中提取出Page-to-Block，Block-to-Page 关系矩阵，构建出新的Web 语义图，并以此计算PageRank。实验表明，BLPR 改进了PageRank 的质量。2.3.1 Block Level WebGraph首先定义两个集合P 和B。P 为所有网页的集合，P = p1, p2, , pk，k 为网页总数。B 为所有语义块的集合，B = b1, b2, , bn，n 为语义块总数。对每个语义块来说，只有一个网页包含它，bi pj 意味着语义块i

22、包含于网页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 的维数为nk，定义如下：Zij1/s= i如果block i中有链接指向page j0 否则si 是block i 所链接的网页总数。Zij 可以理解成是用户从block i 链接

23、到page j 的概率。页块（page-to-block）矩阵X 的维数为kn，定义如下：Xij1/s= i如果block j属于page i0 否则si 是page i 所包含的block 总数。上面的公式分配给page i 中的每一个block 以相同的权值，显然是过于简化了，不能区分block 的重要程度。在BLPR 算法中，采用了一个简单的block 重要度区分的公式，即用block 的文字多少和离整个页面中心点位置的远近来计算block的重要度。每个block 包含的文本长度越大，离页面中心点越近，则越重要。改进后的X定义如下：XijfP= i(bj)如果block j属于page

24、i0 否则其中f 函数给page i 中的每一个block j 赋予一个重要度权值。函数值越大，则block 越重要。在BLPR 的实现中函数f 的定义如下：fP (b)=page p中block b的大小blockb的中心点到页面中心点的距离其中为正规化因子，使得对每个page，fp(b)的总和为1。即fP(b)=1bpfp(b)可以理解为是用户在浏览page p 的时候，关注block b 的可能性。2.3.2 PageGraph传统的PageRank 算法中Page Graph 的权值矩阵计算十分简单，如果从page i到pagej有链接的话，则WP(i,j)为1，反之为0。然而在BLP

25、R算法中，PageGraph 需要体现出不同的语义块的重要程度的不同。也就是说，当用户点击页面中的超链接时，更偏好选择重要的语义块中的URL。所以在BLPR中，WP的定义为：WP(,)=f(b)Z(b,),b,P即WP=XZ 。WP(, )可以理解为是从page 开始，以page 中包含的各语义块为媒介，跳转到page 的概率。2.3.3 BlockGraphWB 的定义为：WB(a,b)=Z(a,)X(,b), a,bB即WB=ZX 。WB(a,b)可以理解为用户从block a 开始，以包含block b 的page 为媒介，跳转到block b 的概率。2.3.4 Block Level

26、PageRankBlock Level PageRank 跟PageRank 区别的实质在于，PageRank 算法基于原始的只有1和0的PageGraph，而BLPR算法基于上面提到的GP。BLPR算法的数学计算公式如下：. _.(U + (1-)M )T p =p其中p 为结果向量，共n 维，每一维代表一个网页的PageRank 值。为适配参数，以1-的概率，用户在当前页面中随机选择一个超链接，跳转到该链接指向的页面；以的概率，用户从所有网页中随机选择一个URL 并跳转。所以U 为nn 的转换矩阵，它满足对所有的i，j，Uij = 1/n。而M 也是nn 的转换矩阵，它是由上面提到的WP

27、权值矩阵对每一行做归一化，令每一行的权值之和为1 得到的。p 向量的值以马尔科夫链的形式循环计算下去，直到算法收敛。Block Level PageRank 比单纯的PageRank 包含了更多的语义信息。因为它的计算基于网页中各语义块的重要程度，噪音块、广告块中的超链接指向的网页的重要性显然不如导航块、正文块中的超链接所指向的网页，所以前者会被分配到较少的PageRank 值，而后者则被分配到较多的PageRank 值。也就是说，网页中的无关信息区域在PageRank 的计算过程中起的作用相对较小，所以BLPR 的效果要优于单纯的PageRank。第3章 天网搜索引擎Quark 模块搜索引擎

28、系统一般包括网页的抓取、预处理、存储、索引、检索等几个部分，其中预处理部分的作用是分析、处理原始网页数据如去除网页噪音，消除重复网页，计算PageRank，中文切词等等，并为后继模块提供统一的数据访问接口，规范数据管理，避免重复计算。同时在天网搜索引擎平台中，基于功能扩展和实验室内部其他相关研究的需要，必须将对原始网页的处理部分单独出来，从而方便模块复用，统一代码管理，减少重复劳动。在天网搜索引擎平台的搭建过程中，也包括了抓取、存储、分析（预处理）、索引、检索等模块，其中的分析模块接受成批量原始网页的输入，然后对每个网页调用Quark 模块，进行网页分块、信息提取等工作，最后将处理后的数据存成

29、TwDocView 格式，再提供给下游模块。我的毕业设计的主要工作，就是围绕Quark 模块而展开。从上面的介绍中可以看出，天网搜索引擎Quark模块有两个比较重要的特点：1、可扩展性。因为搜索引擎是一个比较庞大的系统，并且一直在不停的有新算法，新需求的加入，所以对数据的要求也会一直变化。而基于对原始网页数据集中处理的原则，为了应对下游模块可能提取的新的数据访问需求，Quark 模块必须具备良好的可扩展性，并且提供尽量多的各种类型的数据访问接口。同时由于实验室人员的不固定性，代码的维护十分重要。我自己在刚开始阅读旧有的天网搜索引擎相关代码的时候，就常有十分难懂的感觉，无法复用已有代码，只好自己

30、重新编写。而正由于Quark 模块的可扩展性要求，所以它的代码的可阅读性也十分重要，在编写的过程中，我尽量注意了这一点，遵守了我们统一的代码规范。2、独立性。在我们实验室内部，除了搜索引擎之外，还有Web 数据挖掘，Map-reduce 应用等相关工作也可能需要使用对单个网页的处理和数据提取程序。因此Quark模块必须能独立于搜索引擎代码之外单独编译运行，并且方便他人调用这部分代码。基于上述两个特点，我初步实现了Quark模块。该模块的类结构图如下：1、图中右下及中间蓝色的部分为Quark模块的核心功能类，包括QuarkTree、 QuarkElement、QuarkRecognizer、Qu

31、arkAnalyzer等四个类。QuarkTree 类的作用有两个，一个是以原始网页为输入，建立Html 的 Dom Tree；另一个是存储分好的网页块（在我们的系统中，每一个网页块就叫做一个Quark）并记录Quark与Quark之间的组织架构。QuarkElement 类指代一个Quark,即每个Quark 自身就是一个QuarkElement类的对象。QuarkRecognizer类肩负网页分块的重任，从网页中识别出所有语义块。它依赖于前面的两个类。QuarkAnalyzer类依赖于QuarkRecognizer类，它在分好的块的基础上，判断各个块的类型，提取正文信息。这个类是整个Qua

32、rk模块最核心的类，目前功能只是初步实现，还有很大的改进空间，将来也可以根据功能将其分割成多个类。2、中上部绿色的部分为Quark模块的评测和演示类，包括QuarkEvaluation 和QuarkHtmlBuilder两个类。QuarkEvaluation类是评测类，用来评测Quark核心类的实现效果。当前实现的是对网页正文信息提取的评测，评测需要接受人工标记的网页或网页集为输入。评测算法的细节见后文。QuarkHtmlBuilder类是演示类，用来查看Quark模块各步骤的实现效果。目前可以查看网页分块的效果，也可以查看主题信息提取的效果。3、最上面黄色的部分为Quark 模块的应用类，包括QuarkRank、 Qu