鄭天宏,許杭杰,董黎剛

(浙江工商大學(xué)信息與電子工程學(xué)院,浙江杭州310018)

0 引 言

網(wǎng)絡(luò)在無意間方便了品行不端者進行文章抄襲。為了遏制這種不誠信的行為,國外在20世紀(jì)90年代就開始了相應(yīng)研究。由于英語單詞間存在著空格,因此英語文章的抄襲檢測方法大多是通過比較關(guān)鍵詞的方法來判斷相似性?？墒怯捎谥形呐c外文間存在著巨大差異,詞類與句法間沒有嚴(yán)格的對應(yīng)關(guān)系,因此它們并不直接適用于中文。目前中文抄襲檢測方法主要有基于字符串匹配的方法,基于文檔指紋的方法,基于語義知識的方法。其中基于字符串匹配的方法[1]是一種基于數(shù)理統(tǒng)計的方法。它先通過字符串匹配算法,找出待檢測文檔與數(shù)據(jù)庫中的文檔相匹配的字符串?dāng)?shù)目,隨后利用相似性計算公式求出結(jié)果。然而這種方法對字符串的選取要求很高。基于語義知識的方法[2]是通過分析比較待檢測文章與數(shù)據(jù)庫文章的自然語義相似程度從而達(dá)到判別抄襲的目的。但是這種語義判別法顯然與《著作權(quán)法》“不保護思想,只保護思想的表達(dá)”的思想相悖,這使得此類系統(tǒng)判斷結(jié)果的正確性很難得到保證?；谖臋n指紋的方法[3]通過將代表文檔語義的文本作為“指紋”,通過比較“指紋”從而達(dá)到判別抄襲的目的?？墒窃谶x取“指紋”的過程中由于過分關(guān)注文章的層次結(jié)構(gòu)而造成漏判?；谧址ヅ涞姆椒ㄓ捎谄浔阌诶斫馀c開發(fā)而往往被廣泛使用,而k-grams算法又是其中的一種經(jīng)典算法。因此,對kgrams算法的研究與改良是很有意義的。

1 k-grams介紹

k-grams[4]是一種基于字符串匹配的算法。它通過將文章轉(zhuǎn)化成重疊文本塊,然后以重疊文本塊作為關(guān)鍵信息來與另一文本進行字符串匹配,統(tǒng)計匹配的次數(shù),從而判別文章間的相似度。其中重疊文本塊是指有k-1個字符是重疊的相鄰的文本塊,例如文章S=A1A2…AM,則構(gòu)建的重疊文本塊為A1A2…Ak,A2A3…Ak+1,…,AiAi+1…Ak+i-1,…,AM-k+1AM-k+2…AM。算法如下：

/*每個文本塊長度為k,待比較的兩篇文章為a、b,重疊文本塊為text[N],雷同的總數(shù)量為goal*/

