[转] 文本相似性算法Simhash原理及实践
|
simhash（局部敏感哈希）的原理 simhash的背景?simhash广泛的用于搜索领域中，也许在面试时你会经常遇到这样的问题，如果对抓取的网页进行排重，如何对搜索结果进行排重等等。随着信息膨胀时代的来临，算法也在不断的精进，相似算法同样在不断的发展，接触过lucene的同学想必都会了解相似夹角的概念，那就是一种相似算法，通过计算两个向量的余弦值来判断两个向量的相似性，但这种方式需要两两进行计算向量的余弦夹角，计算量比较大，不能用于实时计算或是大数据量的运算，比如在做搜索结果的相似性排重时，需要对上千条结果进行相似性排重，如果两两比对的话，最少也需要进行上千次的向量余弦值计算，其中涉及到分词，特征提取，余弦值计算等，很难满足性能的需要。jaccard相似度也是一种相似算法，它的计算方式比较直观，就是sim（x,y）= (x∩y) / （x∪y）,例如： 也是一种需要实时生成特征向量并且进行计算的算法。 那么 什么是simhash呢？Simhash 是一种用单个哈希函数得到文档最小哈希签名的方法，过程为：
对两篇文档，它们的?Simhash?值之间不同位的个数越少（即海明距离越小），它们之间的?Jaccard?相似度越高。 什么是局部敏感性哈希呢？局部敏感哈希（LSH）是指这样的哈希方法：对两篇文档，如果它们相似，则它们的哈希值有较高的概率是相同的。有了文档的最小哈希签名，我们就能实现这种哈希方法。直观的做法是，将包含?b×r?个值最小哈希签名分为?b?等份，每份?r?个，对两个文档，定义?P?为两个文档至少含有1个相同份的概率，显然，文档间的Jaccard?相似度越高，哈希签名具有相同值的位数就越多，概率??就越大。
如何计算simhash呢？simhash从内部看就是特征向量hash叠加的效果，并且具有局部敏感性，普通的hash算法针对差别不大的字符串会产生截然不同的hash值，但是simhash计算出来的hash值的海明距离会很相近。
具体的算法是将doc分解为特征向量，具体可以通过分词，也可以通过bigram实现，并且可以赋予一定的权重，针对每个向量使用统一的hash函数进行hash，针对每个特征的hash值的每一位，如果是1就对simhash值的对应位加1，当然也可以使用权重，如果对应位是0，则simhash的对应位减1，对最后的simhash值如果该位大于0则该位置1，如果该位小于0，则该位置0，最后就可以得到一个真正的simhash值。
过程可以参考下面：
汉明距离的计算代码如下：
输出为： hamdistance of 851459198 and 847263864 is 4
simhash的好处？simhash离线计算指纹，方便了大规模数据比较时的消耗，不需要在计算时提取特征进行计算，hash值的可比性很强，只需要比较汉明距离，
方便了从海量数据中发掘相似项的实现，试想一个新文档同百万级甚至千万级数据做相似夹角的情况。simhash大大减少了相似项排重的复杂度。
如何应用simhash呢，具体的应用场景？simhash有两个比较典型的应用，一个是网页抓取的排重，一个是检索时相似doc
的排重
前者是在大集合中寻找是否具有相似项，后者是对检索的集合进行滤重。
检索集中发现相似项比较简单，就是针对要排重的field离线提取特征，并计算simhash值，然后将检索集中德记录进行两两比较，就是计算汉明距离，两个simhash值异或后求二进制中1的个数就是汉明距离了，这是真对较少的记录。
针对较多的记录，例如抓取时做排重，针对上千万，或数亿的数据，就需要对算法进行改进，因为求simhash的相似性，其实就是计算simhash间的汉明距离。
提到查找算法就不得不提到O（1）的hash表，但是如何让simhash和hash表联系在一起呢？
假如我们认为海明距离在3以内的具有很高的相似性，那样我们就可以用到鸽巢原理，如果将simhash分成4段的话，那么至少有一段完全相等的情况下才能满足海明距离在3以内。同理将simhash分为6段，那么至少要满足三段完全相等，以此类推。
这样我们就可以使用相等的部分做为hash的key，然后将具体的simhash值依次链接到value中，方便计算具体汉明距离。
1、将64位的二进制串等分成四块?
2、调整上述64位二进制，将任意一块作为前16位，总共有四种组合，生成四份table? 3、采用精确匹配的方式查找前16位? 4、如果样本库中存有2^34（差不多10亿）的哈希指纹，则每个table返回2^(34-16)=262144个候选结果，大大减少了海明距离的计算成本? 我们可以将这种方法拓展成多种配置，不过，请记住，table的数量与每个table返回的结果呈此消彼长的关系，也就是说，时间效率与空间效率不可兼得，参看下图：?
现在的以图找图功能也是simhash的一种展现，同样适用指纹值分桶查找的原理实现。
参考引用
http://tech.uc.cn/?p=1086
http://grunt1223.iteye.com/blog/964564
http://www.lanceyan.com/tag/simhash
http://www.cs.princeton.edu/courses/archive/spr04/cos598B/bib/CharikarEstim.pdf
来源：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就是基于此算法实现网页文件查重的。我们假设有以下三段文本：?
使用传统hash可能会产生如下的结果：?
引用
irb(main):006:0> p1 = 'the cat sat on the mat'?
irb(main):005:0> p2 = 'the cat sat on a mat'? irb(main):007:0> p3 = 'we all scream for ice cream'? irb(main):007:0> p1.hash? => 415542861? irb(main):007:0> p2.hash? => 668720516? irb(main):007:0> p3.hash? => 767429688 使用simhash会应该产生类似如下的结果：? irb(main):003:0> p1.simhash? => 851459198? 00110010110000000011110002222210? irb(main):004:0> p2.simhash? => 847263864? 00110010100000000011100001111000? irb(main):002:0> p3.simhash? => 984968088? 00111010101101010110101110011000 海明距离的定义，为两个二进制串中不同位的数量。上述三个文本的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? 整个过程可以参考下图：?
?? 使用上述方法产生的simhash可以用来比较两个文本之间的相似度。问题是，如何将其扩展到海量数据的近重复检测中去呢？譬如说对于64位的待查询文本的simhash code来说，如何在海量的样本库（>1M）中查询与其海明距离在3以内的记录呢？下面在引入simhash的索引结构之前，先提供两种常规的思路。第一种是方案是查找待查询文本的64位simhash code的所有3位以内变化的组合，大约需要四万多次的查询，参考下图：?
假设我们要寻找海明距离3以内的数值，根据抽屉原理，只要我们将整个64位的二进制串划分为4块，无论如何，匹配的两个simhash code之间至少有一块区域是完全相同的，如下图所示：?
1、将64位的二进制串等分成四块? 2、调整上述64位二进制，将任意一块作为前16位，总共有四种组合，生成四份table? 3、采用精确匹配的方式查找前16位? 4、如果样本库中存有2^34（差不多10亿）的哈希指纹，则每个table返回2^(34-16)=262144个候选结果，大大减少了海明距离的计算成本? 我们可以将这种方法拓展成多种配置，不过，请记住，table的数量与每个table返回的结果呈此消彼长的关系，也就是说，时间效率与空间效率不可兼得，参看下图：?
也许，读到这里，你已经感受到数学的魅力了。 来源：http://grunt1223.iteye.com/blog/964564?
海量数据相似度计算之simhash和海明距离
通过?采集系统?我们采集了大量文本数据，但是文本中有很多重复数据影响我们对于结果的分析。分析前我们需要对这些数据去除重复，如何选择和设计文本的去重算法？常见的有余弦夹角算法、欧式距离、Jaccard相似度、最长公共子串、编辑距离等。这些算法对于待比较的文本数据不多时还比较好用，如果我们的爬虫每天采集的数据以千万计算，我们如何对于这些海量千万级的数据进行高效的合并去重。最简单的做法是拿着待比较的文本和数据库中所有的文本比较一遍如果是重复的数据就标示为重复。看起来很简单，我们来做个测试，就拿最简单的两个数据使用Apache提供的 Levenshtein for 循环100w次计算这两个数据的相似度。代码结果如下：
? ? ? ? ? ??
String?s1?
=?
"你妈妈喊你回家吃饭哦，回家罗回家罗"?
;
? ? ? ? ? ?? String?s2? =? "你妈妈叫你回家吃饭啦，回家罗回家罗"? ; ? ? ? ? ? ?? long?t1? =? System. currentTimeMillis ( ) ; ? ? ? ? ? ?? for? ( int?i? =? 0 ;?i? <? 1000000 ;?i ++ )? { ? ? ? ? ? ? ? ? ? ? int?dis? =?StringUtils . getLevenshteinDistance (s1,s2 ) ; ? ? ? ? ? ?? } ? ? ? ? ? ?? long?t2? =? currentTimeMillis ( ) ; ? ? ? ? ? ?? System.? out?. println ( " 耗费时间： "? +? (t2? -?t1 )? +? " ?ms " ) ; 耗费时间： 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》?。 介绍下这个算法主要原理，为了便于理解尽量不使用数学公式，分为这几步：
整个过程图为：
大家可能会有疑问，经过这么多步骤搞这么麻烦，不就是为了得到个 0 1 字符串吗？我直接把这个文本作为字符串输入，用hash函数生成 0 1 值更简单。其实不是这样的，传统hash函数解决的是生成唯一值，比如 md5、hashmap等。md5是用于生成唯一签名串，只要稍微多加一个字符md5的两个数字看起来相差甚远；hashmap也是用于键值对查找，便于快速插入和查找的数据结构。不过我们主要解决的是文本相似度计算，要比较的是两个文章是否相识，当然我们降维生成了hashcode也是用于这个目的。看到这里估计大家就明白了，我们使用的simhash就算把文章中的字符串变成 01 串也还是可以用于计算相似度的，而传统的hashcode却不行。我们可以来做个测试，两个相差只有一个字符的文本串，“你妈妈喊你回家吃饭哦，回家罗回家罗” 和 “你妈妈叫你回家吃饭啦，回家罗回家罗”。 通过simhash计算结果为： 1000010010101101122222100000101011010001002222200001001011001011 1000010010101101022222100000101011010001002222200001101010001011 通过 hashcode计算为： 2222222222222222222222222222221110001000001100110100111011011110 1010010002222211110010110011101 大家可以看得出来，相似的文本只有部分 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，长文本的错误率也非常高，如何解决？
参考： 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慢吗，太慢了！很多情况大家想的就是升级、增加机器，但有些时候光是增加机器已经解决不了问题了，就算增加机器也不是短时间能够解决的，需要考虑分布式、客户预算、问题解决的容忍时间？头大时候要相信人类的智慧是无穷的，泡杯茶，听下轻音乐：）畅想下宇宙有多大，宇宙外面还有什么东西，程序员有什么问题能够难倒呢？ 加上客户还提出的几个，汇总一下技术问题： 目前我们估算一下存储空间的大小，就以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一样先通过键值对的方式减少顺序比较的次数。看下图：
存储： 查找： 原理： 通过这样计算，我们的simhash查找过程全部降到了1毫秒以下。就加了一个hash效果这么厉害？我们可以算一下，原来是5000w次顺序比较，现在是少了2的16次方比较，前面16位变成了hash查找。后面的顺序比较的个数是多少？ 2^16 = 65536， 5000w/65536 = 763 次。。。。实际最后链表比较的数据也才 763次！所以效率大大提高！ 到目前第一点降到3.6毫秒、支持5000w数据相似度比较做完了。还有第二点同一时刻发出的文本如果重复也只能保留一条和短文本相识度比较怎么解决。其实上面的问题解决了，这两个就不是什么问题了。
参考： 文章来源：http://www.lanceyan.com/tech/arch/simhash_hamming_distance_similarity2-html.html （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
