[转][转] 文本相似性算法Simhash原理及实践

simhash（局部敏感哈希）的原理

simhash的背景 

simhash广泛的用于搜索领域中，也许在面试时你会经常遇到这样的问题，如果对抓取的网页进行排重，如何对搜索结果进行排重等等。随着信息膨胀时代的来临，算法也在不断的精进，相似算法同样在不断的发展，接触过lucene的同学想必都会了解相似夹角的概念，那就是一种相似算法，通过计算两个向量的余弦值来判断两个向量的相似性，但这种方式需要两两进行计算向量的余弦夹角，计算量比较大，不能用于实时计算或是大数据量的运算，比如在做搜索结果的相似性排重时，需要对上千条结果进行相似性排重，如果两两比对的话，最少也需要进行上千次的向量余弦值计算，其中涉及到分词，特征提取，余弦值计算等，很难满足性能的需要。

jaccard相似度也是一种相似 算法，它的计算方式比较直观，就是sim（x,y）= (x∩y) / （x∪y）,例如：
     若  S={a, d}， T={a, c, d} 
     则  Jaccard_Sim(S, T) = |{a, d}|/|{a, c, d}| = 2/3

也是一种需要实时生成特征向量并且进行计算的算法。

那么

什么是simhash呢？

什么是局部敏感性哈希呢？

如何计算simhash呢？

simhash的好处？

如何应用simhash呢，具体的应用场景？

来源：http://blog.csdn.net/wdxin1322/article/details/16826331

我的数学之美系列二 —— simhash与重复信息识别

在工作学习中，我往往感叹数学奇迹般的解决一些貌似不可能完成的任务，并且十分希望将这种喜悦分享给大家，就好比说：“老婆，出来看上帝”…… 

随着信息爆炸时代的来临，互联网上充斥着着大量的近重复信息，有效地识别它们是一个很有意义的课题。例如，对于搜索引擎的爬虫系统来说，收录重复的网页是毫无意义的，只会造成存储和计算资源的浪费；同时，展示重复的信息对于用户来说也并不是最好的体验。造成网页近重复的可能原因主要包括： 

• 镜像网站
• 内容复制
• 嵌入广告
• 计数改变
• 少量修改

一个简化的爬虫系统架构如下图所示： 




事实上，传统比较两个文本相似性的方法，大多是将文本分词之后，转化为特征向量距离的度量，比如常见的欧氏距离、海明距离或者余弦角度等等。两两比较固然能很好地适应，但这种方法的一个最大的缺点就是，无法将其扩展到海量数据。例如，试想像Google那种收录了数以几十亿互联网信息的大型搜索引擎，每天都会通过爬虫的方式为自己的索引库新增的数百万网页，如果待收录每一条数据都去和网页库里面的每条记录算一下余弦角度，其计算量是相当恐怖的。 

我们考虑采用为每一个web文档通过hash的方式生成一个指纹（fingerprint）。传统的加密式hash，比如md5，其设计的目的是为了让整个分布尽可能地均匀，输入内容哪怕只有轻微变化，hash就会发生很大地变化。我们理想当中的哈希函数，需要对几乎相同的输入内容，产生相同或者相近的hashcode，换句话说，hashcode的相似程度要能直接反映输入内容的相似程度。很明显，前面所说的md5等传统hash无法满足我们的需求。 

simhash是locality sensitive hash（局部敏感哈希）的一种，最早由Moses Charikar在《similarity estimation techniques from rounding algorithms》一文中提出。Google就是基于此算法实现网页文件查重的。我们假设有以下三段文本： 

• the cat sat on the mat
• the cat sat on a mat
• we all scream for ice cream

使用传统hash可能会产生如下的结果： 


使用simhash会应该产生类似如下的结果： 


海明距离的定义，为两个二进制串中不同位的数量。上述三个文本的simhash结果，其两两之间的海明距离为(p1,p2)=4，(p1,p3)=16以及(p2,p3)=12。事实上，这正好符合文本之间的相似度，p1和p2间的相似度要远大于与p3的。 

