基于N-Gram的文本去重方法研究

王小華，盧小康

（杭州電子科技大學(xué)計(jì)算機(jī)應(yīng)用研究所，浙江杭州310018）

0 引 言

隨著因特網(wǎng)的迅速發(fā)展，越來越多的信息出現(xiàn)在互聯(lián)網(wǎng)上。信息規(guī)模無限，而人們的精力有限，搜索引擎技術(shù)的產(chǎn)生，使得人們能夠以最快的速度找到需要的信息。然而，互聯(lián)網(wǎng)上存在大量的重復(fù)信息，降低了搜索引擎的效率，使資源檢索的效果大打折扣。如何快速，準(zhǔn)確地去除重復(fù)的文本信息是一個(gè)值得研究的課題。由于大部分的重復(fù)信息都是通過直接或間接復(fù)制產(chǎn)生的，所以文本去重有時(shí)也被稱為文本復(fù)制檢測(cè)。目前，國(guó)內(nèi)外研究學(xué)者對(duì)文本去重已經(jīng)取得不少成果，國(guó)外典型的有sif系統(tǒng)，該系統(tǒng)提出基于字符串匹配的方法來度量文件之間的相似性［1］；還有Stanford大學(xué)提出的COPS系統(tǒng)等［2］。國(guó)內(nèi)典型的有CDSDG系統(tǒng)［3］，該系統(tǒng)以數(shù)字水印技術(shù)為基礎(chǔ)，采用基于注冊(cè)的機(jī)制來解決數(shù)字商品非法復(fù)制問題。本文提出基于N-Gram和特征映射的文本去重方法，將文本映射成哈希值序列，通過比較哈希值序列之間的相似來程度來判斷文本是否重復(fù)。本文創(chuàng)新點(diǎn)在于將N-Gram項(xiàng)與映射函數(shù)結(jié)合起來，將文本映射到一個(gè)足夠大的空間。該空間能保證不同的文本映射到同一個(gè)值的概率非常小。實(shí)驗(yàn)證明，該方法速度快，同時(shí)能達(dá)到滿意的去重效果。

1 去重算法思想概述

1.1 常用漢字選取

《中華字?！肥珍浟藵h語單字85 568字，可見構(gòu)成文本的漢字?jǐn)?shù)量相當(dāng)大，而大部分的漢字并不常用，因此如果將不常用的漢字和一些特殊符號(hào)作為禁用詞，在文本預(yù)處理階段將它們從文本中去掉，可以提高程序的處理的速度。大規(guī)模的文本實(shí)驗(yàn)結(jié)果顯示，《現(xiàn)代漢語常用字表》提出的2 500個(gè)常用字覆蓋率達(dá)97.97%，1 000個(gè)次常用字覆蓋率達(dá) 1.51%，合計(jì)（3 500字）覆蓋率達(dá)99.48%［4］。常用漢字的覆蓋率如此之高，所以本文利用《現(xiàn)代漢語常用字表》提出的2 500個(gè)常用漢字對(duì)文本進(jìn)行預(yù)處理。建立常用字編碼對(duì)照表，將選取的2 500個(gè)常用漢字（漢字記為W）進(jìn)行編號(hào)（編號(hào)記為V），編號(hào)從1-2 500。通過查表可以得到每個(gè)漢字的編碼，或每個(gè)編碼對(duì)應(yīng)的漢字。如表1所示：

表1 常用字編碼表

1.2 N-Gram 項(xiàng)

對(duì)文本進(jìn)行處理，需要提取文本特征，文本特征的表示方法非常關(guān)鍵。本文通過提取文本的NGram項(xiàng)，將N-Gram項(xiàng)組成的序列作為文本特征［5］。對(duì)于中文來說，N-Gram項(xiàng)一般由相鄰的字構(gòu)成。例如：從現(xiàn)代漢語中提取2-Gram項(xiàng)，可以得到現(xiàn)代、代漢、漢語3個(gè)2-Gram項(xiàng)。N-Gram作為文本的特征與提取詞語作為文本的特征相比，可以避免使用詞典和分詞程序，從而提高特征提取的速度。采用N-Gram項(xiàng)作為文本特征還有一個(gè)重要的優(yōu)點(diǎn)是它不會(huì)遺漏任何連續(xù)N個(gè)字符重復(fù)的文本序列。N-Gram項(xiàng)也存在缺點(diǎn)：與真正的詞相比，語義沒有那么明顯。而且，隨著N的增長(zhǎng)，N-Gram項(xiàng)組成的序列所占的空間會(huì)大大增加，同時(shí)，計(jì)算機(jī)處理N-Gram的計(jì)算量也大大增加。因此，N的取值一般不宜過大。

1.3 文本特征映射模型