為了提高其中字符串匹配速度,往往使用Karp-Rabin串匹配算法[5]。其思想是將待測文章數(shù)值化,從而利用散列法提高串匹配速度。設(shè)字符串為S=A1A2…Am(其中A1A2…Am為字符的ASCII碼或UNICODE碼)。首先將S轉(zhuǎn)化為N進制數(shù)S',其中S'=A1×Nm-1+A2×Nm-2+…+Am(其中N為各類字符總數(shù))。隨后取一個較大的素數(shù)q,通過計算S'mod q獲取S'的HASH值H。對于重疊文本塊,假設(shè)取剛才的字符串S的后一重疊文本塊為T,則T=A2…Am+1。將T轉(zhuǎn)化為數(shù)字T'=A2×Nm-1+…+Am×N+Am+1。因為S'與T'間存在著關(guān)系T'=(S'-A1×Nm-1)×N+Am+1,發(fā)現(xiàn)可以很容易的從S'求得T'。同時由HASH函數(shù)可知很容易從H求出T'的HASH值。整篇文章的HASH值的具體求法如下：/*每個文本塊長度為k,各類字符總數(shù)為N,q為一個素數(shù),待轉(zhuǎn)換的文章為a,重疊文本塊的HASH值ht[M]*/

通過觀察,發(fā)現(xiàn)此方法將分解得到的所有重疊文本塊都進行了字符串匹配判斷,然而并非所有的文本塊都應(yīng)作為關(guān)鍵信息進行匹配判斷,關(guān)鍵信息應(yīng)該是文章中的特有成分,因此像常用語句就不應(yīng)被選為關(guān)鍵信息。常用語句的特征是在文章中出現(xiàn)的頻率高,比如常用語句“分布式操作系統(tǒng)”會出現(xiàn)在所有介紹關(guān)于分布式操作系統(tǒng)的文獻(xiàn)中,若拿它做匹配判斷,顯然會造成錯誤。當(dāng)然,可以人為設(shè)定較長的重疊文本塊長度來避免選擇常用語句。然而較長的重疊文本塊長度卻會導(dǎo)致“關(guān)鍵信息”的漏選,從而導(dǎo)致雷同的部分沒有被認(rèn)定出來。為此提出了改良。

2 利用基于統(tǒng)計的中文分詞技術(shù)進行改良

基于統(tǒng)計的中文分詞技術(shù)原理是在文章中查找特定字組合出現(xiàn)的頻率,若出現(xiàn)的頻率高,則認(rèn)為此字組合為單詞。單純依靠此技術(shù)得到的單詞在不少情況下并非真正的中文單詞,然而這些“單詞”卻滿足常用語句的特征。正因為此,可以利用此技術(shù)對k-grams分解文章得到的重疊文本塊進行篩選,排除出現(xiàn)頻率高的常用語句,從而提取到有效的關(guān)鍵信息,提高k-grams檢查抄襲的準(zhǔn)確性。改良后的k-grams算法的具體操作是：(1)分解文章得到重疊文本塊;(2)定義一個用于判斷頻率高低的門限值;(3)統(tǒng)計這些重疊文本塊在待檢測的文章中出現(xiàn)的頻率;(4)排除出現(xiàn)的頻率高于門限值的文本塊;(5)用剩下的文本塊與其它文章進行字符串匹配;(6)統(tǒng)計抄襲數(shù)量。其中2-4為中文分詞技術(shù)的內(nèi)容,算法如下：/*Article a,b待比較的兩篇文章,text[N]重疊文本塊,GATE為門限值*/

為了避免關(guān)鍵信息的漏選問題,其中重疊文本塊的長度應(yīng)該盡量小,但是為了減少分詞技術(shù)所帶來的時間上的開銷,重疊文本塊的長度也不宜短于常用詞語的長度,一般取5-7。

經(jīng)過步驟2-4后所剩下的文本塊是否為通常意義上的常用語句與門限值的選取有關(guān)。顯然出現(xiàn)頻率高的文本塊更符合通常意義上常用語句的定義(常用語句特點就是出現(xiàn)頻率高)。因此可以設(shè)置較高的門限值,即僅排除出現(xiàn)頻率較高的文本塊。但是實際上沒有必要。因為只有出現(xiàn)頻率很低的文本塊才是應(yīng)該參與匹配判斷的文章特有成分。因此門限值取2就可以了。

3 實驗

因為目前我國不存在對文章抄襲的嚴(yán)格法律定義,認(rèn)定抄襲主要靠相關(guān)專家的審核,所以選取了已經(jīng)被專家認(rèn)定為抄襲的文章做樣本進行檢測。通過對樣本的檢測,驗證了改良的效果。

選擇一份抄襲案例《走向科學(xué)?——一份抄襲樣本的證實與分析》(錢世榮.[J]《秘書》2002.2：13-15)作為樣本進行檢測。在此例中,錢先生提出《秘書學(xué)元科學(xué)層面的研究亟待加強》(以下作為文章a)與《走向科學(xué)_中國現(xiàn)代檔案學(xué)元科學(xué)層面分析》(以下作為文章b,b抄襲了a)是雷同文章,并給出了自己的分析。其提出的觀點得到了《秘書》雜志編輯部的認(rèn)可,抄襲者也承認(rèn)了抄襲的事實。

首先統(tǒng)計出錢先生在其文章中指出的抄襲部分的抄襲字?jǐn)?shù),然后對文章a,b進行測試,運行后的統(tǒng)計結(jié)果如表1所示。

表1 抄襲樣本測試統(tǒng)計結(jié)果

將系統(tǒng)找出的文章中存在的雷同部分與錢先生的分析結(jié)果進行比較,發(fā)現(xiàn)在未使用分詞技術(shù)前,系統(tǒng)找出了錢先生指出的抄襲內(nèi)容。但是,卻將一些常用語句一同包含在抄襲范圍之內(nèi),如“一門獨立的學(xué)科”、“現(xiàn)階段秘書學(xué)”、“基本理論研究”等。而在使用分詞技術(shù)后,系統(tǒng)不但成功找出了錢先生指出的抄襲內(nèi)容,同時還排除了一些常用語句。

由此可知,在使用分詞技術(shù)后,系統(tǒng)避免了一些常用語句被誤判為抄襲,提高了判斷的準(zhǔn)確性。

4 結(jié)束語

首先介紹了k-grams抄襲檢查算法,隨后針對k-grams抄襲檢查算法存在的如何選取關(guān)鍵信息的問題,提出了利用基于統(tǒng)計的分詞方法的中文分詞技術(shù)對其進行了改良。最后通過實驗觀察到通過改良確實提高了系統(tǒng)判斷的準(zhǔn)確性。

[1]李旭.基于串匹配方法的文檔復(fù)制檢測系統(tǒng)研究[DB/OL].http：//cdmd.cnki.com.cn/Article/CDMD-10216-2006066244.htm,2009-08-10.

[2]李旭,趙亞偉,劉國華.基于指紋和語義特征的文檔復(fù)制檢測方法[J].燕山大學(xué)學(xué)報 ,2008,32(4)：334-339.

[3]麻會東,劉國華,李現(xiàn)偉,等.基于文檔指紋的中文復(fù)制檢測方法[J].廣西師范大學(xué)學(xué)報(自然科學(xué)版),2007,25(4)：112-115.

[4]Richard M Karp,Michael O Rabin.Pattern-matching algorithms[J].IBM Journal of Research and Development,1987,31(2)：249-260.

[5]Krisztian Monostori,Arkady Zaslavsky,Heinz Schmidt.MatchDetectReveal：Finding Overlapping and Similar Digital Documents[EB/OL].http：//www.csse.monash.edu.au/projects/MDR/papers/irma2000-mdr-monostori.pdf,2009-09-07.