【毕业学位论文】（Word原稿）大规模网页模块识别与信息提取 系统设计与实现

本科生毕业论文 题目 ： (中文 ) 大 规 模 网 页 模 块 识 别 与 信 息 提 取 系 统 设 计 与 实 现 (英文 ) 名： 学 号： 院 系： 计算机系 专 业： 搜索引擎与 互联网信息 挖掘 指导教师： 二一七年四月十七日 00448174 朱磊 本科毕业论文 2 00448174 朱磊 本科毕业论文 i 摘要 本文 在 已有的基于 启发式规则的网页信息提取算法 的基础上，通过 为所有符合 范的 签分类， 逐个分析各 签所包含的语义信息， 细化规则设置，实现了一种自底向上的 无信息遗漏的网页分块算法，并在此基础上，利用统计方法得到详细的概率分布数据，实现了文本相似度比较和验概率估计两种网页主题内容信息块识别算法，并将其求交，提高了主题内容信息块的识别精确度 。 上述算法已 集成到天网搜索引擎平台的 网页预处理模块中，并且在 008 会议中，以这套算法为框架，组织了主题型网页识别和网页主题内容信息块提取两个中 文 息检索评测项目。 在 这套算法的 基础上，基于天网文件系统 与 算平台 ，实现了分布式 的 网页块级别 法，命名为 法 。 实际检验表明，该套算法具有 很好的适应性与可扩展性，并达到了很高的精度和召回率。 关键词： 网页分块 信息提取 测 磊 本科毕业论文 i on of eb by in 3C by in by it a On of of is of 008 we eb of In at a 0448174 朱磊 本科毕业论文 录 第 1 章 序言 . 3 第 2 章 相关研究工作 . 5 于语义的网页信息提取算法 . 5 于视觉的网页分块算法 . 6 法 . 8 . 8 . 10 第 3 章 天网搜索引擎 块 . 11 页分块算法 . 13 页主题内容提取 . 16 法效果演示 . 18 第 4 章 文 息检索评测 . 23 测任务介绍 . 23 题型网页发现任务 . 23 页内容信息发现任务 . 24 测格式 . 25 测结果 . 25 题型网页发现任务评测结果 . 26 页内容信息发现任务评测结果 . 28 测综述 . 31 第 5 章 网页分块的分布式应用 . 32 . 32 他应用 . 34 第 6 章 总结与展望 . 35 结 . 35 望 . 36 00448174 朱磊 本科毕业论文 3 第 1 章 序言 信息时代，非 以制胜。互联网的高速发展，改变了我们的生活方式，打破了我们的时空界限，重塑着我们的社会形态。 经济、政治、学习、工作、生活、娱乐等等各个层面都在 络中激荡起伏，深刻地影响着人类的未来。而 络的灵魂，就是流动在其中的无穷无尽的信息。 意义就在于 网络内容的提供方从商人和专业人员转变为网络上的每一个普通用户，从而几何级数地增长了 信息量。 然而信息量的增大，随着而来的就是存储成本的增大和信息提取难度的增大，如何有效的获取和整合 息成为大家面对的共同课题。 传统意义上， 整个 络就是由无数的 面而构成， 它们是网络信息存储和提取的基本单位， 获取了这些 面就相当于获取了 息内容。但是把整个页面作为最基本的信息处理单位有一些不合理之处。 首先是因为 主题内容，也有广告，导航栏 ，版权信息，装饰信息，以及在大量网页中重复出现的部分，它们自身的信息含量千差万别。当网页浏览者刚打开一个新页面的时候，如果之前没有浏览过类似页面，就会目不暇接，眼花缭乱，有无所适从的感觉，必须仔细探寻一番才能定位到这个页面的要害；如果之前浏览过类似页面，比如常上这个网站，那么通常浏览者就已经训练出一种直觉或者说是条件反射，他会 立刻定位到他所想要浏览的部分，从而忽略掉页面中的其他部分。 其次还因为现在很多 面是动态更新的，比如博客页面或者论坛讨论帖，它们的更新是以一个一个网页块的形式进行的，更新时页面 上大部分内容并没有变化，如果仍然以整个页面为处理单位，则不可避免地存在效率损失和定义的混淆。 这 些情况 促使我们反思以整个页面为基本信息单元的做法不仅不尽合理，一定程度上甚至已经损害了网络浏览者的用户体验 ，妨碍了网络信息提取的效率 。 解决这个问题的办法其实有两种思路。第一 种 就是从信息的产生方那儿就不再提供网页式的信息，而改为直接提供网页块或者文字段式的信息。最常见的例子 就是 合内容， ，博客或者新闻 的 提供方省去了浏览者 访问网站查看更新的麻烦，直接将精简 后的网页块或者文字段发送给订阅方 。第二种则更为 普适，就是细分网页中的信息单元，也就是给网页分块，在网页分块的基础上存储和提取 面的语义信息。 00448174 朱磊 本科毕业论文 4 基于网页分块的 面的语义 信息 提取在很多方面都有应用。比如， 在常规搜索引擎中， 可以以网页分块为基础去除网页中的噪音信息，识别出网页中的主题内容信息块，从而用提取出的主题内容信息来构建对这个页面的描述，完成网页分类、网页消重 等应用。还可以凭此改进搜索引擎的索引模块和检索模块的效率，比如改进 算法 （详见第五章） 。 面的语义分块另外一个 重要 用途 在于 移动终端访问互联网，比如手机和 。 因为目前 大部分的 面都是针对 设计的， 要求有相对较大的屏幕。而 移动设备通常屏幕较小，计算能力有限， 无法直接访问这些页面。 为了解决这个问题，要么是内容提供商手工编辑专门适用于移动设备的页面，要么就只有对页面 进行语义分割，并在分割后的页面中选择信息量最高的语义块。 除此之外， 面的语义分块还可能对常规搜索引擎之外的其他信息检索系统有帮助。比如类似于新闻人物追踪和历史新闻检索等应用，出于节约存储空间，提高检索精度，方 便更新等目的，可以直接存储和操作网页中的主题内容语义块，而舍弃网页中其他与系统需求无关的语义块。 在这篇论文中， 第 二章介绍了本文的相关研究工作，包括常见的网页分块和信息提取算法、基于视觉的网页分块算法，以及网页分块的一个应用 法 ； 第三章 介绍了我实现的网页分块和主题信息提取算法 四章介绍了 法在 文 息检索评测项目中的实际检验；第五章介绍了在 法基础上实现的一个分布式 序。 第六章是对本文的 总结和工作展望。 00448174 朱磊 本科毕业论文 5 第 2 章 相关研究工作 基于语义 的网页信息提取 算法 由于 对 面 有效 分 块 之后可以极大地方便内容提取、数据挖掘、 息检索领域的相关工作 ， 所以早有很多研究人员前赴后继，就此展开了很多工作。其中，基于语义信息对网页分块是最简便 ， 也最基础的一种方法。所谓语义信息， 通常 包括 网页中包含的 签信息， 的结构信息，文字内容信息， 超链接信息， 以及其他通过统计或学习而得到的全局信息等等 ，也可以理解成 为 除了网页中的视觉信息之外的所有可以得到的信 息。 通 常基于语义的网页分块算法是和后续的网页主题内容提取结合在一起的，也就是在网页分块的过程中，同时完成了主题内容提取的工 作，并且主要的注意点是在主题内容提取上，因此分块算法就比较简单，甚至不显式地分块， 在此我们统称它们为网页信息提取算法。总的来说，网页信息提取算法可以分为两类，一类属于网站级别（ 一类属于网页级别（ 当然也有将两类方法结合使用的算法。 算法顾名思义，就是分析 一个网站或者网页集内部的所有网页，从中提取反复出现的 模式 ， 而一 般来说，在多个网页里重复出现的模式（可理解为 树） 就是导航栏、广告等噪音信息了，单个网页中减去这些信息，剩下的就是主题信息内容。关于 研究一直在继续， 就有一篇名为 的论文 使用正则表达式来提取重复模式，从而更适应网页间的细微变化 ，增加了 召回率 。 算法在处理大型网站的网页时效率常常不如 优势在于灵 活，不受网页类型限制。它只利用单个页面内部的信息， 当然也 可能会用到一些全局信息 。 宾夕法尼亚州立大学 2005 年的论文 2就是其中的典型。 这篇论文 提出 简化块与块之间的层次结构，直接提取一些原子块（ ，诸如以 为根节点的 树，来完成 分块工作。 这一方法虽然简单而易于实现，但 依赖于事先给出的原子块列表，同时忽略了原子块之间的嵌套链接问题。 在分块之后，它也只是简单计算了文字长度等几个变量来决定主题信息块。 00448174 朱磊 本科毕业论文 6 合并 方法也一直有人尝试。 论文先利用 一个 音模板提取器来构建训练集， 然后对所有页面构建 ，为各节点提取分类特征，比如 各节点的文本向量， 各 节点中链接的平均字数， 各 节点中链接文字所占比例等 ，最后 利用以上训练集对测试集中每一个 节点打分， 经过等压平滑之后，判定每个 节点的类型。所以它是典型的先 方法。 基于视觉的网页分块算法 基于 语义 的网页分块算法具有一些无法克服的先天性局限。首先， 直没有有效统一，而且其语法规范很松散，一些不符合 以网页编写者在制作网页时相对随意，导致 3C 规范；其次， 浏览器各自为政，对 签的识别不尽相同， 至还特别为 件设计了特别的 辅助显示，这些都增加了基于规则分块的复杂性。在实际编程中，就必须得借 助一些 范工具如 来修正 结构的错误，但个别中文网页仍然存在无法修正的情况。而且 最早引入是为了在浏览器中进行布局显示而不是进行 面的语义结构描述。比如，即使 中两个结点具有同一个父结点，那么这两个结点在语义上也不一定就是有联系 的 。反之，两个在语义上有关系的结点却可能分布在 的不同之处。因此仅仅通过分析并不能完全获取 面的语义信息 ，所以依赖于 的启发式规则算法存在先天不足。 而基于视觉的网页分块算法就弥补了这个不足。它的原理来自于用户的实际观察体验，即用户并不 关心 面的内部结构 ，而是 使用一些视觉因素，比如背景颜色、字体颜色和大小、边框、逻辑块和逻辑块之间的间距等等 来识别出页面中的语义块 。因此如果充分的使用 面的视觉 信息 ， 模拟人眼识别语义块的过程， 并结合 结构分析进行 页面 分块，则可以 达到更好的效果。 微软亚洲研究院在其 2003 年的论文 A 里首次提出了基于视觉的网页分块算法 法充分利用了 面的布局特征 （见图 1） ， 它 有三个主要步骤： 首先从 中 以较小的粒度 提取出 所有可视标签块 ， 并且给每个可视标签块计算出一个 一致性程度 ”， 值来描述该块内部内容的相关性。 值越大，则表明 该 块内部的内容之间的联系越紧密 ，反之越松散。 第二步利用每个可视标签块 的绝对 位置 和相对位置信息 ， 检测00448174 朱磊 本科毕业论文 7 出它们之间的所有的分割条，包括水平和垂直方向。最后基于这些分割条， 利用更多的诸如颜色等视觉信息，重新构建 面的语义结构 。 法的优点十分明显，它充分利用了网页的视觉信息和结构信息，相对于传统的基于规则的分块算法来说，大大提高了分块的精确度。但 法也有其局限性： 首先，提取网页视觉信息代价很高。因为 言本身并没有包含足够的视觉信息，所以网页真正显示出来的效果因浏览器，因操作系统，甚至因硬件而异。 为了得到网页的完整视觉信息，必须完全下载该网页所链接的 件，件，图片文件等等，然后调用浏览器内核代码渲染这些网页文件，最后从浏览器内核代码的接口中得到每个 签的视觉信息。 整个步 骤不仅耗时，而且十分依赖于浏览器内核代码。网络上看到的一些 法实现都是调用了 口，而微软自身的实现是利用单独优化后的 核，他们都是基于 程环境。在 程环境下，可以利用的只有 览器 的开源代码。 但 码并没有针对网页视觉信息提取这一需求给出方便的使用接口，只有在其渲染完网页之后再截取视觉信息。 我们实验室的毛先领师兄曾经 研究 码，完成了这项艰苦的工作，但实验表明，提取一个网页的视觉信息所需时间超过 1 秒钟，不能 满足搜索引擎等常规应用的使用要求。 其次， 法虽能改进 分块精确度，但算法相对比较复杂，迭代轮数较多，而基于规则的分块算法却只用较少的迭代轮数。 00448174 朱磊 本科毕业论文 8 法 在 法的分块基础上，微软 2004 年的论文 中提出了 法。 之前的大多数链接分析算法都是以一个 面为 中的一个节点，而 法以 网页中的语义块为原子节点，从链接结构和页面结构中提取出 系矩阵，构建出新的 以此计算 验表明， 先定义 两个集合 P 和 B。 P 为所有网页的集合， P = , k 为网页总数。 B 为所有语义块的集合， B = , ， n 为语义块总数。对每个语义块来说，只有一个网页包含它， 味着语义块 i 包含于网页 j。而每个网页包含有多个语义块。 然后定义两个矩阵， 阵 Z 和阵 X。在上述两个矩阵的基础之上，可以构建两个 模型，即网页图 P, 和语义块图 对这两个图来说， V 是节点集合（节点分别是网页和语义块）， E 是连接两个节点的边的集合，而 W 是边的权值矩阵。 阵 块页（ 阵 Z 的维数为 n k，定义如下： i 所链接的网页总数。 以理解成是用户从 i 链接到j 的概率。 阵 页块（ 阵 X 的维数为 k n，定义如下： 1 / b l o c k j p a g e 如 果 属 于 0 否 则1 / b l o c k i p a g e 如 果 中 有 链 接 指 向 0 否 则00448174 朱磊 本科毕业论文 9 i 所包含的 数。上面的公式分配给 i 中的每一个相同的权值，显然是过于简化了，不能区分 重要程度。在法中，采用了一个简单的 要度区分的公式，即用 文字多少和离整个页面中心点位置的远近来计算 重要度。每个 离 页面中心点越近，则越重要。 改进后的 X 定义如下： 其中 f 函数给 i 中的每一个 j 赋予一个重要度权值。函数值越大，则 重要。在 实现中函数 f 的定义如下： 其中 为正规化因子，使得对每个 fp(b)的总和为 1。 即 fp(b)可以理解为是用户在浏览 p 的时候，关注 b 的可能性。 统的 法中 权值 矩阵计算十分简单，如果从 i 到 j 有链接的话，则 WP(i,j)为 1，反之为 0。然而在 法中， 就是说，当用户点击页面中的超链接时，更偏好选择重要的语义块中的 以在 ， 定义为： 即Z。 , )可以理解为是从 开始，以 中包含的各语义块为媒介， b l o c k j p a g e 如 果 属 于 0 否 则 P p a g e p b l o c k bf b l o c k 中 的 大 小的 中 心 点 到 页 面 中 心 点 的 距 离 , , W b b P 00448174 朱磊 本科毕业论文 10 跳转到 的概率。 B 的定义为： 即X。 WB(a,b)可以理解为 用户从 a 开始，以包含 b 的 为媒介，跳转到 b 的概率。 别的实质在于， 法基于 原始 的 只有 1 和 0 的 法基于 上面提到的 其中 p 为结果向量， 共 n 维，每一维代表一个 网页的 。 为适配参数， 以 1概率，用户在当前页面中随机选择一个超链接，跳转到 该链接指向的 页面；以 的概率，用户 从所有网页中随机 选择一个 所以 U 为 n n 的 转换矩阵 ，它满足对所有的 i， j， 1/n。 而 n n 的转换矩阵，它是由上面提到的 值矩阵对每一行做归一化，令每一行的权值之和为 1 得到的。 p 向量的值以马尔科夫链的形式循环计算下去，直到算法收敛。 单纯的 含了更多的语义信息。因为它的计算基于网页中各语义块的重要程度，噪音块、广告块中的超链接指向的网页的重要性显然不如导航块、正文块中的超链接所指向的网页，所以前者会被分配到较少的 ， 而后者则被分配到较多的 。也就是说，网页中的无关信息区域在 计算过程中起的作用相对较小 ， 所以 效果要优于单纯的 B a , b Z a , X b , a , (1 ) ) p p 00448174 朱磊 本科毕业论文 11 第 3 章 天网 搜索引擎 块 搜索引擎 系统 一般包括 网页的抓取、预处理、存储、索引、检索等几个部分，其中预处理部分 的作用是 分析、 处理原始网页数据如去除网页噪音，消除重复网页，计算 文切词 等 等，并为后继模块提供统一的数据访问接口，规范数据管理，避免重复计算。同时 在天网搜索引擎平台中，基于功能扩展和实验室内部其他相关研究的需要， 必须将对原始网页的处理部分单独出来，从而方便模块复用，统一代码管理，减少重复劳动。 在天网搜索引擎平台的搭建过程中， 也包括了抓取、存储、分析（预处理）、索引、检索等模块，其中的分析模块 接受成批量原始网页的输入，然后对每个网页调用 块，进行 网页分块、信息提取等工作 ，最后将处理后的数据存成式，再提供给下游模块。 我的毕业设计的主要工作，就是围绕 从上面的介绍中可以看出，天网搜索引擎 块有两个比较重要的特点： 1、 可扩展性。 因为搜索引擎是一个比较 庞大的系统， 并且一直在不停的有新算法，新需求的加入，所以对数据的要求也会一直变化。而基于对原始网页数据集中处理的原则，为了应对下游模块可能提取的新的数据访问需求， 块必须具备良好的可扩展性 ，并且提供尽量多的各种类型的数据访问接口。 同时由于实验室人员的不固定性，代码的维护十分重要。我自己在刚开始阅读旧有的天网搜索引擎相关代码的时候，就常有十分难懂的感觉，无法复用已有代码，只好自己重新编写。 而正由于 块的可扩展性要求，所以它的代码的可阅读性也十分重要，在编写的过程中，我尽量 注意了这一点 ，遵守 了我们统一的代码规范 。 2、 独立性。 在我们实验室内部，除了搜索引擎之外，还有 据挖掘， 因此块必须能独立于搜索引擎代码之外单独编译运行，并且方便他人调用这部分代码。 00448174 朱磊 本科毕业论文 12 基于上述两个特点 ，我初步实现了 块。 该模块的类结构图 如下 ： 1、 图中右下及中间 蓝色的部分为 核心功能类，包括 四个类。 的作用 有两个，一个是 以原始网页为输入， 建立 一个是存储 分好的网页块 （在我们的系统中，每一个网页块就叫做一个 并记录 间的组织架构。 指代一个 每个 身就是一个的对象。 肩负网页分块的重任，从网页中识别出所有语义块。它依赖于前面的两个类。 依赖于 ， 它在分好的块的基础上，判断各个块的类型，提取正文信息。 这个类是整个 块最核心的类，目前功能只是初步实现，还有很大的改进空间，将来也可以根据功能将其分割成多个类。 00448174 朱磊 本科毕业论文 13 2、 中上部 绿色的部分为 块的评测和演示类，包括 个类。 是评测类，用来评测 心类的实现效果。当前实现的是对网页正文信息提取的评测，评测需要接受人工标记的网页或网页集为输入。评测算法的细节见后文。 演示类， 用来查看 前 可以查看 网页分块的效果，也可以查看主题信息提取的效果。 3、 最上面黄色的部分为 块的应用类 ，包括 ，它们都是利用分好的网页块实现的一些算法，比如基于 法，基于 网页消重算法，以及基于 网页分类算法。 4、 左下方灰色的部分 为 块依赖的外部类 接口，包括中文切词类及图中没有的编码转换类 等。 5、 中下部红色的部分为 块直接的下游模块，包括 和 。 页分块算法 算法 主体在 中。 参见在第二章相关研究里提到的，除了基于视觉的算法之外，大部分基于语义的算法都是利用 签 及其包含的文字信息 的特性 来给网页分块的。 并且由于大多数论文的着重点在于分块后的内容提取上，所以对分块算法本身着墨不多。 综合各篇论文里提到的分块方法， 我设计实现了 法。 这一算法首先的一大特点就是实用性强。 所谓实用性强是指适合在实际系统中使用，效率高，定义完整。 我详细分析了 定的 式规范，将所有规范的 签根据 法的需要分类，完整地列出了所有对网页分块起重要作用的标签，而不是像所有已有论文那样仅仅象征性地列举出几个 签。 分类后的详细 签清单如下： 00448174 朱磊 本科毕业论文 14 1、 超级 标签 （ 简称为 S 型标签） ： 这种标签 可以被直接认定是一个网页块的根标签 ，在 算法过程中一旦遇到这种标签，就可以直接将其加 入 网页 块池。 包括： 2、 大标签（ 简称为 B 型标签）： 这种标签 通常都代表一个网页块，只不过有时其内部内容过少，需要跟其他节点合并成一个网页块，或者在特殊情况下其内部没有可见字符。 所以在算法过程中，遇到这种标签，就判断其单独作为一个网页块的条件是否已经成熟，如成熟，则将其加入网页块池。 包括： 这里需要注意的是像 个标签也作为 B 型标签，原因是这样可以防止分块之后网页内部文字信息的遗漏，因为最终即使有遗漏，也会至少包含在 个最后把关的门神标签手中。 3、 排版标签（ 称为 L 型标签）： 这种标签 能影响到网页的显示效果，改变文字布局。 如果一颗 树中包含多个 L 型标签，则该子树单独成块的可能性增加。 包括： P, 4、 显示标签（ 称为 D 型标签）： 这种标签 数量最多，都是对文字的显示方式做微幅的调整，如改变字体、颜色、粗细等等。 由于它们的存在与否不改变网页布局，所以不影响网页分块。包括： A, B, I, Q, S, U, O:00448174 朱磊 本科毕业论文 15 5、 附属标签（ 简称为 A 型标签 ） ： 这种标签 从属与上述四种标签的某一种， 同时有些也出现在了前面四种里面。由于它们一般不单独出现，对网页布局的影响体现在了其属主标签中，所以 在 法中也不予考虑。 包括： 6、定制标签（ 称为 C 型标签）： 因为不同的应用中，对网页分块会有些不同的要求。比如我们实验室的组在进行新闻网页的数据挖掘的工作中， 需要使用到网页分块，但是他们特别需要提取该新闻网页的发布日期和时间，而这部分内容通常是在新闻标题 与新闻正文之间的一小行文字，正常的网页分块程序并不会将其单独提取成一个网页块。所以我添加了定制标签，由用户指定，它可以是普通的标签如“ ，也可以是正则表达式，凡是其内部文字满足该正则表达式的 S 型、 B 型和 L 型标签，都将 被单独提取为网页块。例如： 在明确了各 签的类别之后， 利用 各标签节点 的类别信息和内 部文字长度 ，以 及 其 子标签节点的类别信息， 对 底向上遍历，在遍历的过程中不断判断出新的网页块，并加入网页块池中，当遍历到最上部的节点时，算法结束，网页分块完毕。 法的核心伪码如下： _ 某单个网页构建的 制标签 (C 型 )节点列表 1 用 叶子节点，也就是文字节点 建立 一个 当前 节点 队列 ，开始自底向上遍历。 2 取 当前节点 队列 的第一个节点 。 3 如果遇到 S 型节点，则立即将此节点加入网页块池。 4 如果遇到 C 型节点，则立即将 此节点加入网页块池。 5 如果遇到 B 型节点，则判断 该节点内部的文字长度是否已超过阈值，或00448174 朱磊 本科毕业论文 16 者该节点内 部的 L 型节点比例是否超过阈值，如果满足上述两个条件之一，则将此节点加入网页块池 ；否则将其内部文字长度信息和自身信息向父节点传递，然后将父节点加入当前节点队列，回到 2。 6 如果遇到 L 型节点 ，则将其内部文字长度信息和其自身信息向父节点传递， 然后将父节点加入当前节点队列，回到 2。 7 如果遇到 D 型或 A 型节点，则将其内部文字长度信息向父节点传递，然后将父节点加入当前节点队列，回到 2。 8 当前节点队列为空时，遍历结束 ，算法终止。 _ 网页块池中的网页块是以 格式存储，而 中包括原来的 树的 构和其他相关信息，同时在上述遍历的过程中，即使有的网页块从 构上来说包含在更高层的网页块之下，但在也消除了包含关系，所有网页块都互相独立，互不包含。 页 主题 内容提取 算法主体 在 中。 采用了基于规则和基于 语义分析相交的方法，也就是分别用基于文本相似 度的方法和基于 方法判断每个网页块的类型（是不是主题块），然后对它们求交集，只有两个方法共同认定的主题内容块才能最终被认定。 法的核心伪码如下： _ 第一步， 基于文本相似度的