王鈺寧，劉曉霞，周紹軍

（四川水利職業(yè)技術(shù)學(xué)院信息工程系,四川崇州,611231）

關(guān)鍵字：重復(fù)率；相似度；估計(jì)；檢測(cè)算法

1 當(dāng)前現(xiàn)狀

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

文檔的相似性檢測(cè)技術(shù)從文檔內(nèi)容的相似程度上判斷文檔是否為有抄襲剽竊的嫌疑。所謂文檔相似性檢測(cè)，就是判斷一個(gè)文件的內(nèi)容與另外一個(gè)或者多個(gè)文件的相似程度，以檢測(cè)抄襲剽竊。而剽竊不僅僅意味著對(duì)原作原封不動(dòng)地照抄，還包括對(duì)原作的移位變換、同義詞替換以及改變說(shuō)法重述等方式。文檔相似性檢測(cè)技術(shù)可以應(yīng)用在數(shù)字化圖書(shū)館、搜索引擎、論文查重、基金申請(qǐng)、獎(jiǎng)勵(lì)評(píng)審等很多領(lǐng)域，為用戶(hù)減小信息的存儲(chǔ)空間，高速搜索信息，防止論文、基金申請(qǐng)書(shū)、項(xiàng)目報(bào)獎(jiǎng)、專(zhuān)利剽竊和網(wǎng)頁(yè)去重提供了很好的解決方案。

文檔相似性檢測(cè)的核心內(nèi)容就是判斷兩篇文本內(nèi)容是否存在重復(fù)成分，并給出一個(gè)相似度數(shù)值評(píng)估。兩篇文檔A 和B的相似度R(A,B),是一個(gè)介于0 和1 之間的數(shù)。相似度越大，文本重復(fù)成分越多。計(jì)算文檔相似度，首先需要把文檔用數(shù)據(jù)模型表示。目前，根據(jù)不同的文檔表示方式，可以把目前的主要的文檔相似性檢測(cè)方法分為三類(lèi)：基于詞頻統(tǒng)計(jì)的方法[3,4]、基于近似指紋的字符串匹配的算法和基于相似度估計(jì)的算法?；谠~頻統(tǒng)計(jì)的文檔相似性的檢測(cè)方法主要檢測(cè)的就是文檔詞頻的相似性?；谧址葘?duì)的文檔相似性檢測(cè)方法主要檢測(cè)的就是文檔經(jīng)過(guò)分詞處理后的字符串集合的交集大小?；谙嗨贫裙烙?jì)的算法既有檢測(cè)文檔詞頻相似性的方法，例如隨機(jī)投影。也有檢測(cè)字符串集合交集為目標(biāo)的minwise 相似度估計(jì)方法。

基于詞頻統(tǒng)計(jì)的方法存在著檢測(cè)結(jié)果準(zhǔn)確率低、誤判率大的缺點(diǎn)。文檔中一些常用詞匯頻率較高，易出現(xiàn)誤差帶來(lái)噪聲。并且該方法的向量空間模型的列的維度很大，實(shí)際比對(duì)時(shí)所花費(fèi)的時(shí)間多?；谧址葘?duì)的方法使用簡(jiǎn)單，但只能進(jìn)行簡(jiǎn)單的字符串匹配，無(wú)法發(fā)現(xiàn)復(fù)雜的相似性方式的重復(fù)文本，比如同義詞替換、改變說(shuō)法等。同時(shí)對(duì)于海量數(shù)據(jù)，該方法需要兩兩文檔的比對(duì)，這種方法實(shí)際上是不可行的。

2 檢測(cè)算法

基于相似度估計(jì)的算法一般采用降維的方式，將文檔向量或者字符串集合轉(zhuǎn)化為k 個(gè)指紋的集合，指紋即為固定長(zhǎng)度的較短的文檔的字符串，這k 個(gè)指紋集合用來(lái)表征一篇文檔，從而當(dāng)求解相似度時(shí)，直接比對(duì)指紋集合的相似度即可得文檔的相似度。

shingle 算法是最常見(jiàn)的文檔相似性檢測(cè)算法。將一個(gè)文檔分解成由w 個(gè)短字符構(gòu)成的字符串集合后，一個(gè)連續(xù)的的子字符串被稱(chēng)為一個(gè)shingle。得到字符串集合后就可以通過(guò)Jaccard 相似度等簡(jiǎn)單的度量標(biāo)準(zhǔn)進(jìn)行相似度檢測(cè)了。比如，一個(gè)文檔

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

圖1 shingle 算法流程圖

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

在shingle 算法的基礎(chǔ)上提出的minwise 哈希方法可以解決該問(wèn)題。minwise 哈希算法將字符集合的求交集問(wèn)題轉(zhuǎn)化為某一事件發(fā)生的概率問(wèn)題。在算法中，不是簡(jiǎn)單的對(duì)shingle 集合進(jìn)行計(jì)算量較大的比對(duì)，而是對(duì)每個(gè)文檔的shingle 集合進(jìn)行minwise 散列函數(shù)處理，進(jìn)行降維，然后再計(jì)算相似程度。minwise 哈希函數(shù)是一類(lèi)局部敏感散列。

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

圖2 局部敏感散列示意圖

