1.先嘮個嗑

前面兩周寫了兩期分布式系統(tǒng)一致性相關(guān)的問題，按照計(jì)劃本周應(yīng)該是3PC協(xié)議了，但是跳票了，因?yàn)檎娴倪€是挺忙，只能請大家吃回鍋肉了。

可能有的讀者會說不就是一篇文章嘛，那么費(fèi)勁嗎？那我只能說：費(fèi)勁。

為啥費(fèi)勁呢？

拾人牙慧，人云亦云，基本上就是浪費(fèi)自己和讀者的時間，所以良好的表達(dá)需要深刻的理解，但是對于讀者來說要想真實(shí)完整地掌握這個知識點(diǎn)，必須是靠自己的實(shí)踐，公眾號只是拋磚引玉。

多年跨專業(yè)跨行業(yè)的親身經(jīng)歷，讓我深深感受到站在小白的角度去闡述澄清一件事情的來龍去脈的重要性，我現(xiàn)在也確實(shí)沒有耐心看很長的文章，但是對于幾個很認(rèn)可的號也還是會認(rèn)真讀完，成為被認(rèn)可的號也是我的目標(biāo)。

沒有誰比誰更笨，天賦這個東西就算我們沒有，勤奮也足夠讓我們超越60%的人，很多時候只不過是信息不對稱，讓我們在門外徘徊轉(zhuǎn)身離開。

廢話不說，直接上車。

和大家重溫一篇19年12月寫的，文本去重相關(guān)的文章，為啥選這一篇呢？因?yàn)槲矣X得這一篇還不錯，但是當(dāng)時訂閱讀者少，曝光不多，新訂閱的讀者就當(dāng)一篇新文章吧...

通過本文你將了解到以下內(nèi)容：

• 信息爆炸的日常生活
• 網(wǎng)頁去重和局部敏感哈希算法
• simhash算法基本原理和過程分析
• 工程中的去重和聚類實(shí)現(xiàn)建議

2. 信息大爆炸

從2010年之后移動互聯(lián)網(wǎng)如火如荼，筆者在2011年的時候還在用只能打電話發(fā)短信的那種手機(jī)，然而現(xiàn)在幾乎每個人手機(jī)里的app起碼有10-20款，以至于經(jīng)常有種信息爆炸到頭暈的感覺，回顧一下匆匆十年手機(jī)里的變化：

以信息流領(lǐng)域來說，有今日頭條、百度App、搜狗搜索app、一點(diǎn)資訊、趣頭條等feed軟件。

很多時候都是自媒體作者會同時在多個平臺發(fā)布相同的文章，然后會出現(xiàn)非常多的洗稿文章、抄襲文章等，我們無法杜絕和制止這種行為，但是很多時候需要我們使用技術(shù)手段來進(jìn)行識別并處理，讓用戶看到最好的形式的文章和資訊。

信息爆炸時代，我們需要一個好的文本去重。

3.網(wǎng)頁去重

文本去重場景是網(wǎng)頁去重，像谷歌、百度、搜狗這種大型的搜索引擎，必須有一套高效的去重算法，要不然網(wǎng)絡(luò)蜘蛛將做非常多的無用功，時效性等都無法得到保證，更重要的是用戶體驗(yàn)也不好。

研究表明：互聯(lián)網(wǎng)上近似重復(fù)的網(wǎng)頁的數(shù)量占網(wǎng)頁總數(shù)量的比例高達(dá)29%，完全相同的網(wǎng)頁大約占網(wǎng)頁總數(shù)量的22%。

實(shí)際中搜索引擎的去重和排序都非常復(fù)雜，本文本著簡化的思路來闡述其中的一些要點(diǎn)，無法全面深入，對此表示歉意。

谷歌出品，必屬精品，我們來看看地表最強(qiáng)搜索引擎是如果做網(wǎng)頁去重呢？

這里就引出了今天要講的主要內(nèi)容simhash算法，本質(zhì)上文本去重算法有很多種，每種算法都有各自的優(yōu)劣勢，本文并不做橫向?qū)Ρ龋侵苯右鰏imhash算法進(jìn)行闡述，對于橫向?qū)Ρ雀信d趣的讀者可以自行查閱相關(guān)資料。

4.局部敏感哈希

