基于段落指纹的大规模近似网页检测算法研究

论文摘要

随着信息技术的飞跃式发展,互联网进入了一个信息爆炸的时代,搜索引擎成为了人们获取信息最主要的途径。然而,互联网上存在很多近似网页,一方面加重了用户从中寻找有价值信息的负担,另一方面,为近似网页建立索引消耗了大量不必要的存储和计算资源,进而影响整个搜索引擎的质量和性能。可见,对网页进行近似检测不仅能够提高索引效率,节约存储资源,同时能够显著地提升搜索引擎的用户体验。本文首先对近似网页检测的研究现状做出综述,并对现有算法做出深入分析。随后,提出了一种基于加权DOM树的网页正文提取算法,通过实验验证了该算法在各类网页集上均获得高的正文提取准确率,并将其应用于本文的近似网页检测算法。接着,提出了一种基于段落指纹的近似网页检测算法,该算法充分利用了中文语言的语法结构、文章主题语义和HTML标签语义,实验数据表明,本文算法能够获得高的准确率和召回率。实现了三种已有的优秀近似网页检测算法,实验数据表明,本文算法在准确率、召回率、效率和指纹占用的存储资源这些关键方面均有优势。最后,基于MapReduce计算模型,对本文近似网页检测算法的并行化做出了深入研究,给出了详细的并行化设计方案,并在Hadoop分布式平台上实现了该方案。在不同的Hadoop集群规模下进行实验,数据表明,本文算法经过并行化设计后,效率得到了显著提升,很好地突破了单机处理的资源瓶颈,是一种能够适用于海量数据规模的且实际可行的方案。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 研究背景
• 1.2 研究意义
• 1.3 本文研究内容
• 1.4 本文组织结构
• 2 近似网页检测算法综述
• 2.1 近似网页的定义
• 2.2 近似网页检测研究现状
• 2.3 近似网页检测算法通用模型
• 2.3.1 特征提取算法
• 2.3.2 特征指纹生成算法
• 2.3.3 文本距离计算方法
• 2.4 近似网页检测算法评价指标
• 2.5 现有近似网页检测算法分析
• 2.6 本章小结
• 3 基于加权DOM树的网页正文提取算法
• 3.1 网页噪声概述
• 3.2 网页正文提取算法分析
• 3.3 基于加权DOM树的网页正文提取算法
• 3.3.1 基本概念
• 3.3.2 算法思想
• 3.3.3 算法描述
• 3.3.4 算法对比与分析
• 3.4 实验数据与分析
• 3.4.1 实验环境和实验所用技术
• 3.4.2 单个网页的实验结果
• 3.4.3 多个网页的实验结果
• 3.4.4 实验数据分析
• 3.5 本章小结
• 4 基于段落指纹的近似网页检测算法
• 4.1 算法的提出
• 4.2 算法的描述
• 4.2.1 算法总体流程的形式化描述
• 4.2.2 算法核心问题分析
• 4.3 基于加权长句的段落特征提取算法
• 4.3.1 段落长句提取
• 4.3.2 段落长句权重计算
• 4.4 基于SimHash的段落指纹生成算法
• 4.4.1 SimHash算法思想
• 4.4.2 段落指纹生成算法描述
• 4.5 网页相似度计算
• 4.6 算法的分析与优化
• 4.7 实验数据与分析
• 4.7.1 实验环境
• 4.7.2 实验内容和实验数据集
• 4.7.3 本文算法实验数据与分析
• 4.7.4 本文算法与已有算法的对比分析
• 4.8 本章小结
• 5 基于MapReduce的近似网页检测算法并行化设计
• 5.1 MapReduce计算模型
• 5.1.1 MapReduce概述
• 5.1.2 MapReduce执行流程
• 5.1.3 Hadoop的开源MapReduce框架
• 5.2 近似网页检测算法的并行化设计
• 5.2.1 总体框架
• 5.2.2 段落指纹索引的建立
• 5.2.3 近似网页的检测
• 5.2.4 段落指纹索引的更新
• 5.3 实验数据与分析
• 5.3.1 实验环境
• 5.3.2 实验内容和实验数据集
• 5.3.3 算法MapReduce化的实现
• 5.3.4 实验数据分析
• 5.4 本章小结
• 6 总结与展望
• 6.1 工作总结
• 6.2 工作展望
• 致谢
• 参考文献