1.先嘮個嗑

前面兩周寫了兩期分布式系統一致性相關的問題，按照計劃本周應該是3PC協議了，但是跳票了，因為真的還是挺忙，只能請大家吃回鍋肉了。

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

為啥費勁呢？

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

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

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

廢話不說，直接上車。

和大家重溫一篇19年12月寫的，文本去重相關的文章，為啥選這一篇呢？因為我覺得這一篇還不錯，但是當時訂閱讀者少，曝光不多，新訂閱的讀者就當一篇新文章吧...

通過本文你將了解到以下內容：

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

2. 信息大爆炸

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

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

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

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

3.網頁去重

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

研究表明：互聯網上近似重復的網頁的數量占網頁總數量的比例高達29%，完全相同的網頁大約占網頁總數量的22%。

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

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

這里就引出了今天要講的主要內容simhash算法，本質上文本去重算法有很多種，每種算法都有各自的優(yōu)劣勢，本文并不做橫向對比，而是直接引出simhash算法進行闡述，對于橫向對比感興趣的讀者可以自行查閱相關資料。

4.局部敏感哈希

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

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

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

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

5.SimHash算法及其基本過程

5.1 simhash和谷歌

simhash算法可以將一個文本生成為一個64bit的二進制數，這里提一句simhash算法最初貌似并不是谷歌提出來的，而是谷歌應用推廣的，所以本文出現的simhash相關的數據也都是基于工程中谷歌提出的simhash網頁去重展開的。

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

5.2 64bit的容量

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

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

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

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

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

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

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

5.3 哈希指紋生成過程

我們如何將一個文本轉換為64bit數據呢？

主要步驟：在新拿到文本之后需要先進行分詞，這是因為需要挑出TopN個詞來表征這篇文本，并且分詞的權重不一樣，可以使用相應數據集的tf-idf值作為分詞的權重，這樣就分成了帶權重的分詞結果。

之后對所有分詞進行哈希運算獲取二值化的hash結果，再將權重與哈希值相乘，獲得帶權重的哈希值，最后進行累加以及二值化處理，先不要暈，后面會具體舉例子，看一張圖來大致了解下：

分詞
使用分詞手段將文本分割成關鍵詞的特征向量，分詞方法有很多一般都是實詞，也就是把停用詞等都去掉之后的部分，使用者可以根據自己的需求選擇，假設分割后的特征實詞如下：

12306 服務器 故障 車次 加載失敗 購買 候補訂單 支付 官方 消費者 建議 卸載 重裝 切換網絡 耐心 等待

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

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

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

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

tf-idf加權的各種形式常被搜索引擎應用，作為文件與用戶查詢之間相關程度的度量或評級。

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

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

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

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

12306 10011100
服務器 01110101
故障 00110011
車次 11001010
…

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

12306 10011100 --> 5 -5 -5 5 5 5 -5 -5
服務器 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
…

特征詞帶權重哈希值累加和二值化降維
經過前面的幾步 我們已經將文本轉換為帶權重的哈希值了，接下來將所有的哈希值累加，最后將累加結果二值化，如下：

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

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

6.漢明距離

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

漢明距離

在信息論中，兩個等長字符串之間的漢明距離（英語：Hamming distance）是兩個字符串對應位置的不同字符的個數。換句話說，它就是將一個字符串變換成另外一個字符串所需要替換的字符個數。

漢明重量是字符串相對于同樣長度的零字符串的漢明距離，也就是說，它是字符串中非零的元素個數：對于二進制字符串來說，就是1的個數，所以11101的漢明重量是4。

對于二進制字符串a與b來說，它等于a 異或b后所得二進制字符串中“1”的個數。

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

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

理論發(fā)明者簡介

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

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

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

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

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

本文就不深究漢明距離的數學原理以及證明過程了，直接使用結論，谷歌經過工程驗證認為當兩個64bit的二值化simhash值的漢明距離超過3則認為不相似，所以判重問題就轉換為求兩個哈希值的漢明距離問題。

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

7.海量數據匹配問題

看到這里，我們又更近一步了，可以判斷兩個文本是否相似了，但是網頁去重是面對海量數據的，我們如何對比所有數據確定相似呢？

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

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

7.1 暴力破解思路

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

• 生成64bit哈希值的3位以內的變化組合
  這是個排列組合問題，相當于從64bit中挑選3bit及其以內數據作為突變點，此種情況生成組合總共有43744種組合，看個圖：

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

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

7.2 鴿巢原理

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

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

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

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

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

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

將鴿巢原理應用到simhash去重問題

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

value可以有其他形式，但是類型是個列表，因為會有很多數據的某16bit的key是一樣的，對應的value中v1...vn就是其4等份中的某一份與當前key相同。

7.3 鴿巢原理應用詳細說明

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

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

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

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

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

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

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

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

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

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

掌握核心要點就可以自己展開設計調整，效果不一定比網上那些成功范例差甚至更好，這也是學習和實踐的樂趣吧！

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