說到hash可能我們第一個想到的是md5這種信息摘要算法，可能兩篇文本只有一個標(biāo)點(diǎn)符號的差距，但是兩篇文本A和B的md5值差異就非常大，感興趣的可以試驗(yàn)一下看看，Linux環(huán)境下直接md5sum即可計(jì)算。

有時候我們希望的是原本相同的文章做了微小改動之后的哈希值也是相似的，這種哈希算法稱為局部敏感哈希LSH(Locality Sensitive Hashing)，這樣我們就能從哈希值來推斷相似的文章。

局部敏感哈希算法使得在原來空間相似的樣本集合，進(jìn)行相關(guān)運(yùn)算映射到特定范圍空間時仍然是相似的，這樣還不夠，還需要保證原來不相似的哈希之后仍然極大概率不相似，這種雙向保證才讓LSH的應(yīng)用成為可能。

筆者個人認(rèn)為LSH常用的用途是判重和聚類，其實(shí)這兩個作用很相似，比如在信息流中我們在識別到文章相似之后無法拒絕入庫，這時候就會做聚類，然后用一個id來串起來很多相似的id，從而實(shí)現(xiàn)相似文章的把控和管理。

5.SimHash算法及其基本過程

5.1 simhash和谷歌

simhash算法可以將一個文本生成為一個64bit的二進(jìn)制數(shù)，這里提一句simhash算法最初貌似并不是谷歌提出來的，而是谷歌應(yīng)用推廣的，所以本文出現(xiàn)的simhash相關(guān)的數(shù)據(jù)也都是基于工程中谷歌提出的simhash網(wǎng)頁去重展開的。

谷歌2007年關(guān)于simhash的論文：https://www2007.org/papers/paper215.pdf

5.2 64bit的容量

simhash值每個位可以是1或者0，這樣就有2^64種可能了，這個有多大呢？想必聰明的讀者一定知道棋盤爆炸理論的故事：

傳說西塔發(fā)明了國際象棋而使國王十分高興，他決定要重賞西塔，西塔說：我不要你的重賞，陛下，只要你在我的棋盤上賞一些麥子就行了。 

在棋盤的第1個格子里放1粒，在第2個格子里放2粒，在第3個格子里放4粒，在第4個格子里放8粒，依此類推，以后每一個格子里放的麥粒數(shù)都是前一個格子里放的麥粒數(shù)的2倍，直到放滿第64個格子就行了。

看似樸實(shí)但是如果真放滿64格需要多少麥粒呢？筆者在網(wǎng)上看了一些相關(guān)的資料和大家分享一下：

總計(jì)需要1844.67億億顆麥粒，以每顆麥粒0.015g計(jì)算大約是2767億噸，在當(dāng)今糧食產(chǎn)量的水平下大約需要300多年才能種出來。

冪次爆炸的影響力絕非臆想所能企及的程度的，這個哥們后來不知道是不是被治了欺君之罪了，要是在我國古代那肯定懸了。

說這么多的目的是想表達(dá)simhash使用64bit的空間足夠，不用有太多的擔(dān)心。

5.3 哈希指紋生成過程

我們如何將一個文本轉(zhuǎn)換為64bit數(shù)據(jù)呢？

主要步驟：在新拿到文本之后需要先進(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ù)自己的需求選擇，假設(shè)分割后的特征實(shí)詞如下：

12306 服務(wù)器 故障 車次 加載失敗 購買 候補(bǔ)訂單 支付 官方 消費(fèi)者 建議 卸載 重裝 切換網(wǎng)絡(luò) 耐心 等待

目前的詞只是進(jìn)行了分割，但是詞與詞含有的信息量是不一樣的，比如12306 服務(wù)器 故障 這三個詞就比 支付 卸載 重裝更能表達(dá)文本的主旨含義，這也就是所謂信息熵的概念。

為此我們還需要設(shè)定特征詞的權(quán)重，簡單一點(diǎn)的可以使用絕對詞頻來表示，也就是某個關(guān)鍵詞出現(xiàn)的次數(shù)，但是事實(shí)上出現(xiàn)次數(shù)少的所含有的信息量可能更多，這就是TF-IDF逆文檔頻率概念，來看下維基百科對tf-idf的解釋：

tf-idf(term frequency–inverse document frequency)是一種用于信息檢索與文本挖掘的常用加權(quán)技術(shù)。

tf-idf是一種統(tǒng)計(jì)方法，用以評估一字詞對于一個文件集或一個語料庫中的其中一份文件的重要程度。字詞的重要性隨著它在文件中出現(xiàn)的次數(shù)成正比增加，但同時會隨著它在語料庫中出現(xiàn)的頻率成反比下降。

