局部敏感哈希算法的內容相似度比較

童學杰 彭緒富

摘要：局部敏感哈希（Locality Sensitive Hashing，LSH）算法，又稱局部敏感散列算法，顧名思義，該算法產生的散列值是局部敏感的。對原始內容做微小的修改后，經過LSH算法生成的散列值的變化也是微小的，因此LSH生成的散列值是局部敏感的。這一特性可以運用在論文查重、網頁比較、文本比較等需要比較內容相似度的場景上。該文著重研究LSH在文本比較上的實現（Simhash算法）。首先，對給定的文本做分詞降噪和加權處理得到帶權重的具有給定文本特征的詞語，其次，使用哈希算法為每個詞語生成對應的哈希值并根據各自的權重形成加權數字串，然后合并所有詞語并降維，最后，通過使用海明距離（Hamming Distance）計算生成的兩個Simhash的相似度。

關鍵詞：局部敏感；哈希；LSH；Simhash；相似度；查重

中圖分類號：TP311 文獻標識碼：A

文章編號：1009-3044（2019）10-0162-02

開放科學（資源服務）標識碼（OSID）：

1 前言

在做數據分析時，我們常常需要比較兩組或多組給定內容之間的差異或者說是相似度的大小。傳統的內容比較是直接使用輸入的字符串做對比，該方法雖然實現起來十分簡單，但是效率極低，無法大規模用于工業生成。相比之下，采用最長公共子序列（Longest Common Subsequence）算法可以達到更好的效果，使用動態規劃計算得到編輯距離（levenshtein distance），即兩個字符串的相似程度，生物學家可以根據該算法對比DNA的相似度來輔助生物工程研究，但是該算法不能較好的使用在大文本的檢索和比較上。通過設計一種特殊性質的算法，即局部敏感哈希算法，可以解決這一問題，并且提高相似度查詢的效率。LSH被廣泛應用于文本、超媒體等檢索領域。

2 分詞降噪

分詞。所謂的分詞主要涉及的是中文（其他亞洲語言比如韓文、日文等也適用），不過拼音語言（比如英語、法語等）的手寫體由于分隔不明顯，也會導致類似分詞的問題，雖然語種不同，但是分詞的思想卻是一致的。分詞在語音識別和翻譯等領域應用也十分廣泛。近年來，中文分詞已經突破了語法語義規則的限制，不再使用傳統的基于規則的方法，而是使用統計語言模型來進行自然語言處理。由于基于規則的方法存在嚴重的性能問題和十分復雜的語義分析，且準確率比較低（大概在70%）等缺陷，其很快被數學中的統計模型代替，該模型不僅具有較高的性能，更重要的是準確率可以達到90%，這是基于規則的方法問世十幾年卻無法達到的水平。

使用統計模型的公式如下：

P（S）=P（W1，W2，…，Wn） （2.1）

其中，S表示一段子序列，P（S）則表示S在文本（W1，W2，…，Wn）中出現的概率。展開后表示如下：

P（W1，W2，W3，…，Wn）=P（W1）﹒P（W2|W1）﹒P（W3|W1，W2）…P（Wn|W1，W2，…，Wn-1） （2.2）

其中，P（W1）表示第一個詞W1出現的概率，P（W2|W1）是在已知第一個詞的前提下，第二個詞出現的概率，后續依此類推。復雜的分詞問題便可以簡單化。

降噪。在輸入的文本中，并不一定是所有的詞或者字都對將要進行的比較有正面作用，比如“的”“地”“得”等和一些副詞，這些詞語對于理解文本意義會產生負面影響，所以應當去掉。該過程被稱為降噪。這時候我們就需要有夾雜著噪音和錯誤的語料文本，且該語料必須是領域內的，比如搜索的語料應該使用網頁的數據，而不是各類規范的日報期刊文章等。

得到具有給定文本特征的帶權詞語。一般需要表達一篇文章的中心思想時，可能會使用該文章特有的詞匯。這些“特有的”詞匯就是計算內容相似度的重要依據。通常情況下，應當給文本特有的詞語賦權值。比如權值可以從高到低依次為5到1，代表使用該權值的詞語在文本中的重要程度，即表達思想的核心程度。如果兩篇文章的用詞和權值吻合程度比較高，那么就可以肯定這兩篇文章的相似度較高。這也是論文查重使用的基本思想。但是僅僅使用這些方法還是遠遠不夠的，譬如：如何快速的比較兩段文本？如何確定文本是否相似？計算相似度的依據是什么？這就需要數字化，即把難以處理的文本轉換為容易計算的數字。

3 生成加權數字串

為每個詞語生成對應的哈希（散列）值。即將給定的特征詞語轉換為哈希值，并使用生成的哈希值代替原始詞語。原始詞被映射為較短（比如8位）的固定長度的二進制數值，該值就是我們后續需要計算的哈希值，它是給定的文本特征詞語唯一的且十分緊湊的數值表現形式。使用散列函數可以將給定的文本的特征詞完整的轉化（壓縮）成摘要，使得數據量顯著減少，并且將數據的格式固定為數字存儲，即數字化。計算機對于數字的運算速度要遠遠高于字符串，因此，數字化不僅方便計算相似度，而且也大大提升了計算能力，是解決實際問題和轉化模型最常用的方法。

