基于相似度估計文檔重復率檢測算法研究

王鈺寧，劉曉霞，周紹軍

（四川水利職業技術學院信息工程系,四川崇州,611231）

關鍵字：重復率；相似度；估計；檢測算法

1 當前現狀

Web 信息正經歷著爆炸性增長，海量文檔中存在大量的相似信息，斯坦福大學研究成果表明：近似的網頁數量占總網頁數量的比例為29%，而完全相同的網頁數量大約占總的網頁數目的22%。這些重復網頁大多只在內容上略微修改，有的甚至只是格式不同。這些相似性文檔一方面消耗了高額的檢索資源，另一方面影響了用戶的使用。文檔的數字化和易獲性在提供了更方便的交流學習環境的同時，也使得非法復制、剽竊等行為越來越容易。

文檔的相似性檢測技術從文檔內容的相似程度上判斷文檔是否為有抄襲剽竊的嫌疑。所謂文檔相似性檢測，就是判斷一個文件的內容與另外一個或者多個文件的相似程度，以檢測抄襲剽竊。而剽竊不僅僅意味著對原作原封不動地照抄，還包括對原作的移位變換、同義詞替換以及改變說法重述等方式。文檔相似性檢測技術可以應用在數字化圖書館、搜索引擎、論文查重、基金申請、獎勵評審等很多領域，為用戶減小信息的存儲空間，高速搜索信息，防止論文、基金申請書、項目報獎、專利剽竊和網頁去重提供了很好的解決方案。

文檔相似性檢測的核心內容就是判斷兩篇文本內容是否存在重復成分，并給出一個相似度數值評估。兩篇文檔A 和B的相似度R(A,B),是一個介于0 和1 之間的數。相似度越大，文本重復成分越多。計算文檔相似度，首先需要把文檔用數據模型表示。目前，根據不同的文檔表示方式，可以把目前的主要的文檔相似性檢測方法分為三類：基于詞頻統計的方法[3,4]、基于近似指紋的字符串匹配的算法和基于相似度估計的算法。基于詞頻統計的文檔相似性的檢測方法主要檢測的就是文檔詞頻的相似性。基于字符串比對的文檔相似性檢測方法主要檢測的就是文檔經過分詞處理后的字符串集合的交集大小。基于相似度估計的算法既有檢測文檔詞頻相似性的方法，例如隨機投影。也有檢測字符串集合交集為目標的minwise 相似度估計方法。

基于詞頻統計的方法存在著檢測結果準確率低、誤判率大的缺點。文檔中一些常用詞匯頻率較高，易出現誤差帶來噪聲。并且該方法的向量空間模型的列的維度很大，實際比對時所花費的時間多。基于字符串比對的方法使用簡單，但只能進行簡單的字符串匹配，無法發現復雜的相似性方式的重復文本，比如同義詞替換、改變說法等。同時對于海量數據，該方法需要兩兩文檔的比對，這種方法實際上是不可行的。

2 檢測算法

基于相似度估計的算法一般采用降維的方式，將文檔向量或者字符串集合轉化為k 個指紋的集合，指紋即為固定長度的較短的文檔的字符串，這k 個指紋集合用來表征一篇文檔，從而當求解相似度時，直接比對指紋集合的相似度即可得文檔的相似度。

shingle 算法是最常見的文檔相似性檢測算法。將一個文檔分解成由w 個短字符構成的字符串集合后，一個連續的的子字符串被稱為一個shingle。得到字符串集合后就可以通過Jaccard 相似度等簡單的度量標準進行相似度檢測了。比如，一個文檔

其中S(A)表示集合A的大小。整個抽取過程如圖1所示：

圖1 shingle 算法流程圖

如果是低維的小數據集，我們通過線性查找就可以容易解決，比如使用shingle 算法，但如果是對一個海量的高維數據集采用線性查找匹配的話，會非常耗時。研究者想通過建立Hash Table 的方式我們能夠得到O(1)的查找時間性能，其中關鍵在于選取一個比較好的散列函數，一般的，在對數據集進行hash 的過程中，會發生不同的數據被映射到了同一個桶中（即發生了沖突collision），這一般通過再次哈希將數據映射到其他空桶內來解決。在文本檢測時，相似的內容轉化為數據時會被轉化為相鄰的數據點，但研究者希望原先相鄰的數據點能被映射到同一個桶中，因此需要一個比較好的散列函數。

在shingle 算法的基礎上提出的minwise 哈希方法可以解決該問題。minwise 哈希算法將字符集合的求交集問題轉化為某一事件發生的概率問題。在算法中，不是簡單的對shingle 集合進行計算量較大的比對，而是對每個文檔的shingle 集合進行minwise 散列函數處理，進行降維，然后再計算相似程度。minwise 哈希函數是一類局部敏感散列。

