《大规模网页模块识别与信息提取系统设计与实现毕业论文.doc》由会员分享，可在线阅读，更多相关《大规模网页模块识别与信息提取系统设计与实现毕业论文.doc（42页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、本 科 生 毕 业 论 文题目： (中文)大规模网页模块识别与信息提取系统设计与实现(英文 )Design and Implementation of Large Scale Web Template Detection and Information Extraction System姓名： 学号： 院系： 专业： 指导教师： 00448174 朱磊 本科毕业论文摘要本文提出了一套基于语义的网页分块和主题内容信息提取算法，在天网搜索 引擎预处理模块中将其实现，并且在 SEWM 2008 会议中，以这套算法为框架， 组织了主题型网页识别和网页主题内容信息块提取两个中文 Web 信息检索评测 项
2、目。在这套算法的基础上，基于天网文件系统与 Map-Reduce 计算平台，实现 了分布式的网页块级别 QuarkRank 算法，改进了 PageRank 算法的效果。实际检 验表明，该套算法具有很好的适应性与可扩展性，并达到了很高的精度和召回率。关键词：网页分块 信息提取 评测 Map-Reduce PageRankiiAbstractThis paper presents a semantic web-page blocking and information extraction of thematic content algorithm, which is achieved in th
3、e pretreatment 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 TianW
4、ang 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 and recall
5、.Keywords:Web-Page Blocking, Information Extraction, Evaluation, Map-Reduce, PageRank目录第 1 章序言3第 2 章相关研究工作52.1基于语义的网页信息提取算法52.2基于视觉的网页分块算法62.3 Block Level PageRank 算法82.3.1 Block Level Web Graph82.3.2 Page Graph92.3.3 Block Graph92.3.4 Block Level PageRank10第 3 章天网搜索引擎 Quark 模块113.1网页分块算法133.2网页主题内容
6、提取163.3算法效果演示18第 4 章SEWM2008 中文 Web 信息检索评测234.1评测任务介绍234.1.1 主题型网页发现任务234.1.2 网页内容信息发现任务244.2评测格式254.3评测结果254.3.1 主题型网页发现任务评测结果264.3.2 网页内容信息发现任务评测结果284.4评测综述31第 5 章网页分块的分布式应用325.1QuarkRank325.2其他应用34第 6 章总结与展望356.1总结356.2展望35参考文献37致谢38第 1 章序言信息时代，非 Web 无以制胜。互联网的高速发展，改变了我们的生活方式， 打破了我们的时空界限，重塑着我们的社会形
7、态。经济、政治、学习、工作、生 活、娱乐等等各个层面都在 Web 网络中激荡起伏，深刻地影响着人类的未来。 而 Web 网络的灵魂，就是流动在其中的无穷无尽的信息。Web2.0 的意义就在于 网络内容的提供方从商人和专业人员转变为网络上的每一个普通用户，从而几何 级数地增长了 Web 的信息量。然而信息量的增大，随着而来的就是存储成本的 增大和信息提取难度的增大，如何有效的获取和整合 Web 信息成为大家面对的 共同课题。传统意义上，整个 Web 网络就是由无数的 Web 页面而构成，它们是网络信 息存储和提取的基本单位，获取了这些 Web 页面就相当于获取了 Web 信息内容。 但是把整个页
8、面作为最基本的信息处理单位有一些不合理之处。首先是因为 Web 页面中信息量的分布非常不均匀，有主题内容，也有广告，导航栏，版权信息， 装饰信息，以及在大量网页中重复出现的部分，它们自身的信息含量千差万别。 当网页浏览者刚打开一个新页面的时候，如果之前没有浏览过类似页面，就会目 不暇接，眼花缭乱，有无所适从的感觉，必须仔细探寻一番才能定位到这个页面 的要害；如果之前浏览过类似页面，比如常上这个网站，那么通常浏览者就已经 训练出一种直觉或者说是条件反射，他会立刻定位到他所想要浏览的部分，从而 忽略掉页面中的其他部分。其次还因为现在很多 Web 页面是动态更新的，比如博客页面或者论坛讨论 帖，它们
9、的更新是以一个一个网页块的形式进行的，更新时页面上大部分内容并 没有变化，如果仍然以整个页面为处理单位，则不可避免地存在效率损失和定义 的混淆。这些情况促使我们反思以整个页面为基本信息单元的做法不仅不尽合 理，一定程度上甚至已经损害了网络浏览者的用户体验，妨碍了网络信息提取的 效率。解决这个问题的办法其实有两种思路。第一种就是从信息的产生方那儿就不 再提供网页式的信息，而改为直接提供网页块或者文字段式的信息。最常见的例 子就是 RSS（聚合内容，Really Simple Syndication），博客或者新闻的提供方省 去了浏览者访问网站查看更新的麻烦，直接将精简后的网页块或者文字段发送给
10、RSS 的订阅方。第二种则更为普适，就是细分网页中的信息单元，也就是给网页 分块，在网页分块的基础上存储和提取 Web 页面的语义信息。19基于网页分块的 Web 页面的语义信息提取在很多方面都有应用。比如，在 常规搜索引擎中，可以以网页分块为基础去除网页中的噪音信息，识别出网页中 的主题内容信息块，从而用提取出的主题内容信息来构建对这个页面的描述，完 成网页分类、网页消重等应用。还可以凭此改进搜索引擎的索引模块和检索模块 的效率，比如改进 TF/IDF 和 PageRank 的算法（详见第五章）。Web 页面的语义分块另外一个重要用途在于移动终端访问互联网，比如手机 和 IPod 等。因为目
11、前大部分的 Web 页面都是针对 PC 机设计的，要求有相对较 大的屏幕。而移动设备通常屏幕较小，计算能力有限，无法直接访问这些页面。 为了解决这个问题，要么是内容提供商手工编辑专门适用于移动设备的页面，要 么就只有对页面进行语义分割，并在分割后的页面中选择信息量最高的语义块。除此之外，Web 页面的语义分块还可能对常规搜索引擎之外的其他信息检索 系统有帮助。比如类似于新闻人物追踪和历史新闻检索等应用，出于节约存储空 间，提高检索精度，方便更新等目的，可以直接存储和操作网页中的主题内容语 义块，而舍弃网页中其他与系统需求无关的语义块。在这篇论文中，第二章介绍了本文的相关研究工作，包括常见的网页
12、分块和 信息提取算法、基于视觉的网页分块算法，以及网页分块的一个应用 Block Level PageRank 算法；第三章介绍了我实现的网页分块和主题信息提取算法Quark 算法；第四章介绍了 Quark 算法在 SEWM2008 中文 Web 信息检索评测项目中的 实际检验；第五章介绍了在 Quark 算法基础上实现的一个分布式 QuarkRank 程 序。第六章是对本文的总结和工作展望。第 2 章相关研究工作2.1基于语义的网页信息提取算法由于对 Web 页面有效分块之后可以极大地方便内容提取、数据挖掘、Web 结构分析等各项 Web 信息检索领域的相关工作，所以早有很多研究人员前赴后
13、继，就此展开了很多工作。其中，基于语义信息对网页分块是最简便，也最基础 的一种方法。所谓语义信息，通常包括网页中包含的 HTML 标签信息，HTML DOM 树的结构信息，文字内容信息，超链接信息，以及其他通过统计或学习而 得到的全局信息等等，也可以理解成为除了网页中的视觉信息之外的所有可以得 到的信息。通常基于语义的网页分块算法是和后续的网页主题内容提取结合在一起的， 也就是在网页分块的过程中，同时完成了主题内容提取的工作，并且主要的注意 点是在主题内容提取上，因此分块算法就比较简单，甚至不显式地分块，在此我 们统称它们为网页信息提取算法。总的来说，网页信息提取算法可以分为两类， 一类属于网
14、站级别（Site-Level），一类属于网页级别（Page-Level），当然也有将 两类方法结合使用的算法。Site-Level 的算法顾名思义，就是分析一个网站或者网页集内部的所有网页， 从中提取反复出现的模式，而一般来说，在多个网页里重复出现的模式（可理解 为 Dom-Tree 子树）就是导航栏、广告等噪音信息了，单个网页中减去这些信息， 剩下的就是主题信息内容。关于 Site-Level 的研究一直在继续，WWW2008 上就 有一篇名为 Web page sectioning using regex-based template1的论文使用正则表 达式来提取重复模式，从而更适应网页间
15、的细微变化，增加了 Site-Level 的召回 率。Page-Level 的算法在处理大型网站的网页时效率常常不如 Site-Level，但优 势在于灵活，不受网页类型限制。它只利用单个页面内部的信息，当然也可能会 用到一些全局信息。宾夕法尼亚州立大学 2005 年的论文2就是其中的典型。这 篇论文提出简化块与块之间的层次结构，直接提取一些原子块（Atomic Block）， 诸如以 list, table, link, object, frame, form 等为根节点的 html 子树，来完成分块工 作。这一方法虽然简单而易于实现，但依赖于事先给出的原子块列表，同时忽略 了原子块之间的嵌
16、套链接问题。在分块之后，它也只是简单计算了文字长度等几 个变量来决定主题信息块。合并 Site-Level 和 Page-Level 的方法也一直有人尝试。WWW2007 的论文 Page-level template detection via isotonic smoothing3先利用一个 Site-Level 噪音 模板提取器来构建训练集，然后对所有页面构建 DOM 树，为各节点提取分类特 征，比如各节点的文本向量，各节点中链接的平均字数，各节点中链接文字所占 比例等，最后利用以上训练集对测试集中每一个 DOM 树节点打分，经过等压平 滑之后，判定每个 DOM 树节点的类型。所以它是典
17、型的先 Site-Level，后 Page-Level 的方法。2.2基于视觉的网页分块算法基于语义的网页分块算法具有一些无法克服的先天性局限。首先，HTML 语言版本众多，一直没有有效统一，而且其语法规范很松散，一些不符合 HTML 规则的网页也能被完全识别，所以网页编写者在制作网页时相对随意，导致 Web 上的很多网页都没有完全遵循 W3C 规范；其次，IE、Firefox 等浏览器各自为政， 对 HTML 标签的识别不尽相同，IE 甚至还特别为 Office 软件设计了特别的 html 标签以辅助显示，这些都增加了基于规则分块的复杂性。在实际编程中，就必须 得借助一些 HTML 规范工具
18、如 tidy 等来修正 DOM 树结构的错误，但个别中文 网页仍然存在无法修正的情况。而且 DOM 树最早引入是为了在浏览器中进行布 局显示而不是进行 Web 页面的语义结构描述。比如，即使 DOM 树中两个结点 具有同一个父结点，那么这两个结点在语义上也不一定就是有联系的。反之，两 个在语义上有关系的结点却可能分布在 DOM 树的不同之处。因此仅仅通过分析 DOM 树并不能完全获取 Web 页面的语义信息，所以依赖于 DOM 树的启发式规 则算法存在先天不足。而基于视觉的网页分块算法就弥补了这个不足。它的原理来自于用户的实际 观察体验，即用户并不关心 Web 页面的内部结构，而是使用一些视觉
19、因素，比 如背景颜色、字体颜色和大小、边框、逻辑块和逻辑块之间的间距等等来识别出 页面中的语义块。因此如果充分的使用 Web 页面的视觉信息，模拟人眼识别语 义块的过程，并结合 DOM 树结构分析进行页面分块，则可以达到更好的效果。微软亚洲研究院在其 2003 年的论文 VIPS: A vision based page segmentation algorithm4 里首次提出了基于视觉的网页分块算法 VIPS(Vision-based page segmentation)。VIPS 算法充分利用了 Web 页面的布局特征（见图 1），它有三个 主要步骤：首先从 DOM 树中以较小的粒度提取
20、出所有可视标签块，并且给每个 可视标签块计算出一个 DOC（“一致性程度”，Degree of Coherence）值来描述该 块内部内容的相关性。DOC 的值越大，则表明该块内部的内容之间的联系越紧 密，反之越松散。第二步利用每个可视标签块的绝对位置和相对位置信息，检测出它们之间的所有的分割条，包括水平和垂直方向。最后基于这些分割条，利用 更多的诸如颜色等视觉信息，重新构建 Web 页面的语义结构。VIPS 算法的优点十分明显，它充分利用了网页的视觉信息和结构信息，相 对于传统的基于规则的分块算法来说，大大提高了分块的精确度。但 VIPS 算法 也有其局限性：首先，提取网页视觉信息代价很高。
21、因为 HTML 语言本身并没有包含足够 的视觉信息，所以网页真正显示出来的效果因浏览器，因操作系统，甚至因硬件 而异。为了得到网页的完整视觉信息，必须完全下载该网页所链接的 CSS 文件， JavaScript 文件，图片文件等等，然后调用浏览器内核代码渲染这些网页文件， 最后从浏览器内核代码的接口中得到每个 HTML 标签的视觉信息。整个步骤不 仅耗时，而且十分依赖于浏览器内核代码。网络上看到的一些 VIPS 算法实现都 是调用了 IE COM 接口，而微软自身的实现是利用单独优化后的 IE 内核，他们 都是基于 Windows 编程环境。在 Linux 编程环境下，可以利用的只有 Mozi
22、lla（Firefox）浏览器的开源代码。但 Mozilla 代码并没有针对网页视觉信息提取这 一需求给出方便的使用接口，只有在其渲染完网页之后再截取视觉信息。我们实 验室的毛先领师兄曾经研究 Mozilla 代码，完成了这项艰苦的工作，但实验表明， 提取一个网页的视觉信息所需时间超过 1 秒钟，不能满足搜索引擎等常规应用的 使用要求。其次，VIPS 算法虽能改进分块精确度，但算法相对比较复杂，迭代轮数较 多，而基于规则的分块算法却只用较少的迭代轮数。2.3 Block Level PageRank 算法在 VIPS 算法的分块基础上，微软 2004 年的论文 Block-level Link
23、 Analysis5 中提出了 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 为所有语义块
24、的集合，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 的维数为 nk，定义如下
25、：Zij1/ s= i如果block i中有链接指向page j0否则si 是 block i 所链接的网页总数。Zij 可以理解成是用户从 block i 链接到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 的 文字多少和离整个
26、页面中心点位置的远近来计算 block 的重要度。每个 block 包含的文本长度越大，离页面中心点越近，则越重要。改进后的 X 定义如下：XijfP= i(bj )如果block j属于page i0否则其中 f 函数给 page i 中的每一个 block j 赋予一个重要度权值。函数值越 大，则 block 越重要。在 BLPR 的实现中函数 f 的定义如下：fP (b) =b page p中block b的大小block b的中心点到页面中心点的距离其中为正规化因子，使得对每个 page，fp(b)的总和为 1。即fP (b) = 1bpfp(b)可以理解为是用户在浏览 page p
27、的时候，关注 block b 的可能性。2.3.2 Page Graph传统的 PageRank 算法中 Page Graph 的权值矩阵计算十分简单，如果从 page i 到 page j 有链接的话，则 WP(i,j)为 1，反之为 0。然而在 BLPR 算法中，Page Graph 需要体现出不同的语义块的重要程度的不同。也就是说，当用户点击页面中的超 链接时，更偏好选择重要的语义块中的 URL。所以在 BLPR 中，WP 的定义为：WP (a,b) = fa (b) Z(b,b),baa,b P即WP= XZ 。WP(, )可以理解为是从 page 开始，以 page 中包含的各语义块
28、为媒介， 跳转到 page 的概率。2.3.3 Block GraphWB 的定义为：WB (a,b) = Z(a,b) X(b, b),a,b B即WB= ZX 。WB(a,b)可以理解为用户从 block a 开始，以包含 block b 的 page 为媒介， 跳转到 block b 的概率。2.3.4 Block Level PageRankBlock Level PageRank 跟 PageRank 区别的实质在于，PageRank 算法基 于原始的只有 1 和 0 的 Page Graph，而 BLPR 算法基于上面提到的 GP。BLPR 算法的数学计算公式如下：._.(eU +
29、 (1- e)M )T p = p其中 p 为结果向量，共 n 维，每一维代表一个网页的 PageRank 值。 为适配参数，以 1- 的概率，用户在当前页面中随机选择一个超链接，跳转 到该链接指向的页面；以 的概率，用户从所有网页中随机选择一个 URL 并跳转。所以 U 为 nn 的转换矩阵，它满足对所有的 i，j，Uij = 1/n。而 M 也是 nn 的转换矩阵，它是由上面提到的 WP 权值矩阵对每一行做归一化， 令每一行的权值之和为 1 得到的。p 向量的值以马尔科夫链的形式循环计算 下去，直到算法收敛。Block Level PageRank 比单纯的 PageRank 包含了更多的
30、语义信息。因为 它的计算基于网页中各语义块的重要程度，噪音块、广告块中的超链接指向 的网页的重要性显然不如导航块、正文块中的超链接所指向的网页，所以前 者会被分配到较少的 PageRank 值，而后者则被分配到较多的 PageRank 值。 也就是说，网页中的无关信息区域在 PageRank 的计算过程中起的作用相对 较小，所以 BLPR 的效果要优于单纯的 PageRank。第 3 章天网搜索引擎 Quark 模块搜索引擎系统一般包括网页的抓取、预处理、存储、索引、检索等几个部分， 其中预处理部分的作用是分析、处理原始网页数据如去除网页噪音，消除重复网 页，计算 PageRank，中文切词等
31、等，并为后继模块提供统一的数据访问接口， 规范数据管理，避免重复计算。同时在天网搜索引擎平台中，基于功能扩展和实 验室内部其他相关研究的需要，必须将对原始网页的处理部分单独出来，从而方 便模块复用，统一代码管理，减少重复劳动。在天网搜索引擎平台的搭建过程中，也包括了抓取、存储、分析（预处理）、 索引、检索等模块，其中的分析模块接受成批量原始网页的输入，然后对每个网 页调用 Quark 模块，进行网页分块、信息提取等工作，最后将处理后的数据存成 TwDocView 格式，再提供给下游模块。我的毕业设计的主要工作，就是围绕 Quark 模块而展开。从上面的介绍中可以看出，天网搜索引擎 Quark
32、模块有两个比较重要的特点：1、可扩展性。 因为搜索引擎是一个比较庞大的系统，并且一直在不停的有新算法，新需求 的加入，所以对数据的要求也会一直变化。而基于对原始网页数据集中处理 的原则，为了应对下游模块可能提取的新的数据访问需求，Quark 模块必须 具备良好的可扩展性，并且提供尽量多的各种类型的数据访问接口。同时由 于实验室人员的不固定性，代码的维护十分重要。我自己在刚开始阅读旧有 的天网搜索引擎相关代码的时候，就常有十分难懂的感觉，无法复用已有代 码，只好自己重新编写。而正由于 Quark 模块的可扩展性要求，所以它的代 码的可阅读性也十分重要，在编写的过程中，我尽量注意了这一点，遵守了
33、我们统一的代码规范。2、独立性。在我们实验室内部，除了搜索引擎之外，还有 Web 数据挖掘，Map-reduce 应用等相关工作也可能需要使用对单个网页的处理和数据提取程序。因此 Quark 模块必须能独立于搜索引擎代码之外单独编译运行，并且方便他人调 用这部分代码。基于上述两个特点，我初步实现了 Quark 模块。该模块的类结构图如下：1、图中右下及中间蓝色的部分为 Quark 模块的核心功能类，包括 QuarkTree、 QuarkElement、QuarkRecognizer、QuarkAnalyzer 等四个类。QuarkTree 类的作用有两个，一个是以原始网页为输入，建立 Html
34、 的 Dom Tree；另一个是存储分好的网页块（在我们的系统中，每一个网页 块就叫做一个 Quark）并记录 Quark 与 Quark 之间的组织架构。QuarkElement 类指代一个 Quark,即每个 Quark 自身就是一个 QuarkElement 类的对象。QuarkRecognizer 类肩负网页分块的重任，从网页中识别出所有语义块。 它依赖于前面的两个类。QuarkAnalyzer 类依赖于 QuarkRecognizer 类，它在分好的块的基础上， 判断各个块的类型，提取正文信息。这个类是整个 Quark 模块最核心的 类，目前功能只是初步实现，还有很大的改进空间，将来
35、也可以根据功 能将其分割成多个类。2、中上部绿色的部分为 Quark 模块的评测和演示类，包括 QuarkEvaluation 和 QuarkHtmlBuilder 两个类。QuarkEvaluation 类是评测类，用来评测 Quark 核心类的实现效果。当 前实现的是对网页正文信息提取的评测，评测需要接受人工标记的网页 或网页集为输入。评测算法的细节见后文。QuarkHtmlBuilder 类是演示类，用来查看 Quark 模块各步骤的实现效果。 目前可以查看网页分块的效果，也可以查看主题信息提取的效果。3、最上面黄色的部分为 Quark 模块的应用类，包括 QuarkRank 、 Qua
36、rkDuplicate、QuarkClassification 等，它们都是利用分好的网页块实现的 一些算法，比如基于 Quark 的 PageRank 算法，基于 Quark 的网页消重算法，以 及基于 Quark 的网页分类算法。4、左下方灰色的部分为 Quark 模块依赖的外部类接口，包括中文切词类 ChineseTokenizer，以及图中没有的编码转换类 CodeConvert 等等。5、中下部红色的部分为 Quark 模块直接的下游模块，包括 TwDocView 类和 TwMd5 类。3.1 网页分块算法算法主体在 QuarkRecognizer 类中。参见在第二章相关研究里提到的
37、，除了 基于视觉的算法之外，大部分基于语义的算法都是利用 html 标签及其包含的文 字信息的特性来给网页分块的。并且由于大多数论文的着重点在于分块后的内容 提取上，所以对分块算法本身着墨不多。综合各篇论文里提到的分块方法，我设 计实现了 QuarkRecognizer 算法。这一算法首先的一大特点就是实用性强。所谓实用性强是指适合在实际系统 中使用，效率高，定义完整。我详细分析了 W3C 制定的 HTML4.01 格式规范， 将所有规范的 Html 标签根据 QuarkRecognizer 算法的需要分类，完整地列出了所 有对网页分块起重要作用的标签，而不是像所有已有论文那样仅仅象征性地列举
38、 出几个 html 标签。分类后的详细 html 标签清单如下：1、超级标签（Super Tag，简称为 S 型标签）： 这种标签可以被直接认定是一个网页块的根标签，在算法过程中一旦遇到这 种标签，就可以直接将其加入网页块池。包括：HEAD, SCRIPT, STYLE, OBJECT, FIELDSET, FRAMESET, IFRAME2、大标签（Big Tag，简称为 B 型标签）： 这种标签通常都代表一个网页块，只不过有时其内部内容过少，需要跟其他 节点合并成一个网页块，或者在特殊情况下其内部没有可见字符。所以在算 法过程中，遇到这种标签，就判断其单独作为一个网页块的条件是否已经成 熟
39、，如成熟，则将其加入网页块池。包括：DIV, TD, TABLE, FORM, FIELDSET, CENTER, NOFRAMES, NOSCRIPT, PRE, BODY, HTML这里需要注意的是像 BODY，HTML 两个标签也作为 B 型标签，原因是这 样可以防止分块之后网页内部文字信息的遗漏，因为最终即使有遗漏，也会 至少包含在 HTML 这个最后把关的门神标签手中。3、排版标签（Layout Tag，简称为 L 型标签）： 这种标签能影响到网页的显示效果，改变文字布局。如果一颗 html 子树中 包含多个 L 型标签，则该子树单独成块的可能性增加。包括：P, UL, OL, DL
40、, DIR, LI, DT, BLOCKQUOTE, ADDRESS,BR, HR, COL, COLGROUP, IMG, MENU, SELECT4、显示标签（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, H
41、5, H6, I, INS,KBD, LABLE, SMALL, STRIKE, STRONG, SUB, SUP, Q,S, SAMP, SPAN, THEAD, TFOOT, TEXTAREA, U, TT, VAR, O:SMARTTAGTYPE5、附属标签（Affiliated Tag，简称为 A 型标签）： 这种标签从属与上述四种标签的某一种，同时有些也出现在了前面四种里 面。由于它们一般不单独出现，对网页布局的影响体现在了其属主标签中， 所以在 QuarkRecognizer 算法中也不予考虑。包括：FRAME, INPUT, ISINDEX, LEGEND, LINK, MAP,
42、 META,OPTION, OPTGROUP, PARAM, TD, TH, TR, TBODY, TITLE6、定制标签（Customized Tag，简称为 C 型标签）：因为不同的应用中，对网页分块会有些不同的要求。比如我们实验室的 WebDigest 小组在进行新闻网页的数据挖掘的工作中，需要使用到网页分块， 但是他们特别需要提取该新闻网页的发布日期和时间，而这部分内容通常是 在新闻标题与新闻正文之间的一小行文字，正常的网页分块程序并不会将其 单独提取成一个网页块。所以我添加了定制标签，由用户指定，它可以是普 通的标签如“TITLE”等，也可以是正则表达式，凡是其内部文字满足该正 则表
43、达式的 S 型、B 型和 L 型标签，都将被单独提取为网页块。例如：H1, H2, TITLE在明确了各 html 标签的类别之后，利用 DomTree 中各标签节点的类别信息 和内部文字长度，以及其子标签节点的类别信息，对 DomTree 自底向上遍历， 在遍历的过程中不断判断出新的网页块，并加入网页块池中，当遍历到最上部的 html 根节点时，算法结束，网页分块完毕。QuarkRecognizer 算法的核心伪码如 下：ALGORITHM QuarkRecognizer (DomTree tree，TagList CType)INPUT :某单个网页构建的 DomTree，定制标签(C 型
44、)节点列表BEGIN1 用 DomTree 的叶子节点，也就是文字节点建立一个当前节点队列，开始 自底向上遍历。2 取当前节点队列的第一个节点。3 如果遇到 S 型节点，则立即将此节点加入网页块池。4 如果遇到 C 型节点，则立即将此节点加入网页块池。5 如果遇到 B 型节点，则判断该节点内部的文字长度是否已超过阈值，或者该节点内部的 L 型节点比例是否超过阈值，如果满足上述两个条件之 一，则将此节点加入网页块池；否则将其内部文字长度信息和自身信息向 父节点传递，然后将父节点加入当前节点队列，回到 2。6 如果遇到 L 型节点，则将其内部文字长度信息和其自身信息向父节点传 递，然后将父节点加入
45、当前节点队列，回到 2。7 如果遇到 D 型或 A 型节点，则将其内部文字长度信息向父节点传递，然 后将父节点加入当前节点队列，回到 2。8 当前节点队列为空时，遍历结束，算法终止。END网页块池中的网页块是以 QuarkElement 的格式存储，而 QuarkElement 类中 包括原来的 html 子树的 DomTree 结构和其他相关信息，同时在上述遍历的过程 中，即使有的网页块从 html 结构上来说包含在更高层的网页块之下，但在 QuarkElement 中也消除了包含关系，所有网页块都互相独立，互不包含。3.2 网页主题内容提取算法主体在 QuarkAnalyzer 类中。采用
46、了基于规则和基于 Bayes 的语义分析 相交的方法，也就是分别用基于文本相似度的方法和基于 Bayes 的方法判断每个 网页块的类型（是不是主题块），然后对它们求交集，只有两个方法共同认定的 主题内容块才能最终被认定。QuarkAnalyzer 算法的核心伪码如下：第一步，基于文本相似度的方法：1、首先，把所有网页块中，文本长度最大的那个网页块判定为主题内容块。2、然后用其余网页块逐个与最大的网页块比较文本相似度。文本相似度的 计算如下：2.1 将两个网页块分别切词，去除停用词后，存储成 token 流。2.2 对两个 token 流分别排序。2.3 对排序后的两个 token 流计算 token 的重复数。2.4 用 token 的重复数除以较小的 token 流中的 token