短文本相似度比较：simHash简介以及java实现

SimHash 简介以及 java 实现

传统的 hash 算法只负责将原始内容尽量均匀随机地映射为一个签名值&＃xff0c;原理上相当于伪随机数产生算法。产生的两个签名&＃xff0c;如果相等&＃xff0c;说明原始内容在一定概 率 下是相等的&＃xff1b;如果不相等&＃xff0c;除了说明原始内容不相等外&＃xff0c;不再提供任何信息&＃xff0c;因为即使原始内容只相差一个字节&＃xff0c;所产生的签名也很可能差别极大。从这个意义 上来 说&＃xff0c;要设计一个 hash 算法&＃xff0c;对相似的内容产生的签名也相近&＃xff0c;是更为艰难的任务&＃xff0c;因为它的签名值除了提供原始内容是否相等的信息外&＃xff0c;还能额外提供不相等的 原始内容的差异程度的信息。
而 Google 的 simhash 算法产生的签名&＃xff0c;可以满足上述要求。出人意料&＃xff0c;这个算法并不深奥&＃xff0c;其思想是非常清澈美妙的。

1、Simhash 算法简介

simhash算法的输入是一个向量&＃xff0c;输出是一个 f 位的签名值。为了陈述方便&＃xff0c;假设输入的是一个文档的特征集合&＃xff0c;每个特征有一定的权重。比如特征可以是文档中的词&＃xff0c;其权重可以是这个词出现的次数。 simhash 算法如下&＃xff1a;
1&＃xff0c;将一个 f 维的向量 V 初始化为 0 &＃xff1b; f 位的二进制数 S 初始化为 0 &＃xff1b;
2&＃xff0c;对每一个特征&＃xff1a;用传统的 hash 算法对该特征产生一个 f 位的签名 b 。对 i&＃61;1 到 f &＃xff1a;
如果b 的第 i 位为 1 &＃xff0c;则 V 的第 i 个元素加上该特征的权重&＃xff1b;
否则&＃xff0c;V 的第 i 个元素减去该特征的权重。 
3&＃xff0c;如果 V 的第 i 个元素大于 0 &＃xff0c;则 S 的第 i 位为 1 &＃xff0c;否则为 0 &＃xff1b;
4&＃xff0c;输出 S 作为签名。

2、算法几何意义和原理

这个算法的几何意义非常明了。它首先将每一个特征映射为f维空间的一个向量&＃xff0c;这个映射规则具体是怎样并不重要&＃xff0c;只要对很多不同的特征来说&＃xff0c;它们对所对应的向量是均匀随机分布的&＃xff0c;并且对相同的特征来说对应的向量是唯一的就行。比如一个特征的4位hash签名的二进制表示为1010&＃xff0c;那么这个特征对应的 4维向量就是(1, -1, 1, -1)T&＃xff0c;即hash签名的某一位为1&＃xff0c;映射到的向量的对应位就为1&＃xff0c;否则为-1。然后&＃xff0c;将一个文档中所包含的各个特征对应的向量加权求和&＃xff0c;加权的系数等于该特征的权重。得到的和向量即表征了这个文档&＃xff0c;我们可以用向量之间的夹角来衡量对应文档之间的相似度。最后&＃xff0c;为了得到一个f位的签名&＃xff0c;需要进一步将其压缩&＃xff0c;如果和向量的某一维大于0&＃xff0c;则最终签名的对应位为1&＃xff0c;否则为0。这样的压缩相当于只留下了和向量所在的象限这个信息&＃xff0c;而64位的签名可以表示多达264个象限&＃xff0c;因此只保存所在象限的信息也足够表征一个文档了。

明确了算法了几何意义&＃xff0c;使这个算法直观上看来是合理的。但是&＃xff0c;为何最终得到的签名相近的程度&＃xff0c;可以衡量原始文档的相似程度呢&＃xff1f;这需要一个清晰的思路和证明。在simhash的发明人Charikar的论文中[2]并没有给出具体的simhash算法和证明&＃xff0c;以下列出我自己得出的证明思路。

Simhash是由随机超平面hash算法演变而来的&＃xff0c;随机超平面hash算法非常简单&＃xff0c;对于一个n维向量v&＃xff0c;要得到一个f位的签名
1&＃xff0c;随机产生f个n维的向量r1,…rf&＃xff1b;
2&＃xff0c;对每一个向量ri&＃xff0c;如果v与ri的点积大于0&＃xff0c;则最终签名的第i位为1&＃xff0c;否则为0.

