基于重复串的STC网页去重算法研究

摘要

随着网络信息呈指数级的不断膨胀,如何从这个信息的海洋快速获得真正有价值的信息变得至关重要。搜索引擎应运而生,提供了在互联网上搜索信息的功能。然而在搜索引擎返回的检索结果中,存在大量的重复网页,其中大部分网页主要来自网站之间的转载。这些冗余网页既占用了网络带宽,又浪费存储资源,如何有效消除这些重复网页,提高检索的准确率,节省用户的时间和精力,提高用户满意度,成为当今搜索引擎领域中一个重要的研究方向。因此,网页去重工作有着十分重要的研究意义。
　　本文在深入学习数据挖掘知识的基础上,对搜索引擎工作原理进行剖析,对现有去重算法进行了分析。重点对STC算法和重复序列算法进行了详细比较,对两种算法进行性能测试后,分析二者利弊,提出一种基于重复串的STC改进算法,核心思想是对字符重复串进行抽取,使用重复串作为短语标引生成后缀树,并映射生成倒排索引进行STC算法去重。实验证实了改进算法有着良好的准确率和召回率,并有着优良的时间和空间特性。
　　为了验证所提出算法的有效性并比较其去重效果,本文开发了一个搜索引擎实验原型系统,完成了该系统的总体设计和各个模块的设计工作,通过该系统实现了算法的改进,并验证了其有效性。
　　在实验过程中,首先对算法进行了编辑测试语料的模拟实验,将一篇文档内容进行标题和正文的删除、修改后生成修改文档。使用改进算法将修改文档与原文进行相似度判断。结果表明,算法能有效判定文档相似度。然后在实现了该算法的搜索引擎实验原型系统中,进行互联网实测。实验结果表明,本文的改进算法具有较高的召回率、去重准确率和较低的漏删率及误删率。
　　本文的研究成果和搜索引擎实验原型系统在信息急剧膨胀的时代,具有较高的应用价值和推广意义,同时也具有良好的社会效益和经济效益。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

§1.1 课题背景及研究意义

§1.1.1 搜索引擎发展及现状

§1.1.2 网页去重的需求

§1.1.3 研究内容及创新点

§1.1.4 本文的组织

第二章 网页去重技术

§2.1 去重技术概述

§2.2 国外去重算法

§2.2.1 SCAM算法

§2.2.2 DSC和DSC-SS算法

§2.2.3 I-Match算法

§2.3 国内去重算法

§2.3.1 北大天网查重算法

§2.3.2 基于特征串的网页查重算法

§2.3.3 基于特征句抽取的网页去重研究

§2.4 本章小结

第三章 STC和重复序列算法比较及改进算法

§3.1 STC和重复序列两种算法比较

§3.1.1 后缀树

§3.1.2 重复序列

§3.1.3 实验结果分析

§3.2 基于重复串的STC改进算法

§3.2.1 算法分析

§3.2.2 基本定义

§3.2.3 算法描述

§3.2.4 实验结果分析

§3.3 本章小结

第四章 搜索引擎系统开发及去重实验

§4.1 搜索引擎的系统框架

§4.2 系统的模块结构

§4.2.1 网络蜘蛛（爬虫）

§4.2.2 去除噪声、文本提取

§4.2.3 Page-Rank网络排名

§4.2.4 切词

§4.2.5 索引

§4.2.6 查询器

§4.3 改进去重算法在搜索引擎系统中的应用

§4.3.1 算法描述

§4.3.2 搜索引擎去重系统的实现

§4.4 改进算法测试结果

§4.4.1 搜索引擎评价指标

§4.4.2 查重效果测试

§4.5 本章小结

第五章 总结及展望

§5.1 总结

§5.2 展望

参考文献

致谢

作者在攻读硕士期间主要研究成果