基于平面图的网页分块算法的研究

摘要

随着网页结构的复杂化与内容的多主题化，搜索引擎的结果越来越无法满足人们的需求，因为网页作为最基本的信息获取单位已不再合适，要更准确的获取web上的信息，就必须对网页进行分块。
　　 然而，现有的网页分块方法多是在DOM结构上的启发式方法，如VIPS(Vision basedPage Segmentation)。这种方法简单易实现，效率也较高，但不具有普遍适用性。另一种基于图论的方法Graph Approach，它将网页转换成图来表示，然后对图进行划分，得到划分结果再映射到网页上。该方法能够应用到web上所有的网页，具有普遍适用性，但由于代表网页的图非常大，划分困难，效率较低，不具实用性。
　　 针对现有网页分块方法不足，本文提出一种基于平面图的网页分块算法。该算法首先将抽取网页结构和视觉信息构造一个无向加权图，其中图的顶点是网页DOM树中的可视叶子节点，图的边为浏览器中显示的节点位置关系。接下来通过Gomory-Hu算法对图进行划分，从而实现网页分块。由于这种结合使用结构信息和视觉信息构造的图是平面图，因而算法效率很高。同时，Gomory-Hu算法可以很好地保证图划分的质量。实验表明，同VIPS算法以及Deepayan的图论算法相比，本文算法的准确率和召回率均有很大提高，同时算法运行时间远远低于Deepayan的图论算法。

目录

文摘

英文文摘

声明

1 绪论

1.1 研究背景

1.2 国内外研究现状

1.3 本文工作及组织

2 相关知识介绍

2.1 HTML DOM树

2.2 图的定义与基本概念

2.3 平面图划分算法

3 网页分块方法详述

3.1 VIPS

3.1.1 算法概述

3.1.2 算法分析总结

3.2 Graph—Theoretic Approach

3.2.1 算法概述

3.2.2 算法分析总结

4 平面图网页分块算法

4.1 平面图网页分块算法

4.1.1 平面图算法思想

4.1.2 平面图算法框架

4.2 平面图构造方法

4.2.1 顶点选择方法

4.2.2 边选择方法

4.2.3 边加权算法

4.3 Gomory—Hu图划分算法

4.3.1 Gomory—Hu算法

4.3.2 最小割算法——Ford—Fulkerson算法

4.4 Gomory—Hu网页分块算法

4.4.1 孤立点处理

4.4.2 Gomory—Hu FPS算法

5 实验结果与分析

5.1 基于平面图分块实验

5.1.1 图构造实验

5.1.2 图划分实验

5.2 对比实验分析

5.2.1 召回率与准确率比较

5.2.2 运行时间比较

结 论

参考文献

攻读硕士学位期间发表学术论文情况

致 谢