simhash算法_python语言程序设计

simhash算法_python语言程序设计讲述了simhash的基本原理和步骤,并用python实现了simhash

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

作者原创,转载请注明出处。

一直想写个总结来回顾simhash,一直没抽出时间,现在还是好好写写总结一下。作者随笔,废话有点多,不喜勿喷,欢迎指教。

谷歌每天从网上抓取海量的信息,怎么样区分重复的呢,据说就采用了simhash算法,当然肯定也不仅仅就只采用它,不过至少可以说明其性能。

预备知识:

我们知道,在文本去重的时候,有很多方式,在文本与文本之间对比,如果是整篇对比,费时费力,有人就想到用什么东西代表每篇文章,如摘要,当然,对计算机来说,摘要和整篇的区别只是缩小了篇幅,所以又有人想到了采用关键字来对比。这样确实可以大大缩减我们对比的复杂性。那我们怎么得到一篇文章的关键字呢?一般采用词频(TF),但是只用词频,如中文出现类似“的”、“我们”之类的词语很多,应该怎么去掉这些词语呢,手动去掉实在是麻烦,于是可以结合逆向词频(IDF),这就是著名的TD-IDF,一种提取一个文章的关键词的算法。词频我们很好理解,一个词语在整篇文章中出现的次数与词语总个数之比。IDF又怎么算呢,假如一个词语,在我们所有文章中出现的频率都非常高(例如“的”在我们多个文本中出现的次数很多),我们就认为,这个词语不具有代表性,就可以降低其作用,也就是赋予其较小的权值。

那这个权重,我们怎么计算呢,(这里敲公式比较麻烦,直接找来图片),如下图,分子代表文章总数,分母表示该词语在这些文章(|D|)出现的篇数。一般我们还会采取分母加一的方法,防止分母为0的情况出现,在这个比值之后取对数,就是IDF了。

simhash算法_python语言程序设计

好了,在得到idf之后,最终用tf*idf得到一个词语的权重。这里我知道了TD-IDF可以计算一篇文章的关键词。在我们取得一篇的文章的关键词,之后,我们可以采取每篇文章对比其关键词的方法来去重。

这里又有一个权衡,假如我们取的关键词过少,就不能很好代表一篇文章,假如我们取很多,又会降低效率。有没有一种方法,既可以很少的对比,又能有好的代表性呢。答案肯定是有的,于是simhash产生了。

(汗,终于讲到正题来了)

原理:

simhash是一种局部敏感hash。我们都知道什么是hash。那什么叫局部敏感呢,假定A、B具有一定的相似性,在hash之后,仍然能保持这种相似性,就称之为局部敏感hash。

在上文中,我们得到一个文档的关键词,取得一篇文章关键词集合,又会降低对比效率,我们可以通过hash的方法,把上述得到的关键词集合hash成一串二进制,这样我们直接对比二进制数,看其相似性就可以得到两篇文档的相似性,在查看相似性的时候我们采用海明距离,即在对比二进制的时候,我们看其有多少位不同,就称海明距离为多少。在这里,我是将文章simhash得到一串64位的二进制,一般取海明距离为3作为阈值,即在64位二进制中,只有三位不同,我们就认为两个文档是相似的。当然了,这里可以根据自己的需求来设置阈值。

就这样,我们把一篇文档用一个二进制代表了,也就是把一个文档hash之后得到一串二进制数的算法,称这个hash为simhash。

具体simhash步骤如下:

(1)将文档分词,取一个文章的TF-IDF权重最高的前20个词(feature)和权重(weight)。即一篇文档得到一个长度为20的(feature:weight)的集合。

(2)对其中的词(feature),进行普通的哈希之后得到一个64为的二进制,得到长度为20的(hash : weight)的集合。

(3)根据(2)中得到一串二进制数(hash)中相应位置是1是0,对相应位置取正值weight和负值weight。例如一个词进过(2)得到(010111:5)进过步骤(3)之后可以得到列表[-5,5,-5,5,5,5],即对一个文档,我们可以得到20个长度为64的列表[weight,-weight…weight]。

(4)对(3)中20个列表进行列向累加得到一个列表。如[-5,5,-5,5,5,5]、[-3,-3,-3,3,-3,3]、[1,-1,-1,1,1,1]进行列向累加得到[-7,1,-9,9,3,9],这样,我们对一个文档得到,一个长度为64的列表。

(5)对(4)中得到的列表中每个值进行判断,当为负值的时候去0,正值取1。例如,[-7,1,-9,9,3,9]得到010111,这样,我们就得到一个文档的simhash值了。

(6)计算相似性。连个simhash取异或,看其中1的个数是否超过3。超过3则判定为不相似,小于等于3则判定为相似。

呼呼呼,终于写完大致的步骤,可参考下图理解步骤。