如何实现这种hash算法呢？以上述三个文本为例，整个过程可以分为以下六步： 
1、选择simhash的位数，请综合考虑存储成本以及数据集的大小，比如说32位 
2、将simhash的各位初始化为0 
3、提取原始文本中的特征，一般采用各种分词的方式。比如对于"the cat sat on the mat"，采用两两分词的方式得到如下结果：{"th", "he", "e ", " c", "ca", "at", "t ", " s", "sa", " o", "on", "n ", " t", " m", "ma"} 
4、使用传统的32位hash函数计算各个word的hashcode，比如："th".hash = -502157718 
，"he".hash = -369049682，…… 
5、对各word的hashcode的每一位，如果该位为1，则simhash相应位的值加1；否则减1 
6、对最后得到的32位的simhash，如果该位大于1，则设为1；否则设为0 

整个过程可以参考下图： 



按照Charikar在论文中阐述的，64位simhash，海明距离在3以内的文本都可以认为是近重复文本。当然，具体数值需要结合具体业务以及经验值来确定。 
  
使用上述方法产生的simhash可以用来比较两个文本之间的相似度。问题是，如何将其扩展到海量数据的近重复检测中去呢？譬如说对于64位的待查询文本的simhash code来说，如何在海量的样本库（>1M）中查询与其海明距离在3以内的记录呢？下面在引入simhash的索引结构之前，先提供两种常规的思路。第一种是方案是查找待查询文本的64位simhash code的所有3位以内变化的组合，大约需要四万多次的查询，参考下图： 



另一种方案是预生成库中所有样本simhash code的3位变化以内的组合，大约需要占据4万多倍的原始空间，参考下图： 



显然，上述两种方法，或者时间复杂度，或者空间复杂度，其一无法满足实际的需求。我们需要一种方法，其时间复杂度优于前者，空间复杂度优于后者。 

假设我们要寻找海明距离3以内的数值，根据抽屉原理，只要我们将整个64位的二进制串划分为4块，无论如何，匹配的两个simhash code之间至少有一块区域是完全相同的，如下图所示： 



由于我们无法事先得知完全相同的是哪一块区域，因此我们必须采用存储多份table的方式。在本例的情况下，我们需要存储4份table，并将64位的simhash code等分成4份；对于每一个输入的code，我们通过精确匹配的方式，查找前16位相同的记录作为候选记录，如下图所示： 



让我们来总结一下上述算法的实质： 
1、将64位的二进制串等分成四块 
2、调整上述64位二进制，将任意一块作为前16位，总共有四种组合，生成四份table 
3、采用精确匹配的方式查找前16位 
4、如果样本库中存有2^34（差不多10亿）的哈希指纹，则每个table返回2^(34-16)=262144个候选结果，大大减少了海明距离的计算成本 

我们可以将这种方法拓展成多种配置，不过，请记住，table的数量与每个table返回的结果呈此消彼长的关系，也就是说，时间效率与空间效率不可兼得，参看下图： 



事实上，这就是Google每天所做的，用来识别获取的网页是否与它庞大的、数以十亿计的网页库是否重复。另外，simhash还可以用于信息聚类、文件压缩等。 

也许，读到这里，你已经感受到数学的魅力了。

来源：http://grunt1223.iteye.com/blog/964564 

海量数据相似度计算之simhash和海明距离

通过  采集系统 我们采集了大量文本数据，但是文本中有很多重复数据影响我们对于结果的分析。分析前我们需要对这些数据去除重复，如何选择和设计文本的去重算法？常见的有余弦夹角算法、欧式距离、Jaccard相似度、最长公共子串、编辑距离等。这些算法对于待比较的文本数据不多时还比较好用，如果我们的爬虫每天采集的数据以千万计算，我们如何对于这些海量千万级的数据进行高效的合并去重。最简单的做法是拿着待比较的文本和数据库中所有的文本比较一遍如果是重复的数据就标示为重复。看起来很简单，我们来做个测试，就拿最简单的两个数据使用Apache提供的 Levenshtein for 循环100w次计算这两个数据的相似度。代码结果如下：

耗费时间： 4266 ms

大跌眼镜，居然计算耗费4秒。假设我们一天需要比较100w次，光是比较100w次的数据是否重复就需要4s，就算4s一个文档，单线程一分钟才处理15个文档，一个小时才900个，一天也才21600个文档，这个数字和一天100w相差甚远，需要多少机器和资源才能解决。

