1.使用背景

最近在做中国软件杯,涉及到文档关联,一开始用的方法是提取文档关键词,然后建立特征向量。
当上传一篇文档的时候,对文档分词,去掉停词,然后对于任意两个文档的特征向量求余弦定理计算相似度。
相似度在一定区间(不能太相似,否则内容基本相同),然后在这两个文档之间建一条边,代表这两个文档相关。
但是有一个问题,太慢,假设有100万个文档,当上传一个新文档的时候,特征向量维度如果很大的话,时间复杂度爆炸。

2.SimHash算法

先说一下传统的hash算法,比如我们有一个字符串“ABCD”,那我们的hash算法(最简单的)

int hashCode = 0;
for (int i = 0; i < length; i++) {
hashCode = (hashCode + (s[i] - 'A') * 171) % 10000007;
}

这样的hash方法都太敏感了,有一个字符的变动就差十万八千里,所以在任意两个文件之间用这种hash码没什么用。
所以我们需要一个相似hash函数-SimHash算法
SimHash算法思想还是很简单的。但是思想很奇妙,绝对数学之美!

第一步:扩展

假设一个文档有词t1, t2, t3,…, tk,他们的权重分别是w1, w2, w3,…,wk。
对于每一个词,我们都给他一个hashcode,然后把这个hashcode看成一个二进制。
比如t1的二进制位 101001,权重为w1,则对应的新的hashcode为(w1,-w1,w1,-w1,-w1,w1)
我们对于一篇文章我们把所有所有的词的hashcode得出来。然后对应位置求和。

第二步:收缩

比如得到的结果为(-0.5,1,2,-0.3),那么我们把每一位再回归为0,1。
如果ri > 0, 那么ri = 1。
如果ri < 0,那么ri = 0。
最终的SimHash = 0110

第三部:海明距离

对于n篇文档,我们已经计算出每篇文档的SimHash(用一个int/longlong类型保存即可),
当新插入一篇文档的时候,我们可以用O(n)的方法扫描所有文件。

在进行两个文档直接求海明距离的时候有一个小技巧:
首先我们对于两个值进行亦或,比如 100111 ^ 110001 = 010110,把相同的位置变成0,不同位置是1.
那么在求海明距离的时候,可以这么做,假设010110为x

int sum = 0; //海明距离
while (x) {
sum++;
x = (x) & (x - 1);
}

x-1就是把最后一位1变成0,然后该位后面都是1,取 & 之后,就全是0了。成功去掉最后一位1.

总结:
SimHash真的很奇妙,在理解之后真的可以感受到数学的奥妙所在。

SimHash具体的实现源码已经用java语言实现了,等比赛结束之后开源。

Lucene分词-最大正向匹配算法-Trie树的应用

分词算法千差万别。正向最大匹配算法应该算比较简单的一种。 性能不是很高,并且不能显示词性等,比较依赖于词典,不能进行语法分析等。   今天在学习的...

阅读全文

最大生成树在图片拼接中的应用

之前已经写过一篇 stitching_detailed的源码理解了。里面提到了最大生成树的问题。 今天想单独拿出来放在一个专栏里面,以后持续的写下去。   以前在ACM...

阅读全文

欢迎留言

*