这个算法相当于随机产生了f个n维超平面&＃xff0c;每个超平面将向量v所在的空间一分为二&＃xff0c;v在这个超平面上方则得到一个1&＃xff0c;否则得到一个0&＃xff0c;然后将得到的 f个0或1组合起来成为一个f维的签名。如果两个向量u, v的夹角为θ&＃xff0c;则一个随机超平面将它们分开的概率为θ/π&＃xff0c;因此u, v的签名的对应位不同的概率等于θ/π。所以&＃xff0c;我们可以用两个向量的签名的不同的对应位的数量&＃xff0c;即汉明距离&＃xff0c;来衡量这两个向量的差异程度。

Simhash算法与随机超平面hash是怎么联系起来的呢&＃xff1f;在simhash算法中&＃xff0c;并没有直接产生用于分割空间的随机向量&＃xff0c;而是间接产生的&＃xff1a;第 k个特征的hash签名的第i位拿出来&＃xff0c;如果为0&＃xff0c;则改为-1&＃xff0c;如果为1则不变&＃xff0c;作为第i个随机向量的第k维。由于hash签名是f位的&＃xff0c;因此这样能产生 f个随机向量&＃xff0c;对应f个随机超平面。下面举个例子&＃xff1a;
假设用5个特征w1,…,w5来表示所有文档&＃xff0c;现要得到任意文档的一个3维签名。假设这5个特征对应的3维向量分别为&＃xff1a;
h(w1) &＃61; (1, -1, 1)T
h(w2) &＃61; (-1, 1, 1)T
h(w3) &＃61; (1, -1, -1)T
h(w4) &＃61; (-1, -1, 1)T
h(w5) &＃61; (1, 1, -1)T

按simhash算法&＃xff0c;要得到一个文档向量d&＃61;(w1&＃61;1, w2&＃61;2, w3&＃61;0, w4&＃61;3, w5&＃61;0) T的签名&＃xff0c;

先要计算向量m &＃61; 1*h(w1) &＃43; 2*h(w2) &＃43; 0*h(w3) &＃43; 3*h(w4) &＃43; 0*h(w5) &＃61; (-4, -2, 6) T&＃xff0c;
然后根据simhash算法的步骤3&＃xff0c;得到最终的签名s&＃61;001。

上面的计算步骤其实相当于&＃xff0c;先得到3个5维的向量&＃xff0c;第1个向量由h(w1),…,h(w5)的第1维组成&＃xff1a;

r1&＃61;(1,-1,1,-1,1) T&＃xff1b;
第2个5维向量由h(w1),…,h(w5)的第2维组成&＃xff1a;
r2&＃61;(-1,1,-1,-1,1) T&＃xff1b;
同理&＃xff0c;第3个5维向量为&＃xff1a;
r3&＃61;(1,1,-1,1,-1) T.
按随机超平面算法的步骤2&＃xff0c;分别求向量d与r1,r2,r3的点积:
d T r1&＃61;-4 <0&＃xff0c;所以s1&＃61;0;
d T r2&＃61;-2 <0&＃xff0c;所以s2&＃61;0;
d T r3&＃61;6 > 0&＃xff0c;所以s3&＃61;1.
故最终的签名s&＃61;001&＃xff0c;与simhash算法产生的结果是一致的。

从上面的计算过程可以看出&＃xff0c;simhash算法其实与随机超平面hash算法是相同的&＃xff0c;simhash算法得到的两个签名的汉明距离&＃xff0c;可以用来衡量原始向量的夹角。这其实是一种降维技术&＃xff0c;将高维的向量用较低维度的签名来表征。衡量两个内容相似度&＃xff0c;需要计算汉明距离&＃xff0c;这对给定签名查找相似内容的应用来说带来了一些计算上的困难&＃xff1b;我想&＃xff0c;是否存在更为理想的simhash算法&＃xff0c;原始内容的差异度&＃xff0c;可以直接由签名值的代数差来表示呢&＃xff1f;

3、比较相似度

海明距离&＃xff1a; 两个码字的对应比特取值不同的比特数称为这两个码字的海明距离。一个有效编码集中, 任意两个码字的海明距离的最小值称为该编码集的海明距离。举例如下&＃xff1a; 10101 和 00110 从第一位开始依次有第一位、第四、第五位不同&＃xff0c;则海明距离为 3.

异或&＃xff1a; 只有在两个比较的位不同时其结果是1 &＃xff0c;否则结果为 0 