为此我们需要一种应对于海量数据场景的去重方案，经过研究发现有种叫 local sensitive hash 局部敏感哈希 的东西，据说这玩意可以把文档降维到hash数字，数字两两计算运算量要小很多。查找很多文档后看到google对于网页去重使用的是simhash，他们每天需要处理的文档在亿级别，大大超过了我们现在文档的水平。既然老大哥也有类似的应用，我们也赶紧尝试下。simhash是由 Charikar 在2002年提出来的，参考  《Similarity estimation techniques from rounding algorithms》 。 介绍下这个算法主要原理，为了便于理解尽量不使用数学公式，分为这几步：

• 1、分词，把需要判断文本分词形成这个文章的特征单词。最后形成去掉噪音词的单词序列并为每个词加上权重，我们假设权重分为5个级别（1~5）。比如：“ 美国“51区”雇员称内部有9架飞碟，曾看见灰色外星人 ” ==> 分词后为 “ 美国（4） 51区（5） 雇员（3） 称（1） 内部（2） 有（1） 9架（3） 飞碟（5） 曾（1） 看见（3） 灰色（4） 外星人（5）”，括号里是代表单词在整个句子里重要程度，数字越大越重要。

• 2、hash，通过hash算法把每个词变成hash值，比如“美国”通过hash算法计算为 100101,“51区”通过hash算法计算为 101011。这样我们的字符串就变成了一串串数字，还记得文章开头说过的吗，要把文章变为数字计算才能提高相似度计算性能，现在是降维过程进行时。

• 3、加权，通过 2步骤的hash生成结果，需要按照单词的权重形成加权数字串，比如“美国”的hash值为“100101”，通过加权计算为“4 -4 -4 4 -4 4”；“51区”的hash值为“101011”，通过加权计算为 “ 5 -5 5 -5 5 5”。

• 4、合并，把上面各个单词算出来的序列值累加，变成只有一个序列串。比如 “美国”的 “4 -4 -4 4 -4 4”，“51区”的 “ 5 -5 5 -5 5 5”， 把每一位进行累加， “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。这里作为示例只算了两个单词的，真实计算需要把所有单词的序列串累加。

• 5、降维，把4步算出来的 “9 -9 1 -1 1 9” 变成 0 1 串，形成我们最终的simhash签名。 如果每一位大于0 记为 1，小于0 记为 0。最后算出结果为：“1 0 1 0 1 1”。

整个过程图为：

大家可能会有疑问，经过这么多步骤搞这么麻烦，不就是为了得到个 0 1 字符串吗？我直接把这个文本作为字符串输入，用hash函数生成 0 1 值更简单。其实不是这样的，传统hash函数解决的是生成唯一值，比如 md5、hashmap等。md5是用于生成唯一签名串，只要稍微多加一个字符md5的两个数字看起来相差甚远；hashmap也是用于键值对查找，便于快速插入和查找的数据结构。不过我们主要解决的是文本相似度计算，要比较的是两个文章是否相识，当然我们降维生成了hashcode也是用于这个目的。看到这里估计大家就明白了，我们使用的simhash就算把文章中的字符串变成 01 串也还是可以用于计算相似度的，而传统的hashcode却不行。我们可以来做个测试，两个相差只有一个字符的文本串，“你妈妈喊你回家吃饭哦，回家罗回家罗” 和 “你妈妈叫你回家吃饭啦，回家罗回家罗”。

通过simhash计算结果为：

1000010010101101111111100000101011010001001111100001001011001011

1000010010101101011111100000101011010001001111100001101010001011

通过 hashcode计算为：

1111111111111111111111111111111110001000001100110100111011011110

1010010001111111110010110011101

大家可以看得出来，相似的文本只有部分 01 串变化了，而普通的hashcode却不能做到，这个就是局部敏感哈希的魅力。目前Broder提出的shingling算法和Charikar的simhash算法应该算是业界公认比较好的算法。在simhash的发明人Charikar的论文中并没有给出具体的simhash算法和证明， “量子图灵”得出的证明simhash是由随机超平面hash算法演变而来的。

