如何利用python实现Simhash算法

目录
  • 1. 为什么需要Simhash?
  • 2. 文章关键词特征提取算法TD-IDF
  • 3. Simhash原理
  • 4. Simhash的不足
  • 5. Simhash算法实现

1. 为什么需要Simhash?

传统相似度算法:文本相似度的计算,一般使用向量空间模型(VSM),先对文本分词,提取特征,根据特征建立文本向量,把文本之间相似度的计算转化为特征向量距离的计算,如欧式距离、余弦夹角等。

缺点:大数据情况下复杂度会很高。

Simhash应用场景:计算大规模文本相似度,实现海量文本信息去重。

Simhash算法原理:通过hash值比较相似度,通过两个字符串计算出的hash值,进行异或操作,然后得到相差的个数,数字越大则差异越大。

2. 文章关键词特征提取算法TD-IDF

词频(TF):一个词语在整篇文章中出现的次数与词语总个数之比;

逆向词频(IDF):一个词语,在所有文章中出现的频率都非常高,这个词语不具有代表性,就可以降低其作用,也就是赋予其较小的权值。

分子代表文章总数,分母表示该词语在这些文章出现的篇数。一般会采取分母加一的方法,防止分母为0的情况出现,在这个比值之后取对数,就是IDF了。

最终用tf*idf得到一个词语的权重,进而计算一篇文章的关键词。然后根据每篇文章对比其关键词的方法来对文章进行去重。simhash算法对效率和性能进行平衡,既可以很少的对比(关键词不能取太多),又能有好的代表性(关键词不能过少)。

3. Simhash原理

Simhash是一种局部敏感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整体流程图如下:

4. Simhash的不足

完全无关的文本正好对应成了相同的simhash,精确度并不是很高,而且simhash更适用于较长的文本,但是在大规模语料进行去重时,simhash的计算速度优势还是很不错的。

5. Simhash算法实现

# !/usr/bin/python
# coding=utf-8
class Simhash:
    def __init__(self, tokens='', hashbits=128):
        self.hashbits = hashbits
        self.hash = self.simhash(tokens)
    def __str__(self):
        return str(self.hash)
    # 生成simhash值
    def simhash(self, tokens):
        v = [0] * self.hashbits
        for t in [self._string_hash(x) for x in tokens]:  # t为token的普通hash值
            for i in range(self.hashbits):
                bitmask = 1 << i
                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
        return fingerprint  # 整个文档的fingerprint为最终各个位>=0的和
    # 求海明距离
    def hamming_distance(self, other):
        x = (self.hash ^ other.hash) & ((1 << self.hashbits) - 1)
        tot = 0
        while x:
            tot += 1
            x &= x - 1
        return tot
    # 求相似度
    def similarity(self, other):
        a = float(self.hash)
        b = float(other.hash)
        if a > b:
            return b / a
        else:
            return a / b
    # 针对source生成hash值
    def _string_hash(self, source):
        if source == "":
            return 0
        else:
            x = ord(source[0]) << 7
            m = 1000003
            mask = 2 ** self.hashbits - 1
            for c in source:
                x = ((x * m) ^ ord(c)) & mask
            x ^= len(source)
            if x == -1:
                x = -2
            return x

测试:

if __name__ == '__main__':
    s = 'This is a test string for testing'
    hash1 = Simhash(s.split())
    s = 'This is a string testing 11'
    hash2 = Simhash(s.split())
    print(hash1.hamming_distance(hash2), "   ", hash1.similarity(hash2))

