大规模网页模块识别与信息提取系统设计与实现本科生毕业论文(44页).doc

-大规模网页模块识别与信息提取系统设计与实现本科生毕业论文-第 37 页本科生毕业论文题目：(中文)大规模网页模块识别与信息提取系统设计与实现(英文 )Design and Implementation of Large Scale Web Template Detection and Information Extraction System毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得 及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。作 者 签 名： 日 期： 指导教师签名： 日期： 使用授权说明本人完全了解 大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。作者签名： 日 期： 学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名： 日期： 年 月 日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期： 年 月 日导师签名： 日期： 年 月 日注 意 事 项1.设计（论文）的内容包括：1）封面（按教务处制定的标准封面格式制作）2）原创性声明3）中文摘要（300字左右）、关键词4）外文摘要、关键词 5）目次页（附件不统一编入）6）论文主体部分：引言（或绪论）、正文、结论7）参考文献8）致谢9）附录（对论文支持必要时）2.论文字数要求：理工类设计（论文）正文字数不少于1万字（不包括图纸、程序清单等），文科类论文正文字数不少于1.2万字。3.附件包括：任务书、开题报告、外文译文、译文原文（复印件）。4.文字、图表要求：1）文字通顺，语言流畅，书写字迹工整，打印字体及大小符合要求，无错别字，不准请他人代写2）工程设计类题目的图纸，要求部分用尺规绘制，部分用计算机绘制，所有图纸应符合国家技术标准规范。图表整洁，布局合理，文字注释必须使用工程字书写，不准用徒手画3）毕业论文须用A4单面打印，论文50页以上的双面打印4）图表应绘制于无格子的页面上5）软件工程类课题应有程序清单，并提供电子文档5.装订顺序1）设计（论文）2）附件：按照任务书、开题报告、外文译文、译文原文（复印件）次序装订摘要本文提出了一套基于语义的网页分块和主题内容信息提取算法，在天网搜索引擎预处理模块中将其实现，并且在SEWM 2008 会议中，以这套算法为框架，组织了主题型网页识别和网页主题内容信息块提取两个中文Web 信息检索评测项目。在这套算法的基础上，基于天网文件系统与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 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 TianWangfile 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.Keywords:Web-Page Blocking, Information Extraction, Evaluation, Map-Reduce, PageRank目录第1 章序言3第2 章相关研究工作52.1基于语义的网页信息提取算法52.2基于视觉的网页分块算法62.3 Block LevelPageRank算法82.3.1 Block LevelWebGraph82.3.2 PageGraph92.3.3 BlockGraph92.3.4 BlockLevelPageRank10第3 章天网搜索引擎Quark 模块113.1网页分块算法133.2网页主题内容提取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 无以制胜。互联网的高速发展，改变了我们的生活方式，打破了我们的时空界限，重塑着我们的社会形态。经济、政治、学习、工作、生活、娱乐等等各个层面都在Web 网络中激荡起伏，深刻地影响着人类的未来。而Web 网络的灵魂，就是流动在其中的无穷无尽的信息。Web2.0 的意义就在于网络内容的提供方从商人和专业人员转变为网络上的每一个普通用户，从而几何级数地增长了Web 的信息量。然而信息量的增大，随着而来的就是存储成本的增大和信息提取难度的增大，如何有效的获取和整合Web 信息成为大家面对的共同课题。传统意义上，整个Web 网络就是由无数的Web 页面而构成，它们是网络信息存储和提取的基本单位，获取了这些Web 页面就相当于获取了Web 信息内容。但是把整个页面作为最基本的信息处理单位有一些不合理之处。首先是因为Web页面中信息量的分布非常不均匀，有主题内容，也有广告，导航栏，版权信息，装饰信息，以及在大量网页中重复出现的部分，它们自身的信息含量千差万别。当网页浏览者刚打开一个新页面的时候，如果之前没有浏览过类似页面，就会目不暇接，眼花缭乱，有无所适从的感觉，必须仔细探寻一番才能定位到这个页面的要害；如果之前浏览过类似页面，比如常上这个网站，那么通常浏览者就已经训练出一种直觉或者说是条件反射，他会立刻定位到他所想要浏览的部分，从而忽略掉页面中的其他部分。其次还因为现在很多Web 页面是动态更新的，比如博客页面或者论坛讨论帖，它们的更新是以一个一个网页块的形式进行的，更新时页面上大部分内容并没有变化，如果仍然以整个页面为处理单位，则不可避免地存在效率损失和定义的混淆。这些情况促使我们反思以整个页面为基本信息单元的做法不仅不尽合理，一定程度上甚至已经损害了网络浏览者的用户体验，妨碍了网络信息提取的效率。解决这个问题的办法其实有两种思路。第一种就是从信息的产生方那儿就不再提供网页式的信息，而改为直接提供网页块或者文字段式的信息。最常见的例子就是RSS（聚合内容，Really Simple Syndication），博客或者新闻的提供方省去了浏览者访问网站查看更新的麻烦，直接将精简后的网页块或者文字段发送给RSS 的订阅方。第二种则更为普适，就是细分网页中的信息单元，也就是给网页分块，在网页分块的基础上存储和提取Web 页面的语义信息。基于网页分块的Web 页面的语义信息提取在很多方面都有应用。比如，在常规搜索引擎中，可以以网页分块为基础去除网页中的噪音信息，识别出网页中的主题内容信息块，从而用提取出的主题内容信息来构建对这个页面的描述，完成网页分类、网页消重等应用。还可以凭此改进搜索引擎的索引模块和检索模块的效率，比如改进TF/IDF 和PageRank 的算法（详见第五章）。Web 页面的语义分块另外一个重要用途在于移动终端访问互联网，比如手机和IPod 等。因为目前大部分的Web 页面都是针对PC 机设计的，要求有相对较大的屏幕。而移动设备通常屏幕较小，计算能力有限，无法直接访问这些页面。为了解决这个问题，要么是内容提供商手工编辑专门适用于移动设备的页面，要么就只有对页面进行语义分割，并在分割后的页面中选择信息量最高的语义块。除此之外，Web 页面的语义分块还可能对常规搜索引擎之外的其他信息检索系统有帮助。比如类似于新闻人物追踪和历史新闻检索等应用，出于节约存储空间，提高检索精度，方便更新等目的，可以直接存储和操作网页中的主题内容语义块，而舍弃网页中其他与系统需求无关的语义块。在这篇论文中，第二章介绍了本文的相关研究工作，包括常见的网页分块和信息提取算法、基于视觉的网页分块算法，以及网页分块的一个应用Block Level PageRank算法；第三章介绍了我实现的网页分块和主题信息提取算法Quark 算法；第四章介绍了Quark 算法在SEWM2008 中文Web信息检索评测项目中的实际检验；第五章介绍了在Quark 算法基础上实现的一个分布式QuarkRank 程序。第六章是对本文的总结和工作展望。第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 template1的论文使用正则表达式来提取重复模式，从而更适应网页间的细微变化，增加了Site-Level 的召回率。Page-Level 的算法在处理大型网站的网页时效率常常不如Site-Level，但优势在于灵活，不受网页类型限制。它只利用单个页面内部的信息，当然也可能会用到一些全局信息。宾夕法尼亚州立大学2005 年的论文2就是其中的典型。这篇论文提出简化块与块之间的层次结构，直接提取一些原子块（Atomic Block），诸如以list, table, link, object, frame, form 等为根节点的html 子树，来完成分块工作。这一方法虽然简单而易于实现，但依赖于事先给出的原子块列表，同时忽略了原子块之间的嵌套链接问题。在分块之后，它也只是简单计算了文字长度等几个变量来决定主题信息块。合并Site-Level 和Page-Level 的方法也一直有人尝试。WWW2007 的论文Page-level template detection via isotonic smoothing3先利用一个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 algorithm4 里首次提出了基于视觉的网页分块算法VIPS(Vision-basedpage segmentation)。VIPS算法充分利用了Web页面的布局特征（见图1），它有三个主要步骤：首先从DOM 树中以较小的粒度提取出所有可视标签块，并且给每个可视标签块计算出一个DOC（“一致性程度”，Degree of Coherence）值来描述该块内部内容的相关性。DOC 的值越大，则表明该块内部的内容之间的联系越紧密，反之越松散。第二步利用每个可视标签块的绝对位置和相对位置信息，检测出它们之间的所有的分割条，包括水平和垂直方向。最后基于这些分割条，利用更多的诸如颜色等视觉信息，重新构建Web 页面的语义结构。VIPS 算法的优点十分明显，它充分利用了网页的视觉信息和结构信息，相对于传统的基于规则的分块算法来说，大大提高了分块的精确度。但VIPS 算法也有其局限性：首先，提取网页视觉信息代价很高。因为HTML 语言本身并没有包含足够的视觉信息，所以网页真正显示出来的效果因浏览器，因操作系统，甚至因硬件而异。为了得到网页的完整视觉信息，必须完全下载该网页所链接的CSS 文件，JavaScript 文件，图片文件等等，然后调用浏览器内核代码渲染这些网页文件，最后从浏览器内核代码的接口中得到每个HTML 标签的视觉信息。整个步骤不仅耗时，而且十分依赖于浏览器内核代码。网络上看到的一些VIPS 算法实现都是调用了IE COM 接口，而微软自身的实现是利用单独优化后的IE 内核，他们都是基于Windows 编程环境。在Linux 编程环境下，可以利用的只有Mozilla（Firefox）浏览器的开源代码。但Mozilla 代码并没有针对网页视觉信息提取这一需求给出方便的使用接口，只有在其渲染完网页之后再截取视觉信息。我们实验室的毛先领师兄曾经研究Mozilla 代码，完成了这项艰苦的工作，但实验表明，提取一个网页的视觉信息所需时间超过1 秒钟，不能满足搜索引擎等常规应用的使用要求。其次，VIPS 算法虽能改进分块精确度，但算法相对比较复杂，迭代轮数较多，而基于规则的分块算法却只用较少的迭代轮数。2.3 Block Level PageRank算法在VIPS 算法的分块基础上，微软2004 年的论文Block-level Link Analysis5 中提出了Block Level PageRank(BLPR)算法。之前的大多数链接分析算法都是以一个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 包含于网页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，定义如下：Zij1/s=i如果block i中有链接指向page j0否则si 是block i 所链接的网页总数。Zij 可以理解成是用户从block i 链接到page j 的概率。页块（page-to-block）矩阵X 的维数为k×n，定义如下：Xij1/s=i如果block j属于page i0否则si 是page i 所包含的block 总数。上面的公式分配给page i 中的每一个block 以相同的权值，显然是过于简化了，不能区分block 的重要程度。在BLPR 算法中，采用了一个简单的block 重要度区分的公式，即用block 的文字多少和离整个页面中心点位置的远近来计算block的重要度。每个block 包含的文本长度越大，离页面中心点越近，则越重要。改进后的X定义如下：Xijf=i(bj)如果block j属于page i0否则其中f 函数给page i 中的每一个block j 赋予一个重要度权值。函数值越大，则block 越重要。在BLPR 的实现中函数f 的定义如下：fP (b)=bpage p中block b的大小blockb的中心点到页面中心点的距离其中为正规化因子，使得对每个page，fp(b)的总和为1。即åfP(b)=1bÎpfp(b)可以理解为是用户在浏览page p 的时候，关注block b 的可能性。2.3.2 PageGraph传统的PageRank 算法中Page Graph 的权值矩阵计算十分简单，如果从page i到pagej有链接的话，则WP(i,j)为1，反之为0。然而在BLPR算法中，PageGraph 需要体现出不同的语义块的重要程度的不同。也就是说，当用户点击页面中的超链接时，更偏好选择重要的语义块中的URL。所以在BLPR中，WP的定义为：WP(a,b)=åfa(b)Z(b,b),bÎaa,bÎP即WP=XZ 。WP(, )可以理解为是从page 开始，以page 中包含的各语义块为媒介，跳转到page 的概率。2.3.3 BlockGraphWB 的定义为：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 LevelPageRankBlock Level PageRank 跟PageRank 区别的实质在于，PageRank 算法基于原始的只有1和0的PageGraph，而BLPR算法基于上面提到的GP。BLPR算法的数学计算公式如下：._.(eU + (1-e)M )T p =p其中p 为结果向量，共n 维，每一维代表一个网页的PageRank 值。为适配参数，以1-的概率，用户在当前页面中随机选择一个超链接，跳转到该链接指向的页面；以的概率，用户从所有网页中随机选择一个URL 并跳转。所以U 为n×n 的转换矩阵，它满足对所有的i，j，Uij = 1/n。而M 也是n×n 的转换矩阵，它是由上面提到的WP 权值矩阵对每一行做归一化，令每一行的权值之和为1 得到的。p 向量的值以马尔科夫链的形式循环计算下去，直到算法收敛。Block Level PageRank 比单纯的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 的 Dom Tree；另一个是存储分好的网页块（在我们的系统中，每一个网页块就叫做一个Quark）并记录Quark与Quark之间的组织架构。QuarkElement 类指代一个Quark,即每个Quark 自身就是一个QuarkElement类的对象。QuarkRecognizer类肩负网页分块的重任，从网页中识别出所有语义块。它依赖于前面的两个类。QuarkAnalyzer类依赖于QuarkRecognizer类，它在分好的块的基础上，判断各个块的类型，提取正文信息。这个类是整个Quark模块最核心的类，目前功能只是初步实现，还有很大的改进空间，将来也可以根据功能将其分割成多个类。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 标签清单如下：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 这个最后把关的门神标签手中。3、排版标签（Layout Tag，简称为L 型标签）：这种标签能影响到网页的显示效果，改变文字布局。如果一颗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"5、附属标签（Affiliated Tag，简称为A 型标签）：这种标签从属与上述四种标签的某一种，同时有些也出现在了前面四种里面。由于它们一般不单独出现，对网页布局的影响体现在了其属主标签中，所以在QuarkRecognizer 算法中也不予考虑。包括："FRAME", "INPUT", "ISINDEX", "LEGEND", "LINK", "MAP", "META","OPTION", "OPTGROUP", "PARAM", "TD", "TH", "TR", "TBODY", "TITLE"6、定制标签（CustomizedTag，简称为C型标签）：因为不同的应用中，对网页分块会有些不同的要求。比如我们实验室的WebDigest 小组在进行新闻网页的数据挖掘的工作中，需要使用到网页分块，但是他们特别需要提取该新闻网页的发布日期和时间，而这部分内容通常是在新闻标题与新闻正文之间的一小行文字，正常的网页分块程序并不会将其单独提取成一个网页块。所以我添加了定制标签，由用户指定，它可以是普通的标签如“TITLE”等，也可以是正则表达式，凡是其内部文字满足该正则表达式的S 型、B 型和L 型标签，都将被单独提取为网页块。例如："H1", "H2", "TITLE"在明确了各html 标签的类别之后，利用DomTree 中各标签节点的类别信息和内部文字长度，以及其子标签节点的类别信息，对DomTree 自底向上遍历，在遍历的过程中不断判断出新的网页块，并加入网页块池中，当遍历到最上部的html 根节点时，算法结束，网页分块完毕。QuarkRecognizer 算法的核心伪码如下：ALGORITHM QuarkRecognizer (DomTree tree，TagList CType)INPUT :某单个网页构建的DomTree，定制标签(C 型)节点列表BEGIN1 用DomTree 的叶子节点，也就是文字节点建立一个当前节点队列，开始自底向上遍历。2 取当前节点队列的第一个节点。3 如果遇到S 型节点，则立即将此节点加入网页块池。4 如果遇到C 型节点，则立即将此节点加入网页块池。5 如果遇到B 型节点，则判断该节点内部的文字长度是否已超过阈值，或者该节点内部的L 型节点比例是否超过阈值，如果满足上述两个条件之一，则将此节点加入网页块池；否则将其内部文字长度信息和自身信息向父节点传递，然后将父节点加入当前节点队列，回到2。6 如果遇到L 型节点，则将其内部文字长度信息和其自身信息向父节点传递，然后将父节点加入当前节点队列，回到2。7 如果遇到D 型或A 型节点，则将其内部文字长度信息向父节点传递，然后将父节点加入当前节点队列，回到2。8 当前节点队列为空时，遍历结束，算法终止。END网页块池中的网页块是以QuarkElement 的格式存储，而QuarkElement 类中包括原来的html 子树的DomTr