由于N-Gram項(xiàng)所占的空間比較大，如果直接利用N-Gram項(xiàng)進(jìn)行文本特征匹配計(jì)算量非常大，對(duì)程序的運(yùn)行速度影響很大。因此，采用一種哈希映射的方式，把N-Gram項(xiàng)映射到一個(gè)數(shù)值，原本在去重過程中，需要進(jìn)行字符串匹配，現(xiàn)在只需要進(jìn)行數(shù)值查找，這樣一來就將去重算法從匹配算法轉(zhuǎn)變到查找算法。這樣不但降低了算法的時(shí)間復(fù)雜度，也降低了算法的空間復(fù)雜度。

2 算法過程描述

該算法過程可以描述成以下步驟：

第一步 對(duì)照常用漢字編碼表，將文本轉(zhuǎn)換成漢字編碼的數(shù)值序列。在這個(gè)過程中，首先剔除文本所有非常用漢字，標(biāo)點(diǎn)符號(hào)以及其它的字符，僅保留常用漢字，將得到的漢字序列通過對(duì)照常用漢字編碼表轉(zhuǎn)換成漢字編碼的數(shù)值序列，即（Vn）；

第二步 對(duì)第一步中所得到的數(shù)值序列（V0，V1，V2，V3，V4，V5，…，Vn）提取 N-Gram 項(xiàng)。對(duì)于數(shù)值序列提取N-Gram項(xiàng)的方法與提取中文N-Gram項(xiàng)類似。本文取N為4。數(shù)值序列提取得到4-Gram項(xiàng)序列：（），…），該步驟最終輸出一個(gè)N-Gram項(xiàng)的序列；

第三步 對(duì)N-Gram項(xiàng)進(jìn)行哈希映射，將N-Gram項(xiàng)映射到一個(gè)4字節(jié)的數(shù)值。我們將每個(gè)NGram項(xiàng)通過哈希函數(shù)映射到一個(gè)可以用4字節(jié)表示的數(shù)字Hi，即（Hi。這樣就由N-Gram項(xiàng)的序列映射成哈希值的序列（H1，H2，H3，…）。為了敘述方便，稱該哈希值序列為文本哈希序列Sh；

第四步 從文本哈希序列Sh中抽取文本特征序列S′f。具體抽取策略下文會(huì)進(jìn)一步描述；

第五步 用待去重文本的文本特征序列S′f與已經(jīng)注冊(cè)文本的文本哈希序列Sh進(jìn)行查找對(duì)比。如果和Sh中相同值的數(shù)量比值達(dá)到設(shè)定的閾值Tset，判定文本重復(fù)，否則不重復(fù)。

3 算法改進(jìn)與效率優(yōu)化

確定去重算法后，可通過兩兩文本的對(duì)比進(jìn)行去重。以下幾點(diǎn)是對(duì)算法改進(jìn)和優(yōu)化。

（1）映射哈希函數(shù)的構(gòu)造。本文使用如下哈希函數(shù)：

在本文中，N-Gram項(xiàng)所選取的N為4，且V的取值范圍是從1-2 500，因此可將哈希值看成是2 500進(jìn)制的數(shù)字，即當(dāng)b=2 500時(shí)，該哈希函數(shù)映射空間完全不存在沖突。雖然該函數(shù)的哈希值在理論上完全不沖突，但是計(jì)算機(jī)實(shí)際上難以處理。因?yàn)楹瘮?shù)產(chǎn)生的最大哈希值為2 5004-1，當(dāng)前32位字長(zhǎng)的無符號(hào)整型最大為232-1。由于無法利用32位來保存該哈希值，如果用大于32位的空間來保存哈希值，計(jì)算機(jī)處理起來效率很低。因此我們需要選擇一個(gè)合適大小的基數(shù)b值，使得N-Gram項(xiàng)映射到的值產(chǎn)生的沖突的概率很小并且函數(shù)哈希值能用32位空間表示。在本文中，b值的選取滿足不等式：2 500×b3+2 500×b2+2 500＜232-1。解該不等式，b!44。本文選取b=44，實(shí)驗(yàn)證明，該取值同時(shí)能滿足上述的兩個(gè)要求。

（2）文本特征序列S′f的抽取策略。從文本哈希序列Sh中抽取合適的文本特征序列S′f，要求文本特征序列S′f選擇合適的長(zhǎng)度，過長(zhǎng)的S′f序列會(huì)導(dǎo)致算法的運(yùn)行效率過低；S′f太短則會(huì)影響算法的準(zhǔn)確率。本文S′f提取策略是從每個(gè)文本哈希序列Sh中每隔一定距離D（距離長(zhǎng)度記為D）提取一個(gè)數(shù)值組成文本特征序列 S′f。例如，當(dāng)距離參數(shù) D=20 時(shí)，Sh=（H0，H1，H2，H3，…），則所提取的 S′f=（H0，H20，H40，H60，…）。一種經(jīng)過改進(jìn)的策略是動(dòng)態(tài)的改變D的值，不同的文本長(zhǎng)度取不同的D的值以及在文本中不同位置取不同的D值，以提高去重的正確率。

