Web页面结构相似性的算法研究及应用

论文摘要

网页结构相似性的度量是Web信息处理中的一项重要任务,在数据抽取和搜索引擎等研究领域有着潜在的重要研究价值。好的相似性度量方法可以提高数据抽取的准确率和速度,还可以提高搜索引擎的速度、提高返回数据的质量、减少大量冗余数据占据的存储空间。实现该任务的已有算法往往存在着时间复杂度过高的问题。通常,简单的DOM树模型可用于HTML文档建模,展现文档的结构信息模型。然而,DOM树只是把文档按照其结点的嵌套结构表示为树结构,它并不能够表达重复子树这样的结构信息。而重复子树这种内部结构信息对于web文档间的结构相似性度量是相当重要的。为了解决这一问题,本文提出了一种称为“Tag-Bag树”的树模型。该模型使用Bag节点来表示树中的重复元素（重复元素在很多web应用中都非常重要）,从而可以捕获半结构化文档的结构信息。基于Tag-Bag树模型,我们进一步提出CTM（Complex Tree Matching）算法来计算两棵Tag-Bag树的最大匹配作为它们之间结构相似度的度量。与现有的编辑距离计算算法相比,CTM算法不允许结点的替换和跨层匹配,从而具有较高的运行效率。此外,CTM算法的另一个优点在于它能够辨别一个页面中出现的单一重复模式（当这个模式可能在另一个页面中出现多次的时候）。最后,试验结果表明:本文所提出的方法不论在速度还是精度上都要优于著名的Bag of XPaths方法。

论文目录

• 目录
• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.2 研究内容与贡献
• 1.3 论文结构
• 第二章 相关工作
• 2.1 建模相关研究
• 2.2 相似性研究
• 2.3 数据抽取
• 2.4 XML相似性研究
• 第三章 模型
• 3.1 HTML文档的树结构表示
• 3.2 HTML文件标签特点
• 3.3 Tag-Bag树模型
• 第四章 算法及实例
• 4.1 CTM算法
• 4.2 相似度计算
• 4.3 构建Tag-Bag树
• 4.4 实例
• 4.5 复杂度分析
• 4.5.1 空间复杂度分析
• 4.5.2 时间复杂度分析
• 第五章 实验结果
• 5.1 Tag-Bag树模型性能
• 5.2 算法CTM的性能
• 5.3 准确度比较
• 第六章 技术应用前景
• 6.1 相似性算法在搜索引擎中的应用
• 6.2 比较购物
• 6.2.1 系统概要
• 6.2.2 网上购物搜索平台系统
• 第七章 总结与展望
• 7.1 论文主要贡献
• 7.2 进一步的研究工作
• 参考文献
• 致谢
• 攻读硕士学位期间发表的论文