视觉特征的网页最优分割算法范文

《计算机科学杂志》2015年第S1期

1引言

随着移动通信技术的迅猛发展，人们通过移动终端访问网页的活动日渐频繁。然而，移动终端屏幕尺寸的限制往往造成Web页面无法正常显示，给用户带来了很大的困扰。为了解决这个问题，早在20世纪90年代，研究人员便开始研究网页自适应呈现技术，提出了若干算法。这些算法可归纳为3类，即网页重构、网页转码、网页分割。其中，网页分割是实现网页自适应呈现的主流技术之一。它首先将网页分割成若干个语义相关的内容段（也称为内容块）；然后在内容服务过程中，服务器根据移动终端特征，选择合适的内容段并推送给用户，以确保网页内容在移动终端上得以正常显示。网页分割技术具有两个优点：一方面，它不需要占用大量的计算资源；另一方面，用户也不需要反复拖动滚动栏查看网页内容，使网页内容的服务质量得以保证。近年来，关于网页分割技术的研究受到了广泛关注，并且取得了丰富的研究成果。其中经典算法是Cai等研究人员提出的基于视觉的网页分割技术（Vision－basedPageSegmenta－tionAlgorithm，VIPS）。VIPS根据人的视觉特点，总结出一些网页分割的规则，然后基于这些规则实现网页分割。此后，许多研究者在该方法的基础上提出了许多改进的网页分割技术，但基于规则的思想没有本质变化。目前，基于视觉的网页分割技术主要存在两方面问题：其一，网页分割结果过碎，不利于网页重构；其二，分割规则的总结需要人工参与，规则的好坏也直接影响网页分割效果。因此，如何划分网页分割的粒度，如何能减少分割过程中人工参与，从而降低主观因素影响，均是需要进一步研究的问题。本文将网页分割转化为图的最优划分问题，提出一种新颖的网页最优分割算法（Vision－basedWebOptimalSegmen－tation，VWOS）。VWOS算法首先基于人的视觉特点设计内容相似度计算模型，然后利用网页结构特征和内容相似度模型，将网页构造为加权无向连通图，并将网页分割转化为图的最优划分问题，最后基于Kruskal算法求解图的最优划分问题，实现网页最优分割。VWOS算法是一种自动算法，不需要人工参与。实验分析表明，该算法能够有效地对网页进行分割，分割效果和算法性能优于VIPS算法。

2相关研究

网页是一类特殊的文本文件，它具有内容特征、结构特征、布局特征和视觉特征。针对上述4种特征，网页分割技术可以分为4种类型：基于内容特征的分割技术、基于结构特征的分割技术、基于布局特征的分割技术和基于视觉特征的分割技术。基于内容特征的网页分割技术主要是基于网页标签。20世纪90年代末的手机浏览器不支持CSS层叠样式，也不支持JavaScript，只能访问简单的静态网页。因此，当时的学者只需基于标签的类型进行分割，即可达到很好的效果。YanleiDiao等人提出具有自学习功能的Web查询处理系统［1］，利用有效标签类型（如〈p〉、〈table〉、〈ul〉、〈h1〉～〈h6〉）进行网页分割；Wai－chingWong提出标签检测算法来检测具有同类型信息的相似标签，并定义标签类型进行网页分割；EijaKaasinen与OrkutBuyukkokten仅仅利用像〈p〉〈ta－ble〉〈ul〉这样的简单标签进行Web网页分割。基于结构特征的网页分割技术采用了DOM（DocumentObjectModel，DOM）技术，将网页表示成DOM树结构，然后根据各内容块在DOM树中的位置对网页进行分割。文献均采用的是基于DOM树的分割技术，RichardRomero［8］在DOM树的基础上进行聚类分析，实现网页分割。基于布局特征的网页分割技术主要包括基于位置的网页分割技术与基于模板的网页分割技术两种。GenHattori提出的基于距离的网页分割技术，利用标签的相对位置与层级关系计算内容块的距离，以此对网页进行分割。然而HTML中某些特殊标签具有布局作用，降低了分割的准确率。通过对HTML标签的研究与分析，GenHattori于2007年提出改进技术：混合分割技术。混合分割技术将〈div〉与〈table〉作为布局信息，进行初步分割，之后将标签间的距离作为内容块的距离做二次分割。基于模板的网页分割技术的主要思想是分割前定义好各类模板，通过将欲分割的网页或内容块与模板匹配来进行分割。YuChen将网页分成上、下、左、右和中间5个部分，之后根据这5个部分的特征将网页的内容提取后纳入到定义好的特征模版中，从而实现网页分割。这种技术适合于结构标准的网页，对于其他结构的网页则无法正确分割。文献将网页归类于八大布局模板，之后依据网页布局（此处考虑的是标签形成的布局，而非样式信息形成的布局）与标题块进行网页分割。基于视觉特征的网页分割技术的原理是标签本身携带内容显示信息，根据人眼的视觉特征，利用这些显示信息实现网页的内容分割。DengCai提出了一种基于视觉特征的网页分割技术（Vision－basedPageSegmentationAlgorithm，VIPS），该算法具有良好的网页分割效果。VIPS存在的问题在于需要人工不断地去总结和调整分割规则，而且当新规则产生后，将影响以前的分割效果。基于VIPS算法，国内外学者提出了一系列的改进技术［14－18］，这些技术在一定程度上优化了VIPS，但上述的本质问题却没有解决。此外，这些技术均没有考虑CSS样式信息对视觉特征的影响。

3VWOS算法设计

根据网页的标签，可以将网页划分为许多语义完整的原子内容块，这些内容块是网页内容的最小组成单元。基于网页视觉特征定义两个原子内容块的相似度计算公式，并利用该公式构造原子内容块相似度矩阵。因此，网页可以视为由原子内容块为顶点、相似关系为边、相似度为权的加权无向连通图，网页分割就转化为图的最优划分问题。

3．1网页最优分割模型为便于表述网页最优分割模型，对其中包含的重要概念做如下定义。通过解析网页得到内容块，并利用内容块相似度公式计算内容块两两之间相似度，得到相似度矩阵。在此前提下，网页可以构造为加权无向连通图。因此，网页分割转化为图的最优划分问题，其最优化模型如式（1）所示。式（1）的最优化模型具有3个典型性质：最优子结构、重叠子问题与贪心选择性质。最优子结构指问题的最优解包含子问题的最优解。如果上述问题的最优解包含了原子内容块n，那么其余原子内容块一定构成子问题n－1个原子内容块在组阈值为St－Sn时的最优解。如果最优解不包含原子内容块n，那么其余原子内容块一定构成子问题n－1个原子内容块在组阈值为St时的最优解。重叠子问题指用递归算法自顶而下解决上述问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算了多次。贪心选择性质指所求问题的整体最优解可以通过一系列局部最优解的选择来达到。若所有原子内容块构成的集合为V，组内已确定的原子内容块构成的集合为U，s［u］［v］表示原子内容块u、v间的相似度。u∈U，v∈V－U，由于U中所有原子内容块构成一棵相似度最大的生成树，根据MST性质，V的所有相似度最大的生成树中一定存在一棵包含边（u，v）。