（3）待去重文本的文本特征序列S′f與已經(jīng)注冊(cè)文本的文本哈希序列Sh進(jìn)行查找對(duì)比算法的效率優(yōu)化。由于Sh序列和S′f序列都由數(shù)值組成，可以先對(duì)Sh和S′f進(jìn)行排序，然后利用折半查找算法進(jìn)行對(duì)比查找。折半查找是一種高效的查找方法。它可以明顯減少比較次數(shù)，提高查找效率。

4 實(shí)驗(yàn)結(jié)果與討論

根據(jù)上述算法進(jìn)行了程序?qū)崿F(xiàn)，用以評(píng)價(jià)算法正確性與效率。算法正確性主要有以下兩個(gè)標(biāo)準(zhǔn)：重復(fù)文本的召回率（Recall）和去重的準(zhǔn)確率（Precision），下面給出定義：Recall=實(shí)驗(yàn)中采用的語料庫是搜狗實(shí)驗(yàn)室提供的文本分類語料庫，該文本分類語料庫來源于搜狐新聞網(wǎng)站保存的大量經(jīng)過編輯手工整理與分類的新聞?wù)Z料與對(duì)應(yīng)的分類信息［6］。從每個(gè)類別中隨機(jī)選取了1 000篇作為實(shí)驗(yàn)文本，8個(gè)類別一共8 000篇文本。經(jīng)過人工與計(jì)算機(jī)結(jié)合的方式，確定其中存在重復(fù)文本的數(shù)量為450篇，事先已經(jīng)將重復(fù)文本做標(biāo)記。然后利用本實(shí)驗(yàn)系統(tǒng)對(duì)這8 000篇文本進(jìn)行測(cè)試。

實(shí)驗(yàn)測(cè)試不同的閾值對(duì)去重結(jié)果的影響。實(shí)驗(yàn)結(jié)果如圖1所示，為了能更直觀地表示實(shí)驗(yàn)結(jié)果，本文橫坐標(biāo)Tset的值從大到小遞減。

從實(shí)驗(yàn)結(jié)果可以看出，當(dāng)Tset=0.6的，去重的準(zhǔn)確率和召回率兩者效果都較為理想。觀察發(fā)現(xiàn)，當(dāng)Tset=0.7時(shí)，誤判為重復(fù)的文本主要是體育報(bào)道以及照片描述類文章。誤判為重復(fù)的文本之間有共同的特點(diǎn)：文本的結(jié)構(gòu)大部分相同，只有少數(shù)詞語和數(shù)據(jù)改變；文本長(zhǎng)度通常較短。

本文根據(jù)上述初步的實(shí)驗(yàn)結(jié)果分析，對(duì)程序做了修改，對(duì)文本長(zhǎng)度小于200的文本單獨(dú)做測(cè)試，發(fā)現(xiàn)在Tset=0.7的時(shí)候，對(duì)于短文本的去重效果最為理想。這表明，一個(gè)合適的解決方法是動(dòng)態(tài)地設(shè)置Tset值，把Tset值與文本長(zhǎng)關(guān)聯(lián)起來，對(duì)于較短的文本設(shè)置較大的值，靈活的設(shè)置Tset值能提高去重效果。

5 結(jié) 論

本文提出了基于N-Gram的文本去重算法，在文本去重時(shí)采用不同Tset閾值設(shè)置，能滿足不同的去重效果需求，說明算法具有很大的靈活性。算法的速度較快，在對(duì)普通網(wǎng)頁文本去重應(yīng)用中，取得了很好的效果。算法存在的缺點(diǎn)之一沒有利用文本的語義信息，這會(huì)導(dǎo)致對(duì)在句子中因少數(shù)關(guān)鍵字不同而含義不同的文本的去重效果不理想。只有利用文本的語義信息才能判斷上述的重復(fù)情況。所以，如果能將文本的內(nèi)容信息與語義信息結(jié)合起來，會(huì)取得更好的去重效果，這應(yīng)該是在文本去重的下一步研究的方向。

圖1 Tset參數(shù)對(duì)去重結(jié)果的影響

［1］ Manber U.Finding similar files in a large file system［C］.California：Proceedings of theWinter USENIX Conference，1994：1-10.

［2］ Brin S，Davis J，Garcia-Molina H.Copy detection mechanisms for digital documents［C］.California：Proceedings of the ACM SIGMOD Annual Conference，1995：98-409.

［3］ 宋擒豹，沈鈞毅.數(shù)字商品非法復(fù)制和擴(kuò)散的監(jiān)測(cè)機(jī)制［J］.計(jì)算機(jī)研究與發(fā)展，2001，（38）：121-125.

［4］ 朱巧明.中文信息處理技術(shù)教程［M］.北京：清華大學(xué)出版社，2005：16-17.

［5］ 苗奪謙.衛(wèi)志華.中文文本信息處理的原理與應(yīng)用［M］.北京：清華大學(xué)出版社，2007：220-221.

［6］ 搜狗實(shí)驗(yàn)室.搜狗實(shí)驗(yàn)室文本分類語料庫［EB/OL］，http：//www.sogou.com/labs/dl/c.html，2008-12-31.