鄭天宏,許杭杰,董黎剛

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

0 引 言

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

1 k-grams介紹

k-grams[4]是一種基于字符串匹配的算法。它通過將文章轉(zhuǎn)化成重疊文本塊,然后以重疊文本塊作為關鍵信息來與另一文本進行字符串匹配,統(tǒng)計匹配的次數(shù),從而判別文章間的相似度。其中重疊文本塊是指有k-1個字符是重疊的相鄰的文本塊,例如文章S=A1A2…AM,則構建的重疊文本塊為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ù)值化,從而利用散列法提高串匹配速度。設字符串為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。對于重疊文本塊,假設取剛才的字符串S的后一重疊文本塊為T,則T=A2…Am+1。將T轉(zhuǎn)化為數(shù)字T'=A2×Nm-1+…+Am×N+Am+1。因為S'與T'間存在著關系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)此方法將分解得到的所有重疊文本塊都進行了字符串匹配判斷,然而并非所有的文本塊都應作為關鍵信息進行匹配判斷,關鍵信息應該是文章中的特有成分,因此像常用語句就不應被選為關鍵信息。常用語句的特征是在文章中出現(xiàn)的頻率高,比如常用語句“分布式操作系統(tǒng)”會出現(xiàn)在所有介紹關于分布式操作系統(tǒng)的文獻中,若拿它做匹配判斷,顯然會造成錯誤。當然,可以人為設定較長的重疊文本塊長度來避免選擇常用語句。然而較長的重疊文本塊長度卻會導致“關鍵信息”的漏選,從而導致雷同的部分沒有被認定出來。為此提出了改良。

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

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

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

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

3 實驗

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

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

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

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

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

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

4 結(jié)束語

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

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

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

[3]麻會東,劉國華,李現(xiàn)偉,等.基于文檔指紋的中文復制檢測方法[J].廣西師范大學學報(自然科學版),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.