simhash算法_python语言程序设计

python实现:

在下面python实现中,用的结巴分词,得到tf-idf的权值。

# -*- coding: utf-8 -*-
import jieba
import jieba.analyse
import numpy as np
import json

class simhash:
    def __init__(self,content):
        self.simhash=self.simhash(content)

    def __str__(self):
        return str(self.simhash)

    def simhash(self,content):
        seg = jieba.cut(content)
        jieba.analyse.set_stop_words('stopword.txt')
        keyWord = jieba.analyse.extract_tags(
            '|'.join(seg), topK=20, withWeight=True, allowPOS=())#在这里对jieba的tfidf.py进行了修改
        #将tags = sorted(freq.items(), key=itemgetter(1), reverse=True)修改成tags = sorted(freq.items(), key=itemgetter(1,0), reverse=True)
        #即先按照权重排序,再按照词排序
        keyList = []
        # print(keyWord)
        for feature, weight in keyWord:
            weight = int(weight * 20)
            feature = self.string_hash(feature)
            temp = []
            for i in feature:
                if(i == '1'):
                    temp.append(weight)
                else:
                    temp.append(-weight)
            # print(temp)
            keyList.append(temp)
        list1 = np.sum(np.array(keyList), axis=0)
        print(list1)
        if(keyList==[]): #编码读不出来
            return '00'   
        simhash = ''
        for i in list1:
            if(i > 0):
                simhash = simhash + '1'
            else:
                simhash = simhash + '0'
        return simhash


    def string_hash(self,source):
        if source == "":
            return 0
        else:
            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:]
            print(source,x)

            return str(x)

        '''
        以下是使用系统自带hash生成,虽然每次相同的会生成的一样,
        不过,对于不同的汉子产生的二进制,在计算海明码的距离会不一样,
        即每次产生的海明距离不一致
        所以不建议使用。
        '''
        # x=str(bin(hash(source)).replace('0b','').replace('-','').zfill(64)[-64:])
        # print(source,x,len(x))
        # return x


    def hammingDis(self,com):
        t1 = '0b' + self.simhash
        t2 = '0b' + com.simhash
        n=int(t1, 2) ^ int(t2, 2)
        i=0
        while n:
            n &= (n-1)
            i+=1
        return i


版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/187312.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • python读取excel单元格内容_python如何读取文件夹下的所有文件

    python读取excel单元格内容_python如何读取文件夹下的所有文件python读取excel文件的内容可以方便我们查看信息。#-*-codeing=utf-8-*-#@Time:2022/4/1621:06#@Author:ning#@File:xlsx.py#@software:PyCharm#引入xlrd2去支持读取xlsx相关的文件importxlrd2#定义文件名file_name=’4016.xlsx’#读取xlsx文件#预计输出#4016.xlsx该文件有2个tab页sku_

  • phpstorm2021.11激活码【2021免费激活】[通俗易懂]

    (phpstorm2021.11激活码)这是一篇idea技术相关文章,由全栈君为大家提供,主要知识点是关于2021JetBrains全家桶永久激活码的内容https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~92U4ILM59M-eyJsaWNlb…

  • 本地连接redis_redis入门

    本地连接redis_redis入门通过前面的学习,相信读者对RedisSentinel有了一定的了解,本节将介绍应用方如何正确地连接RedisSentinel。有人会说这有什么难的,已经知道了主节点的ip地址和端口,用对应编程语言的客户端连接主节点不就可以了吗?但试想一下,如果这样使用客户端,客户端连接RedisSentinel和主从复制的Redis又有什么区别呢,如果主节点挂掉了,虽然RedisSentinel可以完成故障转移,但是客户端无法获取这个变化,那么使用RedisSentinel的意义就不大了,所以各个语言

  • Java设计专题及高级导向「建议收藏」

    Java设计专题及高级导向「建议收藏」Java设计专题及高级导向

  • mybatiscodehelperpro2.9.4-183-204在线激活码(JetBrains全家桶)2022.02.05

    (mybatiscodehelperpro2.9.4-183-204在线激活码)2021最新分享一个能用的的激活码出来,希望能帮到需要激活的朋友。目前这个是能用的,但是用的人多了之后也会失效,会不定时更新的,大家持续关注此网站~https://javaforall.cn/100143.htmlIntelliJ2021最新激活注册码,破解教程可免费永久激活,亲测有效,上面是详细链接哦~76…

  • BigDecimal中divide方法详解

    BigDecimal中divide方法详解首先说一下用法,BigDecimal中的divide主要就是用来做除法的运算。其中有这么一个方法.publicBigDecimaldivide(BigDecimaldivisor,intscale,introundingMode)第一个参数是除数,第二个参数代表保留几位小数,第三个代表的是使用的模式。其中我们标题上就是其中的两种BigDecimal.ROUND_DOW…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号