SimHash 算法原理及实现
SimHash 是Google用来处理海量文本去重的算法
SimHash 最牛逼的一点就是将一个文档，最后转换成一个64位的字节，暂且称之为特征字，
然后判断重复只需要判断他们的特征字的距离是不是<n（根据经验这个n一般取值为3），就可以判断两个文档是否相似。
谷哥（Google）出品，谷哥（Google）风格，简单（Simple）实用，算法原理图：
大概花三分钟看懂这个图就差不多怎么实现这个simhash算法了。
特别简单，谷歌出品嘛，简单实用。
算法过程大概如下：
1）文档分词
将Doc进行关键词抽取(其中包括分词和计算权重)，抽取出n个(关键词，权重)对， 即图中的(feature, weight)们。 记为 feature_weight_pairs = [fw1, fw2 … fwn]，其中 fwn = (feature_n,weight_n`)。
2）哈希权重匹配
hash_weight_pairs = [ (hash(feature), weight) for feature, weight in feature_weight_pairs ] 生成图中的(hash,weight)们, 此时假设hash生成的位数bits_count = 6（如图）;
3）计算权重
然后对 hash_weight_pairs 进行位的纵向累加，如果该位是1，则+weight,如果是0，则-weight，最后生成bits_count个数字，如图所示是[13, 108, -22, -5, -32, 55], 这里产生的值和hash函数所用的算法相关。
4）比较结果
[13,108,-22,-5,-32,55] -> 110001这个就很简单啦，正1负0。
到此，如何从一个doc到一个simhash值的过程已经讲明白了。 但是还有一个重要的部分没讲，
SimHash 值的海明距离计算
二进制串A 和 二进制串B 的海明距离 就是 A xor B 后二进制中1的个数。
举例如下：
A = 100111;
B = 101010;
hamming_distance(A, B) = count_1(A xor B) = count_1(001101) = 3;
当我们算出所有doc的simhash值之后，需要计算doc A和doc B之间是否相似的条件是：
A和B的海明距离是否小于等于n，这个n值根据经验一般取值为3,
simhash本质上是局部敏感性的hash，和md5之类的不一样。 正因为它的局部敏感性，所以我们可以使用海明距离来衡量simhash值的相似度。
『高效计算二进制序列中1的个数』
/* src/Simhasher.hpp */
bool isEqual(uint64_t lhs, uint64_t rhs, unsigned short n = 3)
{
unsigned short cnt = 0;
lhs ^= rhs;
while(lhs && cnt <= n)
{
lhs &= lhs - 1;
cnt++;
}
if(cnt <= n)
{
return true;
}
return false;
}
由上式这个函数来计算的话，时间复杂度是 O(n); 这里的n默认取值为3。由此可见还是蛮高效的。
计算二进制序列中1的个数之O(1)算法实现
感谢 @SCatWang 的评论分享：
感谢您做的simhash库，感觉会很方便。 有关求二进制中1的个数，其实有各种O(1)的实现。可以参考这个地方： http://stackoverflow.com/a/14682688
simhash 实现的工程项目
主要是针对中文文档，也就是此项目进行simhash之前同时还进行了分词和关键词的抽取。
对比其他算法
『百度的去重算法』
百度的去重算法最简单，就是直接找出此文章的最长的n句话，做一遍hash签名。n一般取3。 工程实现巨简单，据说准确率和召回率都能到达80%以上。
『shingle算法』
shingle原理略复杂，不细说。 shingle算法我认为过于学院派，对于工程实现不够友好，速度太慢，基本上无法处理海量数据。
『其他算法』
具体看微博上的讨论
参考
- Similarity estimation techniques from rounding algorithms
- simhash与Google的网页去重
- 海量数据相似度计算之simhash和海明距离
SimHash 算法代码实现
Simhash
传统IR领域内文本相似度比较所采用的经典方法是文本相似度的向量夹角余弦，其主要思想是根据一个文章中出现词的词频构成一个向量，然后计算两篇文章对应向量的向量夹角。但由于有可能一个文章的特征向量词特别多导致整个向量维度很高，使得计算的代价太大，对于Google这种处理万亿级别的网页的搜索引擎而言是不可接受的，simhash算法的主要思想是降维，将高维的特征向量映射成一个f-bit的指纹(fingerprint)，通过比较两篇文章的f-bit指纹的Hamming Distance来确定文章是否重复或者高度近似。
simhash算法很精巧，但却十分容易理解和实现，具体的simhash过程如下：
1. 首先基于传统的IR方法，将文章转换为一组加权的特征值构成的向量。
2.初始化一个f维的向量V，其中每一个元素初始值为0。
3.对于文章的特征向量集中的每一个特征，做如下计算：
利用传统的hash算法映射到一个f-bit的签名。对于这个f- bit的签名，如果签名的第i位上为1，则对向量V中第i维加上这个特征的权值，否则对向量的第i维减去该特征的权值。
4.对整个特征向量集合迭代上述运算后，根据V中每一维向量的符号来确定生成的f-bit指纹的值，如果V的第i维为正数，则生成f-bit指纹的第i维为1，否则为0。
simhash和普通hash最大的不同在于传统的hash函数虽然也可以用于映射来比较文本的重复，但是对于可能差距只有一个字节的文档也会映射成两个完全不同的哈希结果，而simhash对相似的文本的哈希映射结果也相似。Google的论文中取了f=64，即将整个网页的加权特征集合映射到一个64-bit的fingerprint上。
比起simhash，整片文章中Google所采用的查找与给定f-bit的fingerprint的海明距离(Hamming Distance)小于k的算法相对还稍微难理解点。
fingerprint的Hamming Distance
问题：一个80亿的64-bit指纹组成的集合Q，对于一个给定64-bit的指纹F，如何在a few millionseconds中找到Q中和f至多只有k(k=3)位差别的指纹。
思想：1. 对于一个具有2^d个记录的集合，只需要考虑d-bit hash。2. 选取一个d’使得|d’-d|十分小，因此如果两fingerprint在d’-bits上都相同，那么在d-bits也很可能相同。然后在这些d-bit match的结果中寻找整个f-bit的Hamming Distance小于k的fingerprint。简单的说，就是利用fingerprint少量特征位数比较从而首先缩小范围，然后再去确定是否差异小于k个bit。
算法：
1. 首先对于集合Q构建多个表T1，T2…Tt，每一个表都是采用对应的置换函数π(i)将64-bit的fingerprint中的某p(i)位序列置换换到整个序列的最前面。即每个表存储都是整个Q的fingerprint的复制置换。
2.对于给定的F，在每个Ti中进行匹配，寻找所有前pi位与F经过π(i)置换后的前pi位相同的fingerprint。
3.对于所有在上一步中匹配到的置换后的fingerprint，计算其是否与π(i)(F)至多有k-bit不同。
算法的重点在于对于集合Q的分表以及每个表所对应的置换函数，假设对于64-bit的fingerprint，k=3，存储16个table，划分参考下图:
将64-bit按照16位划分为4个区间，每个区间剩余的48-bit再按照每个12-bit划分为4个区间，因此总共16个table并行查找，即使三个不同的k-bit落在A、B、C、D中三个不同的区块，此划分方法也不会导致遗漏。
以上方法是对于online的query，即一个给定的F在集合中查找相似的fingerprint。如果爬虫每天爬取了100w个网页，快速的查找这些新抓取的网页是否在原集合中有Near-duplication，对于这种batch-query的情况，Map-Reduce就发挥它的威力了。
不同的是，在batch-query的处理中，是对待查集合B(1M个fingerprint)进行复制置换构建Table而非8B的目标集合，而在每一个chunkserver上对Fi(F为整个8B的fingerprint)在整个Table(B)中进行探测，每一个chunkserver上的的该Map过程输出该Fi中与整个B的near-duplicates，Reduces过程则将所有的结果收集、去重、然后输出为一个sorted file。
Haffman编码压缩
上述的查询过程，特别是针对online-version的算法，可以看出需要对8B的fingerprint进行多表复制和构建，其占据的容量是非常大的，不过由于构建的每一个置换Table都是sorted的，因此可以利用每一个fingerprint与其前一个的开始不同的bit-position h(h∈[0,f-1]) 来进行数据压缩，即如果前一个编码是11011011，而自身是11011001，则后一个可以编码为(6)1，即h=6，其中6表示从第6位(从0开始编号)开始和上一个fingerprint不相同(上一个为1，这个必然为0)，然后再保存不相同位置右侧的编码，依次生成整个table。
Google首先计算整个排序的fingerprint表中h的分布情况，即不同的h出现次数，依据此对[0,f-1]上出现的h建立Haffman code，再根据上述规则生成table（例如上面的6就表示成对应的Haffman code）。其中table分为多个block，每一个block中的第一个fingerprint保存原数据，后面的依次按照编码生成。
将每一个block中所对应的最后一个fingerprint保存在内存中，因此在比对的时候就可以直接根据内存中的fingerprint来确定是哪一个block需要被decompress进行比较。
8B个64-bit的fingerprint原占据空间大约为64GB，利用上述Haffman code压缩后几乎会减少一般，而内存中又只对每一个block保存了一个fingerprint。
每次看Google的论文都会让人眼前一亮，而且与很多(特别是国内)的论文是对未来进行设想不同，Google的东西都是已经运行了2，3年了再到WWW，OSDI这种顶级会议上灌个水。再次各种羡慕能去这个Dream Company工作的人，你们懂得。
参考:
Detecting Near-Duplicates for Web Crawling(Paper)
Detecting Near-Duplicates for Web Crawling(PPT)
1、Python 代码实现
#!/usr/bin/python
# coding=utf-8
class simhash:
#构造函数
def __init__(self, tokens='', hashbits=128):
self.hashbits = hashbits
self.hash = self.simhash(tokens);
#toString函数
def __str__(self):
return str(self.hash)
#生成simhash值
def simhash(self, tokens):
v = [0] * self.hashbits
for t in [self._string_hash(x) for x in tokens]: #t为token的普通hash值
for i in range(self.hashbits):
bitmask = 1 << i
if t & bitmask :
v[i] += 1 #查看当前bit位是否为1,是的话将该位+1
else:
v[i] -= 1 #否则的话,该位-1
fingerprint = 0
for i in range(self.hashbits):
if v[i] >= 0:
fingerprint += 1 << i
return fingerprint #整个文档的fingerprint为最终各个位>=0的和
#求海明距离
def hamming_distance(self, other):
x = (self.hash ^ other.hash) & ((1 << self.hashbits) - 1)
tot = 0;
while x :
tot += 1
x &= x - 1
return tot
#求相似度
def similarity (self, other):
a = float(self.hash)
b = float(other.hash)
if a > b : return b / a
else: return a / b
#针对source生成hash值 (一个可变长度版本的Python的内置散列)
def _string_hash(self, source):
if source == "":
return 0
else:
x = ord(source[0]) << 7
m = 1000003
mask = 2 ** self.hashbits - 1
for c in source:
x = ((x * m) ^ ord(c)) & mask
x ^= len(source)
if x == -1:
x = -2
return x
if __name__ == '__main__':
s = 'This is a test string for testing'
hash1 = simhash(s.split())
s = 'This is a test string for testing also'
hash2 = simhash(s.split())
s = 'nai nai ge xiong cao'
hash3 = simhash(s.split())
print(hash1.hamming_distance(hash2) , " " , hash1.similarity(hash2))
print(hash1.hamming_distance(hash3) , " " , hash1.similarity(hash3))
2、Java 代码实现
import java.math.BigInteger;
import java.util.StringTokenizer;
public class SimHash {
private String tokens;
private BigInteger strSimHash;
private int hashbits = 128;
public SimHash(String tokens) {
this.tokens = tokens;
this.strSimHash = this.simHash();
}
public SimHash(String tokens, int hashbits) {
this.tokens = tokens;
this.hashbits = hashbits;
this.strSimHash = this.simHash();
}
public BigInteger simHash() {
int[] v = new int[this.hashbits];
StringTokenizer stringTokens = new StringTokenizer(this.tokens);
while (stringTokens.hasMoreTokens()) {
String temp = stringTokens.nextToken();
BigInteger t = this.hash(temp);
for (int i = 0; i < this.hashbits; i++) {
BigInteger bitmask = new BigInteger("1").shiftLeft(i);
if (t.and(bitmask).signum() != 0) {
v[i] += 1;
} else {
v[i] -= 1;
}
}
}
BigInteger fingerprint = new BigInteger("0");
for (int i = 0; i < this.hashbits; i++) {
if (v[i] >= 0) {
fingerprint = fingerprint.add(new BigInteger("1").shiftLeft(i));
}
}
return fingerprint;
}
private BigInteger hash(String source) {
if (source == null || source.length() == 0) {
return new BigInteger("0");
} else {
char[] sourceArray = source.toCharArray();
BigInteger x = BigInteger.valueOf(((long) sourceArray[0]) << 7);
BigInteger m = new BigInteger("1000003");
BigInteger mask = new BigInteger("2").pow(this.hashbits).subtract(
new BigInteger("1"));
for (char item : sourceArray) {
BigInteger temp = BigInteger.valueOf((long) item);
x = x.multiply(m).xor(temp).and(mask);
}
x = x.xor(new BigInteger(String.valueOf(source.length())));
if (x.equals(new BigInteger("-1"))) {
x = new BigInteger("-2");
}
return x;
}
}
public int hammingDistance(SimHash other) {
BigInteger m = new BigInteger("1").shiftLeft(this.hashbits).subtract(
new BigInteger("1"));
BigInteger x = this.strSimHash.xor(other.strSimHash).and(m);
int tot = 0;
while (x.signum() != 0) {
tot += 1;
x = x.and(x.subtract(new BigInteger("1")));
}
return tot;
}
public static void main(String[] args) {
String s = "This is a test string for testing";
SimHash hash1 = new SimHash(s, 128);
System.out.println(hash1.strSimHash + " " + hash1.strSimHash.bitLength());
s = "This is a test string for testing also";
SimHash hash2 = new SimHash(s, 128);
System.out.println(hash2.strSimHash+ " " + hash2.strSimHash.bitCount());
s = "This is a test string for testing als";
SimHash hash3 = new SimHash(s, 128);
System.out.println(hash3.strSimHash+ " " + hash3.strSimHash.bitCount());
System.out.println("============================");
System.out.println(hash1.hammingDistance(hash2));
System.out.println(hash1.hammingDistance(hash3));
}
}
结论：
python的计算能力确实很强，float可以表示任意长度的数字，而对应java、c++只能用其他办法来实现了，比如java的BigIneteger,对应的位操作也只能利用类方法。
另外说明，位运算只适合整数哦。。。因为浮点的存储方案决定不能位运算，如果非要位运算，就需要Float.floatToIntBits，运算完，再通过Float.intBitsToFloat转化回去。(java默认的float,double的hashcode其实就是对应的floatToIntBits的int值)
java左移、右移： 移位运算符和气压的位运算符一样都是用来操作二进制位。
1）<< ,左移位:将操作符左侧的操作数向左移动操作数右侧指定的位数。移动的规则是在二进制的低位补0.
2）>> ,有符号右移位，将操作符左侧的操作数向右移动操作数右侧指定的位数。移动的规则是，如果被操作数的符号为正，则在二进制的高位补0；如果被操作数的符号为负，则在二进制的高位补1
3）>>> ，无符号右移位：将操作符左侧的操作数向右移动操作数右侧指定的位数。移动的对则是，无论被操作数的符号是正是负，都在二进制的高位补0.
中文文档SimHash值计算： https://github.com/yanyiwu/simhash
参考推荐：
版权所有: 本文系米扑博客原创、转载、摘录，或修订后发表，最后更新于 2018-08-22 05:06:53
侵权处理: 本个人博客，不盈利，若侵犯了您的作品权，请联系博主删除，莫恶意，索钱财，感谢！
转载注明: SimHash 算法原理及实现 （米扑博客）