tf-idf加權(quán)的各種形式常被搜索引擎應(yīng)用，作為文件與用戶查詢之間相關(guān)程度的度量或評級。

總之需要選擇一種加權(quán)方法，否則效果會打折扣。

哈希計(jì)算和權(quán)重化
前面我們使用分詞方法和權(quán)重分配將文本就分割成若干個帶權(quán)重的實(shí)詞，比如權(quán)重使用1-5的數(shù)字表示，1最低5最高，這樣我們就把原文本處理成如下的樣式：

12306(5) 服務(wù)器(4) 故障(4) 車次(4) 加載失敗(3) 購買(2) 候補(bǔ)訂單(4) 支付(2) 官方(2) 消費(fèi)者(3) 建議(1) 卸載(3) 重裝(3) 切換網(wǎng)絡(luò)(2) 耐心(1) 等待(1)

我們對各個特征詞進(jìn)行二值化哈希值計(jì)算，為了簡化問題這里設(shè)定哈希值長度為8bit 并非實(shí)踐使用，舉例如下：

12306 10011100
服務(wù)器 01110101
故障 00110011
車次 11001010
…

這樣我們就把特征詞都全部二值化為8bit，這里各個位的1代表+1，0代表-1，依次進(jìn)行權(quán)重相乘，得到新的結(jié)果：

12306 10011100 --> 5 -5 -5 5 5 5 -5 -5
服務(wù)器 01110101 --> -4 4 4 4 -4 4 -4 4
故障 00110011 --> -4 -4 4 4 -4 -4 4 4
車次 11001010 --> 4 4 -4 -4 4 -4 4 -4
…

特征詞帶權(quán)重哈希值累加和二值化降維
經(jīng)過前面的幾步 我們已經(jīng)將文本轉(zhuǎn)換為帶權(quán)重的哈希值了，接下來將所有的哈希值累加，最后將累加結(jié)果二值化，如下：

12306的帶權(quán)重哈希值為5 -5 -5 5 5 5 -5 -5
服務(wù)器的帶權(quán)重哈希值為-4 4 4 4 -4 4 -4 4
二者累加為 1 -1 -1 9 1 9 -9 -1
…
依次累加所有的帶權(quán)重哈希值，假定最終結(jié)果為 18 9 -6 -9 22 -35 12 -5
再按照正數(shù)1負(fù)數(shù)0的規(guī)則將上述結(jié)果二值化為：11001010

至此當(dāng)收到一個新的文本時經(jīng)過分詞、哈希、加權(quán)、累加、二值化幾個步驟就將一個文本映射到一定長度的二進(jìn)制空間內(nèi)，之后所有的判重和聚類操作都會基于這個降維數(shù)值進(jìn)行，最后貼一張網(wǎng)上非常經(jīng)典的圖，展示一個文本進(jìn)行simhash的主要步驟和細(xì)節(jié)，如圖所示：

6.漢明距離

前面講述了如何生成一個文本的simhash值，接下來思考一個更重要的問題：如果對比確定相似呢？別急，先來看看維基百科關(guān)于漢明距離的一些基礎(chǔ)吧，后面要用到這個理論。

漢明距離

在信息論中，兩個等長字符串之間的漢明距離（英語：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ù)雜的編輯距離等算法。

理論發(fā)明者簡介

理查德·衛(wèi)斯里·漢明（Richard Wesley Hamming，1915年2月11日－1998年1月7日），美國數(shù)學(xué)家，主要貢獻(xiàn)在計(jì)算機(jī)科學(xué)和電訊。

1937年芝加哥大學(xué)學(xué)士學(xué)位畢業(yè)，1939年內(nèi)布拉斯加大學(xué)碩士學(xué)位畢業(yè)，1942年伊利諾伊大學(xué)香檳分校博士學(xué)位畢業(yè)，博士論文為《一些線性微分方程邊界值理論上的問題》。

二戰(zhàn)期間在路易斯維爾大學(xué)當(dāng)教授，1945年參加曼哈頓計(jì)劃，負(fù)責(zé)編寫計(jì)算機(jī)程序，計(jì)算物理學(xué)家所提供方程的解。該程式是判斷引爆核彈會否燃燒大氣層，結(jié)果是不會，于是核彈便開始試驗(yàn)。

