相似检测
相似检测
日前接到一个对名言警句这种短文本进行去重的小任务。
如何设计一个比较两篇文章相似度的算法？
来自于Google Moses Charikar发表的一篇论文“detecting near-duplicates for web crawling”中提出了simhash算法，专门用来解决亿万级别的网页的去重任务。
Simhash
simhash作为locality sensitive hash(LSH)（局部敏感哈希）的一种：
其主要思想是降维，将高维的特征向量映射成低维的特征向量，通过两个向量的Hamming Distance来确定文章是否重复或者高度近似。
其中，Hamming Distance，又称汉明距离，在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。也就是说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。例如：1011101 与 1001001 之间的汉明距离是 2。至于我们常说的字符串编辑距离则是一般形式的汉明距离。
如此，通过比较多个文档的simHash值的海明距离，可以获取它们的相似度。
步骤
simhash算法分为5个步骤：分词、hash、加权、合并、降维，具体过程如下所述：
- 分词
给定一段语句，进行分词，得到有效的特征向量，然后为每一个特征向量设置1-5等5个级别的权重（如果是给定一个文本，那么特征向量可以是文本中的词，其权重可以是这个词出现的次数）。
例如给定一段语句：“CSDN博客结构之法算法之道的作者July”，分词后为：“CSDN 博客 结构 之 法 算法 之 道 的 作者 July”，然后为每个特征向量赋予权值：CSDN(4) 博客(5) 结构(3) 之(1) 法(2) 算法(3) 之(1) 道(2) 的(1) 作者(5) July(5)，其中括号里的数字代表这个单词在整条语句中的重要程度，数字越大代表越重要。
- hash
通过普通的hash函数计算各个特征向量的hash值，hash值为二进制数01组成的n-bit签名（一般是64或128位，以根据实际需求增大位数）。
例如“CSDN”的hash值Hash(CSDN)为100101，“博客”的hash值Hash(博客)为“101011”。就这样，字符串就变成了一系列数字。
- 加权
在hash值的基础上，给所有特征向量进行加权，即W=Hash*weight，且遇到1则hash值和权值正相乘，遇到0则hash值和权值负相乘。
例如给“CSDN”的hash值“100101”加权得到：W(CSDN) = 100101*4 = 4 -4 -4 4 -4 4，给“博客”的hash值“101011”加权得到：W(博客)=101011*5 = 5 -5 5 -5 5 5，其余特征向量类似此般操作。
- 合并
将上述各个特征向量的加权结果累加，变成只有一个序列串。
例如“CSDN”的“4 -4 -4 4 -4 4”和“博客”的“5 -5 5 -5 5 5”进行累加，得到“4+5 -4+-5 -4+5 4+-5 -4+5 4+5”，得到“9 -9 1 -1 1”。
- 降维
对于n-bit签名的累加结果，如果大于0则置1，否则置0，从而得到该语句的simhash值，最后我们可以根据不同语句simhash的海明距离来判断相似度。
例如把上面计算出来的“9 -9 1 -1 1 9”降维（某位大于0记为1，小于0记为0），得到的01串为：“1 0 1 0 1 1”，从而形成它们的simhash签名。
比较
相似数据检测算法（shingle，SimHash，Bloomfilter） 比较
Shingle算法的空间和计算复杂性高，相似性精度也高，适合数据量不大且对精度要求高的应用。Simhash和bloom filter算法在空间消耗和计算复杂性方面都优于Shingle算法，但是精度有所损耗，取决于simhash的长度和bloom filter的大小。simhash的长度通常为64位或128位，这个基本可以满足应用的需求，可以根据实际需求增大位数。bloomfilter要大于simhash长度，可以根据最大shingle数的两倍来估算，精度方面也要优于simhash。由于hash函数的碰撞问题，simhash和bloom filter算法可能出现误判现象，即不相似的文件可能会判定为相似的。
总结一下，通常情况下，文件特征值
空间消耗方面，Shingle > bloom filter > simhash；
计算精度方面，Shingle < bloom filter < simhash。
Bloomfilter算法往往是比较折中的相似数据检测方法选择，但海量数据集的相似性计算往往采用simhash算法，在计算性能方面具有很大优势，而且更加适合MapReduce计算模型。