此篇文章主要是闡述了如何運(yùn)用python完成Sim哈希算法，文章內(nèi)容依托于python的相關(guān)信息開(kāi)展Sim哈希算法的詳細(xì)介紹一下，具有很強(qiáng)的參考意義，感興趣的朋友可以了解一下

　　1.為何需用Simhash?

　　傳統(tǒng)式相關(guān)性優(yōu)化算法：語(yǔ)義相似度測(cè)算，一般采用線性空間實(shí)體模型(VSM)，先向文字中文分詞，提取特征，依據(jù)特點(diǎn)創(chuàng)建文字空間向量，把文字中間相關(guān)性測(cè)算轉(zhuǎn)化成矩陣的特征值之間的距離測(cè)算，如歐氏距離、余弦交角等。

　　缺陷：大數(shù)據(jù)技術(shù)前提下復(fù)雜性會(huì)比較高。

　　Simhash應(yīng)用情景：測(cè)算規(guī)模性語(yǔ)義相似度，完成大量文本內(nèi)容去重。

　　Sim哈希算法基本原理：根據(jù)hash值較為相關(guān)性，根據(jù)2個(gè)字符串?dāng)?shù)組測(cè)算出來(lái)的hash值，開(kāi)展取反實(shí)際操作，隨后獲得相距的數(shù)量，數(shù)據(jù)越多則差別越多。

　　2.文章內(nèi)容關(guān)鍵字svm算法優(yōu)化算法TD-IDF

　　高頻詞（TF）：一個(gè)成語(yǔ)在全篇文章中存在的頻次與詞句總數(shù)量比例；

　　反向高頻詞（IDF)：一個(gè)成語(yǔ)，在大多數(shù)文中出現(xiàn)頻率都很高，這個(gè)詞不有代表性的，就能夠降低它的作用，其實(shí)就是給予其比較小的權(quán)重值。

　　分子結(jié)構(gòu)意味著文章內(nèi)容數(shù)量，真分?jǐn)?shù)表明該詞句在各種文章內(nèi)容發(fā)生的篇幅。通常會(huì)采用真分?jǐn)?shù)加一點(diǎn)的辦法，避免真分?jǐn)?shù)為0的情況發(fā)生，在這一比率以后取對(duì)數(shù)，便是IDF了。

　　最后用tf*idf獲得一個(gè)成語(yǔ)的權(quán)重值，從而測(cè)算篇文章核心關(guān)鍵詞。再根據(jù)每篇比照其關(guān)鍵字的方法去文章結(jié)構(gòu)開(kāi)展去重。sim哈希算法對(duì)效率特性開(kāi)展均衡，既能非常少對(duì)比（關(guān)鍵字不可以取過(guò)多），又可有一個(gè)好的標(biāo)志性（關(guān)鍵字不可以太少）。

　　3.Simhash基本原理

　　Simhash是一類部分比較敏感hash。即假設(shè)A、B具有很強(qiáng)的相關(guān)性，在hash之后，依然可以保持這類相關(guān)性，就稱為部分比較敏感hash。

　　獲得篇文章關(guān)鍵字結(jié)合，根據(jù)hash的辦法把關(guān)鍵字集合hash成一長(zhǎng)串2進(jìn)制，立即比照二進(jìn)制，其相關(guān)性便是幾篇文本文檔的相關(guān)性，在查詢相關(guān)性時(shí)使用海明間距，則在比照二進(jìn)制情況下，看它的有多少個(gè)位不一樣，就稱海明間距為是多少。

　　將文章內(nèi)容simhash獲得一長(zhǎng)串64席的2進(jìn)制，依據(jù)工作經(jīng)驗(yàn)通常取海明間距為3做為閥值，則在64位2進(jìn)制中，只要是有3位之內(nèi)不一樣，就能覺(jué)得2個(gè)文本文檔是相近的，這兒的閥值還可以根據(jù)自己的喜好來(lái)設(shè)定。就是把1個(gè)文本文檔hash之后獲得一長(zhǎng)串二進(jìn)制的優(yōu)化算法，稱這一個(gè)hash為simhash。

　　simhash實(shí)際完成過(guò)程如下所示：

　　1.將文本文檔中文分詞，取個(gè)論文的TF-IDF權(quán)重值最高前20個(gè)詞（feature）和權(quán)重值（weight）。即一篇文章文本文檔獲得了一個(gè)長(zhǎng)短為20的（feature：weight）的結(jié)合。

　　2.對(duì)涉及的詞匯（feature），開(kāi)展普通hach以后獲得了一個(gè)64求的2進(jìn)制，獲得長(zhǎng)短為20的（hash:weight）的結(jié)合。

　　3.依據(jù)（2）中獲得一長(zhǎng)串二進(jìn)制（hash）中相對(duì)應(yīng)位置在1是0，對(duì)相對(duì)應(yīng)部位取正逢weight和負(fù)數(shù)weight。比如一個(gè)詞語(yǔ)經(jīng)過(guò)（2）獲得（010111：5）經(jīng)過(guò)過(guò)程（3）以后可以獲得目錄[-5,5,-5,5,5,5]。從而可以獲得20個(gè)長(zhǎng)短為64的目錄[weight，-weight...weight]意味著1個(gè)文本文檔。

　　4.對(duì)（3）中20個(gè)目錄開(kāi)展列向累加獲得了一個(gè)目錄。如[-5,5,-5,5,5,5]、[-3,-3,-3,3,-3,3]、[1,-1,-1,1,1,1]開(kāi)展列向累加獲得[-7，1，-9，9，3，9]，那樣，對(duì)于1個(gè)文本文檔獲得，1個(gè)長(zhǎng)短為64的目錄。

　　5.對(duì)（4）中獲得的頁(yè)面上每一個(gè)值作出判斷，當(dāng)以負(fù)數(shù)時(shí)去0，正逢取1。比如，[-7，1，-9，9，3，9]獲得010111，這個(gè)就獲得了一個(gè)文本文檔的simhash值了。

　　6.測(cè)算相關(guān)性。兩個(gè)simhash取取反，看在其中1的數(shù)量是不是超出3。超出3則認(rèn)定是不類似，應(yīng)當(dāng)小于等于3則認(rèn)定是類似。

　　Simhash總體流程表如下所示：

　　4.Simhash的不足

　　完全無(wú)關(guān)的文本正好對(duì)應(yīng)成了相同的simhash，精確度并不是很高，而且simhash更適用于較長(zhǎng)的文本，但是在大規(guī)模語(yǔ)料進(jìn)行去重時(shí)，simhash的計(jì)算速度優(yōu)勢(shì)還是很不錯(cuò)的。

　　5.Simhash算法實(shí)現(xiàn)

　　#!/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#查看當(dāng)前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#整個(gè)文檔的fingerprint為最終各個(gè)位>=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
　　#針對(duì)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
　　測(cè)試：
　　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))

　　綜上所述，這篇文章就給大家介紹到這里了，希望可以給大家?guī)?lái)幫助。