如果我們能夠找到這樣一些哈希函數(shù)，使得經(jīng)過(guò)它們的哈希映射變換后，原始空間中相鄰的數(shù)據(jù)落入相同的桶內(nèi)的話(huà)，那么我們?cè)谠摂?shù)據(jù)集合中進(jìn)行近鄰查找就變得容易了，將原始數(shù)據(jù)集合分成了多個(gè)子集合，而每個(gè)子集合中的數(shù)據(jù)間是相鄰的，且該子集合中的元素個(gè)數(shù)較小，因此將一個(gè)在超大集合內(nèi)查找相鄰元素的問(wèn)題轉(zhuǎn)化為了在一個(gè)很小的集合內(nèi)查找相鄰元素的問(wèn)題，顯然計(jì)算量下降了很多。實(shí)際上，查找近鄰就是在查找文本檢測(cè)時(shí)的相似內(nèi)容，因?yàn)?，在轉(zhuǎn)化時(shí)，相似的內(nèi)容會(huì)被轉(zhuǎn)化為相鄰的數(shù)據(jù)點(diǎn)。

minwise 哈希算法采用局部敏感散列的思想，首先通過(guò)minwise 哈希函數(shù)將相似數(shù)據(jù)映射到一個(gè)子集合中，運(yùn)用蒙特卡羅思想，將集合的求交集問(wèn)題轉(zhuǎn)換為待查文本內(nèi)容的數(shù)據(jù)點(diǎn)被映射到相應(yīng)集合中的概率問(wèn)題。通過(guò)一定的實(shí)驗(yàn)次數(shù)k 來(lái)估計(jì)事件的發(fā)生概率，從而估計(jì)兩篇文檔的相似度。同時(shí)，將對(duì)文檔進(jìn)行釆樣的實(shí)驗(yàn)中生成的minvalue 存儲(chǔ)下來(lái)，作為文檔的特征值向量，以便之后的其他文檔與此文檔的相似度比對(duì)。

后來(lái)，在minwise 哈希算法的基礎(chǔ)上，有人提出了simhash 算法。simhash 算法的核心思想是用一個(gè)b 位的值來(lái)表示文檔的特征值，然后使用simhash 之間的海明距離來(lái)衡量相似性。海明距離的定義為兩個(gè)二進(jìn)制序列中對(duì)應(yīng)位不同的個(gè)數(shù)。與傳統(tǒng)hash 函數(shù)相比，simhash 函數(shù)也是一種局部敏感散列LSH。因此，函數(shù)具有一個(gè)特征，即越相似的文檔具有越相似的simhash 值，也就是說(shuō)海明距離越小。顯而易見(jiàn)，僅使用b 位的值來(lái)表示文件的特征，節(jié)省了大量的存儲(chǔ)開(kāi)銷(xiāo)；海明距離計(jì)算簡(jiǎn)單高效，simhash 使用海明距離來(lái)衡量相似性，計(jì)算復(fù)雜性也得到大大降低。簡(jiǎn)而言之，simhash 算法將minvalue 值從髙位降低到位，然而，simhash 算法的精確度也會(huì)有所損耗，并且與simhash 的位數(shù)b 有關(guān)，b 越大精確度越高。

3 問(wèn)題探討

目前的文檔相似性檢測(cè)技術(shù)還在一些方面存在著一定的問(wèn)題，同時(shí)這些問(wèn)題也即是該技術(shù)在未來(lái)的研究方向。

3.1 海量性文檔的相似性檢測(cè)

海量數(shù)據(jù)的相似性檢測(cè)一直是文檔相似性檢測(cè)的難點(diǎn)。隨著信息爆炸時(shí)代的到來(lái)，各個(gè)系統(tǒng)中的數(shù)據(jù)都是億萬(wàn)級(jí)別的，數(shù)據(jù)特征的存儲(chǔ)空間和相似性的檢測(cè)時(shí)間都有了更高的要求。b 位minwise 哈希算法中 b 越大精度越高，但是相應(yīng)的存儲(chǔ)空間和計(jì)算時(shí)間也變得巨大。所以需要一種比較好的方法去解決這個(gè)問(wèn)題。

3.2 語(yǔ)義級(jí)文檔相似性檢查

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

3.3 跨語(yǔ)言相似性檢查

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

3.4 分布式數(shù)據(jù)相似性檢測(cè)

現(xiàn)今大量的文檔以分布式的形式散列在各地，這些大規(guī)模的數(shù)據(jù)相似性的文檔相當(dāng)多，而目前的文檔相似性檢測(cè)系統(tǒng)大多只能針對(duì)系統(tǒng)內(nèi)部的文檔進(jìn)行檢測(cè)，而進(jìn)行分布式數(shù)據(jù)相似性檢測(cè)是未來(lái)檢測(cè)的發(fā)展方向。

4 總結(jié)

文檔相似性檢測(cè)技術(shù)的廣泛應(yīng)用推動(dòng)了信息時(shí)代的發(fā)展，有效的保護(hù)了原創(chuàng)的信息內(nèi)容。針對(duì)海量數(shù)據(jù)下的相似性檢測(cè)，基于相似度估計(jì)的檢測(cè)方法保持高效的性能的同時(shí)，大大降低了時(shí)間復(fù)雜度和空間內(nèi)存消耗。本文對(duì)基于相似度估計(jì)的shingle 算法和minwise 算法進(jìn)行了一定分析。特別地，minwise 哈希算法采用局部敏感序列的思想，降低了在海量數(shù)據(jù)下的檢測(cè)相似性的部署難度。同時(shí)，文檔相似性檢測(cè)技術(shù)的還存在著一定不足，本文總結(jié)了該技術(shù)目前存在的一些問(wèn)題和未來(lái)的研究方向。