Simhash算法詳解及python實現

GoogleMoses Charikar發表的一篇論文“detecting near-duplicates for web crawling”中提出了simhash算法，專門用來解決億萬級別的網頁的去重任務。

---

文章目錄

• Simhash算法詳解及python實現
• 前言
• 一、什么是simhash
• 二、simhash步驟
• • 1.分詞
  • 2.hash
  • 3.加權
  • 4.合并
  • 5.降維
• 三、simhash比對
• 總結

---

前言

simhash算法用來進行文本比對的

---

提示：以下是本篇文章正文內容，下面案例可供參考

一、什么是simhash

simhash算法用來進行文本比對的

二、simhash步驟

simhash包含分詞、hash、加權、合并、降維五大步驟

---

simhash代碼如下

import jieba import jieba.analyse import numpy as npclass SimHash(object):def simHash(self, content):seg = jieba.cut(content)# jieba.analyse.set_stop_words('stopword.txt')# jieba基于TF-IDF提取關鍵詞keyWords = jieba.analyse.extract_tags("|".join(seg), topK=10, withWeight=True)keyList = []for feature, weight in keyWords:# print('feature:' + feature)print('weight: {}'.format(weight))# weight = math.ceil(weight)weight = int(weight)binstr = self.string_hash(feature)print('feature: %s , string_hash %s' % (feature, binstr))temp = []for c in binstr:if (c == '1'):temp.append(weight)else:temp.append(-weight)keyList.append(temp)listSum = np.sum(np.array(keyList), axis=0)if (keyList == []):return '00'simhash = ''for i in listSum:if (i > 0):simhash = simhash + '1'else:simhash = simhash + '0'return simhashdef string_hash(self, source):if source == "":return 0else:temp = source[0]temp1 = ord(temp)x = ord(source[0]) << 7m = 1000003mask = 2 ** 128 - 1for c in source:x = ((x * m) ^ ord(c)) & maskx ^= len(source)if x == -1:x = -2x = bin(x).replace('0b', '').zfill(64)[-64:]return str(x)def getDistance(self, hashstr1, hashstr2):'''計算兩個simhash的漢明距離'''length = 0for index, char in enumerate(hashstr1):if char == hashstr2[index]:continueelse:length += 1return length

---

1.分詞

分詞是將文本文檔進行分割成不同的詞組，比如詞1為：今天星期四，詞2為：今天星期五

得出分詞結果為【今天，星期四】【今天，星期五】

2.hash

hash是將分詞結果取hash值
星期四hash為：0010001100100000101001101010000000101111011010010001100011011110
今天hash為：0010001111010100010011110001110010100011110111111011001011110101
星期五hash為：0010001100100000101001101010000000101111011010010000000010010001

3.加權

加權是將取分詞的hash結果分別對應乘以權重，假設分詞的hash分別為
$$hash(1)=\left[\begin{array}{cccc}0& 1& 0& 1\end{array}\right]$$
$$hash(2)=\left[\begin{array}{cccc}1& 0& 1& 0\end{array}\right]$$
權重（有幾個分詞對應幾個權重）為
$$weight=\left[\begin{array}{cc}100& 20\end{array}\right]$$
那么對應的加權為將hash值為0的置為-1，1的置為1，
然后分別乘以權重，得出的結果分別為
$$simhash(1)=\left[\begin{array}{cccc}?100& 100& ?100& 100\end{array}\right]$$
$$simhash(2)=\left[\begin{array}{cccc}20& ?20& 20& ?20\end{array}\right]$$

4.合并

合并是將加權的結果進行sum操作,比如上述兩個加權結果相加，得到的值為
$$simhas{h}_{temp}=\left[\begin{array}{cccc}?80& 80& ?80& 80\end{array}\right]$$

5.降維

降維是將合并的結果進行降維，如果值大于0，則置為1小于0 則置為0，因此得到的結果為：
$$simhas{h}_{temp}=\left[\begin{array}{cccc}0& 1& 0& 1\end{array}\right]$$

三、simhash比對

一般simhash采用海明距離來進行計算相似度，海明距離計算如下：
對于A，B兩個n維二進制數

$$A=(a_1,a_2,a_3,\dots ,a_n)$$
$$B=(b_1,b_2,b_3,\dots ,b_n)$$
二者的海明距離為：

$$distance(A,B)=\sum _{i=1}^n{d}_i$$
其中
$$d_i=\{\begin{array}{ll}0,& a_i=b_i\\ 1,& a_i=b_i\end{array}$$
舉例：
1000與1111的海明距離為3

---

總結

提示：這里對文章進行總結：
可以采用simhash對不同參數進行權重取值，然后使用漢明距離進行比對

總結

以上是生活随笔為你收集整理的Simhash算法详解及python实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。