局部敏感散列的基本思想是：將原始數據空間中的兩個相鄰數據點通過相同的映射或投影變換（projection）后，這兩個數據點在新的數據空間中仍然相鄰的概率很大，而不相鄰的數據點被映射到同一個桶的概率很小。如圖2，球q 和球p 相近，被分到一個桶內，它們與粉球和藍球相距較遠，所以沒有被分到一個桶里。

圖2 局部敏感散列示意圖

如果我們能夠找到這樣一些哈希函數，使得經過它們的哈希映射變換后，原始空間中相鄰的數據落入相同的桶內的話，那么我們在該數據集合中進行近鄰查找就變得容易了，將原始數據集合分成了多個子集合，而每個子集合中的數據間是相鄰的，且該子集合中的元素個數較小，因此將一個在超大集合內查找相鄰元素的問題轉化為了在一個很小的集合內查找相鄰元素的問題，顯然計算量下降了很多。實際上，查找近鄰就是在查找文本檢測時的相似內容，因為，在轉化時，相似的內容會被轉化為相鄰的數據點。

minwise 哈希算法采用局部敏感散列的思想，首先通過minwise 哈希函數將相似數據映射到一個子集合中，運用蒙特卡羅思想，將集合的求交集問題轉換為待查文本內容的數據點被映射到相應集合中的概率問題。通過一定的實驗次數k 來估計事件的發生概率，從而估計兩篇文檔的相似度。同時，將對文檔進行釆樣的實驗中生成的minvalue 存儲下來，作為文檔的特征值向量，以便之后的其他文檔與此文檔的相似度比對。

后來，在minwise 哈希算法的基礎上，有人提出了simhash 算法。simhash 算法的核心思想是用一個b 位的值來表示文檔的特征值，然后使用simhash 之間的海明距離來衡量相似性。海明距離的定義為兩個二進制序列中對應位不同的個數。與傳統hash 函數相比，simhash 函數也是一種局部敏感散列LSH。因此，函數具有一個特征，即越相似的文檔具有越相似的simhash 值，也就是說海明距離越小。顯而易見，僅使用b 位的值來表示文件的特征，節省了大量的存儲開銷；海明距離計算簡單高效，simhash 使用海明距離來衡量相似性，計算復雜性也得到大大降低。簡而言之，simhash 算法將minvalue 值從髙位降低到位，然而，simhash 算法的精確度也會有所損耗，并且與simhash 的位數b 有關，b 越大精確度越高。

3 問題探討

目前的文檔相似性檢測技術還在一些方面存在著一定的問題，同時這些問題也即是該技術在未來的研究方向。

3.1 海量性文檔的相似性檢測

海量數據的相似性檢測一直是文檔相似性檢測的難點。隨著信息爆炸時代的到來，各個系統中的數據都是億萬級別的，數據特征的存儲空間和相似性的檢測時間都有了更高的要求。b 位minwise 哈希算法中 b 越大精度越高，但是相應的存儲空間和計算時間也變得巨大。所以需要一種比較好的方法去解決這個問題。

3.2 語義級文檔相似性檢查

中文信息處理技術目前還不成熟，分詞、詞義標注和句法分析的處理效率還不是非常理想，此外，漢語是一種意合語言，其語言現象非常復雜。目前包括minwise 在內的文檔相似性檢測方法只能發現一部分的文本復制方式，例如同義詞替換、斷句等等，但是對于句子結構發生變化的一些復雜文本復制方式，還沒有找到理想的解決方法。需要考慮將語義分析作為重要突破點，才能從語義層面最終完全解決自然語言的相似性檢測。

3.3 跨語言相似性檢查

目前，很多相似性的文檔并不只存在于同一語言之中，直接抄襲同一語言的著作較為容易被檢査到，但若拿一篇文檔通過翻譯或摘譯后則很難發現。在未來的工作中，可以考慮不同語言的因素，綜合各類語言的句法結構和語義兩方面的信息來生成相似的指紋信息，從而度量不同語言的文檔間的相似性。

3.4 分布式數據相似性檢測

現今大量的文檔以分布式的形式散列在各地，這些大規模的數據相似性的文檔相當多，而目前的文檔相似性檢測系統大多只能針對系統內部的文檔進行檢測，而進行分布式數據相似性檢測是未來檢測的發展方向。

4 總結

文檔相似性檢測技術的廣泛應用推動了信息時代的發展，有效的保護了原創的信息內容。針對海量數據下的相似性檢測，基于相似度估計的檢測方法保持高效的性能的同時，大大降低了時間復雜度和空間內存消耗。本文對基于相似度估計的shingle 算法和minwise 算法進行了一定分析。特別地，minwise 哈希算法采用局部敏感序列的思想，降低了在海量數據下的檢測相似性的部署難度。同時，文檔相似性檢測技術的還存在著一定不足，本文總結了該技術目前存在的一些問題和未來的研究方向。