现在通过这样的转换，我们把库里的文本都转换为simhash 代码，并转换为long类型存储，空间大大减少。现在我们虽然解决了空间，但是如何计算两个simhash的相似度呢？难道是比较两个simhash的01有多少个不同吗？对的，其实也就是这样，我们通过海明距离（Hamming distance）就可以计算出两个simhash到底相似不相似。两个simhash对应二进制（01串）取值不同的数量称为这两个simhash的海明距离。举例如下： 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同，则海明距离为3。对于二进制字符串的a和b，海明距离为等于在a XOR b运算结果中1的个数（普遍算法）。

为了高效比较，我们预先加载了库里存在文本并转换为simhash code 存储在内存空间。来一条文本先转换为 simhash code，然后和内存里的simhash code 进行比较，测试100w次计算在100ms。速度大大提升。

未完待续：

1、目前速度提升了但是数据是不断增量的，如果未来数据发展到一个小时100w，按现在一次100ms，一个线程处理一秒钟 10次，一分钟 60 * 10 次，一个小时 60*10 *60 次 = 36000次，一天 60*10*60*24 = 864000次。 我们目标是一天100w次，通过增加两个线程就可以完成。但是如果要一个小时100w次呢？则需要增加30个线程和相应的硬件资源保证速度能够达到，这样成本也上去了。能否有更好的办法，提高我们比较的效率？

2、通过大量测试，simhash用于比较大文本，比如500字以上效果都还蛮好，距离小于3的基本都是相似，误判率也比较低。但是如果我们处理的是微博信息，最多也就140个字，使用simhash的效果并不那么理想。看如下图，在距离为3时是一个比较折中的点，在距离为10时效果已经很差了，不过我们测试短文本很多看起来相似的距离确实为10。如果使用距离为3，短文本大量重复信息不会被过滤，如果使用距离为10，长文本的错误率也非常高，如何解决？

参考：
Detecting near-duplicates for web crawling.

Similarity estimation techniques from rounding algorithms.

http://en.wikipedia.org/wiki/Locality_sensitive_hashing

http://en.wikipedia.org/wiki/Hamming_distance

simHash 简介以及 java 实现

simhash原理推导

文章来源：http://www.lanceyan.com/tech/arch/simhash_hamming_distance_similarity.html

海量数据相似度计算之simhash短文本查找

在前一篇文章 《 海量数据相似度计算之simhash和海明距离》 介绍了simhash的原理，大家应该感觉到了算法的魅力。但是随着业务的增长 simhash的数据也会暴增，如果一天100w，10天就1000w了。我们如果插入一条数据就要去比较1000w次的simhash，计算量还是蛮大，普通PC 比较1000w次海明距离需要 300ms ，和5000w数据比较需要1.8 s。看起来相似度计算不是很慢，还在秒级别。给大家算一笔账就知道了：

随着业务增长需要一个小时处理100w次，一个小时为3600 *1000 = 360w毫秒，计算一下一次相似度比较最多只能消耗 360w / 100w = 3.6毫秒。300ms慢吗，慢！1.8S慢吗，太慢了！很多情况大家想的就是升级、增加机器，但有些时候光是增加机器已经解决不了问题了，就算增加机器也不是短时间能够解决的，需要考虑分布式、客户预算、问题解决的容忍时间？头大时候要相信人类的智慧是无穷的，泡杯茶，听下轻音乐：）畅想下宇宙有多大，宇宙外面还有什么东西，程序员有什么问题能够难倒呢？

加上客户还提出的几个，汇总一下技术问题：

• 1、一个小时需要比较100w次，也就是每条数据和simhash库里的数据比较需要做到3.6毫秒。
• 2、两条同一时刻发出的文本如果重复也只能保留一条。
• 3、希望保留2天的数据进行比较去重，按照目前的量级和未来的增长，2天大概在2000w — 5000w 中间。
• 4、短文本和长文本都要去重，经过测试长文本使用simhash效果很好，短文本使用simhash 准备度不高。

