如何运用python完成Sim哈希算法

89542767 发布于2022-12-28 14:08 / 364人阅读

　　此篇文章主要是阐述了如何运用python完成Sim哈希算法，文章内容依托于python的相关信息开展Sim哈希算法的详细介绍一下，具有很强的参考意义，感兴趣的朋友可以了解一下

　　1.为何需用Simhash?

　　传统式相关性优化算法：语义相似度测算，一般采用线性空间实体模型(VSM)，先向文字中文分词，提取特征，依据特点创建文字空间向量，把文字中间相关性测算转化成矩阵的特征值之间的距离测算，如欧氏距离、余弦交角等。

　　缺陷：大数据技术前提下复杂性会比较高。

　　Simhash应用情景：测算规模性语义相似度，完成大量文本内容去重。

　　Sim哈希算法基本原理：根据hash值较为相关性，根据2个字符串数组测算出来的hash值，开展取反实际操作，随后获得相距的数量，数据越多则差别越多。

　　2.文章内容关键字svm算法优化算法TD-IDF

　　高频词（TF）：一个成语在全篇文章中存在的频次与词句总数量比例；

　　反向高频词（IDF)：一个成语，在大多数文中出现频率都很高，这个词不有代表性的，就能够降低它的作用，其实就是给予其比较小的权重值。

　　分子结构意味着文章内容数量，真分数表明该词句在各种文章内容发生的篇幅。通常会采用真分数加一点的办法，避免真分数为0的情况发生，在这一比率以后取对数，便是IDF了。

　　最后用tf*idf获得一个成语的权重值，从而测算篇文章核心关键词。再根据每篇比照其关键字的方法去文章结构开展去重。sim哈希算法对效率特性开展均衡，既能非常少对比（关键字不可以取过多），又可有一个好的标志性（关键字不可以太少）。

　　3.Simhash基本原理

　　Simhash是一类部分比较敏感hash。即假设A、B具有很强的相关性，在hash之后，依然可以保持这类相关性，就称为部分比较敏感hash。

　　获得篇文章关键字结合，根据hash的办法把关键字集合hash成一长串2进制，立即比照二进制，其相关性便是几篇文本文档的相关性，在查询相关性时使用海明间距，则在比照二进制情况下，看它的有多少个位不一样，就称海明间距为是多少。

　　将文章内容simhash获得一长串64席的2进制，依据工作经验通常取海明间距为3做为阀值，则在64位2进制中，只要是有3位之内不一样，就能觉得2个文本文档是相近的，这儿的阀值还可以根据自己的喜好来设定。就是把1个文本文档hash之后获得一长串二进制的优化算法，称这一个hash为simhash。

　　simhash实际完成过程如下所示：

　　1.将文本文档中文分词，取个论文的TF-IDF权重值最高前20个词（feature）和权重值（weight）。即一篇文章文本文档获得了一个长短为20的（feature：weight）的结合。

　　2.对涉及的词汇（feature），开展普通hach以后获得了一个64求的2进制，获得长短为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]意味着1个文本文档。

　　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]，那样，对于1个文本文档获得，1个长短为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&lt;&lt;i
　　if t&bitmask:
　　v&lt;i&gt;+=1#查看当前bit位是否为1,是的话将该位+1
　　else:
　　v&lt;i&gt;-=1#否则的话,该位-1
　　fingerprint=0
　　for i in range(self.hashbits):
　　if v&lt;i&gt;&gt;=0:
　　fingerprint+=1&lt;&lt;i
　　return fingerprint#整个文档的fingerprint为最终各个位&gt;=0的和
　　#求海明距离
　　def hamming_distance(self,other):
　　x=(self.hash^other.hash)&((1&lt;&lt;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&gt;b:
　　return b/a
　　else:
　　return a/b
　　#针对source生成hash值
　　def _string_hash(self,source):
　　if source=="":
　　return 0
　　else:
　　x=ord(source[0])&lt;&lt;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))

　　综上所述，这篇文章就给大家介绍到这里了，希望可以给大家带来帮助。

专线服务混合云哈希算法最小哈希算法一致性哈希算法哈希ip地址hash算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/128830.html

python协程3：用仿真实验学习协程

摘要：徘徊和行程所用的时间使用指数分布生成，我们将时间设为分钟数，以便显示清楚。迭代表示各辆出租车的进程在各辆出租车上调用函数，预激协程。前两篇我们已经介绍了python 协程的使用和yield from 的原理，这一篇，我们用一个例子来揭示如何使用协程在单线程中管理并发活动。。什么是离散事件仿真 Wiki上的定义是：离散事件仿真将系统随时间的变化抽象成一系列的离散时间点上的事件，通过...

banana_pi 2019-07-31 10:58 评论0 收藏0
协同过滤算法

摘要：协作型过滤协同过滤是利用集体智慧的一个典型方法。这就是协同过滤的核心思想。要实现协同过滤，需要以下几个步骤搜集偏好寻找相近用户推荐物品搜集偏好首先，我们要寻找一种表达不同人及其偏好的方法。协作型过滤协同过滤是利用集体智慧的一个典型方法。要理解什么是协同过滤 (Collaborative Filtering, 简称CF)，首先想一个简单的问题，如果你现在想看个电影，但你不知道具体看哪...

Batkid 2019-07-24 18:14 评论0 收藏0
Item-Based Collaborative Filtering Recommendation

摘要：用户过去的偏好很可能展示或者反应未来的兴趣偏好。数据集我们选用，下载地址数据集算法理论算法框架如图，输入是的评分矩阵，该矩阵非常稀疏。所以预测分两步进行计算项目之间的相似性和根据相似性进行预测评分。【参考文献】：Sarwar B M . Item-based collaborative filtering recommendation algorithms[C]// Internat...

voyagelab 2019-07-30 18:35 评论0 收藏0
Python图像处理之图片文字识别（OCR）

摘要：与介绍将图片翻译成文字一般被称为光学文字识别，。是目前公认最优秀最精确的开源系统。我们以图片为例输入命令识别结果如下只识别错了一个字，识别率还是不错的。最后加一句，对于彩色图片的识别效果没有黑白图片的效果好。 OCR与Tesseract介绍将图片翻译成文字一般被称为光学文字识别（Optical Character Recognition，OCR）。可以实现OCR 的底层库并不多，...

W4n9Hu1 2019-07-30 16:48 评论0 收藏0