---

互聯(lián)網(wǎng)網(wǎng)頁存在著大量重復(fù)內(nèi)容，必須有一套高效的去重算法，否則爬蟲將做非常多的無用功，工作時效性無法得到保證，更重要的是用戶體驗(yàn)也不好。業(yè)界關(guān)于文本指紋去重的算法眾多，如 k-shingle 算法、google 提出的simhash 算法、Minhash 算法、百度top k 最長句子簽名算法等等，本文主要介紹simhash算法以及python應(yīng)用.

simhash

• simhash 與傳統(tǒng)hash 的區(qū)別

傳統(tǒng)的Hash算法只負(fù)責(zé)將原始內(nèi)容盡量均勻隨機(jī)地映射為一個簽名值，原理上僅相當(dāng)于偽隨機(jī)數(shù)產(chǎn)生算法。傳統(tǒng)的hash算法產(chǎn)生的兩個簽名，如果原始內(nèi)容在一定概率下是相等的；如果不相等，除了說明原始內(nèi)容不相等外，不提供任何信息，因?yàn)榧词乖純?nèi)容只相差一個字節(jié)，所產(chǎn)生的簽名也很可能差別很大。所以傳統(tǒng)的Hash是無法在簽名的維度上來衡量原內(nèi)容的相似度，而SimHash本身屬于一種局部敏感哈希算法，它產(chǎn)生的hash簽名在一定程度上可以表征原內(nèi)容的相似度。

我們主要解決的是文本相似度計(jì)算，我們降維生成hash簽名也是用于這個目的?？吹竭@里估計(jì)大家就明白了，我們使用的simhash就算把文章中的字符串變成 01 串也還是可以用于計(jì)算相似度的，而傳統(tǒng)的hash卻不行。我們可以來做個測試，兩個相差只有一個字符的文本串，“你媽媽喊你回家吃飯哦” 和 “你媽媽叫你回家吃飯啦”。

通過simhash計(jì)算結(jié)果為：

1000010010101101111111100000101011010001001111100001001011001011

1000010010101101011111100000101011010001001111100001101010001011

通過傳統(tǒng)hash計(jì)算為：

0001000001100110100111011011110

1010010001111111110010110011101

大家可以看得出來，相似的文本只有部分 01 串變化了，而普通的hash卻不能做到，這個就是局部敏感哈希的魅力。

• simhash簡介

simhash 是 google 用來處理海量文本去重的算法。 simhash 可以將一個文檔轉(zhuǎn)換成一個 64 位的字節(jié)，暫且稱之為特征字。判斷文檔是否重復(fù)，只需要判斷文檔特征字之間的漢明距離。根據(jù)經(jīng)驗(yàn)，一般當(dāng)兩個文檔特征字之間的漢明距離小于 3， 就可以判定兩個文檔相似。

主要步驟：在新拿到文本之后需要先進(jìn)行分詞，這是因?yàn)樾枰舫鯰opN個詞來表征這篇文本，并且分詞的權(quán)重不一樣，可以使用相應(yīng)數(shù)據(jù)集的tf-idf值作為分詞的權(quán)重，這樣就分成了帶權(quán)重的分詞結(jié)果。

之后對所有分詞進(jìn)行哈希運(yùn)算獲取二值化的hash結(jié)果，再將權(quán)重與哈希值相乘，獲得帶權(quán)重的哈希值，最后進(jìn)行累加以及二值化處理.

• 分詞

使用分詞手段將文本分割成關(guān)鍵詞的特征向量，分詞方法有很多一般都是實(shí)詞，也就是把停用詞等都去掉之后的部分，使用者可以根據(jù)自己的需求選擇.最后形成去掉噪音詞的單詞序列并為每個詞加上權(quán)重. 例如:

行者AI 專注 于 游戲 領(lǐng)域 多年 AI技術(shù) 積淀 一站式 提供 文本 圖片 音視頻 內(nèi)容 審核 游戲AI 以及 數(shù)據(jù) 平臺 服務(wù)