目前我们估算一下存储空间的大小，就以JAVA 来说，存储一个simhash 需要一个原生态 lang 类型是64位 = 8 byte，如果是 Object 对象还需要额外的 8 byte，所以我们尽量节约空间使用原生态的lang类型。假设增长到最大的5000w数据， 5000w * 8byte = 400000000byte = 400000000/( 1024 * 1024) = 382 Mb，所以按照这个大小普通PC服务器就可以支持，这样第三个问题就解决了。

比较5000w次怎么减少时间呢？其实这也是一个查找的过程，我们想想以前学过的查找算法： 顺序查找、二分查找、二叉排序树查找、索引查找、哈希查找。不过我们这个不是比较数字是否相同，而是比较海明距离，以前的算法并不怎么通用，不过解决问题的过程都是通用的。还是和以前一样，不使用数学公式，使用程序猿大家都理解的方式。还记得JAVA里有个HashMap吗？我们要查找一个key值时，通过传入一个key就可以很快的返回一个value，这个号称查找速度最快的数据结构是如何实现的呢？看下hashmap的内部结构：

如果我们需要得到key对应的value，需要经过这些计算，传入key，计算key的hashcode，得到7的位置；发现7位置对应的value还有好几个，就通过链表查找，直到找到v72。其实通过这么分析，如果我们的hashcode设置的不够好，hashmap的效率也不见得高。借鉴这个算法，来设计我们的simhash查找。通过顺序查找肯定是不行的，能否像hashmap一样先通过键值对的方式减少顺序比较的次数。看下图：

存储：
1、将一个64位的simhash code拆分成4个16位的二进制码。（图上红色的16位）
2、分别拿着4个16位二进制码查找当前对应位置上是否有元素。（放大后的16位）
3、对应位置没有元素，直接追加到链表上；对应位置有则直接追加到链表尾端。（图上的 S1 — SN）

查找：
1、将需要比较的simhash code拆分成4个16位的二进制码。
2、分别拿着4个16位二进制码每一个去查找simhash集合对应位置上是否有元素。
2、如果有元素，则把链表拿出来顺序查找比较，直到simhash小于一定大小的值，整个过程完成。

原理：
借鉴hashmap算法找出可以hash的key值，因为我们使用的simhash是局部敏感哈希，这个算法的特点是只要相似的字符串只有个别的位数是有差别变化。那这样我们可以推断两个相似的文本，至少有16位的simhash是一样的。具体选择16位、8位、4位，大家根据自己的数据测试选择，虽然比较的位数越小越精准，但是空间会变大。分为4个16位段的存储空间是单独simhash存储空间的4倍。之前算出5000w数据是 382 Mb，扩大4倍1.5G左右，还可以接受：）

通过这样计算，我们的simhash查找过程全部降到了1毫秒以下。就加了一个hash效果这么厉害？我们可以算一下，原来是5000w次顺序比较，现在是少了2的16次方比较，前面16位变成了hash查找。后面的顺序比较的个数是多少？ 2^16 = 65536， 5000w/65536 = 763 次。。。。实际最后链表比较的数据也才 763次！所以效率大大提高！

到目前第一点降到3.6毫秒、支持5000w数据相似度比较做完了。还有第二点同一时刻发出的文本如果重复也只能保留一条和短文本相识度比较怎么解决。其实上面的问题解决了，这两个就不是什么问题了。

• 之前的评估一直都是按照线性计算来估计的，就算有多线程提交相似度计算比较，我们提供相似度计算服务器也需要线性计算。比如同时客户端发送过来两条需要比较相似度的请求，在服务器这边都进行了一个排队处理，一个接着一个，第一个处理完了在处理第二个，等到第一个处理完了也就加入了simhash库。所以只要服务端加了队列，就不存在同时请求不能判断的情况。
• simhash如何处理短文本？换一种思路，simhash可以作为局部敏感哈希第一次计算缩小整个比较的范围，等到我们只有比较700多次比较时，就算使用我们之前精准度高计算很慢的编辑距离也可以搞定。当然如果觉得慢了，也可以使用余弦夹角等效率稍微高点的相似度算法。

参考：
我的数学之美系列二 —— simhash与重复信息识别

文章来源：http://www.lanceyan.com/tech/arch/simhash_hamming_distance_similarity2-html.html