到此这篇关于如何利用python实现Simhash算法的文章就介绍到这了,更多相关pythonSimhash算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • python实现Simhash算法

    1.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')

  • 论文查重python文本相似性计算simhash源码

    场景: 1.计算SimHash值,及Hamming距离.2.SimHash适用于较长文本(大于三五百字)的相似性比较,文本越短误判率越高. Python实现: 代码如下 # -*- encoding:utf-8 -*- import math import jieba import jieba.analyse class SimHash(object): def getBinStr(self, source): if source == "": return 0 else: x = o

  • python实现simhash算法实例

    Simhash的算法简单的来说就是,从海量文本中快速搜索和已知simhash相差小于k位的simhash集合,这里每个文本都可以用一个simhash值来代表,一个simhash有64bit,相似的文本,64bit也相似,论文中k的经验值为3.该方法的缺点如优点一样明显,主要有两点,对于短文本,k值很敏感:另一个是由于算法是以空间换时间,系统内存吃不消. 复制代码 代码如下: #!/usr/bin/python# coding=utf-8class simhash: #构造函数    def __

  • 如何利用python实现Simhash算法

    目录 1. 为什么需要Simhash? 2. 文章关键词特征提取算法TD-IDF 3. Simhash原理 4. Simhash的不足 5. Simhash算法实现 1. 为什么需要Simhash? 传统相似度算法:文本相似度的计算,一般使用向量空间模型(VSM),先对文本分词,提取特征,根据特征建立文本向量,把文本之间相似度的计算转化为特征向量距离的计算,如欧式距离.余弦夹角等. 缺点:大数据情况下复杂度会很高. Simhash应用场景:计算大规模文本相似度,实现海量文本信息去重. Simha

  • 利用python实现PSO算法优化二元函数

    python实现PSO算法优化二元函数,具体代码如下所示: import numpy as np import random import matplotlib.pyplot as plt from mpl_toolkits.mplot3d import Axes3D #----------------------PSO参数设置--------------------------------- class PSO(): def __init__(self,pN,dim,max_iter): #初

  • 利用python实现冒泡排序算法实例代码

    冒泡排序 冒泡排序(英语:Bubble Sort)是一种简单的排序算法.它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 冒泡排序算法的运作如下: 1.比较相邻的元素.如果第一个比第二个大(升序),就交换他们两个. 2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.这步做完后,最后的元素会是最大的数.

  • 利用Python实现kNN算法的代码

    邻近算法(k-NearestNeighbor) 是机器学习中的一种分类(classification)算法,也是机器学习中最简单的算法之一了.虽然很简单,但在解决特定问题时却能发挥很好的效果.因此,学习kNN算法是机器学习入门的一个很好的途径. kNN算法的思想非常的朴素,它选取k个离测试点最近的样本点,输出在这k个样本点中数量最多的标签(label).我们假设每一个样本有m个特征值(property),则一个样本的可以用一个m维向量表示: X =( x1,x2,... , xm ),  同样地

  • Python利用正则表达式实现计算器算法思路解析

    (1)不使用eval()等系统自带的计算方法 (2)实现四则混合运算.括号优先级解析 思路: 1.字符串预处理,将所有空格去除 2.判断是否存在括号运算,若存在进行第3步,若不存在则直接进入第4步 3.利用正则表达式获取最底层括号内的四则运算表达式 4.将四则运算表达式进行预处理:表达式开头有负数时,在表达式前加上一个0 5.利用re.split().re.findall()方法,通过加减符号,对四则运算进行拆分为乘除运算式和数字,并保留对应的位置下标. 6.利用re.split().re.fi

  • 利用Python如何实现K-means聚类算法

    目录 前言 算法原理 目标函数 算法流程 Python实现 总结 前言 K-Means 是一种非常简单的聚类算法(聚类算法都属于无监督学习).给定固定数量的聚类和输入数据集,该算法试图将数据划分为聚类,使得聚类内部具有较高的相似性,聚类与聚类之间具有较低的相似性. 算法原理 1. 初始化聚类中心,或者在输入数据范围内随机选择,或者使用一些现有的训练样本(推荐) 2. 直到收敛 将每个数据点分配到最近的聚类.点与聚类中心之间的距离是通过欧几里德距离测量得到的. 通过将聚类中心的当前估计值设置为属于

  • 如何利用Python动态展示排序算法

    目录 前言 选择冒泡 插入排序 归并排序 希尔排序 总结 前言 经常看到这种算法可视化的图片,但往往做不到和画图的人心灵相通,所以想自己画一下,本文主要实现归并排序和希尔排序,如果想实现其他算法可参考这篇 C语言实现各种排序算法[选择,冒泡,插入,归并,希尔,快排,堆排序,计数] 选择冒泡 这两种排序方案简单到很难说是什么算法,其中选择排序通过遍历一次数组,选出其中最大(小)的值放在新数组的第一位,再从剩下的数里选出最大(小)的,放到第二位,依次类推:冒泡排序则是通过重复走访要排序的数组,比较相

  • 利用python实现聚类分析K-means算法的详细过程

    K-means算法介绍 K-means算法是很典型的基于距离的聚类算法,采用距离作为相似性的评价指标,即认为两个对象的距离越近,其相似度就越大.该算法认为簇是由距离靠近的对象组成的,因此把得到紧凑且独立的簇作为最终目标. 算法过程如下: 1)从N个文档随机选取K个文档作为中心点: 2)对剩余的每个文档测量其到每个中心点的距离,并把它归到最近的质心的类: 3)重新计算已经得到的各个类的中心点: 4)迭代2-3步直至新的质心与原质心相等或小于指定阈值,算法结束. 算法优缺点: 优点: 原理简单 速度

随机推荐