[python]#!/usr/bin/env python
# -*- coding=utf-8 -*-
# Implementation of Charikar simhashes in Python
# See: http://dsrg.mff.cuni.cz/~holub/sw/shash/#a1
class simhash():
def __init__(self, tokens='', hashbits=128):
self.hashbits = hashbits
self.hash = self.simhash(tokens)
def __str__(self):
return str(self.hash)
def __long__(self):
return long(self.hash)
def __float__(self):
return float(self.hash)
def simhash(self, tokens):
# Returns a Charikar simhash with appropriate bitlength
v = [0]*self.hashbits
for t in [self._string_hash(x) for x in tokens]:
bitmask = 0
#print (t)
for i in range(self.hashbits):
bitmask = 1 << i
#print(t,bitmask, t & bitmask)
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
#整个文档的fingerprint为最终各个位大于等于0的位的和
return fingerprint
def _string_hash(self, v):
# A variable-length version of Python's builtin hash
if v == "":
return 0
else:
x = ord(v[0])<<7
m = 1000003
mask = 2**self.hashbits-1
for c in v:
x = ((x*m)^ord(c)) & mask
x ^= len(v)
if x == -1:
x = -2
return x
def hamming_distance(self, other_hash):
x = (self.hash ^ other_hash.hash) & ((1 << self.hashbits) - 1)
tot = 0
while x:
tot += 1
x &= x-1
return tot
def similarity(self, other_hash):
a = float(self.hash)
b = float(other_hash)
if a>b: return b/a
return a/b
if __name__ == '__main__':
#看看哪些东西google最看重?标点?
s = '看看哪些东西google最看重?标点?'
hash1 =simhash(s.split())
#print("0x%x" % hash1)
#print ("%s\t0x%x" % (s, hash1))
s = '看看哪些东西google最看重!标点!'
hash2 = simhash(s.split())
#print ("%s\t[simhash = 0x%x]" % (s, hash2))
print '%f%% percent similarity on hash' %(100*(hash1.similarity(hash2)))
print hash1.hamming_distance(hash2),"bits differ out of", hash1.hashbits
[/python]
传统的hash函数能够将一样的文本生成一样的hash函数,但是,通过simhash方法,能够差不多相同的文档得到的hash函数也比较相近。
Charikar's hash 通过Charikar‘s hash,能够将比较相似度的文档得到比较相近的fingerprint。
该算法的流程如下:
12 * Document is split into tokens (words for example)or super-tokens (word tuples) * Each token is represented by its hash value; a traditional hash function is used * Weights are associated with tokens * A vector V of integers is initialized to 0, length of the vector corresponds to the desired hash size in bits * In a cycle for all token's hash values (h), vector V is updated: o ith element is decreased by token's weight if the ith bit of the hash h is 0, otherwise o ith element is increased by token's weight if the ith bit of the hash h is 1 * Finally, signs of elements of V corresponds to the bits of the final fingerprint 该hash不是将文档总体计算hash值,而是将文档中的每个token计算哈希值,对文档中每个token的hash值,按照位 对hash值进行求和,如果当前token的hash值在该位上是0,则减去1,如果在该位上是1,则加上1.将所有的token按照这种方式累加,求的最终的值作为fingerprint。
simhash简介:http://www.cnblogs.com/linecong/archive/2010/08/28/simhash.html
Googlecode simhash算法简介:http://simhash.googlecode.com/svn/trunk/paper/SimHashWithBib.pdf
我自己也实现了一下simhash,发现基本不能用,来测下,你这个感觉也不能用啊,你找到原因了吗?而且你怎么不分词呢?
刚对上面这个算法做了一些调试测试,发现算法抗随机字符干扰差,而且两条很不相像的字符串相似度有时也会很高(如下面的测试结果),不太适合我所研究的领域。。
:新年快乐好消息,见副件 [simhash = 0x7b452ce82fc2468927e08904d80c18995d4c4131859a6bb1be0dc66c3a1acb1f]
Re:232adt股权激励的主要形式3e3 [simhash = 0xa1414dbe70f726d26a68822f98fb5e2ae11bd2adb92fdea6bcb5bb3fe23491cd]
========================================
76.444232% percent similarity on hash
126 bits differ out of 256