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

　　1.為何需用Simhash?

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

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

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

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

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

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

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

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

　　最后用tf*idf獲得一個成語的權重值，從而測算篇文章核心關鍵詞。再根據(jù)每篇比照其關鍵字的方法去文章結構開展去重。sim哈希算法對效率特性開展均衡，既能非常少對比（關鍵字不可以取過多），又可有一個好的標志性（關鍵字不可以太少）。

　　3.Simhash基本原理

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

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

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

　　simhash實際完成過程如下所示：

　　1.將文本文檔中文分詞，取個論文的TF-IDF權重值最高前20個詞（feature）和權重值（weight）。即一篇文章文本文檔獲得了一個長短為20的（feature：weight）的結合。

　　2.對涉及的詞匯（feature），開展普通hach以后獲得了一個64求的2進制，獲得長短為20的（hash:weight）的結合。

　　3.依據(jù)（2）中獲得一長串二進制（hash）中相對應位置在1是0，對相對應部位取正逢weight和負數(shù)weight。比如一個詞語經(jīng)過（2）獲得（010111：5）經(jīng)過過程（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）中獲得的頁面上每一個值作出判斷，當以負數(shù)時去0，正逢取1。比如，[-7，1，-9，9，3，9]獲得010111，這個就獲得了一個文本文檔的simhash值了。

　　6.測算相關性。兩個simhash取取反，看在其中1的數(shù)量是不是超出3。超出3則認定是不類似，應當小于等于3則認定是類似。

　　Simhash總體流程表如下所示：

　　4.Simhash的不足

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

　　5.Simhash算法實現(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#查看當前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))

　　綜上所述，這篇文章就給大家介紹到這里了，希望可以給大家?guī)韼椭?/p>