基于特征码的大规模中文网页并行去重方法

论文摘要

随着互联网的发展,网上信息迅速增加,搜索引擎作为帮助人们从网络中快速获取信息的工具,使用日益广泛。但由于存在许多网页转载的情况,搜索引擎的返回结果中存在重复信息,既浪费了带宽,降低了检索效率,又浪费了搜索引擎的存储空间,同时也给用户带来糟糕的用户体验,这都使得网页查重技术在搜索引擎技术中占据重要的地位。本文研究面向搜索引擎系统的大规模中文网页去重方法,着力解决以下两个问题:第一,近似重复网页的查重问题。由于互联网上转载的内容常采用不同的显示风格或加入评论等其他信息,仅检测完全重复的网页不能满足实际需求,能否检测出近似重复网页成为衡量网页去重算法性能的关键因素。第二,如何在搜索引擎的大规模数据集上实现模糊去重,使程序运行所需时间和空间在可接受的范围是本文实现部分要解决的主要问题。网页查重技术,按照利用的信息类别来分可分为基于URL,基于链接关系和基于网页内容三种。前两种对近似重复网页的检测效果不甚理想,因此目前研究较多的是第三种基于内容的方法,基于特征码的网页去重方法就是其中的一种。它通过提取特征码将网页内容映射到较短的字符串上,再据此定义相似度并判重。该类方法充分利用了中文网页的特点,运算速度快,准确度高,在中文网页去重中应用较多。本文使用一种基于变长特征码的网页去重方法,通过定义独立抽取单元,屏蔽小段落对特征码的影响,克服传统的特征码抗噪性能不佳的问题,使得系统具有良好的模糊去重能力。通过引入基于最长公共子串的重复度定义,以及对模糊匹配的支持,进一步增强了系统的模糊去重能力,为近似网页查重问题提供了更好的解决方法。为了达到更快的运算速度,本文利用广义后缀树求解特征码之间的最长公共子串以加快运行速度。由于数据量大,同时后缀树也需要大量内存空间,本文采用了基于MPI的并行编程环境,实现了在集群环境中多个节点上并行运行的网页去重系统,既解决了内存限制的问题也提高了程序运行的效率。实验结果表明,该算法能高效的去除掉重复网页,在保证去重效果的同时准确率可达到99.03%,达到了预期的效果。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 课题背景
• 1.2 研究目的和意义
• 1.3 国内外相关技术
• 1.3.1 搜索引擎概述
• 1.3.2 网页查重技术研究现状
• 1.4 本文主要研究内容
• 第2章 网页查重技术
• 2.1 重复网页分类及检测重复网页的意义
• 2.2 基于内容的网页查重方法
• 2.2.1 SCAM算法
• 2.2.2 CHECK方法
• 2.2.3 北大天网的查重方法
• 2.2.4 基于特征码的网页查重方法
• 2.2.5 去重方法比较和分析
• 2.3 本章小结
• 第3章 基于特征码的网页去重
• 3.1 引言
• 3.2 特征码提取算法
• 3.3 网页重复度定义
• 3.4 基于后缀树的网页去重系统
• 3.4.1 系统实现
• 3.4.2 模糊去重的信息损失
• 3.5 本章小结
• 第4章 网页去重系统的并行实现
• 4.1 引言
• 4.2 系统实现的主要问题及框架
• 4.3 并行系统主要模块
• 4.3.1 特征码提取模块
• 4.3.2 精确匹配特征码去重模块
• 4.3.3 后缀树去重模块
• 4.4 本章小结
• 第5章 实验结果与分析
• 5.1 引言
• 5.2 实验环境
• 5.3 基于特征码的网页去重算法评测
• 5.3.1 特征码的抗噪性测试
• 5.3.2 算法准确率评测
• 5.3.3 系统重复度阈值对准确率和去重率的影响
• 5.4 并行去重系统正确性验证和性能测试
• 5.4.1 并行算法的正确性验证
• 5.4.2 并行算法的效率
• 5.5 本章小结
• 结论
• 参考文献
• 致谢