【计算机专业毕业论文】大规模网页模块识别与信息提取 系统设计与实现.doc
本科生毕业论文 题目:(中文) 大规模网页模块识别与信息提取
系统设计与实现
(英文) Design and Implementation of Large Scale Web Template Detection and
Information Extraction System
姓 名:
学 号:
院 系:计算机
专 业:搜索引擎与互联网信息挖掘
指导教师:
摘要
本文在已有的基于Dom-Tree和启发式规则的网页信息提取算法的基础上，通过为所有符合W3C
规范
编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载
的Html标签分类，逐个分析各Html标签所包含的语义信息，细化规则设置，实现了一种自底向上的无信息遗漏的网页分块算法，并在此基础上，利用统计
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
得到详细的概率分布数据，实现了文本相似度比较和Bayes后验概率估计两种网页主题内容信息块识别算法，并将其求交，提高了主题内容信息块的识别精确度。
上述算法已集成到天网搜索引擎平台的网页预处理模块中，并且在SEWM 2008会议中，以这套算法为框架，组织了主题型网页识别和网页主题内容信息块提取两个中文Web信息检索评测项目。在这套算法的基础上，基于天网文件系统与Map-Reduce计算平台，实现了分布式的网页块级别PageRank算法，命名为QuarkRank算法。实际检验表明，该套算法具有很好的适应性与可扩展性，并达到了很高的精度和召回率。
关键词:网页分块 信息提取 SEWM 评测 PageRank
i
Abstract
This paper has been based on the Dom-Tree and heuristic rules of the Web information extraction method, by classifying all the Html tags in line with W3C standards, and by analyzing semantic information contained in the Html tags one by one, it refines the rules set and achieves a bottom-up page block algorithm without information missing.
On this basis, with the probability distribution of data getting from statistical methods, this paper realizes two algorithms of information block recognition, one is text similarity comparison and the other is Bayes posterior probability estimates, and the final result comes from their intersection, which improves the accuracy of information theme block recognition.
These algorithms have been integrated into the page pretreatment module of TianWang search engine platform, and in SEWM 2008 meeting, using these algorithms, we organized two Chinese Web Information Retrieval Evaluation Project, Which two are theme-based Web page identification and block extraction of the information theme content.
In this method, based on TianWang file system and the Map-Reduce computing platform, this paper reports the distributed block-level PageRank algorithm, named QuarkRank algorithm here. The actual test showed that these algorithms are good at adaptability and scalability, and reach a very high precision and recall.
Keywords:
Web-Page Blocking, SEWM, Information Extraction, Evaluation , PageRank
i
目录
第 1 章 序言.................................................................................................... 3 第 2 章 相关研究工作.................................................................................... 5
2.1 基于语义的网页信息提取算法 ....................................................... 5
2.2 基于视觉的网页分块算法 ............................................................... 6
2.3 Block Level PageRank算法 ............................................................. 8
2.3.1 Block Level Web Graph ............................................................... 8
2.3.2 Block Level PageRank ............................................................... 10 第 3 章 天网搜索引擎Quark模块.............................................................. 11
3.1 网页分块算法 ................................................................................. 13
3.2 网页主题内容提取 ......................................................................... 16
3.3 算法效果演示 ................................................................................. 18 第 4 章 SEWM2008中文Web信息检索评测 ........................................... 23
4.1 评测任务介绍 ................................................................................. 23
4.1.1 主题型网页发现任务 ................................................................ 23
4.1.2 网页内容信息发现任务 ............................................................ 24
4.2 评测格式 ......................................................................................... 25
4.3 评测结果 ......................................................................................... 25
4.3.1 主题型网页发现任务评测结果 ................................................ 26
4.3.2 网页内容信息发现任务评测结果 ............................................ 28
4.4 评测综述 ......................................................................................... 31 第 5 章 网页分块的分布式应用.................................................................. 33
5.1 QuarkRank....................................................................................... 33
5.2 其他应用 ......................................................................................... 35 第 6 章 总结与展望...................................................................................... 36
6.1 总结 ................................................................................................. 36
6.2 展望 ................................................................................................. 37
ii
第 1 章 序言
信息时代，非Web无以制胜。互联网的高速发展，改变了我们的生活方式，打破了我们的时空界限，重塑着我们的社会形态。经济、政治、学习、工作、生活、娱乐等等各个层面都在Web网络中激荡起伏，深刻地影响着人类的未来。而Web网络的灵魂，就是流动在其中的无穷无尽的信息。Web2.0的意义就在于 网络内容的提供方从商人和专业人员转变为网络上的每一个普通用户，从而几何级数地增长了Web的信息量。然而信息量的增大，随着而来的就是存储成本的增大和信息提取难度的增大，如何有效的获取和整合Web信息成为大家面对的共同课题。
传统意义上，整个Web网络就是由无数的Web页面而构成，它们是网络信息存储和提取的基本单位，获取了这些Web页面就相当于获取了Web信息内容。但是把整个页面作为最基本的信息处理单位有一些不合理之处。首先是因为Web页面中信息量的分布非常不均匀，有主题内容，也有广告，导航栏，版权信息，装饰信息，以及在大量网页中重复出现的部分，它们自身的信息含量千差万别。当网页浏览者刚打开一个新页面的时候，如果之前没有浏览过类似页面，就会目不暇接，眼花缭乱，有无所适从的感觉，必须仔细探寻一番才能定位到这个页面的要害;如果之前浏览过类似页面，比如常上这个网站，那么通常浏览者就已经训练出一种直觉或者说是条件反射，他会立刻定位到他所想要浏览的部分，从而忽略掉页面中的其他部分。
其次还因为现在很多Web页面是动态更新的，比如博客页面或者论坛讨论帖，它们的更新是以一个一个网页块的形式进行的，更新时页面上大部分内容并没有变化，如果仍然以整个页面为处理单位，则不可避免地存在效率损失和定义的混淆。这些情况促使我们反思以整个页面为基本信息单元的做法不仅不尽合理，一定程度上甚至已经损害了网络浏览者的用户体验，妨碍了网络信息提取的效率。
解决这个问题的办法其实有两种思路。第一种就是从信息的产生方那儿就不再提供网页式的信息，而改为直接提供网页块或者文字段式的信息。最常见的例子就是RSS(聚合内容，Really Simple Syndication)，博客或者新闻的提供方省去了浏览者访问网站查看更新的麻烦，直接将精简后的网页块或者文字段发送给RSS的订阅方。第二种则更为普适，就是细分网页中的信息单元，也就是给网页分块，在网页分块的基础上存储和提取Web页面的语义信息。
3
基于网页分块的Web页面的语义信息提取在很多方面都有应用。比如，在常规搜索引擎中，可以以网页分块为基础去除网页中的噪音信息，识别出网页中的主题内容信息块，从而用提取出的主题内容信息来构建对这个页面的描述，完成网页分类、网页消重等应用。还可以凭此改进搜索引擎的索引模块和检索模块的效率，比如改进TF/IDF和PageRank的算法(详见第五章)。
Web页面的语义分块另外一个重要用途在于移动终端访问互联网，比如手机和IPod等。因为目前大部分的Web页面都是针对PC机设计的，要求有相对较大的屏幕。而移动设备通常屏幕较小，计算能力有限，无法直接访问这些页面。 为了解决这个问题，要么是内容提供商手工编辑专门适用于移动设备的页面，要么就只有对页面进行语义分割，并在分割后的页面中选择信息量最高的语义块。
除此之外，Web页面的语义分块还可能对常规搜索引擎之外的其他信息检索系统有帮助。比如类似于新闻人物追踪和历史新闻检索等应用，出于节约存储空间，提高检索精度，方便更新等目的，可以直接存储和操作网页中的主题内容语义块，而舍弃网页中其他与系统需求无关的语义块。
在这篇论文中，第二章介绍了本文的相关研究工作，包括常见的网页分块和信息提取算法、基于视觉的网页分块算法，以及网页分块的一个应用Block Level PageRank算法;第三章介绍了我实现的网页分块和主题信息提取算法——Quark算法;第四章介绍了Quark算法在SEWM2008中文Web信息检索评测项目中的实际检验;第五章介绍了在Quark算法基础上实现的一个分布式QuarkRank程序。第六章是对本文的总结和工作展望。
4
第 2 章 相关研究工作
2.1 基于语义的网页信息提取算法
由于对Web页面有效分块之后可以极大地方便内容提取、数据挖掘、Web结构分析等各项Web信息检索领域的相关工作，所以早有很多研究人员前赴后继，就此展开了很多工作。其中，基于语义信息对网页分块是最简便，也最基础的一种方法。所谓语义信息，通常包括网页中包含的HTML标签信息，HTML DOM树的结构信息，文字内容信息，超链接信息，以及其他通过统计或学习而得到的全局信息等等，也可以理解成为除了网页中的视觉信息之外的所有可以得到的信息。
通常基于语义的网页分块算法是和后续的网页主题内容提取结合在一起的，也就是在网页分块的过程中，同时完成了主题内容提取的工作，并且主要的注意点是在主题内容提取上，因此分块算法就比较简单，甚至不显式地分块，在此我们统称它们为网页信息提取算法。总的来说，网页信息提取算法可以分为两类，一类属于网站级别(Site-Level)，一类属于网页级别(Page-Level)，当然也有将两类方法结合使用的算法。
Site-Level的算法顾名思义，就是分析一个网站或者网页集内部的所有网页，从中提取反复出现的模式，而一般来说，在多个网页里重复出现的模式(可理解为Dom-Tree子树)就是导航栏、广告等噪音信息了，单个网页中减去这些信息，剩下的就是主题信息内容。关于Site-Level的研究一直在继续，WWW2008上就有一篇名为Web page sectioning using regex,-based template[1]的论文使用正则表达式来提取重复模式，从而更适应网页间的细微变化，增加了Site-Level的召回率。
Page-Level的算法在处理大型网站的网页时效率常常不如Site-Level，但优势在于灵活，不受网页类型限制。它只利用单个页面内部的信息，当然也可能会用到一些全局信息。宾夕法尼亚州立大学2005年的论文[2]就是其中的典型。这篇论文提出简化块与块之间的层次结构，直接提取一些原子块(Atomic Block)，诸如以list, table, link, object, frame, form等为根节点的html子树，来完成分块工作。这一方法虽然简单而易于实现，但依赖于事先给出的原子块列表，同时忽略了原子块之间的嵌套链接问题。在分块之后，它也只是简单计算了文字长度等几个变量来决定主题信息块。
5
合并Site-Level和Page-Level的方法也一直有人尝试。WWW2007的论文Page-level template detection via isotonic smoothing[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: A vision based page segmentation
algorithm[4]里首次提出了基于视觉的网页分块算法VIPS(Vision-based page
segmentation)。VIPS算法充分利用了Web页面的布局特征(见图1)，它有三个主要步骤:首先从DOM树中以较小的粒度提取出所有可视标签块，并且给每个可视标签块计算出一个DOC(“一致性程度”，Degree of Coherence)值来描述该块内部内容的相关性。DOC的值越大，则表明该块内部的内容之间的联系越紧密，反之越松散。第二步利用每个可视标签块的绝对位置和相对位置信息，检测
6
出它们之间的所有的分割条，包括水平和垂直方向。最后基于这些分割条，利用更多的诸如颜色等视觉信息，重新构建Web页面的语义结构。
VIPS算法的优点十分明显，它充分利用了网页的视觉信息和结构信息，相对于传统的基于规则的分块算法来说，大大提高了分块的精确度。但VIPS算法也有其局限性:
首先，提取网页视觉信息代价很高。因为HTML语言本身并没有包含足够的视觉信息，所以网页真正显示出来的效果因浏览器，因操作系统，甚至因硬件而异。为了得到网页的完整视觉信息，必须完全下载该网页所链接的CSS文件，JavaScript文件，图片文件等等，然后调用浏览器内核代码渲染这些网页文件，最后从浏览器内核代码的接口中得到每个HTML标签的视觉信息。整个步骤不仅耗时，而且十分依赖于浏览器内核代码。网络上看到的一些VIPS算法实现都是调用了IE COM接口，而微软自身的实现是利用单独优化后的IE内核，他们都是基于Windows编程环境。在Linux编程环境下，可以利用的只有Mozilla(Firefox)浏览器的开源代码。但Mozilla代码并没有针对网页视觉信息提取这一需求给出方便的使用接口，只有在其渲染完网页之后再截取视觉信息。我们实验室的毛先领师兄曾经研究Mozilla代码，完成了这项艰苦的工作，但实验表明，提取一个网页的视觉信息所需时间超过1秒钟，不能满足搜索引擎等常规应用的使用要求。
其次，VIPS算法虽能改进分块精确度，但算法相对比较复杂，迭代轮数较多，而基于规则的分块算法却只用较少的迭代轮数。
7
2.3 Block Level PageRank算法
在VIPS算法的分块基础上，微软2004年的论文Block-level Link Analysis[5]
中提出了Block Level PageRank(BLPR)算法。之前的大多数链接分析算法都是以一个Web页面为Web图中的一个节点，而BLPR算法以网页中的语义块为原子节点，从链接结构和页面结构中提取出Page-to-Block，Block-to-Page关系矩阵，构建出新的Web语义图，并以此计算PageRank。实验表明，BLPR改进了PageRank的质量。
2.3.1 Block Level Web Graph
首先定义两个集合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图模型，
, W) 和语义块图G (V, E, W)。对这两个图来说，V是节即网页图G(V,EPPBBBBP P
点集合(节点分别是网页和语义块)，E是连接两个节点的边的集合，而W是边的权值矩阵。
2.3.1.1 Block-to-Page矩阵
块页(block-to-page)矩阵Z的维数为n×k，定义如下:
1/blockipagejs 如果 中有链接指向 ,i Z,,ij0 否则,
si是block i所链接的网页总数。Z可以理解成是用户从block i链接到ij
page j的概率。
2.3.1.2 Page-to-Block矩阵
页块(page-to-block)矩阵X的维数为k×n，定义如下:
1/blockjpageis 如果 属于 , iX,,ij 0 否则,
8
si是page i所包含的block总数。上面的
公式
小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载
分配给page i中的每一个block以相同的权值，显然是过于简化了，不能区分block的重要程度。在BLPR算法中，采用了一个简单的block重要度区分的公式，即用block的文字多少和离整个页面中心点位置的远近来计算block的重要度。每个block包含的文本长度越大，离页面中心点越近，则越重要。改进后的X定义如下:
,fblockjpageib 如果 属于 ，，,PjiX, ,ij
0 否则,,
其中f函数给page i中的每一个block j赋予一个重要度权值。函数值越大，则block越重要。在BLPR的实现中函数f的定义如下:
page pblock b中的大小
fb,,，，P block b的中心点到页面中心点的距离
其中β为正规化因子，使得对每个page，fp(b)的总和为1。即
f1b,，，,P
,bp
fp(b)可以理解为是用户在浏览page p的时候，关注block b的可能性。 2.3.1.3 Page Graph
传统的PageRank算法中Page Graph的权值矩阵计算十分简单，如果从page i到page j有链接的话，则W(i,j)为1，反之为0。然而在BLPR算法中，Page GraphP
需要体现出不同的语义块的重要程度的不同。也就是说，当用户点击页面中的超链接时，更偏好选择重要的语义块中的URL。所以在BLPR中，W的定义为: P
WbbP,～,,,,～,,fZ,, ，，，，，，,P, b,,
WXZ,即。 P
W(α, β)可以理解为是从page α 开始，以page α中包含的各语义块为媒介，P
9
跳转到page β的概率。
2.3.1.4 Block Graph
W的定义为: B
WBa,bZa,Xb, a,b,,,～,，，，，，，B
WZX,即。 B
W(a,b)可以理解为用户从block a开始，以包含block b的page β为媒介，B
跳转到block b的概率。
2.3.2 Block Level PageRank
Block Level PageRank跟PageRank区别的实质在于，PageRank算法基于原始的只有1和0的Page Graph，而BLPR算法基于上面提到的G。BLPRP算法的数学计算公式如下:
,,,,
T ，,，,,,UMpp(1))
其中p为结果向量，共n维，每一维代表一个网页的PageRank值。ε
-ε的概率，用户在当前页面中随机选择一个超链接，跳转为适配参数，以1
到该链接指向的页面;以ε的概率，用户从所有网页中随机选择一个URL并跳转。所以U为n×n的转换矩阵，它满足对所有的i，j，U = 1/n。而Mij也是n×n的转换矩阵，它是由上面提到的W权值矩阵对每一行做归一化，P
令每一行的权值之和为1得到的。p向量的值以马尔科夫链的形式循环计算下去，直到算法收敛。
Block Level PageRank比单纯的PageRank包含了更多的语义信息。因为它的计算基于网页中各语义块的重要程度，噪音块、广告块中的超链接指向的网页的重要性显然不如导航块、正文块中的超链接所指向的网页，所以前者会被分配到较少的PageRank值，而后者则被分配到较多的PageRank值。也就是说，网页中的无关信息区域在PageRank的计算过程中起的作用相对较小，所以BLPR的效果要优于单纯的PageRank。
10
第 3 章 天网搜索引擎Quark模块
搜索引擎系统一般包括网页的抓取、预处理、存储、索引、检索等几个部分，其中预处理部分的作用是分析、处理原始网页数据如去除网页噪音，消除重复网页，计算PageRank，中文切词等等，并为后继模块提供统一的数据访问接口，规范数据管理，避免重复计算。同时在天网搜索引擎平台中，基于功能扩展和实验室内部其他相关研究的需要，必须将对原始网页的处理部分单独出来，从而方便模块复用，统一代码管理，减少重复劳动。
在天网搜索引擎平台的搭建过程中，也包括了抓取、存储、分析(预处理)、索引、检索等模块，其中的分析模块接受成批量原始网页的输入，然后对每个网页调用Quark模块，进行网页分块、信息提取等工作，最后将处理后的数据存成TwDocView格式，再提供给下游模块。我的毕业设计的主要工作，就是围绕Quark模块而展开。
从上面的介绍中可以看出，天网搜索引擎Quark模块有两个比较重要的特点:
1、可扩展性。
因为搜索引擎是一个比较庞大的系统，并且一直在不停的有新算法，新需求
的加入，所以对数据的要求也会一直变化。而基于对原始网页数据集中处理
的原则，为了应对下游模块可能提取的新的数据访问需求，Quark模块必须
具备良好的可扩展性，并且提供尽量多的各种类型的数据访问接口。同时由
于实验室人员的不固定性，代码的维护十分重要。我自己在刚开始阅读旧有
的天网搜索引擎相关代码的时候，就常有十分难懂的感觉，无法复用已有代
码，只好自己重新编写。而正由于Quark模块的可扩展性要求，所以它的代
码的可阅读性也十分重要，在编写的过程中，我尽量注意了这一点，遵守了
我们统一的代码规范。
2、独立性。
在我们实验室内部，除了搜索引擎之外，还有Web数据挖掘，Map-reduce
应用等相关工作也可能需要使用对单个网页的处理和数据提取程序。因此
Quark模块必须能独立于搜索引擎代码之外单独编译运行，并且方便他人调
用这部分代码。
11
基于上述两个特点，我初步实现了Quark模块。该模块的类结构图如下:
1、图中右下及中间蓝色的部分为Quark模块的核心功能类，包括QuarkTree、
QuarkElement、QuarkRecognizer、QuarkAnalyzer等四个类。
QuarkTree类的作用有两个，一个是以原始网页为输入，建立Html的
Dom Tree;另一个是存储分好的网页块(在我们的系统中，每一个网页
块就叫做一个Quark)并记录Quark与Quark之间的组织架构。
QuarkElement类指代一个Quark,即每个Quark自身就是一个
QuarkElement类的对象。
QuarkRecognizer类肩负网页分块的重任，从网页中识别出所有语义块。
它依赖于前面的两个类。
QuarkAnalyzer类依赖于QuarkRecognizer类，它在分好的块的基础上，
判断各个块的类型，提取正文信息。这个类是整个Quark模块最核心的
类，目前功能只是初步实现，还有很大的改进空间，将来也可以根据功
能将其分割成多个类。
12
2、中上部绿色的部分为Quark模块的评测和演示类，包括QuarkEvaluation
和QuarkHtmlBuilder两个类。
QuarkEvaluation类是评测类，用来评测Quark核心类的实现效果。当
前实现的是对网页正文信息提取的评测，评测需要接受人工标记的网页
或网页集为输入。评测算法的细节见后文。
QuarkHtmlBuilder类是演示类，用来查看Quark模块各步骤的实现效果。
目前可以查看网页分块的效果，也可以查看主题信息提取的效果。
3、最上面黄色的部分为Quark模块的应用类，包括QuarkRank、QuarkDuplicate、QuarkClassification等，它们都是利用分好的网页块实现的一些算法，比如基于Quark的PageRank算法，基于Quark的网页消重算法，以及基于Quark的网页分类算法。
4、左下方灰色的部分为Quark模块依赖的外部类接口，包括中文切词类ChineseTokenizer，以及图中没有的编码转换类CodeConvert等等。
5、中下部红色的部分为Quark模块直接的下游模块，包括TwDocView类和TwMd5类。
3.1 网页分块算法
算法主体在QuarkRecognizer类中。参见在第二章相关研究里提到的，除了基于视觉的算法之外，大部分基于语义的算法都是利用html标签及其包含的文字信息的特性来给网页分块的。并且由于大多数论文的着重点在于分块后的内容提取上，所以对分块算法本身着墨不多。综合各篇论文里提到的分块方法，我设计实现了QuarkRecognizer算法。
这一算法首先的一大特点就是实用性强。所谓实用性强是指适合在实际系统中使用，效率高，定义完整。我详细分析了W3C制定的HTML4.01格式规范，将所有规范的Html标签根据QuarkRecognizer算法的需要分类，完整地列出了所有对网页分块起重要作用的标签，而不是像所有已有论文那样仅仅象征性地列举出几个html标签。分类后的详细html标签清单如下:
13
1、超级标签(Super Tag，简称为S型标签):
这种标签可以被直接认定是一个网页块的根标签，在算法过程中一旦遇到这
种标签，就可以直接将其加入网页块池。包括:
"HEAD", "SCRIPT", "STYLE", "OBJECT", "FIELDSET", "FRAMESET", "IFRAME"
2、大标签(Big Tag，简称为B型标签):
这种标签通常都代表一个网页块，只不过有时其内部内容过少，需要跟其他
节点合并成一个网页块，或者在特殊情况下其内部没有可见字符。所以在算
法过程中，遇到这种标签，就判断其单独作为一个网页块的条件是否已经成
熟，如成熟，则将其加入网页块池。包括:
"DIV", "TD", "TABLE", "FORM", "FIELDSET", "CENTER", "NOFRAMES", "NOSCRIPT", "PRE", "BODY", "HTML"
这里需要注意的是像BODY，HTML两个标签也作为B型标签，原因是这
样可以防止分块之后网页内部文字信息的遗漏，因为最终即使有遗漏，也会
至少包含在HTML这个最后把关的门神标签手中。
、排版标签(Layout Tag，简称为L型标签): 3
这种标签能影响到网页的显示效果，改变文字布局。如果一颗html子树中
包含多个L型标签，则该子树单独成块的可能性增加。包括:
"P", "UL", "OL", "DL", "DIR", "LI", "DT", "BLOCKQUOTE", "ADDRESS", "BR", "HR", "COL", "COLGROUP", "IMG", "MENU", "SELECT"
4、显示标签(Display Tag，简称为D型标签):
这种标签数量最多，都是对文字的显示方式做微幅的调整，如改变字体、颜
色、粗细等等。由于它们的存在与否不改变网页布局，所以不影响网页分块。
包括:
"A", "ABBR", "ACRONYM", "AREA", "B", "BASE", "BASEFONT", "BDO", BIG", "BUTTON", "CAPTION", "CITE", "CODE", "DD", "DEL", "DFN", "EM", "FONT", "H1", "H2", "H3", "H4", "H5", "H6", "I", "INS", "KBD", "LABLE", "SMALL", "STRIKE", "STRONG", "SUB", "SUP", "Q", "S", "SAMP", "SPAN", "THEAD", "TFOOT", "TEXTAREA", "U", "TT", "VAR", "O:SMARTTAGTYPE"
14
5、附属标签(Affiliated Tag，简称为A型标签):
这种标签从属与上述四种标签的某一种，同时有些也出现在了前面四种里面。由于它们一般不单独出现，对网页布局的影响体现在了其属主标签中，所以
在QuarkRecognizer算法中也不予考虑。包括:
"FRAME", "INPUT", "ISINDEX", "LEGEND", "LINK", "MAP", "META",
"OPTION", "OPTGROUP", "PARAM", "TD", "TH", "TR", "TBODY", "TITLE"
6、定制标签(Customized Tag，简称为C型标签):
因为不同的应用中，对网页分块会有些不同的要求。比如我们实验室的WebDigest小组在进行新闻网页的数据挖掘的工作中，需要使用到网页分块，但是他们特别需要提取该新闻网页的发布日期和时间，而这部分内容通常是在新闻标题与新闻正文之间的一小行文字，正常的网页分块程序并不会将其单独提取成一个网页块。所以我添加了定制标签，由用户指定，它可以是普通的标签如“TITLE”等，也可以是正则表达式，凡是其内部文字满足该正则表达式的S型、B型和L型标签，都将被单独提取为网页块。例如:
"H1", "H2", "TITLE"
在明确了各html标签的类别之后，利用DomTree中各标签节点的类别信息
和内部文字长度，以及其子标签节点的类别信息，对DomTree自底向上遍历，
在遍历的过程中不断判断出新的网页块，并加入网页块池中，当遍历到最上部的
html根节点时，算法结束，网页分块完毕。QuarkRecognizer算法的核心伪码如
下:
_________________________________________________________________ ALGORITHM QuarkRecognizer (DomTree tree，TagList CType) INPUT :
某单个网页构建的DomTree，定制标签(C型)节点列表
BEGIN
1 用DomTree的叶子节点，也就是文字节点建立一个当前节点队列，开始自底向上遍历。
2 取当前节点队列的第一个节点。
3 如果遇到S型节点，则立即将此节点加入网页块池。
4 如果遇到C型节点，则立即将此节点加入网页块池。
5 如果遇到B型节点，则判断该节点内部的文字长度是否已超过阈值，或
15
者该节点内部的L型节点比例是否超过阈值，如果满足上述两个条件之
一，则将此节点加入网页块池;否则将其内部文字长度信息和自身信息向
父节点传递，然后将父节点加入当前节点队列，回到2。
6 如果遇到L型节点，则将其内部文字长度信息和其自身信息向父节点传
递，然后将父节点加入当前节点队列，回到2。
7 如果遇到D型或A型节点，则将其内部文字长度信息向父节点传递，然
后将父节点加入当前节点队列，回到2。
8 当前节点队列为空时，遍历结束，算法终止。
END
_________________________________________________________________
网页块池中的网页块是以QuarkElement的格式存储，而QuarkElement类中包括原来的html子树的DomTree结构和其他相关信息，同时在上述遍历的过程中，即使有的网页块从html结构上来说包含在更高层的网页块之下，但在QuarkElement中也消除了包含关系，所有网页块都互相独立，互不包含。
3.2 网页主题内容提取
算法主体在QuarkAnalyzer类中。采用了基于规则和基于Bayes的语义分析相交的方法，也就是分别用基于文本相似度的方法和基于Bayes的方法判断每个网页块的类型(是不是主题块)，然后对它们求交集，只有两个方法共同认定的主题内容块才能最终被认定。
QuarkAnalyzer算法的核心伪码如下:
_________________________________________________________________
第一步，基于文本相似度的方法:
1、首先，把所有网页块中，文本长度最大的那个网页块判定为主题内容块。
2、然后用其余网页块逐个与最大的网页块比较文本相似度。文本相似度的
计算如下:
2.1 将两个网页块分别切词，去除停用词后，存储成token流。
2.2 对两个token流分别排序。
2.3 对排序后的两个token流计算token的重复数。
2.4 用token的重复数除以较小的token流中的token个数，得到两个网
页块的文本相似度。
3、若文本相似度大于一个阈值，则该网页块也判定为主题内容块。
16
第二步，基于Bayes的方法:
根据下面列出的7项先验概率和该网页块相对应的这7项特性的(0，1)值，利用Bayes概率的计算公式，计算出每个网页块是不是主题内容块的后验概率。若该后验概率大于0.5，则判定该网页块为主题内容块，否则反之。
第三步，求交。
两个方法共同判定的主题内容块即为最后认定的主题内容块。 _________________________________________________________________ 其中Bayes方法的各先验概率事先用手工标记的样本网页计算得到，结果如
下:
在该网页块为主题内容块的条件下，
# 该块中包含定制标签的概率
p1_costomizedTag = 0.29;
# 该块中包含常见噪音词并且文本长度小于100的概率
p1_noise = 0.04;
# 该块中每10个字符中的标点符号数大于0.3的概率
p1_punctuationScale = 0.85;
# 该块中标点符号总数大于4的概率
p1_punctuation = 0.77
# 该块中非锚接文本的长度大于200的概率
p1_size = 0.84
# 该块中链接数量大于20的概率
p1_linkNum = 0.10;
# 该块中锚接文本和非锚接文本的长度之比大于0.3
p1_scale = 0.08;
在该网页块为非主题内容块的条件下，
# 该块中包含定制标签的概率
p2_costomizedTag = 0.01;
# 该块中包含常见噪音词并且文本长度小于100的概率
p1_noise = 0.45;
# 该块中每10个字符中的标点符号数大于0.3的概率
p2_punctuationScale = 0.25;
# 该块中标点符号总数大于4的概率
p2_punctuation = 0.34
# 该块中非锚接文本的长度大于200的概率
17
p2_size = 0.06
# 该块中链接数量大于20的概率
p2_linkNum = 0.71;
# 该块中锚接文本和非锚接文本的长度之比大于0.3
p2_scale = 0.85;
网页块为主题内容块的概率:
p_isContent = 0.16;
网页块为非主题内容块的概率:
p_isNoise = 1 - p_isContent;
3.3 算法效果演示
为了检验上述算法的效果，除了下一章会提到的评测程序外，还可以用QuarkHtmlBuilder类所编写的演示程序以及自搭的Apache服务器上的python脚本来查看网页分块后和主题信息提取后的效果。限于篇幅，这里就不再详细介绍算法的细节，但是附有几张对照图片，以利说明。
第一幅图:
这是用python脚本写的一个在浏览器上查看网页主题内容提取效果的demo，可以选择用PageModel的算法(即Quark模块)，也可以选择用SiteModel的算法，点击submit按钮，就可以出现手工标记的主题内容，和程序判断的主题内容的对比画面。由于时间关系，该Demo比较粗糙，没有过多修饰。Submit后的效果图见后面的第五幅图。
18
第一幅图:这是从新浪网上保存的一个新闻网页。显然，其主题内容信息块应该是屏幕中左部的大块文字内容。在处理这种类型的新闻网页时，算法的效率很高，但事实上，Quark模块还可以处理更复杂的网页类型。
19
第二幅图:这是网页分块之后的示意图。从图中可以看出，红色、绿色、紫色的网页块间杂排列，就像地图一样，每一种颜色表示一个被识别出的网页块。图中没有颜色，依旧是蓝色的链接色的部分是新浪网动态生成的内容，在html源代码中并不存在，所以没有被标上字体颜色。
20
第三幅图:这是网页正文提取之后的示意图。图中红色的部分为QuarkAnalyzer识别的正文内容，绿色部分为其识别的相关链接，其余紫色部分为噪音内容。从图中可以看出，就这个网页而言，网页主题内容的提取基本成功了。
21
第五幅图:这是第一幅图所示Demo的结果界面截图，可见，图片上方是手工标注的文字内容，共720个字符。图片下方是程序生成的文字内容，共628个字符。两部分内容大致相等，说明网页主题内容提取成功。
22
第 4 章 SEWM2008中文Web信息检索评测
4.1 评测任务介绍
SEWM中文Web信息检索评测[6]是由北京大学网络实验室主办的中文Web检索评测项目，自2004年起，在SEWM会议中已连续举办了五届，今年(2008年)是第五届。其目标在于为中文信息检索领域的研究人员提供一个
标准
excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载
的评测平台，希望在国内外各个研究小组的共同参与下建立并完善以中文为主的网页测试集CWT(Chinese Web Test collection)，解决支持中文WEB研究的基础设施建设和应用中的基本方法与关键技术，一起推动中文Web信息检索技术的发展。
SEWM2008中文Web信息检索评测有三个任务: 主题型网页发现和网页内容信息块发现，非网页数字资源分类和垃圾邮件过滤，其中前两个任务主要由何靖师兄设计，由我处理各参赛队伍提交的数据并给出评测结果。本届评测采用的数据集是CWT70th。文档集数据格式参见[7]。 由于本次评测任务的设计和上文提到的天网Quark模块关系密切，评测所使用的程序就是天网Quark模块中QuarkEvaluation类的python版本的代码，同时天网Quark模块的一个稍早期版本也参加了第二个任务关于网页主题内容的评测，所以也可以作为天网Quark模块的一个实验结果，检验第三章提到的算法的效率。
4.1.1 主题型网页发现任务
主题型网页是指通过文字描述了一件或多件事物，具有一定主题的网页。如一张具体的新闻网页就是典型的主题型网页。
下面是对主题型网页的一个补充定义:
1、仅由图片，flash，网络视频等构成主题块的网页，除非亦包括独立成段
的文字性描述信息，否则不属于主题型网页。
2、某些导航型网页，如同类软件下载网页中，虽然对每个链接都使用了适
量文字来介绍，从而文字比例比较高，但也应该算作非主题型网页。
3、错误网页，空网页，垃圾网页，Spam网页等属于非主题型网页。
4、论坛、博客网页属于主题型网页，但没有主贴，只包括无意义回复语句
的网页属于非主题型网页。
23
任务评测根据准确度、召回率和Macro-F1三个指标，它们的定义如下:
主题型网页判断正确的个数 MacroPrecision ,,实际的主题型网页的总数目
主题型网页判断正确的个数 MacroRecall ,,实际的主题型网页的总数目
2 * -* -MacroPrecision MacroRecallMacroF1 ,,MacroPrecisionMacroRecall,，,
4.1.2 网页内容信息发现任务
在一个主题型的网页中， 一般会包括主题内容信息，噪音信息，和相关链
接信息。本项任务的目的在于找出主题型网页中的主题内容信息。 噪音信息定义:
a. 与网页主旨内容不相关的信息
b. 由网站提供的内容模板信息
c. 广告信息
d. 脚本程序信息
相关链接定义:
指向与本网页相关网页的链接，如新闻网页下方的相关新闻链接。
补充定义:
1、新闻网页的内容信息应包括出现在页面里的标题，时间，通讯社，记者
名等信息。
2、一个网页中的内容信息不一定只有一块，可能有多块，甚至可能是零散
分布的文字段。
3、无意义的论坛回帖(如”顶”等)不属于内容信息，但有一定内容的论坛
回帖属于内容信息。
4、相关链接不算内容信息。
任务评测根据准确度、召回率和Macro-F1三个指标，它们的定义如下:
在某个网页中正确提取的内容信息长度Macro-Precision , 在某个网页中提取的内容信息总长度
在某个网页中正确提取的内容信息长度MacroRecall ,, 在某个网页中人工标注的内容信息总长度
24
2 * -* -MacroPrecision MacroRecall MacroF1 ,, MacroPrecisionMacroRecall,，,
4.2 评测格式
评测要求参加评测单位以一定的格式提交，每个评测任务接受参加者的一到
二组检索结果。具体要求如下:
主题型网页发现:提交一个纯文本文件，包含所有找到的主题网页，每个网
页的编号占一行。如:
CWTquark080103-00000010
CWTquark080103-00000019
网页内信息块发现:只需要把正文内容找出来即可， 一个网页可能包括多
个彼此不连续的正文内容， 正文内容可以包括包含内容标签， 也可以不包含内
容标签。
结果的格式如下:
Document-Number Start-Position Length三元组
其中Document-Number是网页的编号，Start-Position是某段正文内容在原网
页文档中的开始位置(网页的起始位置从0开始计算)， Length是该段正文内容
的长度。 一个网页可以有多个正文内容段， 因此可以有类似下面的情况:
CWTquark080103-00000001 200 300 // 该网页中的第一段正文内容
CWTquark080103-00000001 450 500 // 该网页中的第二段正文内容
4.3 评测结果
本次评测任务最终共有七支参赛队伍，提交了12组结果。
1、大连理工大学信息检索实验室 DLUT1 DLUT2 2、四川大学计算机学院数据库与知识工程研究所 SCU1 SCU2 3、华南理工大学广东省计算机网络重点实验室一队 SCUT1 SCUT2 4、华南理工大学广东省计算机网络重点实验室二队 SCUT3 SCUT4 5、山东大学信息检索实验室 SDU1 SDU2 6、人民大学信息学院 RUC 7、北京大学网络实验室 PKU
25
4.3.1 主题型网页发现任务评测结果
在数据集CWT70th中的所有71502个网页中，有71281个不重复URL。
在这71281个网页中，随机抽取了300个URL，人工判断其类型。为了消除对主题型网页认定上的分歧，在300个URL中去除了部分混合型以及不易判别类型的网页，共得到227个确定类型的网页，其中包括138个主题型网页，89个非主题型网页，主题型网页数目/非主题型网页数目 = 1.5505618，经验证，大致符合原网页集中的类型分布。利用该227个网页，评测各组参赛数据。
虽然我们的样本数偏少，但由于样本中的类型分布大致符合原网页集中的类型分布，所以评测结果基本反映了各组的实际分类质量，只不过没有形成明显差距。华南理工一队和大连理工的分类质量相对最佳，而人民大学和山东大学提交的三个结果，分别将71502个网页中的66498、56509、55111个判断为了主题型网页，过高地估计了主题型网页的比例，从而大大降低了精度，但值得一提的是，山东大学提交的结果2获得了最高的召回率。
评测结果如下:
TEAM Macro-PrecisioMacro-Recall Macro-F1
n
DLUT1 0.888888888889 0.869565217391 0.879120879121
DLUT2 0.89552238806 0.869565217391 0.882352941176
SCU1 0.846153846154 0.876811594203 0.861209964413
SCU2 0.840277777778 0.876811594203 0.858156028369
SCUT1 0.883211678832 0.876811594203 0.88
SCUT2 0.889705882353 0.876811594203 0.88321167883
2
SCUT3 0.82119205298 0.898550724638 0.858131487889
SCUT4 0.794871794872 0.898550724638 0.843537414966
SDU1 0.78125 0.905797101449 0.838926174497
SDU2 0.774566473988 0.971014492754 0.861736334405
RUC 0.670103092784 0.942028985507 0.78313253012
主题型网页发现任务评测结果较好的队伍是华南理工一队和大连理工，分别代表了网页整体性判断和网页分块判断两种主要的实现方法。
1、网页整体性判断方法
以华南理工一队的方法最为典型，综合使用了启发式规则和分类器方法:
26
第一步先根据主题型网页的重要特征，基于启发式规则判断;
第二步提取更详细的特征信息，用SVM分类;
第三步还基于信息块提取的结果反馈，进一步筛选出主题型网页。
华南理工一队也属于整体性判断方法，但只使用了分类器方法;山东大
学队则只使用了较简单的启发式规则。
2、网页分块判断方法
以大连理工队的方法最为典型，在网页分块的基础上，判断各个网页块的类型。如果一个网页里都是非主题型块，则为非主题网页。若含有主题块，则为主题型网页。其中判断各个网页块的类型是综合基于规则和基于概率的方法，同时针对本次任务的网页特性做了优化。
而四川大学的方法比较特殊，在网页分块的基础上，使用网页块分布的方差和弯曲度属性区分导航型和主题型网页，不足在于使用规则过少，只使用了网页块的文本大小信息。
3、综合所有队伍提取和使用的特征信息，大致有如下几类:
1、URL相关的特征信息
包括URL中数字的个数、URL的深度以及URL的后缀。
2、链接相关的特征信息
包括链接数、链接文字与非链接文字比、链接标签占网页的所有标签的
比率、链接文本内容占全文内容的比率、非链接文字的长度等等。
3、其他特征信息
包括网页文本内容中标点符号的个数、正文的文字长度、特殊标签(如
,
,
)是否出现，以及包含特殊关键词与否。
下图是各组结果的Macro-F1值大小的直观显示:
27
4.3.2 网页内容信息发现任务评测结果
我们事先人工标记了71281个网页中的303个主题型网页，标记方法为给html的tag标签添加quark属性，如:
正文内容
相关链接
噪音内容
其中标记为quark=”content”的就是内容信息块;
标记为quark=”rel_link”的是相关链接;
而标记为quark=”noise”的则是噪音内容。
因为各组提交的结果只针对第一项任务中发现的主题型网页找出内容信息块，而我们标记的303个网页并没有被各组一致判定为主题型网页，只有其中的104个网页被各组一致判定为主题型并提取了内容信息块(其中华南理工二队没有根据他们第一项任务里找出的所有主题型网页来完成第二项任务，一定程度上影响了各组的重合度)。所以本任务的评测就依据这104个标记过的主题型网页，样本量偏少。
根据各组提交的格式为(doc_no start_pos length)的结果文件，为各组产生出对应的104个内容信息块网页，然后逐一比较标记过的网页与各组提取的网
28
页。
从评测结果可以看出，大连理工提交的结果1评测成绩十分优异，精度和
F1值超过了90%。鉴于我们标记的样本集中也可能存在少量的误标的情况，其
召回率应该也达到了90%。
评测结果如下:
TEAM Macro-PrecisioMacro-Recall Macro-F1
n
DLUT1 0.948241982858 0.895990483304 0.90711161340
4
DLUT2 0.916974796418 0.78011163593 0.800641946786 SCU1 0.421928878326 0.253235056464 0.286056385361 SCU2 0.421928878326 0.253235056464 0.286056385361 SCUT1 0.555072287002 0.392915434611 0.43368650087 SCUT2 0.555072287002 0.392915434611 0.43368650087 SCUT3 0.679200090711 0.306407428682 0.404795170073 SCUT4 0.659522262145 0.307243313285 0.401949693823 SDU1 0.386879266785 0.408527124722 0.374533440385 SDU2 0.386879266785 0.408527124722 0.374533440385 RUC 0.664387822235 0.382808621572 0.465854595858 PKU 0.93288255881 0.77966651466 0.82174136330
6
网页内容信息块发现任务评测结果较好的队伍是大连理工队和我的Quark
模块。同样，各队的实现方法可大致分为网页整体性判断和网页分块判断两种。
1、网页分块判断
其余各队的分块方法都比较简单。大连理工提交的两个结果分别采用了以、、 、 四个标签为分块节点，和仅以 标签为分块节点两种方法。后者由于过于简单，实际评测效果不如前者。而山东大学提到根据 ，， ， 等容器标签对网页分块，再根据某种规则对某些网页块进行合并的改进型算法，但不知是否最终实现。
在噪音过滤，网页分块的基础上，大连理工采用了基于规则和基于Bayes的语义分析方法，同时针对本次任务的网页特性做了优化，效果优异。但大连理工的这两种方法有一些重合之处，并且从它提交的结果内容看，对
29
等标签可能做了特殊处理，在他们的工作报告中没有提及。
在网页分块的基础上，山东大学提取文字数最多的网页块作为网页内容信息块，这一方法的缺点是不能处理含有多个内容信息块的网页。
2、网页整体性判断
华南理工一队，二队采用了整体性判断方法。
华南理工一队的方法是由叶子节点开始，向上寻找包含所有有效文本信息的最近节点。其中有效文本信息的判断是依靠每个节点的文本长度。这个方法的局限一是不能处理含有多个内容信息块的网页，而是不能处理所有网页，比如表格型网页需要单独处理。
华南理工二队采用DSE算法，考察了URL相似度对DSE的影响，通过网页间结构比较，并计算锚文本与正文块的比例来提取内容信息块，算法相对比较完善，但也有对不同类型的网页处理时普适性不够的问题。
3、其他特殊方法
四川大学的算法比较特殊，他们认为内容信息块在长度上相对孤立，所以使用了基于偏差的孤立点检测算法，以块的大小作为属性，检测孤立点，得到的孤立点即内容块。这个算法的缺点在于只以内容长度作为衡量标准，特征过少。
下图是各组结果的直观显示:
30
4.4 评测综述
本次评测从设计上和数据上还有很多缺憾:
1、数据集的抓取不够有代表性，集中在几个网站，同种类型网页过多，新闻
类网页也过多，一定程度上降低了内容提取的难度。
2、对主题型网页的定义不够清晰。比如有的新闻网页由一幅大图片和少量文
字构成主题块，在现有的单纯依靠文字的评测机制下倾向于认为不是主题
块，但事实上应该算是主题块，而这种网页也应该算是主题型网页。又比
如很多网页虽然是一个链接型网页，但对其中每个链接用了适量文字来介
绍，这种网页虽然文字比例很高，也应该算是链接型网页。
3、对内容信息块的定义不够清晰。比如论坛或者博客的回帖该不该算作主题
型应该明确规定，以后可以考虑将这种类型的网站单独作为评测项目，比
如分别提取主贴与回帖(提问与解答)的内容。又比如相关链接算不算内
容信息块，在这次评测中是不算的，以后可以考虑将相关链接的提取也列
为评测项目。
4、由于标记样本网页工作量很大，而我们事先准备不够，所以最后用作评测
的样本网页数量较少，从而使得评测结果可能不够准确。而且在评测过程
中发现，已标记的303个网页，由于标记人员工作不够细致，质量不高，
部分存在将噪音内容也标记为主题内容的情况。以后我们应该制作更精良
和更具有代表性的样本网页集。
31
而Quark模块从本次评测中得到的教育是:
1、各队都没有一个详细，可操作性强的网页分块算法，这一点上，Quark
模块做的比较好。
2、在网页主题信息提取方面，大连理工队的方法效果比较明显，所以我从
中吸收了他们的长处，在原有的文本相似度方法的基础上，增加了Bayes
方法，并自己定义和计算了7条先验概率，然后让两个方法的结果求教，
实验数据显示，改进后的天网Quark模块的评测结果大大提高，达到了
大连理工队的水平。
32
第 5 章 网页分块的分布式应用
在前面提到的网页分块算法的基础之上，我尝试了基于网页分块的PageRank算法，与相关研究里提到的BLPR算法不同的是，我的这项工作是在我们实验室自己开发的天网文件系统[8](TFS)和分布式计算平台(Map-Reduce)上实现的。
5.1 QuarkRank
在Map-Reduce上，QuarkRank算法主要需要实现两个类，一个是QuarkRankMapper类，一个是QuarkRankReducer类。同时，200GB的原始网页文件作为输入文件，而输出则是一个列有所有URL的PageRank值的文件，输入与输出文件都存储在天网文件系统中，以最大64MB的数据块的形式存在于整个机群中。
由于QuarkRank是一个多轮迭代，直到收敛的算法，所以也要进行多轮Map-Reduce。所以除了实现Map-Reduce工作类之外，还得自己编写一个主控程序中，控制和调用了多轮Map-Reduce任务，并决定迭代何时终止。下面是主控程序的核心部分伪码:
_________________________________________________________________
ALGORITHM QuarkRank (TwRawPage Cwt200G)
INPUT :
天网原始数据Cwt200G.dat
BEGIN
1、预处理:
将Cwt200G处理成
(URL，初始PageRank值，)
格式，存到input文件中。
2、Mapper:
Mapper的输入格式:
(URL，当前PageRank值，)
Mapper的输出格式有两种:
第一种:(URL，)
33
第二种:
foreach url in 该url的出链列表:
输出(url，value)， 其中value为根据该url所在的Quark的权值而
计算出的当前URL的PageRank的分配值。
3、Reducer:
Reducer的输入格式有两种:
第一种:(URL，) 第二种:
foreach url in 该url的出链列表:
输出(url，value)， 其中value为根据该url所在的Quark的权值而
计算出的当前URL的PageRank的分配值。
Reducer加成得到新一轮的PageRank值。
Reducer的输出格式:
(URL，新一轮的PageRank值，)
4、Writer:将reducer的输出存入output文件中，并替换掉input文件。 5、若满足收敛条件，则迭代终止，否则回到2。
END
_________________________________________________________________
分布式QuarkRank算法与分布式PageRank算法最大的区别就在于决定当前
URL对它的出链的分配值的时候，PageRank是单纯地分配给它的每一个出链
(PageRank/Sum，Sum为出链总数)的PageRank值，而QuarkRank则是分配给
它的每一个出链如下的PageRank值:
PageRankQuarkWeight*i ,网页里的数Quark
QuarkSumQuarkWeight*,jj ,1j
为当前的值，PageRankURLPageRank
为当前出链所属的权值，QuarkWeightURLQuark i i
为里的总数，QuarkSumQuarkURLjj
为的权值QuarkWeightQuark jj
34
显然，所有出链分配得到的PageRank加起来，恰好等于原PageRank值:
网页里的数QuarkPageRankQuarkWeight*i,QuarkSumPageRank*,i网页里的数Quark,i1QuarkSumQuarkWeight*,jj
,j1
在我现在实现的QuarkRank算法里，给Quark(也就是分好的网页块)赋予权值的方法比较简单，就是主题内容信息块给以1.5的权值，而非主题内容信息块给以0.5的权值。事实上，Quark的重要性衡量也是一项专门的工作，微软2004年发表在WWW会议上的论文Learning block importance models for web pages [9]就是一篇关于网页块重要性衡量的文章，可以用在QuarkRank算法中帮助改进Quark的权重赋值方法。
5.2 其他应用
其他应用包括基于分块的网页消重算法QuarkDuplicate。传统的消重算法用原始网页作为消重的输入数据，这样导致只能消去内容完全一样或者内容大致一样的重复网页。而事实上，很多网页都是互相转载，转载网页的特点就是正文部分几乎一样，而其他部分，诸如导航条、网站链接、个人信息等就不一样了，QuarkDuplicate算法就可以利用提取后的网页主题内容作为消重的输入数据，然后再调用传统消重算法，这样在某些需求下，转载网页也可以高效率地去除。
还有基于分块的网页分类，基于分块的网页图片检索，基于分块的网络结构分析等等应用，这些算法暂时我还没有实现，但可以作为我的后继工作，以后继续在此方向努力。
35
第 6 章 总结与展望
6.1 总结
本文提出了一套基于语义的网页分块和主题内容信息提取算法，在天网搜索引擎预处理模块中将其实现，并通过了SEWM2008中文Web信息检索评测项目的检验。在该套算法基础上，还实现了基于Map-Reduce的分布式QuarkRank算法，该算法改进了PageRank算法的效果。
1、基于语义的网页分块。提出了QuarkRecognizer算法，该算法详细剖析了所有符合W3C标准的Html标签的功能特性，将它们分为超级标签、大标签、排版标签、显示标签、附属标签、定制标签等六大类，按类处理，较好地实现了网页分块功能。该算法具有十分强的鲁棒性，能适应各种不常见的Html代码，同时将原先树型架构的网页语义块层次结构转换成为平行架构，各个语义块相互独立开来，方便在此基础上的应用。
2、网页主题内容信息提取。提出了QuarkAnalyzer算法，该算法是对文本相似度和Bayes后验概率估计两种方法的结合。文本相似度算法偏重于语义块内部的文字内容，是从文本的角度衡量一个语义块的重要程度;而Bayes后验概率估计算法提出的7条先验概率都反映的是语义块内部的结构信息，是从结构的角度衡量语义块的重要程度。两个算法分别计算主题内容信息块，然后求交，最后得到的信息块既能反映其文本的重要性，又能反映其内部结构的重要性，防止了单个算法可能导致的偏差，提高了网页主题内容信息提取的精度和召回率。
3、SEWM2008中文Web信息检索评测项目。本文介绍了这次评测项目的题目设计，测试集产生、评测方法和评测结果，检讨了这次评测的不足之处。通过这次评测，Quark算法的效果得到了检验，同时，受大连理工等参赛队伍的思路启发，我改进了Quark算法，提高了效率。
4、QuarkRank算法。QuarkRank算法起源于MSRA的BLPR算法，但后者不是分布式的。QuarkRank算法基于网络实验室的天网文件系统和Map-Reduce计算平台，本文描述了Map环节和Reduce环节的算法步骤。
36
6.2 展望
这篇论文基于我这一段时间以来在网络实验室天网组的工作，现在虽然论文已经告一段落，但工作上仍然有许多遗憾，我还会尽量改进。
1、QuarkRecognizer算法的一大遗憾就是没有利用视觉信息。虽然我们是在Linux平台下，但仍然有可能通过调用Mozilla的开源代码来获取网页中的视觉信息。其次，应该可以尝试用类似于第二章提到的[3]的算法，用机器学习的方法来指导分块。
2、QuarkAnalyzer算法中，文本相似度比较方法可以改进，比如增加IDF权重，或者采用其他更复杂的文本相似度比较方法。而Bayes后验概率密度方法也可以进一步改进效率，比如增加更多的概率项。
3、SEWM评测中，今年的评测存在样本数过少，评测题目设计不够精确等问题，而参赛队伍提交的结果的质量也是参差不齐。希望明年能更详细设计，吸引更多优秀的参赛队伍。今年的评测报告公布之后，也有其他大学未参赛的学生跟我联系和讨论，认为我们的评测是中文Web领域很权威的信息检索评测，这让我感到很惭愧，当初应该更认真地将这次评测做得更好。
4、QuarkRank算法对网络传输的消耗很大，应该探讨有没有更好的Map-Reduce设计
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
可以改善网络传输量。同时应该实现更多基于Quark的相关应用。
37
致谢
在即将要离开北大的时候，心中充满了留恋与感慨。这篇稚嫩的毕业论文主要基于我这一年来在网络实验室天网组的学习和工作内容，这一年对我来说是弥足珍贵的一年，在天网组浓郁而愉悦的学术氛围中，我得以天天向各位老师和师兄师姐们学习，努力获取一点一滴的进步。虽然最后这篇论文里的工作分量并不突出，还有很多需要改进和提高的地方，但却印刻了我这一年的足印。
感谢闫宏飞老师在我的平常学习生活中以及在这篇论文的撰写过程中对我的监督与鼓励。闫老师踏实的治学态度和严谨的工作作风使我受益匪浅，一直指导和规范着我在实验室的学习和工作。
感谢我的班主任彭波老师在学习和生活上给我的一贯帮助。彭老师除了对班级同学尽心尽力，工作中也认真负责，教给了我很多以前没有了解的知识和技术。
感谢天网组里的每一位聪明进取的师兄师姐们。每当我有不懂的问题时候，他们总会不厌其烦地教导我。从他们身上我不仅学到了很多知识，还学到了很多做人做事的道理，感受到了他们刻苦学习的热情，他们是我永远的榜样。在天网组里有温馨有欢笑，有学术有运动，使我度过了无比充实而快乐的一年。
感谢关心我的同学和朋友们。你们不仅让我感受到生活的乐趣，还不断鞭策我反省自己的过错和不足，努力向你们看齐。
感谢北京大学四年来的教育。从我很小的时候起，北京大学就是我唯一梦牵魂绕的地方，能有这四年与北大共呼吸同命运，是我最大的自豪。不论以后我走到哪里，北大都将是我最牵挂的地方。
最后要感谢我的爸爸妈妈，一直毫无保留地支持我的选择，支持我的学业。
38
参考文献
[1] Rupesh R. Mehta, and Amit Madaan, Web Page Sectioning Using Regex,based Template, In Proceedings of World Wide Web conference, 2008.
[2] SandipDebnath, Prasenjit Mitra, Nirmal Pal, and C.Lee Giles, Automatic Identification of Informative Sections of Web-pages, IEEE Transactions on Knowledge and Data Engineering, 2005.
[3] Deepayan Chakrabarti, Ravi Kumar, and Kunal Punera, Page-level Template Detection via Isotonic Smoothing, In Proceedings of World Wide Web conference, 2007.
[4] D. Cai, S. Yu, J.-R. Wen, and W.-Y. Ma, VIPS: a visionbased page segmentation algorithm, Microsoft Technical Report, MSR-TR-2003-79, 2003.
] D. Cai, X-F. He, J.-R. Wen, and W.-Y. Ma, Block-level Link [5
Analysis, In Proceedings of the ACM-SIGIR, 2004.
[6] 中文Web信息检索论坛:
[7] 网页信息存储的天网格式
[8] Zhifeng Yang, Qichen Tu, Kai Fan, Lei Zhu, Rishan Chen, Bo Peng, Performance Gain with Variable Chunk Size in GFS-like File Systems, Journal of Computational Information Systems4:3(2008) 1077-1084
[9] Ruihua Song, Haifeng Liu, Ji-Rong Wen, Wei-Ying Ma, Learning Block Importance Models for Web Pages, In Proceedings of World Wide Web conference, 2004.
39
本文档为【【计算机专业毕业论文】大规模网页模块识别与信息提取 系统设计与实现.doc】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
格式：doc
大小：324KB
软件：Word
页数：0
分类：
上传时间：2018-12-14
浏览量：8
| |
浙公网安备 33021202002483