simHash海量文本去重

simHash是google提出的用于计算海量文本相似度的算法：
(1) 分词 => word
(2) 单词权重 tfidf word => (word, weight)
(3) 每个词hash为指定长度的二进制串， 如 10010 => (hash, weight)
(4) 所有词加权合并 sum(hash * weight), 加权乘的时候把0当做-1对待
(5) 降维： (4)得到文档的向量， > 0映射 为 1 ， <=0 映射为0， 得到文档的 二进制向量，即文档的simHash签名
(6) 计算文档间的汉明距离
汉明距离计算方式：

  p1 = 100101 
  p2 = 101100
  p3 = p1 XOR p2
  i = 0 
  while(p3){
      p3 &= p3 -1
      i ++
}

simhash用于比较大的长文本, 可以取汉明距离为3， 对于短文本的效果比较差， 汉明距离可以取大一些进行相似过滤

———————————————————————————-
算法过程很简单，我们来理解一下原理，主要是参考自 http://www.cnblogs.com/hxsyl/p/4518506.html 。
假设词汇总量是5， 那么我们用于标记文档唯一性的词向量就是5维，文档d=(1, 2, 0, 3, 0), 权值标识该词对d的重要程度，0表示没有。词的hash函数生成3byte二进制串：
h(w1) = 101
h(w2) = 011
h(w3) = 100
h(w4) = 001
h(w5) = 110
特征矩阵(0 视为 -1)

1	-1	1
-1	1	1
1	-1	-1
-1	-1	1
1	1	-1

因为文档向量d(1, 2, 0, 3, 0) 是5维向量， 我们取特征矩阵的列向量：

    v1 = 1 -1 1 -1 1
    v2 = -1 1 -1 -1 -1 
    v3 = 1 1 -1 1 1 

v1, v2, v3 看做5维空间的三个超平面，文档d也是这个空间的一个平面， 现在我们想以v1, v2, v3为分割平面， 定位d的位置， 分别计算d与v1~v3超平面的夹角， 也就是算向量的点积， 点积大于0 标记为1 ，点积小于等于0 标记为0， 这样：
d T v1 = -4 < 0 钝角
d T v2 = -2 < 0 钝角
d T v3 = 6 > 0 锐角
得到d的签名=001，simHash的有效性这样就比较清楚了， 就是利用这3个超平面来定位出文档平面所在的位置，类似决策树中的树桩， 2^3 种分法，100万的文档， 理论上 20 byte签名就可以区分， 10亿的文档需要30byte（30个超平面）

图片.png

———————————————————————————-

假设我们库中有5000万(2^26)的文本， 每来一个新文本我们都需要做5000万次的汉明距离计算， 这个计算量还是比较大的，假设签名为64位。

考虑目标文档3位以内变化的签名有 C(64, 3) 4万多可能， 然后 4万 * 5000万的hash查询， 时间复杂度太大了

我们可以将库中已有的5000万文章的签名表切成4个表， 分别存储将64byte切开的ABCD四段中一段， 每进来一篇新文章，同样的分割为ABCD字段， 去与对应的表精确匹配(这个过程可以设置4个并发比较)， 取每个表join后剩下的文档ID， 大概每个表产出备选文档ID 有5000万/2^16 = 1000左右的量级，要找到5000万文档中和目标文档汉明距离小于3的文档集， 那么库中的文档至少ABCD有一段和目标文档完全匹配，这样我们最多会有 4 * 2 ^(26 -16) 篇备选文档， 大概4000多次汉明距离的计算就可以了

图片.png

参考：
http://grunt1223.iteye.com/blog/964564
http://www.cnblogs.com/hxsyl/p/4518506.html
http://blog.chinaunix.net/uid-25304914-id-4857313.htmlew