当前位置: 首页 > 工具软件 > simhash > 使用案例 >

Simhash算法详解及python实现

濮阳繁
2023-12-01

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)=[100100100100]
s i m h a s h ( 2 ) = [ 20 − 20 20 − 20 ] simhash(2)=\begin{bmatrix} 20 & -20 & 20 & -20 \\ \end{bmatrix} simhash(2)=[20202020]

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=[80808080]

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=1ndi
其中
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
举例:
10001111的海明距离为3


总结

提示:这里对文章进行总结:
可以采用simhash对不同参数进行权重取值,然后使用汉明距离进行比对

 类似资料: