童學(xué)杰 彭緒富

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

關(guān)鍵詞：局部敏感；哈希；LSH；Simhash；相似度；查重

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）10-0162-02

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

1 前言

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

2 分詞降噪

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

使用統(tǒng)計(jì)模型的公式如下：

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

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

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

其中，P（W1）表示第一個(gè)詞W1出現(xiàn)的概率，P（W2|W1）是在已知第一個(gè)詞的前提下，第二個(gè)詞出現(xiàn)的概率，后續(xù)依此類推。復(fù)雜的分詞問題便可以簡(jiǎn)單化。

降噪。在輸入的文本中，并不一定是所有的詞或者字都對(duì)將要進(jìn)行的比較有正面作用，比如“的”“地”“得”等和一些副詞，這些詞語(yǔ)對(duì)于理解文本意義會(huì)產(chǎn)生負(fù)面影響，所以應(yīng)當(dāng)去掉。該過程被稱為降噪。這時(shí)候我們就需要有夾雜著噪音和錯(cuò)誤的語(yǔ)料文本，且該語(yǔ)料必須是領(lǐng)域內(nèi)的，比如搜索的語(yǔ)料應(yīng)該使用網(wǎng)頁(yè)的數(shù)據(jù)，而不是各類規(guī)范的日?qǐng)?bào)期刊文章等。

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

3 生成加權(quán)數(shù)字串

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

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

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

再比如，特征詞“哈希值”的權(quán)值為4，散列值為00101010，那么計(jì)算加權(quán)數(shù)字串的過程如下：

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

4 降維

合并所有特征詞語(yǔ)。帶運(yùn)算符號(hào)累加所有特征詞語(yǔ)對(duì)應(yīng)位的權(quán)值，形成新的數(shù)字串。假設(shè)有哈希值H1和H2，權(quán)值W1和W2，其數(shù)字串如下：

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運(yùn)算，第二位W1和第二位W2運(yùn)算，注意所有運(yùn)算必須帶上符號(hào)，依次類推。最后得到一個(gè)8位（本例假設(shè)是8位）的二進(jìn)制數(shù)值，結(jié)果如下：

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）

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

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

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

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

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

01011001

5 計(jì)算相似度

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

C1：0 1 0 1 0 0 1 1

C2：0 0 0 1 0 1 0 1

其中，C1與C2對(duì)應(yīng)位不一致的地方使用黑色粗體標(biāo)識(shí)出來(lái)。通過比較不難發(fā)現(xiàn)兩者共有3處不一致，所以C1與C2的碼距為3，即海明距離為3。

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

6 結(jié)語(yǔ)

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

參考文獻(xiàn)：

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

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

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

[4] 周志華.機(jī)器學(xué)習(xí)[M]. 北京：清華大學(xué)出版社，2016：60-66.

【通聯(lián)編輯：代影】