simhash的中文实现(python)

最近工作上需要处理文本相似度的问题，一共5万多个文档；
第一步，是先是要进行颗粒度较粗的，发现基本相似的文档，进行基本的 “聚类”；
第二步，针对相似的文档，然后进行详细的比较；

经过调研，发现google的simhash是在颗粒度较粗的方面，进行文本相似度比较的较好的方案；

一. 何为simhash

关于什么是simhash，网上学院派的介绍还是很多的，核心思想就是，对文本进行分词，并统计词频(相当于权重)，然后，进行对每个词进行hash操作，并将结果按二进制位乘以权重；然后将所有结果，按位相加，统计出文本的“指纹”。
此处以一个例子进行介绍更为形象：

1. 假设，需要进行simhash的文本为：“我很想要打游戏，但是女朋友会生气！”；
2. 首先，就是对文本进行分词操作，使用结巴分词的全分词模式，结果为：['我', '很', '想要', '打游戏', '游戏', '但是', '女朋友', '朋友', '会生', '生气']；
3. 然后，进行词频统计，得到：{'会生': 1, '但是': 1, '女朋友': 1, '很': 1, '想要': 1, '我': 1, '打游戏': 1, '朋友': 1, '游戏': 1, '生气': 1};
4. 然后，对以上每个词进行 HASH操作，比如md5，比如，'会生'的md5是 f3ab426bf0c05aa49cd0903c31adcb38，然后，以二进制位的方式，进行处理，如果 bit == 1，则 为 1x1；如果，bit == 0，则 为-1x1；
5. 计算完，每一个词之后，将所有的结果按位相加，并生成唯一的HASH，结果为：1459185014329402212；

二. python上的实现

首先，python是有现成的simhash的包的，包名，就是这个名字；
直接执行pip install simhash即可；
刚开始看，这是针对英文的，所以，想去搜搜有没有中文方面现成的，找了找没有，于是就去看看simhash的源码，看看对中文的支持如何；

结果：simhash“表面”上对中文的支持不好，是因为它的中文分词是完全一个个字的分解；

但是，这完全不影响对simhash包的使用，simhash支持分词完的列表作为输入数据，所以，完全可以使用jieba分词之后，在使用simhash进行计算；

PS：可以看看simhash的实现代码，很简洁

三. 例子

例子就很简单了：

import jieba
from simhash import Simhash

words1 = jieba.lcut('我很想要打游戏，但是女朋友会生气！', cut_all=True)
words2 = jieba.lcut('我很想要打游戏，但是女朋友非常生气！', cut_all=True)

print(Simhash(words1).distance(Simhash(words2))) 

#输出：6，因为短文本使用simhash的话，文字稍微有些改动，还是挺明显的，大家可以用长文本尝试

四. simhash的核心源码

# 说明：self.f 为simhash的长度；
#            self.value 为当前实例的simhash值；
#            self.hashfunc 为计算hash的函数，默认是md5；

# 计算文本的hash值
def build_by_features(self, features): 
    """
    `features` might be a list of unweighted tokens (a weight of 1
                will be assumed), a list of (token, weight) tuples or
                a token -> weight dict.
    """
    v = [0] * self.f
    masks = [1 << i for i in range(self.f)]  #生成从1位到f位的mashs值，用于每个位的匹配操作
    if isinstance(features, dict):
        features = features.items()
    # h是计算的hash值， w是权重(词频)
    for f in features:
        if isinstance(f, basestring):
            h = self.hashfunc(f.encode('utf-8'))
            w = 1
        else:
            assert isinstance(f, collections.Iterable)
            h = self.hashfunc(f[0].encode('utf-8'))
            w = f[1]
        for i in range(self.f):
            v[i] += w if h & masks[i] else -w  # 位操作，位值为1，则为w，位值为0，则为-w；
    ans = 0
    for i in range(self.f):
        if v[i] > 0:
            ans |= masks[i]  # 合并所有计算结果
    self.value = ans

# 计算两个hash值得距离
def distance(self, another):
    assert self.f == another.f
    x = (self.value ^ another.value) & ((1 << self.f) - 1)
    ans = 0
    while x:
        ans += 1
        x &= x - 1
    return ans