3．2VWOS算法网页最优分割算法VWOS分为4个步骤：第一，根据手机分辨率信息，确定网页分割阈值St；第二，建立原子内容块池Pc与相似度池Ps，相似度按值从大到小排序；第三，构建网页加权无向连通图G（V，E）；第四，求解图G（V，E）最优划分问题。（1）网页分割阈值确定不同手机的分辨率不同，所能呈现的信息量亦不同。因此网页分割时，需要设置不同的阈值，以达到在不影响正常显示与用户体验的情况下，子页所呈现的信息量最大化。网页分割算法采用像素面积确定分割阈值St。使用诺基亚5800W手机，随机浏览100个手机版网页，统计分析知，平均每个网页需要3．51屏显示；随机抽取100位大学生手机网民，对“手机版网页出现几屏显示时，会心生埋怨心理”问题进行调查，分析发现其平均值为2．87。考虑到用户体验的重要性，对上述两个结果以比例1：2进行加权求均值得3．08。因此，可确定最适合手机显示的网页大小为手机屏幕的3倍。由于VWOS算法所用的网页分割算法的特殊性，有时分割形成的子页结果为所设阈值的2倍。对此，将网页分割阈值St设为1．5屏，即St＝1．5×水平分辨率×垂直分辨率。（2）原子内容块池Pc与相似度池Ps的建立为了更有效地实现网页分割，需要建立原子内容块池Pc与相似度池Ps。Pc中存放原子内容块算法获得的所有内容块。原子内容块相似度计算及后期建立连通分支时均从Pc中获取所需的内容块。Ps中存放采用基于网页视觉特征的相似度公式得到的相似度值，并按值从大到小的顺序排列。内容相似度基于网页视觉特征，在此将网页视觉特征定义为6维向量，根据向量中维度的不同度量属性，采用不同的计算公式计算各维度相似度值，最后用加权求和的方式计算出最终的内容块相似度值［19］。Pc存放的内容块类型为Perfect－Node，而Ps存放的相似度以本文自定义的Similarity类型标识，其类图如图1所示。对Ps而言，由于构建连通分支时，以相似度值从大到小的顺序连通各分支，因此，Ps中的Similar－ity数据是按值递减的有序队列。1Similarity类（3）连通分支构建Pc中含有网页所有的原子内容块，Ps中含有两原子内容块间的相似度值，并按值从大到小排列。对Pc与Ps采用如下算法构建连通分支，以确保每个分支的相似度权值最大，且每个分支中所有顶点的像素面积和Sk均小于分割阈值St。这样便实现了网页分割所需的每个连通分支均可转换为各个子页，这些子页不仅可在手机浏览器中正常显示，而且具有较好的用户体验。连通分支构建算法如图2所示。1）将Pc中n个内容块看成n个孤立的连通分支，并建立关联池cr。2）计算各连通分支像素面积和Sk，并与St比较：如果Sk≥St或所有边都被查看过，则将连通分支中的顶点从Pc中取出存入关联池cr中；如果Sk＜St，按下述方法连接两个不同的连通分支：设查看到第s条边，若该边两端点分别是当前两个不同的连通分支T1和T2中的顶点，则用该边将T1和T2连成一个连通分支；若该边两端点在当前的同一个连通分支中，直接查看第s＋1条边。3）如果所有边都被查看过或Pc中已经没有原子内容块，则连通分支构建算法结束，否则转步骤2）。需要特别指出的是，若以是否含有孤立的连通分支或查看边数是否达到n＋1作为结束算法的条件，虽然可以大幅度减少算法循环次数，但是，却不能保证最后生成的连通分支不能再合并。而仅仅以判断所有边是否被查看过作为结束算法的条件，虽然可以保证Sk在小于St的情况下最大化，然而因需要过多的循环次数导致时间复杂度过大，从而影响VWOS算法的性能。通过分析与测试发现，多数情况下，各连通分支均不能再合并时，有很多边没有被查看，对此，连通分支构建算法采用“所有边都被查看过或Pc中已经没有原子内容块”作为算法结束条件，以达到在满足Sk最大化的同时性能最大化。（4）求解网页最优分割问题网页最优分割模型如式（1）所示，基于模型的最优子结构和贪心选择性质，可采用贪心策略求解该模型。因为，加权无向连通图G（V，E）可构造为一棵生成树，使生成树上各边权值最大，于是网页分割可变为在特定阈值St条件下构造子生成树的过程，每个子生成树均满足特定阈值St。采用最优化理论中的Prim算法与Kruskal算法所需的时间复杂度分别为O（n2）与O（eloge），其中e为图的边数。当e＝Ω（n2）时，O（n2）＜O（eloge），当e＝O（n2）时，O（n2）＜O（eloge）。因为网页对应的加权无向连通图G（V，E）是一张完全图，即e＝n（n－1）／2＝O（n2），所以用Kruskal算法比用上述其它算法时间复杂度低。因此，本文采用Kruskal算法实现网页最优分割问题求解。

4实验与分析

为检验VWOS算法的执行效果和性能，设计了一组网页分割对比实验。实验基于Web服务设计，通过移动终端访问网页。将VWOS算法和VIPS算法部署在服务器，以国家精品课程站点随机选取的100个网页为对象，移动终端采用分辨率为360×640像素的Android2．3手机模拟器，分割阈值St＝1．5×360×640＝3．456×e5。采用3个评价指标：平均分割块数、语义完整度和平均执行时间。其中语义完整度定义见式（2）。通过网页在移动终端的呈现结果，比较VWOS算法与VIPS算法在3个指标上的表现，评价算法效果和性能。

结果与分析本节以具体的2个网页呈现的结果为例，比较两种算法分割效果和性能，并分析其中的原因。结合专业背景，选取的网页定为北京师范大学的国家精品教育技术学导论与南京师范大学国家精品课程教育社会学。图3（a）为北京师范大学的国家精品教育技术学导论经VWOS算法分割的效果。VWOS算法将该网页分割为两个子页，如图3（b）与图3（c）所示，图3（b）为主页，图3（c）为子页。从图中可以发现，VWOS算法分割该页面后得到的两个子页语义完整且适合手机浏览器显示，具有较好的用户体验。图4为教育技术导论网页采用VIPS算法的分割结果。