1946至76年在貝爾實(shí)驗(yàn)室工作。他曾和約翰·懷爾德·杜奇、克勞德·艾爾伍德·香農(nóng)合作。1956年他參與了IBM 650的編程語言發(fā)展工作。1976年7月23日起在美國海軍研究院擔(dān)當(dāng)兼任教授，1997年為名譽(yù)教授。他是美國電腦協(xié)會ACM的創(chuàng)立人之一，曾任該組織的主席。

相關(guān)獎項(xiàng)和榮譽(yù)：1968年ACM圖靈獎、1968年IEEE院士、1979年EmanuelR.Piore獎、1980年美國國家工程學(xué)院院士、1981年賓夕法尼亞大學(xué)Harold Pender獎、1988年IEEE理查·衛(wèi)斯里·漢明獎

本文就不深究漢明距離的數(shù)學(xué)原理以及證明過程了，直接使用結(jié)論，谷歌經(jīng)過工程驗(yàn)證認(rèn)為當(dāng)兩個64bit的二值化simhash值的漢明距離超過3則認(rèn)為不相似，所以判重問題就轉(zhuǎn)換為求兩個哈希值的漢明距離問題。

谷歌對于漢明距離的選取，筆者查詢了相關(guān)論文后了解到，谷歌使用80億的數(shù)據(jù)將漢明距離從1-10進(jìn)行試驗(yàn)，我們可以知道當(dāng)漢明距離越大意味著判重越不嚴(yán)格，漢明距離越小則判重更加嚴(yán)格，對此谷歌給出的是一個權(quán)衡值：

7.海量數(shù)據(jù)匹配問題

看到這里，我們又更近一步了，可以判斷兩個文本是否相似了，但是網(wǎng)頁去重是面對海量數(shù)據(jù)的，我們?nèi)绾螌Ρ人袛?shù)據(jù)確定相似呢？

假如庫存10億條數(shù)據(jù)的simhash值，每新來一個文本生成simhash值之后就要對庫存10億數(shù)據(jù)進(jìn)行O(n)遍歷嗎？

這個時間消耗有些大，為此我們需要進(jìn)行一些工程加速，理論才能在工程中展示威力。

7.1 暴力破解思路

先看下暴力方法是如何實(shí)現(xiàn)的呢？我們不知道3位以內(nèi)的變化究竟會是哪些，所以這是個非精確匹配問題，計(jì)算機(jī)是無法像人一樣去模糊思考的，從兩個角度去分析暴力破解的情況：

• 生成64bit哈希值的3位以內(nèi)的變化組合
  這是個排列組合問題，相當(dāng)于從64bit中挑選3bit及其以內(nèi)數(shù)據(jù)作為突變點(diǎn)，此種情況生成組合總共有43744種組合，看個圖：

• 存儲時生成每個原始simhash值的所有3位內(nèi)的變化組合
  也就是說存儲1個simhash要輔助存儲43744個組合變化，空間大了4.37w倍，仿佛聽到心在顫抖…

暴力破解就是典型的空間換時間，在數(shù)據(jù)量不大且不會持續(xù)增長時還好，對于海量數(shù)據(jù)無法接受，所以還得繼續(xù)想辦法！

7.2 鴿巢原理

高中在做概率題目的時候經(jīng)常有這種場景：問yyy事件的概率是多少？

一般對于這種問題正面求解的計(jì)算量會比較龐大，大的計(jì)算量也意味著出錯，所以常用的套路是轉(zhuǎn)換為其對立面xxx事件的概率，然后1-xxx事件的概率就是yyy的概率，然而xxx事件的概率比較好計(jì)算，采用對立迂回的戰(zhàn)術(shù)同樣解決了問題。

再看看我們的simhash相似判定的問題，之前一直關(guān)注于有至少有61位相同，現(xiàn)在轉(zhuǎn)換為看最多有3位不同要怎么分布，或許有驚喜！

考慮一個問題：假如現(xiàn)在有3只鴿子，給你4個鴿子窩，每個鴿子窩可以有任意只鴿子，所以放鴿子的時候會出現(xiàn)什么情況呢？思考3分鐘......

答案：無論怎么放最少會有1個鴿子窩是空的。

將鴿巢原理遷移到simhash相似度問題上來看，假如我們把64bit的哈希值均分為4份(鴿子窩)，那么兩文本相似假如有3位不一樣(3只鴿子)，那么也必然最少有一份16bit長度是完全一樣的(最少有1個鴿子窩是空的)。

