微信的原創(chuàng)保護(hù)機(jī)制，太牛逼了！
前言
眾所周知，目前微信公眾號(hào)是最具商業(yè)價(jià)值的寫作平臺(tái)，這與它優(yōu)秀的原創(chuàng)保護(hù)機(jī)制密不可分，如果你想將其他公眾號(hào)上的文章標(biāo)為原創(chuàng)，微信會(huì)給出類似如下的信息告訴你未通過(guò)原創(chuàng)校驗(yàn)邏輯。
如果你抓包會(huì)發(fā)現(xiàn)微信返回了如下錯(cuò)誤
如果你想改幾個(gè)字蒙混過(guò)關(guān)，對(duì)不起，不行！依然會(huì)報(bào)上述錯(cuò)誤，這得益于微信原創(chuàng)檢測(cè)機(jī)制所采用的 simhash 技術(shù)，它是 Google 為了解決大規(guī)模的網(wǎng)頁(yè)去重而發(fā)明的算法，廣泛用在大規(guī)模的文章，評(píng)論判重等地方，效率極高，那么這項(xiàng)技術(shù)是如何實(shí)現(xiàn)的呢，通過(guò)上面的錯(cuò)誤信息不難發(fā)現(xiàn)微信是為每篇文章生成了一個(gè)指紋（fingerprint），最終文章相似性的比較其實(shí)是指紋的比較，那么這個(gè)指紋又是如何生成的呢，本文將會(huì)為你由淺入深地揭曉 simhash 的秘密。
本文的目錄結(jié)構(gòu)如下：
傳統(tǒng) Hash 與其局限性 余弦定理實(shí)現(xiàn)及其局限性 基于隨機(jī)投影來(lái)實(shí)現(xiàn)空間向量的降維 simhash 原理及實(shí)現(xiàn)
傳統(tǒng) Hash 與其局限性
如何比較兩篇文章是否相同，相信大家不難想到以下步驟
通過(guò)一個(gè) Hash 函數(shù)（MD5 等）將文章轉(zhuǎn)成定長(zhǎng)字符串，比如 32 位 比較上一步生成的定長(zhǎng)字符串是否相等
第一步的主要作用是將大范圍映射到小范圍，這樣使用小范圍的定長(zhǎng)字符串「一般我們把它稱為指紋（fingerprint）」大大縮小了空間，更利于保存，并且更利于比較，但對(duì)于計(jì)算兩篇文章的相似度傳統(tǒng) hash 就無(wú)能為力了，因?yàn)閷?duì)于傳統(tǒng) hash 來(lái)說(shuō)，它要求隨機(jī)性足夠好，也就是說(shuō)對(duì)于兩個(gè)輸入字符串，哪怕只有一個(gè)字母不同，使用傳統(tǒng) hash 的輸出結(jié)果也是大不相同。
如圖示，以 SHA1為例，兩個(gè)字符串「我是中國(guó)人」與「我是中國(guó)人啊」只相差了一個(gè)字，但輸出的結(jié)果完全不同，根本沒(méi)法比較，退一步來(lái)說(shuō)，就算要比較，每個(gè) hash 結(jié)果也要一個(gè)字符一個(gè)字符的比，性能極差！
所以我們需要找到這樣的一個(gè) hash 函數(shù)，它需要滿足兩個(gè)條件
可以實(shí)現(xiàn)局部相似性 生成的 hash 結(jié)果利于比較
先來(lái)看第二點(diǎn)，要讓 hash 結(jié)果利于比較，可以將結(jié)果轉(zhuǎn)化為僅由 0，1組成的定長(zhǎng)二進(jìn)制數(shù)字，這樣只要將結(jié)果進(jìn)行異或運(yùn)算，算出結(jié)果有幾位 1 即可，simhash 就是這么做的
如圖示：將結(jié)果進(jìn)行異或運(yùn)算后只有兩位為 1，即只有兩位是不一樣的
接下來(lái)我們?cè)賮?lái)看第一個(gè)問(wèn)題，simhash 如何輸出局部相似性的結(jié)果， 它的計(jì)算過(guò)程與利用余弦定理來(lái)計(jì)算文本相似度有一定的相似性，可以認(rèn)為是余弦定理的一個(gè)演變，所以我們先來(lái)看看如何用余弦定理來(lái)計(jì)算兩者的相似度
余弦定理
第一次聽說(shuō)余弦定理是在吳軍的<<數(shù)學(xué)之美>>里看到的，通過(guò)余弦可以判斷兩篇文章是否相似，步驟都是類似的，將文章轉(zhuǎn)化為 n 個(gè)維度的空間向量，再計(jì)算這兩個(gè)空間向量的在空間中的夾角，我們以下兩個(gè)文本為例來(lái)看看如何利用余弦定理來(lái)計(jì)算這兩個(gè)文本的相似度（本例子來(lái)自阮一峰博客）
句子A：我喜歡看電視，不喜歡看電影。
句子B：我不喜歡看電視，也不喜歡看電影。
步驟一：分詞
句子A：我/喜歡/看/電視，不/喜歡/看/電影。
句子B：我/不/喜歡/看/電視，也/不/喜歡/看/電影。
第二步，列出所有的關(guān)鍵詞。
我，喜歡，看，電視，電影，不，也。
畫外音：使用 TF-IDF 算法來(lái)算出所有的關(guān)鍵詞，像 「的」,「地」，「得」這種無(wú)意義的頓詞需要去掉
第三步，計(jì)算詞頻。
句子A：我 1，喜歡 2，看 2，電視 1，電影 1，不 1，也 0。
句子B：我 1，喜歡 2，看 2，電視 1，電影 1，不 2，也 1。
第四步，寫出詞頻向量。
句子A：[1, 2, 2, 1, 1, 1, 0]
句子B：[1, 2, 2, 1, 1, 2, 1]
注：這里為了演示方便簡(jiǎn)單用出現(xiàn)的次數(shù)來(lái)作為詞頻向量，實(shí)際上生產(chǎn)上一般不會(huì)這么干，一般會(huì)利用 TF-IDF 算法來(lái)生成詞頻向量，本文不作展開，感興趣的讀者可以自行研究
于是問(wèn)題表現(xiàn)為了如何在空間中計(jì)算這兩個(gè)向量的相似度了，我們可以把這兩個(gè)向量認(rèn)為是兩條線段，從原點(diǎn)[0, 0, xxx]，指向這兩點(diǎn)的線段，這兩個(gè)線段形成了一個(gè)夾角，夾角越小，說(shuō)明這兩個(gè)向量越相似，如何知道這兩個(gè)夾角的大小呢，計(jì)算它們的余弦值（cosθ）即可，如果值越接近 1， 說(shuō)明 θ 越小，兩個(gè)向量就越接近，文本也就越相似
于是問(wèn)題轉(zhuǎn)化為了如何計(jì)算 cosθ 的值，回憶下大學(xué)的數(shù)據(jù)公式,其值計(jì)算如下
于是我們可以根據(jù)以上公式計(jì)算出句子 A 和句子 B 的 cosθ 值為:
高達(dá) 93.8% 的相似度！這與實(shí)際情況吻合，既然使用余弦定理就可以計(jì)算文章的相似性，那為啥還要搞出 simhash 這樣的算法呢，細(xì)心的朋友不難發(fā)現(xiàn)它的缺點(diǎn)，計(jì)算余弦的過(guò)程涉及到很多的乘法開方等計(jì)算，n 個(gè)分詞最終轉(zhuǎn)化后就是 n 維向量，一篇文章的分詞是非常多的，也就意味著這個(gè) n 是非常大的，所以計(jì)算余弦是非常耗時(shí)的，肯定無(wú)法應(yīng)用于 Google 這樣需要海量網(wǎng)頁(yè)判重的場(chǎng)景。
由此分析可知余弘定理計(jì)算主要性能瓶頸在于文章轉(zhuǎn)化后的高維度向量，高維度所需的計(jì)算量較復(fù)雜，那能否考慮降維呢，即把 n 維降低到 k 維（k 遠(yuǎn)小于 n）甚至是一維，維度越小，計(jì)算量就越小，接下來(lái)我們就來(lái)看看如何利用隨機(jī)投影實(shí)現(xiàn)數(shù)據(jù)降維。
基于隨機(jī)投影來(lái)實(shí)現(xiàn)空間向量的降維
向量點(diǎn)積含義
隨機(jī)投影的基礎(chǔ)方法，是向量點(diǎn)積運(yùn)算。所以理解隨機(jī)投影的基礎(chǔ)，是理解向量點(diǎn)積運(yùn)算的含義。
設(shè)二維空間內(nèi)有兩個(gè)向量，則其點(diǎn)積（也叫內(nèi)積）定義為以下實(shí)數(shù)：
點(diǎn)積運(yùn)算
表示的是兩個(gè)投影積，一個(gè)是
在 上的投影長(zhǎng)度:
一個(gè)是 OB 在其本身的投影長(zhǎng)則為 |OB|，
如果我們把
看作是新空間的坐標(biāo)軸，那么點(diǎn) A 在新空間的坐標(biāo)是
假設(shè)有如下兩個(gè)向量
那么點(diǎn) A 以向量
所在直線為坐標(biāo)軸的空間中，坐標(biāo)為 a.b=7*1+3* (-1)=4，發(fā)現(xiàn)了嗎，此時(shí)點(diǎn) A 在新空間中的坐標(biāo)由 2 維降到了 1 維，實(shí)際上向量點(diǎn)積不光可以實(shí)現(xiàn)二維降一維，也可以實(shí)現(xiàn)從 M 維降到 K 維。只要基于高斯分布（即正態(tài)分布），在原向量空間中找到一個(gè) k 維向量
就可以讓原來(lái)任意一個(gè)在 M 維空間的向量 M 通過(guò)點(diǎn)積 M ? R 將其降維到 K 維，Johnson–Lindenstrauss 引理指出：在歐式空間中的若干點(diǎn)，經(jīng)過(guò)相同的映射后進(jìn)入新的空間，它們?nèi)匀粫?huì)保持原來(lái)的相對(duì)位置，也就是說(shuō)原來(lái)向量之間的夾角在向量降維映射到新空間后依然可以認(rèn)為基本不變，這也就意味著降維后不會(huì)對(duì)文本的相似度計(jì)算產(chǎn)生影響。
隨機(jī)投影降維離散化----基于隨機(jī)投影的局部敏感哈希
通過(guò)隨機(jī)投影法，確實(shí)實(shí)現(xiàn)了高維度降到低維度的目標(biāo)，但降維后生成的向量坐標(biāo)很可能是 float 型的，不利于存儲(chǔ)，而且在計(jì)算比如余弦時(shí)，需要 float * float 的計(jì)算，我們知道浮點(diǎn)型計(jì)算是比較耗性能的，所以有人就提出能否對(duì)這些 float 的連續(xù)型坐標(biāo)離散化，這樣就解決了存儲(chǔ)，計(jì)算的難點(diǎn)。
在將數(shù)據(jù)映射到降維后的新空間后，我們將落在坐標(biāo)軸負(fù)軸的維度(該維度取值為負(fù)數(shù))，統(tǒng)一賦值為 0（或者 -1，使用 -1 的話 是將映射后的詞語(yǔ)放置在整個(gè)空間中，而不是某一個(gè)象限，這樣可以讓數(shù)據(jù)點(diǎn)分布得更均勻一點(diǎn)），表示數(shù)據(jù)與對(duì)應(yīng)隨機(jī)向量夾角大于 90 度。類似的，我們將落在坐標(biāo)軸非負(fù)軸的維度，統(tǒng)一賦值為 1。這樣原始數(shù)據(jù)就被映射到了一個(gè)離散的新空間里。
這種離散化的數(shù)據(jù)映射方法，就是我們常說(shuō)的基于隨機(jī)投影的局部敏感哈希，經(jīng)過(guò)離散化后，原來(lái)在空間中接近的數(shù)據(jù)點(diǎn)依然是相似或相同的，更重要的是經(jīng)過(guò)離散化后轉(zhuǎn)化為了 0，1 二進(jìn)制數(shù)字，計(jì)算速度大大提高！
基于隨機(jī)投影的局部敏感哈希，也是隨機(jī)投影 hash 的一種，通過(guò)上述映射規(guī)則，將原空間向量進(jìn)行了離散化降維
隨機(jī)超平面 hash
知道了什么是基于隨機(jī)投影的局部敏感哈希, 也就不難理解隨機(jī)超平面 hash 了，它也是隨機(jī)投影 hash 離散化的變種，對(duì)于一個(gè) n 維向量 v，如果要得到一個(gè)由 0，1 組成的 f 位簽名（f 遠(yuǎn)小于 n），它的算法如下：
隨機(jī)產(chǎn)生 f 個(gè) n 維的向量 r1,…rf； 對(duì)每一個(gè)向量 ri，如果 v 與 ri 的點(diǎn)積大于 0（說(shuō)明在此向量劃分的空間是相似的），則最終簽名的第 i 位為 1，否則為 0。
這個(gè)算法相當(dāng)于隨機(jī)產(chǎn)生了 f 個(gè) n 維超平面，每個(gè)超平面將向量 v 所在的空間一分為二，v 在這個(gè)超平面上方則得到一個(gè) 1，否則得到一個(gè) 0，然后將得到的 f 個(gè) 0 或 1 組合起來(lái)成為一個(gè) f 維的簽名
如圖所示，隨機(jī)在空間里劃幾個(gè)超平面，就可以把數(shù)據(jù)分到不同空間里，比如中間這個(gè)小三角的區(qū)域就可以賦值為110
每個(gè)降維后的 f 維簽名，就是文章的最終簽名！通過(guò)這樣的解釋相信大家不難理解通過(guò)異或比較位數(shù)的不同來(lái)判斷文章的相似度的幾何意義：位數(shù)不同，代表其在相應(yīng)超平面上不相似
simhash 原理及實(shí)現(xiàn)
為啥前面花這么大力氣介紹引出隨機(jī)超平面 hash 呢，因?yàn)?simhash 就是基于超平面 hash 演變而來(lái)的，可以說(shuō)理解了超平面 hash 也就理解了 simhash，接下來(lái)我們看看 simhash 的生成流程:
simhash 的生成劃分為五個(gè)步驟：分詞->hash->加權(quán)->合并->降維
分詞: 這一步可以余弦定理的 1~4 步類似，首先，判斷文本分詞，形成這個(gè)文章的特征單詞。然后，形成去掉噪音詞的單詞序列。最后，為每個(gè)分詞加上權(quán)重。我們假設(shè)權(quán)重分為5個(gè)級(jí)別（1~5），比如：“ 美國(guó)“51區(qū)”雇員稱內(nèi)部有9架飛碟，曾看見灰色外星人 ” ==> 分詞后為 “ 美國(guó)（4） 51區(qū)（5） 雇員（3） 稱（1） 內(nèi)部（2） 有（1） 9架（3） 飛碟（5） 曾（1） 看見（3） 灰色（4） 外星人（5）”，括號(hào)里是代表單詞在整個(gè)句子里重要程度，數(shù)字越大越重要，為了方便解釋，以下我們假設(shè)文檔只有「美國(guó)」和「51區(qū)」這兩個(gè)分詞。
hash: 通過(guò) hash 算法把每個(gè)詞變成 hash 值，比如“美國(guó)”通過(guò) hash 算法計(jì)算為 100101，“51區(qū)”通過(guò) hash 算法計(jì)算為 101011。這樣，我們的字符串就變成了一串串?dāng)?shù)字，此 hash 值我們稱為這些詞對(duì)應(yīng)的獨(dú)熱編碼，然后再將 0 轉(zhuǎn)為 -1，這樣美國(guó)的「100101」編碼為了「1-1-11-11」，51區(qū)的編碼為「1-11-111」，將 0 轉(zhuǎn)為 -1 的目的是將映射后的詞語(yǔ)放置在整個(gè)空間中，而不是某一個(gè)象限，這樣可以讓數(shù)據(jù)點(diǎn)分布得更均勻一點(diǎn)，與隨機(jī)超平面hash相比，這里使用了一個(gè)“不隨機(jī)”的超平面，將空間進(jìn)行了分割。
加權(quán): 通過(guò) 2 步驟的 hash 生成結(jié)果，需要按照單詞的權(quán)重形成加權(quán)數(shù)字串，比如「美國(guó)」的hash值為「1-1-11-11」，通過(guò)加權(quán)（權(quán)重參見步驟一得出的各個(gè)詞語(yǔ)的權(quán)重值）計(jì)算（相乘）為「4 -4 -4 4 -4 4」；「51區(qū)」的 hash 值為「1-11-111」，通過(guò)加權(quán)計(jì)算為 「5 -5 5 -5 5 5」，得到的各向量即表征了這個(gè)文檔
合并: 把上面各個(gè)單詞算出來(lái)的序列值累加，變成只有一個(gè)序列串。比如 “美國(guó)”的 “4 -4 -4 4 -4 4”，“51區(qū)”的 “ 5 -5 5 -5 5 5”， 把每一位進(jìn)行累加， “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。
降維: 把第 4 步算出來(lái)的 「9 -9 1 -1 1 9」變成 0 1 串，形成我們最終的 simhash 簽名。如果每一位大于 0 記為 1，小于 0 記為 0。最后算出結(jié)果為：「1 0 1 0 1 1」，這里采用了隨機(jī)超平面 hash 的離散化方法，得到文本的最終表示
相信細(xì)心的你不難發(fā)現(xiàn)在第二步和第五步可以看到隨機(jī)超平面的身影，也就是說(shuō)并沒(méi)有產(chǎn)生直接的隨機(jī)超平面向量來(lái)映射，是間接產(chǎn)生的，如果想找到直接的超平面向量 R 來(lái)生成最后的簽名也不難，我們就假設(shè)文檔只有「美國(guó)」,「51區(qū)」這兩個(gè)特征詞，由第一，二步可知其文檔向量為 d = (4, 5)，hash 后的編碼為 100101，101011，我們注意到第二步hash會(huì)做一層編碼轉(zhuǎn)換， 1 不變， 0 轉(zhuǎn)為 -1
100101 ----> 1-1-11-11
101011 ----> 1-11-111
再用逗號(hào)隔開，使其成為了特征詞對(duì)應(yīng)的映射向量
「美國(guó)」對(duì)應(yīng)的映射向量：(1, -1, -1, 1, -1, 1)
「51區(qū)」對(duì)應(yīng)的映射向量：(1, -1, 1, -1, 1, 1)
再把上述每個(gè)特征詞對(duì)應(yīng)向量的第 i 位取出來(lái)組成 ri 向量，如下
r1 = (1, 1), r2 = (-1, -1), r3 = (-1, 1), r4 = (1, -1), r5 = (-1, 1), r6 = (1, 1)
再回顧下隨機(jī) hash 超平面算法的第二步:
對(duì)每一個(gè)向量 ri，如果 v 與 ri 的點(diǎn)積大于 0，則最終簽名的第 i 位為 1，否則為 0。
將文檔向量 d = (4, 5) 與上述 r1...r5 每一個(gè)向量相乘，可得結(jié)果為
（9, -9, 1, -1, 1, 9） ----> (1 , 0, 1, 0, 1, 1)
與 simhash 生成的完全一致！所以我們說(shuō) simhash 是從超平面 hash 算法演變更來(lái)的。
一般 simhash 生成的簽名為 64 位，只要兩個(gè)簽名不同的位數(shù)少于等于 3 位我們就認(rèn)為兩個(gè)文章相似，這種使用不同進(jìn)制位個(gè)數(shù)來(lái)計(jì)算兩者差異的方式我們也叫漢明距離。
simhash 查詢優(yōu)化
生成了 64 位的簽名，然后就通過(guò)計(jì)算簽名的異或來(lái)查詢文章的相似度嗎？too young too naive! 對(duì)于 Google 網(wǎng)頁(yè)去重來(lái)說(shuō)，可能會(huì)有幾十億的網(wǎng)頁(yè)內(nèi)容，那每次判重都需要使用簽名進(jìn)行幾十億的異或比較，這誰(shuí)頂?shù)米“?，那該如何?yōu)化呢？答案是利用抽屜原理進(jìn)行優(yōu)化存儲(chǔ)。
什么是抽屜原理？把三個(gè)蘋果放進(jìn)四個(gè)抽屜里，必然有一個(gè)是空的
我們注意到判斷文章相似的條件 ，對(duì)于簽名為 64 位的 simhash 簽名，只要位數(shù)少于等于 3 位即可判斷為相似，這樣的話我們可以把 64 位的簽名分成四份，每份 16 位，如果相似，那必然有一份是完全相同的。
我們可以把簽名用 K-V 的形式進(jìn)行存儲(chǔ)， K 為其中的一部分，V 為剩余的 3 部分，先比較 K 是否精確匹配相同，如果匹配，再比較 V 部分的相似度，那么這四部分哪一部分應(yīng)該為 K 呢，由于我們不知道哪一部分是精確匹配的，所以每一部分都應(yīng)該為 K，剩余的部分為 V，以文本 1 為例，它應(yīng)該設(shè)計(jì)成如下方式進(jìn)行存儲(chǔ)，這樣保證不會(huì)有遺漏
以下是查詢庫(kù)
那么用這樣的方式來(lái)存儲(chǔ)到底提升了多少速度，我們一起來(lái)算筆帳。
假設(shè)數(shù)據(jù)庫(kù)中有 2^30 條數(shù)據(jù)，也就是差不多 10 億條數(shù)據(jù)：
如果不用抽屜原理，則需要進(jìn)行 10 億次的比較 如果使用抽屜原理 首先先進(jìn)行 K 的比較，由于是 K-V 也就是 hash 存儲(chǔ)，所以 K 比較時(shí)間復(fù)雜度是 0(1)，可以忽略不計(jì)， K 如果精確匹配,把所有對(duì)應(yīng)的 V 取出來(lái)即可，那么 V 可能有多少數(shù)據(jù)？因?yàn)?K 最多可能有 2^16位，所以 V 最多有 2^(30-16) = 2^14 位， 由于最多進(jìn)行 4 次 K 的比較，所以最多會(huì)進(jìn)行 4 * 2^14 = 65536，約 6 萬(wàn)次比較
可以看到利用抽屜原理比較次數(shù)從 10 億次降到了 6 萬(wàn)次！查詢性能大大提升，當(dāng)然了天下沒(méi)有免費(fèi)的午餐，由于數(shù)據(jù)復(fù)制了四份，存儲(chǔ)空間也增大了 4 倍，這就是典型的以空間換時(shí)間。
simhash 缺點(diǎn)
simhash 比較適合海量長(zhǎng)文上，短文本準(zhǔn)確度上不高，因?yàn)橛脕?lái)度量長(zhǎng)文本相似的漢明距離閾值為 3，但是短文本中，相似文本之間的漢明距離通常是大于 3 的。
所以你會(huì)發(fā)現(xiàn)在公眾號(hào)后臺(tái)如果你要標(biāo)原創(chuàng)，字?jǐn)?shù)必須大于 300，也是這個(gè)原因
總結(jié)
理解 simhash 的關(guān)鍵在于理解超平面隨機(jī) hash，使用它可以實(shí)現(xiàn)向量從高維度到低維度的降維。網(wǎng)上有很多講 simhash 的的文章，但大多把降維這個(gè)具體過(guò)程給跳過(guò)了，看得是讓人一頭霧頭，所以筆者查閱了大量資料希望能幫助大家理解這一流程，希望大家能有收獲，如果想對(duì) simhash 有更深入的理解，可以查閱文末一堆的參考鏈接，都非常棒！