学校编码：10384 分类号 密级
学号： UDC
本 科 学 位 论 文
Simhash 在文本相似领域的应用与效果
Applied Simhash on the Domian of Text Similarity
XXX
指导教师姓名：教授
专 业 名 称：计算机科学与技术
论文提交日期：2013 年 05 月
论文答辩时间：2013 年 06 月
学位授予日期：2013 年 月
答辩委员会主席：
评 阅 人：
2013 年 05 月
摘 要
2
摘 要
随着网页及其它文本数目的急剧增加，从大量文本中迅速地检测出近似的文
本成了研究热点。高效、准确地实现文本相似的检测，能极大地影响到信息检索、
知识产权保护、文本聚类、网页去重等领域的效果。因此，文本相似度的研究得
到了国内外众多学者的重视，成为信息检索中重要的方向之一。
计算文本相似度的方法很多，其中 SimHash 方法由于其速度上优势，成为
Google 公司使用的方法，得到了较多的关注。本文主要是研究 SimHash 的原理，
通过实验，验证 SimHash 在文本相似计算上的效果，并与其它一些相关的算法进
行比较，并根据结果的数据分析，选定 SimHash 的阈值。
关键字：信息检索 文本相似 Simhash；
Abstract
The amount of web pages is numerous , how to efficiently find the
similar text has become an important topic. It has great influence on some
areas such as IR, document clustering . So this topic attracted numerous
domestic and foreign scholar’s attention and research, became the import
domain in information retrieval.
Plenty of methods for similar text had published.Among them, SimHash
was chosen by Google for their search engine ,because it has a efficient
capable.This thesis mainly focus on the principles of SimHash and its
performance. Based on a great deal of experiments and analysis of real
data, this paper will show some relationship between SimHash and other
methods , then try to choose the threshold for SimHash.
Key words：information retrieval similar text Simhash
Abstract
4
目 录
摘 要 ..............................................................................................................................................2
Abstract ..........................................................................................................................................3
第一章 引 言 .................................................................................................................................1
1.1 研究背景综述 ....................................................................................................................1
1.2 文本相似技术的研究进展.................................................................................................2
1.3 本文的主要工作 ................................................................................................................3
第二章 文本相似检测过程.............................................................................................................5
2.1 分词 ....................................................................................................................................5
2.1.1 分词介绍 ................................................................................................................5
2.2 特征提取 ............................................................................................................................7
2.3 相似度计算方法................................................................................................................7
2.3.1 相似度计算方法介绍..............................................................................................8
第三章 SimHash 算法 .....................................................................................................................9
3.1 SimHash 介绍......................................................................................................................9
3.2 SimHash 算法基本原理....................................................................................................10
3.3 SimHash 的实现................................................................................................................11
3.3.1 hash 函数实现.......................................................................................................11
3.3.2 生成权重向量 V ...................................................................................................12
3.3.3 生成特征指纹 fingerprint ....................................................................................13
第四章 实验测试及结果分析.......................................................................................................14
4.1 实验数据集说明..............................................................................................................14
4.2 实验内容 .........................................................................................................................14
4.2.1 相似判断的准确性实验.......................................................................................14
4.2.2 bits、k 值与 precision-recall 实验 ........................................................................16
4.2.3 Hamming 距离与集合相似度实验 .......................................................................17
4.2.3 时间测试 ..............................................................................................................20
第五章 总结和展望 ......................................................................................................................22
致谢 ................................................................................................................................................23
第一章 引 言
1
第一章 引 言
1.1 研究背景综述
计算机作为纸张、印刷术后又一个革命性的技术成果，推动了人类科技全面
的发展。而互联网的出现和普及，更是彻底改变了人们的生活方式，增强了人们
获取信息的能力。
据《第 31 次中国互联网络发展状况调查统计报告》[1]指出，截至 2012 年
12 月底，我国网民规模达到 5.64 亿，全年共计新增网民 5090 万人。互联网普
及率为 42.1%，较 2011 年底提升 3.8%。79.4%的网民经常使用搜索引擎获取信息，
71.5%经常浏览网络新闻。互联网为人类知识的传播提供了极大的方便。
然而互联网规模的急剧扩大，人们面临的不再是信息缺失的问题，而是信息
过载及信息检索，如何从互联网上检索自己需求的信息。而随着大数据的热度逐
渐升级，人们越来越关注如何从海量的数据中更高效地获取信息。
影响人们获取信息的因素有很多。比如搜索引擎的精确理解问题，比如，搜
索引擎会返回大量重复或相似的网页，浪费读者大量的时间。《第 16 次中国互
联网络发展状况调查统计报告》[2]显示，44.6%的被调查网民反映：“重复信息
太多”是“在互联网上查询信息时遇到的最大问题”。
1996 年，Broder 等人在对 AltaVista 搜集到的 30,000,000 个网页进行实验
得出结论[3]：有近 18％的网页是完全相同的。有 41％的网页是具有 50％的相似
性。Stanford 的 Cho 等人在 1999 年利用 Google 搜索到的 25,000,000 个网页的
数据集统计得出约 48％的网页是重复的[4]。
通过分析，可以将近似网页根据性质分为以下几种：
1) 完全重复。例如 FAQ、RFC、法律文件、热门网站的镜像站点等等。
2) 部分重复，即近似镜像的网页。这些网页内容不完全相同，但是通过分
析，可以明显发现相似、相近。例如，相同的文档可能在网上存在不同格式的版
本。这些网页也有可能是内容部分重复的网页。例如未更新的文档。这些近似镜
像的网页正是本文研究的重点和难点。例如抄袭其他网页的文章。
近似网页的存在已经成为了一个很严重的问题。它所带来的代价就是