对每篇文档根据SimHash 算出签名后&＃xff0c;再计算两个签名的海明距离&＃xff08;两个二进制异或后 1 的个数&＃xff09;即可。根据经验值&＃xff0c;对 64 位的 SimHash &＃xff0c;海明距离在 3 以内的可以认为相似度比较高。
假设对64 位的 SimHash &＃xff0c;我们要找海明距离在 3 以内的所有签名。我们可以把 64 位的二进制签名均分成 4块&＃xff0c;每块 16 位。根据鸽巢原理&＃xff08;也成抽屉原理&＃xff0c;见组合数学&＃xff09;&＃xff0c;如果两个签名的海明距离在 3 以内&＃xff0c;它们必有一块完全相同。
我们把上面分成的4 块中的每一个块分别作为前 16 位来进行查找。 建立倒排索引。

如果库中有2^34 个&＃xff08;大概 10 亿&＃xff09;签名&＃xff0c;那么匹配上每个块的结果最多有 2^(34-16)&＃61;262144 个候选结果 (假设数据是均匀分布&＃xff0c; 16 位的数据&＃xff0c;产生的像限为 2^16 个&＃xff0c;则平均每个像限分布的文档数则 2^34/2^16 &＃61; 2^(34-16)) &＃xff0c;四个块返回的总结果数为 4* 262144 &＃xff08;大概 100 万&＃xff09;。原本需要比较 10 亿次&＃xff0c;经过索引&＃xff0c;大概就只需要处理 100 万次了。由此可见&＃xff0c;确实大大减少了计算量。 

4、示例代码&＃xff1a;

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.StringTokenizer;public class SimHash1 {private String tokens;private BigInteger intSimHash;private String strSimHash;private int hashbits &＃61; 64;public SimHash1(String tokens) {this.tokens &＃61; tokens;this.intSimHash &＃61; this.simHash();}public SimHash1(String tokens, int hashbits) {this.tokens &＃61; tokens;this.hashbits &＃61; hashbits;this.intSimHash &＃61; this.simHash();}HashMap wordMap &＃61; new HashMap();public BigInteger simHash() {// 定义特征向量/数组int[] v &＃61; new int[this.hashbits];// 1、将文本去掉格式后, 分词.StringTokenizer stringTokens &＃61; new StringTokenizer(this.tokens);while (stringTokens.hasMoreTokens()) {String temp &＃61; stringTokens.nextToken();// 2、将每一个分词hash为一组固定长度的数列.比如 64bit 的一个整数.BigInteger t &＃61; this.hash(temp);for (int i &＃61; 0; i &＃61; 0) {fingerprint &＃61; fingerprint.add(new BigInteger("1").shiftLeft(i));simHashBuffer.append("1");} else {simHashBuffer.append("0");}}this.strSimHash &＃61; simHashBuffer.toString();System.out.println(this.strSimHash &＃43; " length " &＃43; this.strSimHash.length());return fingerprint;}private BigInteger hash(String source) {if (source &＃61;&＃61; null || source.length() &＃61;&＃61; 0) {return new BigInteger("0");} else {char[] sourceArray &＃61; source.toCharArray();BigInteger x &＃61; BigInteger.valueOf(((long) sourceArray[0]) <<7);BigInteger m &＃61; new BigInteger("1000003");BigInteger mask &＃61; new BigInteger("2").pow(this.hashbits).subtract(new BigInteger("1"));for (char item : sourceArray) {BigInteger temp &＃61; BigInteger.valueOf((long) item);x &＃61; x.multiply(m).xor(temp).and(mask);}x &＃61; x.xor(new BigInteger(String.valueOf(source.length())));if (x.equals(new BigInteger("-1"))) {x &＃61; new BigInteger("-2");}return x;}}/*统计x中二进制位数为1的个数public int Count(int v){int num&＃61;0;while(v){v&&＃61;(v-1);num&＃43;&＃43;;}return num;}*/public int hammingDistance(SimHash1 other) {BigInteger x &＃61; this.intSimHash.xor(other.intSimHash);int tot &＃61; 0;// 统计x中二进制位数为1的个数// 我们想想&＃xff0c;一个二进制数减去1&＃xff0c;那么&＃xff0c;从最后那个1&＃xff08;包括那个1&＃xff09;后面的数字全都反了&＃xff0c;对吧&＃xff0c;然后&＃xff0c;n&(n-1)就相当于把后面的数字清0&＃xff0c;// 我们看n能做多少次这样的操作就OK了。while (x.signum() !&＃61; 0) {tot &＃43;&＃61; 1;x &＃61; x.and(x.subtract(new BigInteger("1")));}return tot;}public int getDistance(String str1, String str2) {int distance;if (str1.length() !&＃61; str2.length()) {distance &＃61; -1;} else {distance &＃61; 0;for (int i &＃61; 0; i