VIPS将该网页分割为6个子页。其中只有表格子页的像素面积与分割阈值接近，而其他5个子页尺寸均远小于阈值。VIPS算法之所以将网页分割得过碎，主要因为其以DOM树为基础，对每个内容块用DoC（DegreeofCoherence）表示紧密程度。按照VIPS的规则，DoC在DOM树中呈现自顶而下逐渐增大的规律。而VIPS采用自顶而下的方式分割，因此当DOM树底层的内容块符合分割阈值时，上层内容块因DoC小于PDoC（PermittedDegreeofCoherence）而被过度分割。VWOS算法基于最优化理论，将网页分割看作分组最优化问题，并设计网页分割算法以自底而上的方式对网页进行分割，有效地避免了分割过碎问题。由此可以看出在分割后形成子页数方面，VWOS算法较VIPS算法内容块语义更完整，也更适合移动设备显示。图5为南京师范大学国家精品课程教育社会学分别经VWOS与VIPS分割的效果。采用VWOS算法进行分割后形成两个子页，其中图5（b）所示子页为原网页右下角部分。该部分像素面积略大于分割阈值St，按照VWOS算法设计的网页分割算法，该部分会作为一个完整子页存在。采用VIPS算法，将页面分割为3个子页，如图5（c）所示，其中黑色方框内的部分为分割后保留下的内容块。观察图5（c）很容易发现丢失了部分内容块。分析该网页的代码可发现，丢失的部分均为样式信息，该部分的样式信息存储在CSS文件中，而非HTML标签的style属性中。由此，再一次证明了由于“数据内容－样式信息”的分离，致使VIPS分割效果无法满足手机用户需求的假设，也再一次说明了网页分割预处理算法的必要性。

VWOS算法充分考虑了〈link〉、〈style〉与HTML标签style属性中的样式信息，并将样式信息与数据内容融合，以此保证内容块视觉特征的全面性与精确度。因此可以看出，在分割后形成的内容块方面，VWOS算法得到的内容块具有语义完整的特点，而VIPS算法分割过程中，会造成内容块视觉特征的丢失，甚至会造成部分内容块的丢失。此外观察图5（b）可以发现，分割形成的子页的像素面积比手机尺寸大，这主要因为该部分采用〈table〉标签进行布局，而VWOS算法并未对〈table〉标签的宽高信息进行处理。实验采用VWOS算法和VIPS算法共对100个精品课程站点网页进行网页分割，并在3个性能指标上进行统计对比，结果如表1所列。通过上述实验，初步证明VWOS算法在内容块语义完整性和网页适应性方面，比VIPS算法具有更好的性能。具体而言，VWOS算法比VIPS算法具有以下4点优势：第一，VWOS算法不需要人工参与，是一种网页分割自动处理方法；第二，在同样的分割阈值条件下，VWOS算法生成的子页数少，因此用户在各子页中遍历浏览时，不易迷航；第三，VWOS算法生成的每个子页的像素面积SP均在［St，2St）区域中，没有过度分割的子页；第四，VWOS算法充分利用视觉特征表示内容块的特征，分割得到的每个内容块均具有高度的语义完整性。结束语网页分割技术被广泛应用于网页信息获取和网页自适应呈现等领域。目前，经典的网页分割算法仍存在需要人工参与和分割过碎的问题。针对这些问题，综合视觉特征和网页结构，将网页构造为加权无向连通图，并将网页分割转化为图的最优划分问题，最后基于经典的最优化算法，结合网页分割的过程，提出了一种基于视觉特征的网页最优分割算法VWOS。实验证明，VWOS算法在语义完整性和网页适应性方面，性能优于经典分割算法VIPS。与VIPS算法相比，VWOS算法有两个优点。其一是网页分割结果没有过多的内容碎片，较好地保留了内容块的语义完整性；其二是它属于自动算法，不需要人工参与。当然，VWOS算法仍存在一些不足之处，集中表现在由于网页样式采用技术不同对构造网页无向连通图G影响较大，因此该算法的鲁棒性存在不足。

下一步研究将从3方面展开。第一，将采用更多的客观评价指标（如信息检索领域评价指标），全面对比VWOS和VIPS两种算法的性能，并以此为依据对VWOS算法做改进。第二，在算法中增加对网页样式技术的识别，并做相应的处理，提高算法的鲁棒性。第三，将以VWOS算法为核心，研究网页自适应呈现技术，以期达到Web学习资源移动访问的目标，提高Web学习资源的利用率，为移动学习服务打下技术基础。

作者：李文昊 彭红超 童名文 石俊杰 单位：华中师范大学教育信息技术学院 解放军63981部队