simhash的文本去重原理是什么

這篇文章主要介紹“simhash的文本去重原理是什么”，在日常操作中，相信很多人在simhash的文本去重原理是什么問(wèn)題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”simhash的文本去重原理是什么”的疑惑有所幫助！接下來(lái)，請(qǐng)跟著小編一起來(lái)學(xué)習(xí)吧！

互聯(lián)網(wǎng)網(wǎng)頁(yè)存在大量的內(nèi)容重復(fù)的網(wǎng)頁(yè)，文本，無(wú)論對(duì)于搜索引擎，爬蟲(chóng)的網(wǎng)頁(yè)去重和過(guò)濾、新聞小說(shuō)等內(nèi)容網(wǎng)站的內(nèi)容反盜版和追蹤，還是社交媒體等文本去重和聚類(lèi)，都需要對(duì)網(wǎng)頁(yè)或者文本進(jìn)行去重和過(guò)濾。為此必須有一套高效的去重算法，要不然爬蟲(chóng)將做非常多的無(wú)用功，時(shí)效性等都無(wú)法得到保證，更重要的是用戶(hù)體驗(yàn)也不好。業(yè)界關(guān)于文本指紋去重的算法眾多，如 k-shingle 算法、google 提出的simhash 算法、Minhash 算法、百度top k 最長(zhǎng)句子簽名算法等等，下面介紹下simhash算法以及python應(yīng)用。

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

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

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

我們主要解決的是文本相似度計(jì)算，要比較的是兩個(gè)文章是否相識(shí)，當(dāng)然我們降維生成了hash簽名也是用于這個(gè)目的。看到這里估計(jì)大家就明白了，我們使用的simhash就算把文章中的字符串變成 01 串也還是可以用于計(jì)算相似度的，而傳統(tǒng)的hash卻不行。我們可以來(lái)做個(gè)測(cè)試，兩個(gè)相差只有一個(gè)字符的文本串，“你媽媽喊你回家吃飯哦” 和 “你媽媽叫你回家吃飯啦”。

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

1000010010101101111111100000101011010001001111100001001011001011

1000010010101101011111100000101011010001001111100001101010001011

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

0001000001100110100111011011110

1010010001111111110010110011101

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

2. simhash實(shí)現(xiàn)的主要步驟

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

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

2.1 分詞

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

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

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

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

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

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

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

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

2.3 漢明距離

在信息論中，兩個(gè)等長(zhǎng)字符串之間的漢明距離（英語(yǔ)：Hamming distance）是兩個(gè)字符串對(duì)應(yīng)位置的不同字符的個(gè)數(shù)。換句話說(shuō)，它就是將一個(gè)字符串變換成另外一個(gè)字符串所需要替換的字符個(gè)數(shù)。

漢明重量是字符串相對(duì)于同樣長(zhǎng)度的零字符串的漢明距離，也就是說(shuō)，它是字符串中非零的元素個(gè)數(shù)：對(duì)于二進(jìn)制字符串來(lái)說(shuō)，就是1的個(gè)數(shù)，所以11101的漢明重量是4。

對(duì)于二進(jìn)制字符串a(chǎn)與b來(lái)說(shuō)，它等于a 異或b后所得二進(jìn)制字符串中“1”的個(gè)數(shù)。

漢明距離是以理查德·衛(wèi)斯里·漢明的名字命名的，漢明在誤差檢測(cè)與校正碼的基礎(chǔ)性論文中首次引入這個(gè)概念。

在通信中累計(jì)定長(zhǎng)二進(jìn)制字中發(fā)生翻轉(zhuǎn)的錯(cuò)誤數(shù)據(jù)位，所以它也被稱(chēng)為信號(hào)距離。漢明重量分析在包括信息論、編碼理論、密碼學(xué)等領(lǐng)域都有應(yīng)用。但是，如果要比較兩個(gè)不同長(zhǎng)度的字符串，不僅要進(jìn)行替換，而且要進(jìn)行插入與刪除的運(yùn)算，在這種場(chǎng)合下，通常使用更加復(fù)雜的編輯距離等算法。

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

3. python 實(shí)現(xiàn)

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

pip install simhash

使用例子

from simhash import Simhash


def 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 similar


if __name__ == '__main__':
text1 = "行者AI專(zhuān)注于游戲領(lǐng)域,多年的AI技術(shù)積淀,一站式提供文本、圖片、音/視頻內(nèi)容審核,游戲AI以及數(shù)據(jù)平臺(tái)服務(wù)"

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

similar = simhash_demo(text1, text2)
print(similar)

到此，關(guān)于“simhash的文本去重原理是什么”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注億速云網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)?lái)更多實(shí)用的文章！