目前的詞只是進(jìn)行了分割，但是詞與詞含有的信息量是不一樣的，比如行者AI 游戲 審核 這三個詞就比 專注 服務(wù) 以及更能表達(dá)文本的主旨含義，這也就是所謂信息熵的概念。

為此我們還需要設(shè)定特征詞的權(quán)重，簡單一點(diǎn)的可以使用絕對詞頻來表示，也就是某個關(guān)鍵詞出現(xiàn)的次數(shù)，但是事實(shí)上出現(xiàn)次數(shù)少的所含有的信息量可能更多.總之需要選擇一種加權(quán)方法，否則效果會打折扣。

• 哈希和權(quán)重化

前面我們使用分詞方法和權(quán)重分配將文本就分割成若干個帶權(quán)重的實(shí)詞，比如權(quán)重使用1-5的數(shù)字表示，1最低5最高

行者AI(5) 專注(2) 于(1) 游戲(3) 領(lǐng)域(1) ......

對各個特征詞進(jìn)行二值化哈希值計(jì)算, 再將所有的哈希值累加，最后將累加結(jié)果二值化.

• 漢明距離

在信息論中，兩個等長字符串之間的漢明距離（英語：Hamming distance）是兩個字符串對應(yīng)位置的不同字符的個數(shù)。換句話說，它就是將一個字符串變換成另外一個字符串所需要替換的字符個數(shù)。 漢明重量是字符串相對于同樣長度的零字符串的漢明距離，也就是說，它是字符串中非零的元素個數(shù)：對于二進(jìn)制字符串來說，就是1的個數(shù)，所以11101的漢明重量是4。 對于二進(jìn)制字符串a(chǎn)與b來說，它等于a 異或b后所得二進(jìn)制字符串中“1”的個數(shù)。 漢明距離是以理查德·衛(wèi)斯里·漢明的名字命名的，漢明在誤差檢測與校正碼的基礎(chǔ)性論文中首次引入這個概念。 在通信中累計(jì)定長二進(jìn)制字中發(fā)生翻轉(zhuǎn)的錯誤數(shù)據(jù)位，所以它也被稱為信號距離。漢明重量分析在包括信息論、編碼理論、密碼學(xué)等領(lǐng)域都有應(yīng)用。但是，如果要比較兩個不同長度的字符串，不僅要進(jìn)行替換，而且要進(jìn)行插入與刪除的運(yùn)算，在這種場合下，通常使用更加復(fù)雜的編輯距離等算法。

谷歌經(jīng)過工程驗(yàn)證認(rèn)為當(dāng)兩個64bit的二值化simhash值的漢明距離超過3則認(rèn)為不相似，所以判重問題就轉(zhuǎn)換為求兩個哈希值的漢明距離問題。

• python 實(shí)現(xiàn)

pip 源中有數(shù)種 simhash 的實(shí)現(xiàn)，simhash，使用起來十分方便，直接使用 pip 就可以安裝

pip install simhash

使用例子

from simhash import Simhashdef simhash_demo(text1, text2): """ 求兩文本的相似度 :param text1: :param text2: :return: """ a_simhash = Simhash(text1) b_simhash = Simhash(text2) max_hashbit = max(len(bin(a_simhash.value)), (len(bin(b_simhash.value)))) # 漢明距離 distince = a_simhash.distance(b_simhash) print(distince) similar = 1 - distince / max_hashbit return similarif __name__ == '__main__': text1 = "行者AI專注于游戲領(lǐng)域,多年的AI技術(shù)積淀,一站式提供文本、圖片、音/視頻內(nèi)容審核,游戲AI以及數(shù)據(jù)平臺服務(wù)"text2 = "行者AI專注于游戲領(lǐng)域,多年的AI技術(shù)積淀,二站式提供文本、圖片、音 視頻內(nèi)容審核,游戲AI以及數(shù)據(jù)平臺服務(wù)"similar = simhash_demo(text1, text2) print(similar)

---

PS：

我們是行者AI，我們在“AI＋游戲”中不斷前行。

如果你也對游戲感興趣，對AI充滿好奇，那就快來加入我們（contact@xingzhe.ai）。

總結(jié)

以上是生活随笔為你收集整理的hashset去重原理_基于simhash的文本去重原理的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。