一种基于Simhash的文本快速去重算法

发布时间：2017-08-05 00:12

  本文关键词：一种基于Simhash的文本快速去重算法

  更多相关文章： Simhash 文本去重 特征向量 海明距离 Hash

【摘要】：在万维网中，大多数的网页都是重复的，然而，这些重复的网页对于搜索引擎返回的搜索结果是冗余的，搜索结果大多数不能体现用户查询意图。如果能将这些冗余的搜索结果去重，并实现返回结果按照重复率最大的网页进行排序显示给用户，，无疑是一种可以满足用户查询需求的方式，那么，网页去重亟需解决的是使用什么样的技术手段判断网页内容是重复的最重要，如何能够去除相同或者相似的网页可以提高检索效率、降低存储开销。 实际搜索中，搜索引擎返回数据会给用户提供很多相同的查询记录，但是如果返回重复的搜索结果是不科学的，因为大多数返回结果存在相似度极高的情况，甚至就被检索到的是同一个网页，当爬虫抓取网页的同时可以判断下其网址是否在已经下载的列表中，如果该网址的前半部分是相同的，可以认为它们可能是重复性的网页，这些重复的网页直接就不用下载，但是，在网址不相同的情况下，也可能网页内容是重复的，这种情况下的网页也不必出现的结果也中，那么，一个精锐的问题就是：很多重复的网页到底选哪一个作为返回结果呢？ 提到文本相似性计算，首先要想到的应该是向量空间模型VSM（VectorSpace Model），这种方法存在的问题是：需要对网页两两比较相似度，无法扩展到海量网页的处理。传统的判断网页相似度的经典方法是“向量夹角余弦”，其主要思想是一篇网页中出现词的词频构成一个二维向量，然后计算网页之间对应的向量夹角余弦，但是，尤其一篇网页中含有大量的特征词，导致生成的二维向量的维度特别的高，这样一来使得计算的代价太大乃至于超出了预计的时间、空间复杂程度，那么对于大型的搜索引擎处理上万亿级别的网页请求是不可接受的。于是，Simhash算法诞生了，其主要思想是“降维”，将高维的特征向量映射成一个唯一“Simhash”值标识，所以比较网页唯一“指纹码”标识来确定的网页的是否重复。 本文主要方法是一种基于Simhash的文本快速去方重法，一篇网页提取出网页内容后，必须经过基本的预处理，比如：（中文的，去除停留词、中文分词处理、英文的，去除停留词、词根还原），最后会得到一个向量，实验结果表明，本文提出的方法的实验结果良好。
【关键词】：Simhash 文本去重 特征向量 海明距离 Hash
【学位授予单位】：吉林大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP391.3;TP393.092
【目录】：

• 提要4-5
• 摘要5-7
• Abstract7-11
• 第1章 引言11-15
• 1.1 研究背景11-12
• 1.2 研究意义12
• 1.3 研究现状12-13
• 1.4 研究内容13-14
• 1.5 论文结构14-15
• 第2章 网页去重算法简介15-18
• 2.1 文本去重预处理技术15-16
• 2.2 获取重复文本技术16-17
• 2.2.1 网页自动聚类16
• 2.2.2 网页自动分类16-17
• 2.2.3 基于网页规则的算法17
• 2.2.4 基于网页距离的算法17
• 2.3 小结17-18
• 第3章 一种基于 Simhash 的文本快速去重算法18-29
• 3.1 文本去重基本概念18-19
• 3.1.1 文本相似基本定义18-19
• 3.1.2 文本相似基本性质19
• 3.1.3 文本去重字符表及其含义19
• 3.2 文本去重算法之 IF-IDF 算法19-21
• 3.2.1 IF-TDF 算法19-20
• 3.2.2 基于 TF-IDF 相似度算法描述20-21
• 3.2.3 基于密度的去重算法21
• 3.3 基于 Simhash 文本快速去重算法21-27
• 3.3.1 Simhash 算法22-24
• 3.3.2 Simhash 算法流程图24-25
• 3.3.3 Simhash 算法应用与海量数据去重25-27
• 3.4 小结27-29
• 第4章 实验结果及分析29-35
• 4.1 Simhash 和 hash 算法比较29-30
• 4.2 运行时间及压缩比实验分析30-34
• 4.2.1 运行时间分析30-31
• 4.2.2 几种算法去重压缩比31
• 4.2.3 获取文本 Simhash 值实验分析31-34
• 4.2.4 海量文本 Simhash 实验分析34
• 4.3 小结34-35
• 第5章 结论与展望35-37
• 5.1 结论35-36
• 5.2 进一步研究方向36-37
• 参考文献37-39
• 作者简介及在学期间所取得的科研成果39-40
• 致谢40

【参考文献】

中国期刊全文数据库 前6条

1 樊勇;郑家恒;;基于主题的网页去重[J];电脑开发与应用;2008年04期

2 王小华;卢小康;;基于N-Gram的文本去重方法研究[J];杭州电子科技大学学报;2010年02期

3 黄仁;冯胜;杨吉云;刘宇;敖民;;基于正文结构和长句提取的网页去重算法[J];计算机应用研究;2010年07期

4 吴平博,陈群秀,马亮;基于特征串的大规模中文网页快速去重算法研究[J];中文信息学报;2003年02期

5 曹玉娟;牛振东;彭学平;江鹏;;一个基于特征向量的近似网页去重算法[J];中国索引;2009年01期

6 谢蕙;秦杰;胡双双;;基于用户查询关键词的网页去重方法研究[J];现代图书情报技术;2008年07期

本文编号：622360