根據各自散列值計算權重并生成加權數字串。權值指的是該特征詞在給定的內容中的重要程度，一般權值越大，說明該特征詞越重要。權值的確定需要強大的語料和訓練，因此，可能同一個應用采用同樣的算法，但是如果訓練的模型不一樣，監督的方式不一樣則會導致得到結果的差異非常巨大。比如同一個特征詞（Words）在應用A1中的權值為5，記作[Words，5]，但是在另一個應用A2中的權值可能是1，記作[Words，1]，顯然該特征詞在應用A1中要比A2重要。在計算加權數字串時，按照0為負，1為正來計算權值。假設權值為W，散列值等于1時記作+W，散列值等于0時記作-W。由此計算出一個由+W和-W組成的數字串。例如特征詞語“散列值”的權值為5，散列值為01011001（假設壓縮后的位數是8位），那么計算加權數字串的過程如下：

-5 +5 -5 +5 +5 -5 -5 +5

再比如，特征詞“哈希值”的權值為4，散列值為00101010，那么計算加權數字串的過程如下：

-4-4+4-4+4-4+4-4

4 降維

合并所有特征詞語。帶運算符號累加所有特征詞語對應位的權值，形成新的數字串。假設有哈希值H1和H2，權值W1和W2，其數字串如下：

H1：-W1 +W1 -W1 +W1 +W1 -W1 -W1 +W1 （4.1）

H2：-W2 -W2 +W2 -W2 +W2 -W2 +W2 -W2 （4.2）

則合并公式如下：

-W1-W2 +W1-W2 -W1+W2 +W1-W2 +W1+W2 -W1-W2 -W1+W2 +W1-W2 （4.3）

即第一位W1和第一位W2運算，第二位W1和第二位W2運算，注意所有運算必須帶上符號，依次類推。最后得到一個8位（本例假設是8位）的二進制數值，結果如下：

W（-W1-W2） W（+W1-W2） W（-W1+W2） W3（+W1-W2） W（+W1+W2） W（-W1-W2） W（-W1+W2） W（+W1-W2） （4.4）

按照上例中“散列值”和“哈希值”生成的數字串得到如下計算過程：

-5-4 +5-4 -5+4 +5-4 +5+4 -5-4 -5+4 +5-4

由上述過程可得出新的數字串如下所示：

-9+1-1+1+9-9-11

降維。即生成最終的哈希簽名。根據給定的公式計算得到合并后的權值，若W小于或者等于0，則該位記為0，若W大于0，則該位記為1。由此可知“散列值”和“哈希值”生成的二進制串如下所示：

01011001

5 計算相似度

使用海明距離（Hamming Distance）計算相似度。在計算機的信息編碼中，海明距離可以將給定的編碼串進行異或（XOR）運算得到，即給定的兩組編碼對應位上不同的位數稱為碼距，或海明距離。假設有兩組8位的編碼C1和C2，依次對應為：

C1：0 1 0 1 0 0 1 1

C2：0 0 0 1 0 1 0 1

其中，C1與C2對應位不一致的地方使用黑色粗體標識出來。通過比較不難發現兩者共有3處不一致，所以C1與C2的碼距為3，即海明距離為3。

海明距離可以表示兩組編碼之間的差異，常被用于編碼的檢錯和糾錯等，也可表示兩組編碼的相似度。假設C1是我們前面提到的特征詞“哈希值”的編碼，而C2是特征詞“散列值”的編碼，那么C1與C2的海明距離則是“哈希值”與“散列值”之間的距離，即兩個特征詞之間的相似距離。由此，兩個中文特征詞之間的相似度關系便轉化成了兩個二進制編碼的碼距問題。碼距越大，說明兩者距離越遠，相似度越低。如果我們比較的是兩篇文章，那么很容易就可以得到兩篇文章的相似度，從而可以輔助判斷作者是否在文章內使用了過多的引用，甚至是否有抄襲的嫌疑。

6 結語

以局部敏感哈希算法為核心的字符比較算法，利用海明距離計算碼長，實現給定兩組或多組內容的相似度計算。由于LSH是基于權值空間的算法，因此，在計算之前必須要得到給定特征詞的權值，這就涉及了分詞和加權，目前被廣為接受的分詞方法是基于數學中的統計語言模型，加權的難點在于如何確定給定特征詞的權值，得到特征詞和對應的權值后使用合并降維等方法最終生成給定內容的Simhash。

參考文獻：

[1] 吳軍.數學之美[M].北京：人民郵電出版社，2014：41-45.

[2] AdityaBhargava. 算法圖解[M].北京：人民郵電出版社，2017：178-179.

[3] Richard E.Neapolitan. FoundationsofAlgorithms[M].北京：人民郵電出版社，2016：66-67.

[4] 周志華.機器學習[M]. 北京：清華大學出版社，2016：60-66.

【通聯編輯：代影】