（计算机应用技术专业论文）基于平面图的网页分块算法的研究.pdf

大连理工大学硕士学位论文 摘要 随着网页结构的复杂化与内容的多主题化，搜索引擎的结果越来越无法满足人们的 需求，因为网页作为最基本的信息获取单位已不再合适，要更准确的获取、e b 上的信息， 就必须对网页进行分块。 然而，现有的网页分块方法多是在d o m 结构上的启发式方法，如v i p s ( v i s i o nb a s e d p a g es e g m e n 诅t i o n ) 。这种方法简单易实现，效率也较高，但不具有普遍适用性。另一 种基于图论的方法g 掰p h a p p f o a c h ，它将网页转换成图来表示，然后对图进行划分，得 到划分结果再映射到网页上。该方法能够应用到w e b 上所有的网页，具有普遍适用性， 但由于代表网页的图非常大，划分困难，效率较低，不具实用性。 针对现有网页分块方法不足，本文提出一种基于平面图的网页分块算法。该算法 首先将抽取网页结构和视觉信息构造一个无向加权图，其中图的顶点是网页d o m 树中 的可视叶子节点，图的边为浏览器中显示的节点位置关系。接下来通过g o m o r y h u 算 法对图进行划分，从而实现网页分块。由于这种结合使用结构信息和视觉信息构造的图 是平面图，因而算法效率很高。同时，( 论m o r y h u 算法可以很好地保证图划分的质量。 实验表明，同v i p s 算法以及d e e p a y a n 的图论算法相比，本文算法的准确率和召回率均 有很大提高，同时算法运行时间远远低于d e e p a y a n 的图论算法。 关键词：网页分块；h t m ld o m 树；g o m o r y h u 算法；平面图 基于平面图的网页分块算法的研究 w e b p a g es e g m e n t a t i o na l g o r i t h mb a s e do np 1 a n 2 u r 研印h s a b s t r a c t n o w a d a y s ，p e o p l er e l yo ns e a r c he n g i n et 0f i n di 塔e m li i l f o m a t i o n 丘d m l e 、耽b ， t h ev 王s ta n df a p i d l y 殍- 0 w i l 玛r 印o s i t 0 巧o fi i l 内 衄a t i o n h 0 w e v e r ，s i n c ew e bp a g e sa r eu s u m l ye m b e d d e dw i 廿lv a r i o i l sk i n d so fv m 妇b l es e m 跹t i ci 1 1 f o r m a t i o 玛也e ya r en o t a t o m i cu n i t sf o ri n f o m a t i o ns e a r c ho nt l l ew e b w e bp a g es e g m e m a ：t i o 玛、) l ，：h o s e 缅 i st 0p a r t i t i o naw e bp a g ei i i t 0v i s u 甜1 yc o n t i m l o u sa n dc o h e s i v er e g i o n sw i t h 疵f i e d m e m ei l lc o n t e n t 趴dp u 印o s e ，i s 趾e s s e n t i a lt a s ko fw e bp a g eu i l d e r s t a 】1 d i n g t r 习l d i t i o i l a l 印p r o a c h e st o 、) ，e bp a g es e g 阻e n t a t i o nl l s u 豇i yu s eh e u r i s t i co rm a u c m n e l e a 玎：1 i 1 1 9a l g o r i 吐1 l n s t 0a i l m y z e 也ed o ms 扛u m 聆o f 也ep a g e ，e 汕e rb y 、，i s u a la 1 1 a l y - s i s0 ri n t e i p r e t i n g 吐l em e a l l i 】呜o f 切g s 臼咖e si ns o m ew a y w 1 l i l et h e s ea p p r o a c h e sm i g h t 、o r kw e l lo ns o m ek i n do fp a g e s ，也e ys t i l lk ep r o b l e m st l l a tl i l i l i tt h e mt 0 b eu m v e r s a l 印p l i c a b l e v e 巧r e c 训y ，c h 蛐a n ie ta 1 d e a h 、) l ，i mw e bp a g es e g m e n t a t i o n 丘- 0 mag r a p h - t 1 1 e o r e t i cp e r s p e c t i v e ，h o w e v e r ，m eu n d e d y i i l g 孕a p ho f 也i s 印p r o a c hi st 0 0c o m p l e x ，m a k i l 玛m et a s ko fs 0 1 v i i l g 廿l em i i l i m i z a t i o np r o b l 锄v e 巧d i f j i c l l i 吒n u st h i sa p l ) a c hi sn o te 旃c i e n t 锄dd o e sn o ts l l i tf o rr e 砌印p l i c a t i o n s w ep r o p o s ean 0 v e lw e bp a g es e g m e n t a t i o na l g o r i t h mb a s e do n 血d i n g 也eg o m o 巧- h u 仃e ei nap 1 撇g r a p h 1 ka l g o r i 也m 触l yd i s t i l l s s i o na 1 1 ds t i 咖i n f o 珊 一a t i o nf b maw e bp a g et 0c o n s t m c taw e i 曲：t e du n d i r e c t e d 鲫kw h o s ev 矾c e sa r e 廿1 el e a fn o d e so ft l l ed o m 白哈ea n d 廿1 ee d g e sr 印r e s e m 血e 、r i s i b l ep o s i t i o nr e l a t i o i l s 坷pb e 铆e e nv e f t i c e s 1 1 1 e ni tp 硎t i o l l sm e 鲫h 谢m 吐瞎g o m o 巧一h un 优b a s e dc l u s t e 血ga l g o 血h m s i n c e 吐l e 舒a p hc o 删e db yb o t h 、，i s i o n 趾ds 仃咖i n f o m a t i o ni sap l 砒m r 铲印吣也ea j g o r i 廿l mi sv e r ye f ! f i c i e n t m e 缸m 缸l e ，也eq u a l 埘o f 铲a p hp - a r t i t i o nc a nb e 母l a ：鼬t e e d 也r o u g h 也eu s eo fg o m o 巧一h ua l g o r i 也m e x p e r i m e n t 甜r e s u l t ss h o wt t l 矾c o m p a r e d 埘t hv i p sa n dc h a k 曲a n ie ta 1 s 鲫ht h e o r e t i ca l g o f i t h m ， o u ra l g o r i 也mi i i l p r o v e su p o n 也eo t l l e rt w o 、) l ，i t hm u c hh i 曲e rp r e c i s i o na i l dr e c a l i ，a - n di t s1 1 m n 迦t i m ei s 缸1 0 啊t h a n 吐成o fc h 出曲a r t ie ta 1 s 鄹岫m e o 硼ca l g o r i - t b m k e yw o r d s ：w e b p a g e 轮g m e n t a t o n ；h t m ld o mt r e e ；g o m o r y - h ua 【g o r i t h m ； p 【a n a rg r a p h i i 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目 作者签名 导师签名 ：蕉立墅血逢盛园巡警叠圣李笙 ：! 望些日期：型2 年j 三月曼日 ：争幺乒一魄丑年上月盟日 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他己申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，i 本人愿意承担相关法律责任。 学位论文题目： 作者签名：望丝日期：丝里z 也月旦日 大连理工大学硕士学位论文 1 绪论 1 1 研究背景 在网络信息时代，如何在互联网上迅速找到有用的信息是非常重要的问题，也是近 年来计算机科学的热点之一。然而由于网页结构的复杂性与内容的多主题性，信息检索 的结果常常无法满足人们的需求。其中一个重要原因是大部分信息检索系统将网页作为 互联网上最基本的信息获取单位。事实上，一个网页上通常包含多个语义单元，每个单 元在视觉上形成页面上的一个连续的区域，通常称作网页的块。以块为单位才能更准确 地定位用户所需要的信息。因此，如何发现这些语义块，鄙如何对一个网页以语义块为 单位进行分割，对提高信息单元排名精度以及信息获取精度都是十分关键的f l 司。 不仅是在信息检索中，在许多其他网络应用中都涉及到了网页划分。例如，在网络 信息存取中，为了解决顺序浏览以及关键词搜索的局限性，有些学者提出使用数据库技 术中的包装器( 砌a p p e r ) 来对网络数据进行结构化，而在构建包装器的过程中，就需要 将网络文档分割成多个信息块。另外一个应用就是近年来日益受到关注的网页链接分 析。在过去的研究中，链接分析算法是建立在一个假设的基础上的，即：如果两个网页 之间存在着一个链接的话，那么这两个网页整体之间就存在一定的关联。这种做法充分 考虑了每一个链接对网页间关联的影响，但缺点也很明显，它对同一网页中的不同链接 总是不加区分地同等处理。近来的研究发现，在大多数情况下两个网页之间的链接仅仅 表明这两个网页的某些部分之间可能存在着一定的关联，而并不代表这两个完整的网页 之间也存在着这样的关联。另外，大量噪声链接的存在更是会给算法带来主题漂移的问 题。对网页进行分块后，区别对待不同分块中的链接，使链接分析更加具体化，从而得 到较好的结果。此外，随着个人掌上电子设备的普及，利用掌上电子设备进行互联网信 息浏览成为可能，而在使用掌上电子设备小巧的显示屏进行较大网页的浏览时，自然需 要对网页进行分割，从而使信息的浏览更具直观性和目的性i l 】。 因此，研究网页分块问题对信息检索、网页信息提取、链接分析以及小型电子设备 浏览网页等网络应用都有着重要意义。国内外众多知名学者已投入了网页分块问题的研 究，并提出多种可行方法解决问题。 1 2 国内外研究现状 根据实际应用的需要，网页分块的内涵略有不同。在识别信息与非信息，去除网页 垃圾信息中，只需要将网页分为两部分。在链接分析与搜索引擎中，对网页分块就要求 去除网页中的垃圾内容，识别出网页的主要内容。在手机浏览网页的技术上，需要将网 基于平面图的网页分块算法的研究 页显示在小屏幕上，这时对网页分块是对整个网页进行划分。本文的研究重点主要是在 网页的主要内容上，即去除非重要信息分块，只保留重要信息分块。我们将一个分块定 义为h n 儿文档的一个片段，它在浏览器上显示为一个连续的区域。例如：导航条， 网页的相关链接，网页中的广告，网页中关于体育信息的内容，关于电影的内容或者关 于其他主题的内容都是网页的一个分块。 目前已有多种网页分块的方法，我们对这些方法进行了分析并归结为四类： ( 1 ) 基于启发式规则：v m s 一种基于可视化信息进行网页分块的方法是这类方法 的代表，它从网页中提取出的结构与可视化信息，依据启发式规则，对网页进行分块。 该类方法【铀】简单易实现，效率也较高，但不具有普遍适用性，对某一类网页效果很好， 对另一类就不一定有效果。 ( 2 ) 基于机器学习：s h u m e e te ta 1 【_ 7 j 将网页分块问题转化为机器学习的问题，通过 决策树来进行网页分块。该类方法虽然有很强的数学理论基础，但由于涉及相关性判断， 故不能保证分块结果的正确率。 ( 3 ) 基于模式识别：p e i f i e n ge ta 1 【8 】事先定义一些普遍的模式，然后在布局树中搜 索这些模式，主要是用于基于网站进行的网页分块。该类方法需要人为去识别模式，适 用于某个特定的网站，不具有普遍适用性【9 1 0 1 。 ( 4 ) 基于图论：d e e p a y a ne ta 1 f 1 1 j 在2 0 0 8 年提出了基于图论的方法进行网页分割， 并首次将网页分块问题转化为加权图上的组合最优化问题。它将网页转换成图来表示， 然后对图进行划分，得到划分结果再映射到网页上。该方法能够应用到、e b 上所有的网 页，具有普遍适用性，但由于图的构造方式，使得代表网页的图非常大，图划分困难， 效率也较低，不具实用性。 1 3 本文工作及组织 针对现有网页分块方法不足，本文提出了一种新的基于平面图的方法进行网页分 块。首先利用网页的结构信息与可视化信息构造代表其信息的无向加权图，然后基于图 论分割算法进行图划分，最后将图划分结果映射回网页，得到最终分块结果。本文设计 了一种新的平面图构造方法，并采用基于( 蛔m o 巧 王u 的算法进行图划分。g b m o r y h u 算法【1 2 】图论中的经典算法，用于求解图的最小流割等价树，具有理论最优解的特性。它 只需要求解n 1 ( n 是图的顶点数) 次最大流就能够最优地将图划分为k 个子图。我们 基g o m o r y h u 算法进行图划分，不仅具有理论最优解，而且较般图分割算法速度快。 本文的主要内容安排如下： 一2 一 大连理工大学硕士学位论文 第一章首先介绍了网页分块的研究背景和意义，然后总结了目前国内外的研究现 状，以及各种方法的优缺点，最后阐述了本文所做的工作以及本文的结构安排。 第二章主要介绍了h n 儿d o m 树结构以及图论的相关知识，是基于平面图网页分 块算法研究的重要基础。 第三章详细说明了v i p s 以及( 如p h t h e o r e t i ca p p r o a c h 两种网页分块算法的原理及 算法，是本文基于平面图的网页分块算法研究的基础。 第四章详细阐述了本文提出基于平面图的网页分块算法的图构造方法，描述了基于 图论g o m o 巧h u 算法的平面图划分方法。 第五章通过实验，与v i p s 以及渤p h 1 1 l e o r e t i ca p p r o a c h 两种算法进行对比，证明 了本文方法的有效性与实用性。 第六章为总结与展望，总结了本文的工作，并对以后的改进提出了一些想法。 基于平面图的网页分块算法的研究 2 相关知识介绍 本章主要介绍了基于图划分的网页分块的预备知识，包括h n 血d o m 树以及图论 相关知识。h 眦是一种制作网页的语言，有着它自己的规范与特点。d o m ( d o c 啪e n t 0 b j e c tm o d e l ) 可以将网页中的标签按照嵌套关系整理成一棵树状结构。要研究网页分 块，必须先对h t m ld o m 树结构有所了解。图论是研究具有独特性质的个体之间的关 系的数学理论和方法，虽其源于数学，但是应用非常广泛。本章回顾和总结了图论中的 基本理论，包括一些基本定义，定理和基本算法，这是我们进行平面图网页分块算法研 究的基石。 2 1h t m ld o m 树 h n 皿d o m 定义了一套标准的针对m m l 文档的对象，把h n 儿文档呈现为 带有元素、属性和文本的树结构( 节点数即h t m ld o m 树) 。根据d o m ，h t m l 文 档中的每个成分都是一个节点。d o m 规定：整个文档是一个文档节点；每个h t m l 标 签是一个元素节点；包含在删，元素中的文本是文本节点；每一个h t m l 属性是 一个属性节点；注释属于注释节点；节点彼此都有等级关系。h n 儿文档中的所有节 点组成了一个文档树( 或节点树) h 踟l 文档中的每个元素、属性、文本等都代表 着树中的一个节点。树起始于文档节点，并由此继续伸出枝条，直到处于这棵树最低级 别的所有文本节点为止。 图2 1 表示一个文档树( 节点树) ： 文挡 根元索： li 元索：元索： l h r e f ll ( a i文本：文本： 文本： 。文挡标题。我的链接4。我的标题 一4 一 大连理工大学硕士学位论文 图2 1 文档树 f i g 2 1 d 0 c u m 踟t t r e e 节点是d o m 的基本概念，节点的特有类型，例如：d o c 咖e n t ，e l e m e n t 等等都是 从基础的n o d e 接口继承的。d o m 的设计基本原理是“每个事物都是节点，n o d e 接 口包含基本节点操作所需要的全部方法和属性，但是不包含节点的创建。节点的创建是 由d o c u m e n t 接口来处理的。 n o d e 接口中提供了很多的属性，比如n o de _ n a m e ，n o d e v a l u e 和a 缸h l t e 。之所以提 供这些属性，是为了检索他们提供的信息，而不必将他们设定为特定的类型。在很多的 实际工作中都有对于节点类型的访问的要求。我们简要介绍几种比较重要的属性和方法 如表2 1 所示。 表2 1n o d e 接口属性和方法 t a b 2 1a 倒b u t e sa i l d 印p r o a c h e so f n o d ei n t e r e 属性和方法 含义 p 鲫舶t n o d e该节点的父节点 c h i l d n o d e s该节点的子节点列表 f i r s t c h i l d 第一个子节点 l 嘲c h i l d 最后一个子节点 p r e v i o u s s i b l i n g n e ) ( t s i b l i n g 节点的前后节点 a 慨b u t e s 包含一个n 锄e 心甜絮置黧鬈构表示一个附在该节 o w e r d o c u m e n t包含了一个对于根节点的引用 表2 1n o d e 接口属性和方法( 续表) t a b 2 1a t t r i b u t e sa n da p p m a c h e so f n o d ei n t e m l c e 属性和方法 含义 i l a 【i i l e s p a c e u p r e f i 】【 l o c a l n 锄e i 】1 s e 旭e f o o r 印l a c e c h i l d o r e m o v e c h 订d 0 印p e n d c h i l d ( ) 节点命名空间u 刚 命名空间前缀 该节点的限定名称的局部部分 在该节点的制定子节点之前插入新节点 用一个新的节点代替该节点指定的子节点 删除o l d c h n d 参数指定的子节点 给该节点添加一个新的子节点 下面我们来介绍和网页处理密切相关的其他几种重要节点： 一5 一 基于平面图的网页分块算法的研究 d o m h t l p l 锄e i l ：僦0 n 接口。该接口提供了一些不依靠d o m 文楷的任何单独的方法。 我们可以使用这个接口来测试d o m 具体实现是否实现了某一个接口或者是功能。 d o c u m e n t 接口。它表示了整个文档。是文档树的根节点。它包含了创建各种节点 所必须的f a c t o 巧方法。其他几个重要的方法和属性都在表2 2 中进行了描述。 表2 2d o c u m e n t 接口属性和方法 t a b 2 2 a t t r i b u t e s 鲫d 印p r o a c h e so fd o c 啪e n ti n t e 幢l c e 属性和方法 含义 d o c t y p e i m p l e m e n 眦i o n d o c 啪e n t e l e m e n t c r e a t e d o c u m e n t f r a g m e n t o c r e a t e e l e m e m o c r e a t e t 铡= t n o d d a t a ) i m p o r t n o d e o 文档类型 该文档的实现对象 该属性提供了对子节点的直接访问，该子节点表示文档的根 元素，也就是h n i l l 文档的标签 创建一个空的d o c u m e n t f r a 舯锄t 对象 创建一个提供了标记名称的新元素。例如一个i m g 元素， 但没有插入到文档中 创建一个t e 斌节点，d a t a 是节点的初始内容 把其他文档的内容导入该文档 实际上，d o c 眦e n t 接口还有很多的方法和属性，但是他们的名字都十分的直观， 可以很容易的理解他们的含意。 d o c 啪e n _ t f r a g m e n t 接口。作为一种轻量级的方式添加，它可以析取文档的一部分并 且处理它们。 e l e m e m 接口。在h n l l 文档中，e l e m e m 接口表示一个元素。元素从n o d e 接口继承。 其中比较重要的属性有：t a g n 锄e ，可以直接得到元素的名称。g e b u t e 方法可以得 到一个属性值，它把舭值以字符串的形式返回。 a t t r 接口。表示e l e m e n t 对象的属性，也是从n o d e 节点继承的，但是它并不是d o m 树的一个节点，也就是说，如果想读取它的p a r e n n o d e ，p r e v i o l l s s i b l i n g 属性的值，将会 返回一个n u l i 。 c o n l i i l e n t 接口。它继承自c h a r a c t e r d a t a 接口，表示h 廿n l 或x i i l l 注释的原文内容。 t e x t 接口。继承自c h a r a t e r d a t a 接口，表示e l e m e n t 和舭对象的原文内容。 2 2 图的定义与基本概念 ( 1 ) 图的定义 一6 一 大连理工大学硕士学位论文 图是由若干给定的顶点及连接两顶点的边所构成的一种拓扑图形，这种图形通常用 来描述事物之间的相互关系，例如用顶点代表事物，用连接两顶点的边表示相应两个事 物间的关系。数学上，图g 定义为一系列的顶点v 和连接这些顶点的边e 的集合。通 常图g 可以写为g = v ，e ) ，每条边对应着一对顶点，即e 属于v v 。图2 2 描述了一 个简单的图，图中用点来表示顶点，用点之间的连线表示边。 j l 图2 2 图的示例 f i g 2 2e x 锄p l eo fg r a p h 一个图通常包括这么几个部分： 顶点集合v 顶点是图中的基本元素，它代表图中相互关联的个体，如图2 2 第i ，j 个顶点，我 们分别用v i ，m 表示。顶点的集合v 就可以表示为v ( g ) = v l ，v 2 ，v i ，v j ，v n ) 。 边 边是指图中连接两个关联的顶点的连线，如图2 1 中连接第i j 个顶点的边，可以 表示为e k = e 自= v i ，v j ，它表示两个顶点之间的联系。边的集合e 可以表示为 e ( g ) = e l ，e 2 ，e n i 。边又可以分为有向边和无向边，当e i j = v i ，v j ) 为有向边时，称v i 为起点，v i 为终点。 权 权是指分配给连接两个顶点的边的一个数值，它表示这两个顶点的关系的紧密程 度，例如图2 2 中连接第i ，j 个顶点的边e j 的权值为s i j 。一个带有权值可以表示为 g = v ，e ，w ，其中w 为图的权值矩阵。 ( 2 ) 图的基本概念 结合图2 2 我们介绍图的几个重要的基本概念： 顶点的度 基于平面图的网页分块算法的研究 顶点的度是指图中与其关联的边的数目。对于带权的图，顶点的度定义为连接某个 顶点的所有的边的权值之和，例如顶点v i 的度为。对于有向图，顶点的度有分为入度和 出度。入度是指射入顶点的边数，出度是指射出顶点的边数。 顶点的度的大小反映了顶点和图中其他顶点的联系紧密程度，度越大的顶点往往是 图的“关键点。而度为零的顶点被成为孤立点。因此度和权值都是图的分割中首要考 虑的两个重要的参考量，权值较大的边连接的两个顶点属于同一类，而度很小的顶点或 者孤立点则自成一类。 连通图和图的直径 设图中有一条从顶点v l 到v n 的有限顶点和边交替序列v l e l v 2e 2 v n j e n 1 v n ，其 中与边e i ( 1 i n ) 相邻的两顶点v i ，v 计l 正好是e j 的两个端点，则称这个序列为从v l 到v n 的一个途径，如果序列中所有顶点均不相同的途径称为道路。图g 中的两个顶点 如果存在道路，那么称这两个顶点是连通的。如果图g 中任意一对顶点都有一条道路， 则称图g 是连通的。 从顶点v i 到v n 的道路的最小长度称为v l 到v n 的距离，把图中所有顶点之间距离 的最大值称为图的直径。图的连通性反映了图中各区域之间的关联程度，而图的直径则 反映了图的松散程度的上限。在对图进行分割时，图的各个连通分量很自然的被分成分 立的子图。 图的阶和容量 图的顶点的个数称为图的阶，图的容量是指图内部所有边的权值之和。图的阶和容 量都是描述图的尺度的量度，只是一个从顶点数目考虑，一个从边的数目和权值考虑。 当对图进行分割时需要考虑所分的子图的阶和容量的大小，过分细小的分割是没有意义 的。 子图和割 设图g - v ，e ) ，g l = v l ，e l ，如果vl 属于v ，e1 属于e ，则称g l 为g 的子图。 如图2 3 中g l 和g 2 都是g 的子图。 一8 一 大连理工大学硕士学位论文 g 1 图2 3 子图与割 f i g 2 3s u b g r 印h 勰dc u t s 对于子图g 】- v l ，e l ，g 2 = _ ( v 2 ，e 2 ) ，如果v 】并v 2 为v ，则称g l 和g 2 互为补图。 若将图二分为互为补图的子图，连接两个子图的边的集合叫做割集。如图2 3 中两 个子图g 1 ，g 2 之间的虚线所表示的边既是一个割换句话说，一个割集s 是这样一个边 集：在g 中去掉s 中的所有的g 变成具有二分支的分离图，但是只去掉s 中的部分边， 图将仍然是连通的。割集的权值之和称作割。 2 3 平面图划分算法 在研究如何将图理论运用于图分割之前，我们首先介绍几种图划分算法，这些算法 是图理论的重要研究成果，也是我们拿来做图分割的基础。 ( 1 ) 能量最小化法 人们研究发现，最小割最大流方法可以将计算机视觉中的某个能量函数最小化。在 基于图论的方法中，这个能量描述为 e ( 三) = 印( 印) + 场9 ( 印，幻) ( 2 1 ) 其中，上= 印ip d 是对网页i 的标签( l a b e l i n g ) ，d p ( ) 是数据惩罚函数( d a t a p e r 谢够f 衄c t i o n ) ，v p q 是交互位势( i n t e r a c t i o np o t e n t i a l ) ，n 是所有相邻像节点对的 集合。以网页分块标签( h n a g el a b e l 吨) ( 网页分块实际上是将网页的区域进行标签 的过程) 为例，d p ( ) 表示在已知网页特征和可能性函数的前提下，对每个分块进行的 标签选择，而v p q 通过惩罚相邻页快间的不连续性来保证空间的一致性。 ( 2 ) 谱方法 对一个已知的量确定描述其特征的坐标系，称为特征分析( e i g e na n a l y s i s ) ，主要 包括求解特征值与特征向量的问题。在矩阵代数中，特征分析往往与矩阵的谱分析联系 在一起：一个线性算子的谱定义为该算子矩阵特征值的集合，而描述线性算子特征的基 本向量定义为其特征向量的集合。在图论中，人们最早使用矩阵理论和线性代数方法来 一9 一 基于平面图的网页分块算法的研究 分析图的邻接矩阵( a 由a c e n c ym a t r i x ) 或关联矩阵( i n c i d e n c em a n 叔) 的谱，在规则和 对称矩阵上面取得了非常好的效果。 在图论理论中，进行图谱分析的一个主要目的是通过图谱( 娜s p e 蝴) 来发 现图的主要性质与结构。因为特征值往往非常紧密地与图的几乎所有不变量联系在 起，它们反映图的极值性质，并且相互联系。可以说，特征值对于图的理解来说至关重 要。谱方法就是求解网页的相似度矩阵特征向量对网页进行分割。因为特征向量的值是 连续的，而网页的分割是离散的，需要采取一定的方法将连续的特征向量转变为离散的 分割门限。 ( 3 ) 最大流最小割法 最大流最小割法是图论中的经典方法，具有理论依据，对于平面图划分有着很好的 效果。我们首先介绍最大流最小割定理： 定义l ：设n ( s ，t ，v ，e ，c ) 是一个网络流。其中，v 代表顶点集，e 是有向图g ，e ) 的有向边集，s 、t 是v 中两个不同的点，称为始点和汇点，每条边( v i ，v j ) 属于e ， 伴随一个容量c ( c a p a c i 劬，表示为c i ，) 容量指定了从v i 到v j 通过流( v i ，v j ) 的上限。 定义2 ：给定一个网络流n ( s ，t ，v ，e ，c ) ，流( n o w ) 是一个函数，为每条有向边( v i ， v ) 属于e 赋予非负数f ( v i ，v i ) 满足以下条件： 0 s 厂( 哆，v ，) c ( m ，y ，) ( 2 2 ) 【 ) e e 厂( ，d = ( v ，脚( 1 ，材a v 矿一 ( 2 3 ) 定义3 ：给定一个网络流n ( s ，t ，v ，e ，c ) ，n 的“最小割就是寻找割集的最小值c m ，v t ) ， 把顶点集v 划分为两个不连接的集合v 。和v 。，其中 s k ，r 巧，c ( k ，巧) = ( 匕，v ，) f ( b ，1 ，) e e k 1 ，杉) ( 2 4 ) 最大流最小割定理( f o r d f u 墩e r s o i l 1 9 6 2 ) ：存在一个割，其容量= 最大流的流量。 亦即，具有容量限制的最大流的流量= 最小割的容量。 f o r d 和f 皿e r s o n 已经证明了，在同一个网络流n 中，s - t 最大流问题等同于s t 最小割问题。因此，称此类问题为最大流最小割问题。基于f o r d 和f u l 】姒s o n 理论，提 出了许多有效的最大流最小割算法。最短增广路径算法就是一种非常有效的算法，复杂 度为o m 2 ) 。 我们选择基于最大流最小割理论的g o m o d r h u 算法对网页的平面图进行划分。 g o m o 巧h u 算法图论中的经典算法，用于求解图的最小流割等价树，具有理论最优解的 特性。它只需要求解n 1( n 是图的顶点数) 次最大流就能够最优地将图划分为k 个 大连理工大学硕士学位论文 子图。使用g o m o 巧- h u 算法不仅保证图划分具有最优性质，同时平面图上g o m o 巧一h u 算法的运算效率非常高。因此，本文算法在求解质量和计算效率方面都有很好的保证。 s 图2 4 最大流最小割 f i g 2 4m a x - f l o wa n dm i n - c u t s i n k 基于平面图的网页分块算法的研究 3 网页分块方法详述 本章首先介绍了两种现有的算法：v 口s ( v i s i o n - b a u s e dp a g es e 舯e i i t a t i o n ) 和基于 图论的方法g r 印h n l e o r e t i ca p p r 0 2 u c h 。v i p s 是一种基于视觉效果的网页分割方法，是 网页分块方法中的经典算法。基于图论的方法是一种新的较严密的网页分块的方法，它 将问题转化为加权图上的组合最优化问题来解决，为网页分块问题开辟了一片新的天 空。 3 1vip s 3 1 1 算法概述 基于视觉特征的网页分割算法v p s 不同于以往的网页处理技术，它充分考虑了人 们的视觉感知对网页主题获知的影响。在此算法中，网页被表述成一个分层的语义结构， 这个结构的每一个结点对应着网页中的一个具体分块，而这些分块与人们对一个网页的 观划分是较为一致的。每个分块都被赋予一个表示相关度的值d o c ，d o c 值用衡量每一 个分块之间在视觉空间上的内容一致度。 基于视觉特征的网页分割算法是一个自上而下的过程，如图3 1 所示，它可以概括 为三个步骤：分块抽取、分割符探知以及网页内容结构构建，这三个步骤可以循环执行。 关于以上三个步骤的详细过程，我们将在下面的三节中作相关阐述。 ( 1 ) 分块抽取 图3 1v i p s 算法流程 f i g 3 1v i p sa | g o r i t h m 图 围 大连理工大学碘士学位论文 分块抽取是依据视觉信息在 讥网页的d o m 树结构上进行的节点提取。一般来 说，d o m 树的每一个节点是可以表示一个视觉上的分块的，但是也存在像 、 、啪、 、 这些能够影响外观的标签，而外节点则是包含除上述标签以外其它 标签的节点。根据节点在浏览器中所代表的内容以及其子节点的特性又可以将节点分为 有效节点、文本节点和虚文本节点。有效节点代表的内容通过浏览器可以直观地看到， 节点的高度和宽度都不为0 ；文本节点则对应着不包含h r m l 标签的文本：如果内节点 的子节点全部都是文本节点或者只含有文本节点和虚文本节点，那么这样的内节点就称 为虚文本节点，如图3 0 为分块抽取示例。 a jb j 图32 分块抽取示例“1 f 嘻32 v b 删u o c k 强h n i o f as 砌p l 。p 帮 根据以上的定义我们可以制定出一些用于划分分块的重要依据：标签、颜色、文 本以及太小。标签畸等经常作为视觉上区分不同主题的依据，所以如果一个d o m 节点包含这类标签，那么就将这个结点继续划分。一个内节点如果有一个子节点是外结 点，那么这个内节点也需要继续划分。有些节点的背景色与其某个子节点的背景色不同， 善熬，兰篓至掣篓虽 喜三霎 一一量一。 一 善挚盟f荸筐 廑袅巨璧 l 基于平面图的阿页分块算法的研究 这时就要将这个节点划分，但是在这一轮划分中，与其不同背景色的子结点并不进行划 分。当一个节点的大多数子节点是文本节点或者虚文本节点时，这个节点需要继续进行 划分。如果个节点的大小超过了预先设定的阀值，那么这个节点也需要继续划分。上 图即为一个分块抽取示例。 ( 2 ) 分隔符探知 在将所有分块抽取出来并存储在池中以后，接下来要进行的是分割符的探知。分割 符定义为网页中可见的、不与分块相交的水平或竖直线，这些水平或竖直线最适合在视 觉上区分网页中不同语义的内容。 由于分割符有水平、竖直两类，所以在分割符探知过程中，需要分别从水平、竖直 两个方向进行探知，其算法描述如下： 初始化分割符序列。在初始情况下，分割符序列中只有一个初始分割符，此分割 符的大小与池中整个页面的大小一致。 随着分块的不断被抽取出来加入弛中，要对分割符进行不断调整，规则如：如果 分块包含在分割符内，则将分割符划分；如果分块与分割符相交，相应改变分割符的大 小；如果分割符贯穿分块，则删除分割符。 删除位于存储池4 个边的分割符。 在实际执行时，可以按照上述算法描述先进行水平方向的操作，再进行竖直方向的 操作，最终得到所有分割符，如图3 3 所示： _ j i 已1 j i “i i 霹”量i 妾 量亘- 塞雾霆 l 嵋1 | 一ll i li ii i 鲤口= 圈j 鲥：1 甜i s 1s 2 。s i s 2 。s l 。s 2 善 c l 图3 3 分隔符探知过程“1 f 遮3 jas 枷棚o p a g ea r i d 由e 珊脚山：b e c t i o n p o e 大连理工大学硪士学位论文 由原始两页划分成的分块都具有一定的语义内容。而这些分块依靠分割符进行区 别，因而分割符的权值可以依据相邻分块间内容上的差异度来进行设定。具体规则如下： 分割符两边分块的距离越远，分割符的权值越大： 分割符与某些特定的加 眦标签( 如标签船等) 重台，则权值较大； 分割符两边分块的背景色不同，则权值较大； 对于水平分割符，如果其两侧分块中字体的太小等特征差异越大，则权值越大； 如果上方分块中的字体大小耍小于下方分块中的字体，则权值较大，字体大小差异越大， 权值越大。但是当两侧分块中的内容较为相似时( 如都是纯文本信息时) ，水平分割符的 权值就较小。 ( 3 ) 网页内容构建 当对一个网页进行了分块抽取和分割符的探知、赋权值等操作以后，就可以根据网 页内容构建网页的结构框架了。由权值最小的分割符开始，将其两边的分块合并构成新 的分块，重复执行此过程，直至遇到权值最大的分割符。新分块的d o c 值则根据分割 符的权重设置。在合并操作结束以后，检查合并后的分块是否满足粒度需要但d o c 值 大于p d o c 值。如果满足需要，则根据合并结果构建起整个网页的内容结构；如果不满足， 则要重新进行新的子分块抽取操作，图34 为网页内容构建示例。 d 砸d 鸯 龟：菱 卜m 慕；“l ；匝 o 卜五曰c 砷 压四 盈；燮 五e d = q 窿。 ，h 玉1 9 = ( a 、 ( b j( c )( d ) 图34 阿页内容构建示铡 f 培34 a 蛐脚eo f c 0 e m n m c 帆c o 他们c l i o n 雾 基于平面图的网页分块算法的研究 3 1 2 算法分析总结 v i p s 算法使用视觉信息与启发式规则进行网页分块。充分利用了网页的h n 皿 d o m 树的结构信息与浏览器显示的可视化信息，作为一种基础的分割算法有很强的扩 展能力与实际应用能力。但依据视觉信息使得算法比较适合于传统的按表格布局的页 面，对现在越来越多的按d + c s s 布局的页面不太适合。在对进行分块抽取与分隔符 探知时使用启发式规则，则使算法加入更多人为因素，对于某类网页效果好，但不适用 于网络上众多不规则的、质量较低的页面。 3 2 g r a p h t h e o r e tica p p r o a c h 3 2 1 算法概述 该算法不同于以往的基于启发式规则的算法，它将网页分块问题转化为加权图上组 合最优化问题，即用图来代表网页的信息，对图进行划分，得到分割结果，映射回网页 。即对网页进行分块。用图论的方法进行网页分块比基于启发式规则的方法更加具有理论 深度与实际应用能力，使网页分块算法研究有了进一步的提高。 算法首先利用h n 儿网页的d o m 树结构信息与可视化信息为网页构造加权图，然 后利用图论中的算法进行图划分，得到划分结果后，映射回网页，即得到网页的分块结 果。图划分采用相关聚簇与能量最小分割两种算法进行，相关聚簇方法只采用d o m 树 的叶子节点作为图的边，而能量最小割方法则采用了所有的d o m 树节点，下面将具体 介绍。 ( 1 ) 基本定义 算法从h t m l 网页的d o m 树中提取图的节点。边代表将两端节点分配给不同标签 的c o s t 。同时规定：如果一棵子树的根节点属于某个块，那么这个子树的所有结点都属 于该块。具体定义如下： n 为d o m 树的节点，即图上顶点；l 是一组标签的集合，标签互不相同；d p 代表 将标签分配给节点p 的c o s t ；v p q 代表将两个不同的标签分配给一条边的两端节点的 c o s t ，s 为一个从n 乱的函数，对于n 中的每个p 节点记为s ( p ) ；则一个分块定义 为： 厍印( s ( p ) ) + p ，非印( s ( p ) ，s ( g ) ) m 1 ( 3 1 ) ( 2 ) 相关聚簇图划分算法 大连理工大学硕士学位论文 相关聚簇图划分时，图上的节