將鴿巢原理應(yīng)用到simhash去重問題

我們在存儲時將64bit哈希值平均分為4份每份16bit長，然后使用每一份作為key，value是64bit哈希值數(shù)組，原來是單個哈希值存儲，彼此沒有關(guān)系，現(xiàn)在每個哈希值都劃分為4份，由整體存儲轉(zhuǎn)換為分散復(fù)用存儲，復(fù)用的就是劃分的key，從概率上來說超過2^16個數(shù)據(jù)集后必然存在key的相同數(shù)據(jù)，再貼一張筆者畫的圖：

value可以有其他形式，但是類型是個列表，因?yàn)闀泻芏鄶?shù)據(jù)的某16bit的key是一樣的，對應(yīng)的value中v1...vn就是其4等份中的某一份與當(dāng)前key相同。

7.3 鴿巢原理應(yīng)用詳細(xì)說明

在圖中對于一個64bit的哈希值S均分為16位長度四個部分ABCD，在存儲時分別以ABCD為key進(jìn)行存儲，如果當(dāng)前key已經(jīng)存在，那么就將S追加到key對應(yīng)的value列表中，也就是說value中存儲的都是四等份中存在key的哈希值。

當(dāng)新來一個文本生成哈希值S'之后，按照相同的規(guī)則生成abcd四部分，之后逐個進(jìn)行哈希對比，這個時間復(fù)雜度是O(1)：

• 如果abcd四個作為key都不存在，那么可以認(rèn)為S'沒有相似的文本；
• 如果abcd四個key中有命中，那么就開始遍歷對應(yīng)key的value，查看是否滿足<=3的漢明距離確定相似性；
• 如果上一個命中的key未找到相似文本，則繼續(xù)遍歷剩下的key，重復(fù)相同的過程，直至所有的key全部遍歷完或者命中相似文本，則結(jié)束。

以庫存10億數(shù)據(jù)為例復(fù)雜度分析
10億數(shù)據(jù)大約是2^30，key的長度為16bit，由于數(shù)據(jù)量比較大所以理論上key分布均勻，存儲中約有2^16(65536)個key，肯定不會多于65536的。

每個key對應(yīng)value的list長度最大是(2^14)*4=65546個，因?yàn)閗ey在哈希值中的位置可能是1/2/3/4，這樣理論上第1位是key的數(shù)量是2^30/2^16=2^14，同理第2/3/4位置上也是這樣的，所以value最大長度是(2^14)*4。

最壞情況待匹配哈數(shù)值S'的四個key，ABCD均命中了但是依次遍歷之后都相似度判斷失敗了，這種情況的理論最大匹配次數(shù)是4*65536=262144次。

8.一些工程實(shí)踐優(yōu)化

前面重點(diǎn)闡述了simhash的原理和網(wǎng)頁去重應(yīng)用過程，實(shí)際中很多新聞類文章的時效性區(qū)分比較明顯，比如2019年12月20號的文章跟2018年12月20號的文章相似的概率很低，這種場景下存儲海量數(shù)據(jù)可能產(chǎn)生浪費(fèi)，因?yàn)榇蟛糠謹(jǐn)?shù)據(jù)都是不相似的，所以在實(shí)際使用中旨在理解simhash的核心思想，然后采用適合自己的判重和聚類算法。

一般來說進(jìn)行判重和聚類離不開分詞，在實(shí)踐中筆者使用JieBa分詞的C++版本封裝了一個分詞服務(wù)，支持批量和多種分詞方式，不過結(jié)巴的詞庫貌似是使用人民日報的語料訓(xùn)練的tf-idf，并不適用所有場景，所以可能要建立了自己的tf-idf表，實(shí)際效果比默認(rèn)的tf-idf好一些。

沒有萬能的方法 只有萬能的思想。

掌握核心要點(diǎn)就可以自己展開設(shè)計(jì)調(diào)整，效果不一定比網(wǎng)上那些成功范例差甚至更好，這也是學(xué)習(xí)和實(shí)踐的樂趣吧！

9.巨人的肩膀

• https://zhuanlan.zhihu.com/p/55372480
• https://wizardforcel.gitbooks.io/the-art-of-programming-by-july/content/06.03.html
• https://cloud.tencent.com/developer/article/1189493
• https://www2007.org/papers/paper215.pdf