Simhash算法详解及python实现
Simhash算法详解及python实现
GoogleMoses Charikar发表的一篇论文“detecting near-duplicates for web crawling”中提出了simhash算法，专门用来解决亿万级别的网页的去重任务。
前言
simhash算法用来进行文本比对的
提示：以下是本篇文章正文内容，下面案例可供参考
一、什么是simhash
simhash算法用来进行文本比对的
二、simhash步骤
simhash包含分词、hash、加权、合并、降维五大步骤
simhash代码如下
import jieba
import jieba.analyse
import numpy as np
class SimHash(object):
def simHash(self, content):
seg = jieba.cut(content)
# jieba.analyse.set_stop_words('stopword.txt')
# jieba基于TF-IDF提取关键词
keyWords = jieba.analyse.extract_tags("|".join(seg), topK=10, withWeight=True)
keyList = []
for feature, weight in keyWords:
# print('feature:' + feature)
print('weight: {}'.format(weight))
# weight = math.ceil(weight)
weight = int(weight)
binstr = self.string_hash(feature)
print('feature: %s , string_hash %s' % (feature, binstr))
temp = []
for c in binstr:
if (c == '1'):
temp.append(weight)
else:
temp.append(-weight)
keyList.append(temp)
listSum = np.sum(np.array(keyList), axis=0)
if (keyList == []):
return '00'
simhash = ''
for i in listSum:
if (i > 0):
simhash = simhash + '1'
else:
simhash = simhash + '0'
return simhash
def string_hash(self, source):
if source == "":
return 0
else:
temp = source[0]
temp1 = ord(temp)
x = ord(source[0]) << 7
m = 1000003
mask = 2 ** 128 - 1
for c in source:
x = ((x * m) ^ ord(c)) & mask
x ^= len(source)
if x == -1:
x = -2
x = bin(x).replace('0b', '').zfill(64)[-64:]
return str(x)
def getDistance(self, hashstr1, hashstr2):
'''
计算两个simhash的汉明距离
'''
length = 0
for index, char in enumerate(hashstr1):
if char == hashstr2[index]:
continue
else:
length += 1
return length
1.分词
分词是将文本文档进行分割成不同的词组，比如词1为：今天星期四，词2为：今天星期五
得出分词结果为【今天，星期四】【今天，星期五】
2.hash
hash是将分词结果取hash值
星期四hash为：0010001100100000101001101010000000101111011010010001100011011110
今天hash为：0010001111010100010011110001110010100011110111111011001011110101
星期五hash为：0010001100100000101001101010000000101111011010010000000010010001
3.加权
加权是将取分词的hash结果分别对应乘以权重，假设分词的hash分别为
h
a
s
h
(
1
)
=
[
0
1
0
1
]
hash(1)=\begin{bmatrix} 0 & 1 & 0 & 1 \\ \end{bmatrix}
hash(1)=[0101]
h
a
s
h
(
2
)
=
[
1
0
1
0
]
hash(2)=\begin{bmatrix} 1 & 0 & 1 & 0 \\ \end{bmatrix}
hash(2)=[1010]
权重（有几个分词对应几个权重）为
w
e
i
g
h
t
=
[
100
20
]
weight=\begin{bmatrix} 100 & 20 \end{bmatrix}
weight=[10020]
那么对应的加权为将hash值为0的置为-1，1的置为1，
然后分别乘以权重，得出的结果分别为
s
i
m
h
a
s
h
(
1
)
=
[
−
100
100
−
100
100
]
simhash(1)=\begin{bmatrix} -100 & 100 & -100 & 100 \\ \end{bmatrix}
simhash(1)=[−100100−100100]
s
i
m
h
a
s
h
(
2
)
=
[
20
−
20
20
−
20
]
simhash(2)=\begin{bmatrix} 20 & -20 & 20 & -20 \\ \end{bmatrix}
simhash(2)=[20−2020−20]
4.合并
合并是将加权的结果进行sum操作,比如上述两个加权结果相加，得到的值为
s
i
m
h
a
s
h
t
e
m
p
=
[
−
80
80
−
80
80
]
simhash_{temp}=\begin{bmatrix} -80 & 80 &-80& 80 \\ \end{bmatrix}
simhashtemp=[−8080−8080]
5.降维
降维是将合并的结果进行降维，如果值大于0，则置为1小于0 则置为0，因此得到的结果为：
s
i
m
h
a
s
h
t
e
m
p
=
[
0
1
0
1
]
simhash_{temp}=\begin{bmatrix} 0 & 1 & 0 & 1 \\ \end{bmatrix}
simhashtemp=[0101]
三、simhash比对
一般simhash采用海明距离来进行计算相似度，海明距离计算如下：
对于A，B两个n维二进制数
A
=
(
a
1
,
a
2
,
a
3
,
…
,
a
n
)
A=(a_1,a_2,a_3,\ldots,a_n)
A=(a1,a2,a3,…,an)
B
=
(
b
1
,
b
2
,
b
3
,
…
,
b
n
)
B = (b_1,b_2,b_3,\ldots,b_n)
B=(b1,b2,b3,…,bn)
二者的海明距离为：
d
i
s
t
a
n
c
e
(
A
,
B
)
=
∑
i
=
1
n
d
i
distance(A,B) =\sum_{i=1}^{n}d_i
distance(A,B)=i=1∑ndi
其中
d
i
=
{
0
,
a
i
=
b
i
1
,
a
i
≠
b
i
d_i=\begin{cases} 0, & a_i=b_i \\ 1, & a_i \neq b_i \\ \end{cases}
di={0,1,ai=biai=bi
举例：
1000与1111的海明距离为3
总结
提示：这里对文章进行总结：
可以采用simhash对不同参数进行权重取值，然后使用汉明距离进行比对