近年來，學(xué)術(shù)抄襲事件頻出，國家相關(guān)部門也開始高度重視學(xué)術(shù)抄襲問題。2007 年1 月16 日，中國科協(xié)發(fā)布《科技工作者科學(xué)道德規(guī)范( 試行) 》，提到“旗幟鮮明地抵制敗壞學(xué)術(shù)風(fēng)氣的行為。摒棄心浮氣躁、急功近利的學(xué)風(fēng)，堅(jiān)決反對(duì)投機(jī)取巧、弄虛作假和抄襲剽竊等丑惡行為”。2011 年9 月，中國科協(xié)、教育部聯(lián)合下發(fā)《關(guān)于開展科學(xué)道德和學(xué)風(fēng)建設(shè)宣講教育活動(dòng)的通知》。為杜絕學(xué)術(shù)抄襲行為，營造一個(gè)良好的學(xué)術(shù)環(huán)境，學(xué)術(shù)文獻(xiàn)抄襲檢測(cè)成為研究熱點(diǎn)。當(dāng)前的抄襲檢測(cè)技術(shù)主要從兩個(gè)方面解決此問題: 一是“防止復(fù)制( copy prevention) ”; 二是“復(fù)制檢測(cè)( copy detection) ”。“防止復(fù)制”不考慮檢測(cè)問題，包括信息物理隔離法、文件授權(quán)保護(hù)法［1］、文件封裝法［2］等。隨著網(wǎng)絡(luò)的發(fā)展，這些方法目前已逐漸失去了優(yōu)勢(shì)［3］，本文主要討論“復(fù)制檢測(cè)法”。

復(fù)制檢測(cè)是針對(duì)數(shù)字文檔的檢測(cè)，主要分為自然語言文本( 如小說、論文) 和形式語言文本( 如數(shù)據(jù)文件、計(jì)算機(jī)程序代碼)］。鑒于形式化語言文本具有嚴(yán)格的語法結(jié)構(gòu)，易于處理，以至于早期的抄襲檢測(cè)主要針對(duì)形式化語言文本。最早開始研究形式化語言文本抄襲并取得實(shí)質(zhì)進(jìn)展的是K． J． Ottenstein［5］，他于1976 年針對(duì)學(xué)生計(jì)算機(jī)程序作業(yè)抄襲的問題提出了基于4 組統(tǒng)計(jì)量的屬性計(jì)數(shù)法的識(shí)別方法。N． Bulut［6］的統(tǒng)計(jì)結(jié)果證實(shí)了該方法的可行性。然而，這些屬性都無法體現(xiàn)局部特征，因此對(duì)于部分抄襲該方法無法檢測(cè)，這也是屬性計(jì)數(shù)法的局限性。與之相對(duì)，自然語言的抄襲形式多樣，往往伴隨著語序的調(diào)整、同義詞的替換、標(biāo)點(diǎn)符號(hào)的更改等。直到1991 年，才出現(xiàn)了自然語言文本抄襲識(shí)別軟件WordCheck［7］，該軟件由Ｒichard 采用關(guān)鍵詞匹配算法開發(fā)，開啟了自然語言文本抄襲識(shí)別的序幕，本文討論的學(xué)術(shù)抄襲檢測(cè)即屬于自然語言抄襲檢測(cè)。

學(xué)術(shù)文獻(xiàn)抄襲定義

按照N． Heintze［8］和吳育嬌等［9］的觀點(diǎn)，常見的抄襲現(xiàn)象包括: ①完全抄襲文獻(xiàn); ②經(jīng)過細(xì)微修改的文獻(xiàn); ③經(jīng)過重新組織結(jié)構(gòu)的文獻(xiàn); ④經(jīng)過校訂的新版本文獻(xiàn); ⑤某文獻(xiàn)的擴(kuò)展版本文獻(xiàn); ⑥包含其他文獻(xiàn)中部分內(nèi)容的文獻(xiàn)，部分內(nèi)容被修改。除此之外，若兩篇文獻(xiàn)的主題和內(nèi)容類似，則這兩篇文獻(xiàn)的關(guān)系屬于內(nèi)容相關(guān)［10］。在當(dāng)今學(xué)術(shù)界，上述現(xiàn)象: ①即雷同文獻(xiàn)幾乎不會(huì)出現(xiàn)，而第④、⑤種情況由于其根本出自于同一作者之手，因此也不是本文關(guān)注的重點(diǎn)。而第②、③種情況盡管很容易被識(shí)別，但是也有少數(shù)抄襲者“頂風(fēng)作案”［11］，邵文利于2003 年發(fā)表論文［12］，披露了一起碩士生名家作品的抄襲事件，抄襲篇幅達(dá)50%。

最常見也最難檢測(cè)的抄襲是第⑥種情況［11］，即一篇文獻(xiàn)抄襲另外一篇文獻(xiàn)的一部分而未經(jīng)引用，或針對(duì)這一部分修改后再抄襲。修改后抄襲分為兩種情況: 一種是字面( literal) 抄襲; 一種是智能( intelligent)抄襲［13］。字面抄襲是指抄襲者在抄襲時(shí)并未做隱蔽工作，通常只調(diào)整語序，如主動(dòng)句變被動(dòng)句，拆分從句，通常不會(huì)對(duì)詞進(jìn)行替換。而智能抄襲則更加隱蔽，通常作者會(huì)有意對(duì)原文進(jìn)行修改，企圖蒙蔽讀者，常見的方式包括: 替換同義詞; 對(duì)文章進(jìn)行總結(jié); 翻譯其他語言的文章; 通過自動(dòng)翻譯軟件將原文翻譯至一目標(biāo)語言然后再翻譯回原語言; 將別人的思想( 包括實(shí)驗(yàn)結(jié)果、貢獻(xiàn)、發(fā)現(xiàn)、結(jié)論等) 通過自己的語言描述出來等。一個(gè)理想的抄襲檢測(cè)系統(tǒng)應(yīng)該檢測(cè)上述所有抄襲現(xiàn)象。值得注意的是，以上列舉的幾種現(xiàn)象，不僅包括對(duì)他人作品的抄襲，同時(shí)也包括自我抄襲。C． S．Collberg 等［14］認(rèn)為由于自我抄襲的隱蔽性，當(dāng)今學(xué)術(shù)界自我抄襲的情況似乎遠(yuǎn)超過對(duì)他人的抄襲。

抄襲檢測(cè)系統(tǒng)

一個(gè)抄襲檢測(cè)系統(tǒng)應(yīng)能識(shí)別人為刻意的抄襲，此外還需對(duì)如下因素情況作出合適的判斷:忽略空格在匹配自然語言文檔時(shí)，空格、大小寫以及標(biāo)點(diǎn)符號(hào)的不同不應(yīng)該影響匹配結(jié)果。噪聲抑制對(duì)于非常短的字符串匹配要進(jìn)行

適當(dāng)?shù)淖R(shí)別，例如兩篇文檔中都出現(xiàn)the 并不代表抄襲，抄襲應(yīng)該是足夠長的一段材料，而俗語等常見的語句不應(yīng)該被認(rèn)為是抄襲。位置獨(dú)立對(duì)于只是粗略地調(diào)整過順序的抄襲應(yīng)該能夠識(shí)別，另外諸如加入一段內(nèi)容或者刪除一段內(nèi)容都不應(yīng)該影響剩余部分匹配結(jié)果。第一個(gè)完整的抄襲檢測(cè)系統(tǒng)是由斯坦福大學(xué)S．Brin 等開發(fā)的COPS( copy prevention system) ［3］。該系統(tǒng)是首個(gè)提出文檔注冊(cè)機(jī)制的系統(tǒng)，之后的系統(tǒng)基本都沿用了這個(gè)結(jié)構(gòu)［10，15 － 17］。該系統(tǒng)的工作流程如圖1所示:由圖1 可知，抄襲檢測(cè)可以被看作是一個(gè)以文檔為查詢的信息檢索任務(wù)，因此抄襲檢測(cè)所使用的各類方法與信息檢索技術(shù)息息相關(guān)。

基于特征空間的方法

基于特征空間的方法是信息檢索領(lǐng)域最常見的方法之一，通常需要對(duì)一篇文獻(xiàn)進(jìn)行分塊( chunking) ，使用詞袋模型( bag of words) 為文獻(xiàn)構(gòu)造特征空間，然后

運(yùn)用線性代數(shù)的計(jì)算方法進(jìn)行相似度計(jì)算。不同于信息檢索系統(tǒng)，抄襲檢測(cè)系統(tǒng)除了使用自然語言的單詞或者常見的k-gram 作為詞項(xiàng)外，還會(huì)使用句子或者定長的字符串作為詞項(xiàng)。本章所列舉的技術(shù)，若無特殊說明，對(duì)各類分塊方法皆適用。

向量空間模型

向量空間模型( vector space model，VSM) 由C．Salton［18］于1971 年首先提出，他將文獻(xiàn)看作以詞項(xiàng)權(quán)重為分量的特征向量。對(duì)于任何一個(gè)給定的查詢( query) 文本，為其生成特征向量，然后與數(shù)據(jù)庫中的文檔特征向量做相似度運(yùn)算，通過預(yù)設(shè)的閥值實(shí)現(xiàn)抄襲檢測(cè)。常見的特征向量以詞頻作為分量，通常使用tf*idf( term frequency * inverse document frequency) 詞頻權(quán)重表示法。

點(diǎn)積( inner product) 點(diǎn)積相似度計(jì)算是一個(gè)常見的向量空間模型計(jì)算方法，該計(jì)算方法形式如下:sim( D1，D2) =ΣNi = 1α2i* Fi( D1) * Fi( D2) 公式( 1)上述公式計(jì)算D1和D2兩個(gè)文檔的點(diǎn)積相似度，其中αi表示第i 個(gè)詞項(xiàng)的權(quán)重，F(xiàn)i( D1) 表示D1文檔的第i 個(gè)詞項(xiàng)分量。這種計(jì)算方法對(duì)于篇幅接近的文檔識(shí)別能力強(qiáng)，但是對(duì)于文檔篇幅差別明顯的文檔則會(huì)由于其中一個(gè)文檔的分量數(shù)值過小而失去影響力。

 余弦相似度( cosine similarity) ［10］ 余弦相似度實(shí)質(zhì)上計(jì)算兩個(gè)向量的夾角，余弦值越大，則夾角越小，即向量越相似，因此可以使用這種方法進(jìn)行計(jì)算，計(jì)算方法如下:

可以看出，公式( 2) 在公式( 1) 的基礎(chǔ)之上加入了歸一化分母，由于分母對(duì)分子的分量進(jìn)行了歸一化處理，因此所得的分量不再受文檔長度的影響，可以有效實(shí)現(xiàn)相似性的檢測(cè)。國內(nèi)學(xué)者趙俊杰等［19］即基于此方法利用KNN 算法提出了一種基于分類的抄襲檢測(cè)方法。除了使用詞袋模型，學(xué)者郭武斌等［20］基于余弦相似度使用了馬爾科夫模型進(jìn)行相似度計(jì)算，提高了準(zhǔn)確率。

同一度量( identity measures) ［21］ T． C． Hoad等認(rèn)為無論是點(diǎn)積還是余弦相似度，都適用于ad hoc檢索，而若要應(yīng)用到全長度文檔則需要對(duì)計(jì)算方法進(jìn)行改進(jìn)。他認(rèn)為相似的文檔中同一個(gè)單詞出現(xiàn)的頻率應(yīng)該接近，并由此提出了同一度量法。作為點(diǎn)積計(jì)算的一個(gè)改進(jìn)版本，同一度量引入了同一個(gè)詞在兩個(gè)文檔D1和D2中出現(xiàn)的頻率之差| FD1，t－ FD2，t| ，通過將其置于分母達(dá)到加大詞項(xiàng)權(quán)重的目的。該方法表面上提出了一種創(chuàng)新的計(jì)算方法，但是與相對(duì)頻率模型的思想是相通的。由于相對(duì)頻率模型的出現(xiàn)要早于同一度量，因此在這里不再贅述。

相對(duì)頻率模型

V． Shivakumar 等［10］在開發(fā)SCAM 系統(tǒng)時(shí)提出了相對(duì)頻率模型( relative frequency model，ＲFM) 。相對(duì)頻率模型是基于向量空間模型的一種改進(jìn)模型。對(duì)于任意給定的兩個(gè)文檔D1和D2，定義相近集合closeness set c( D1，D2) ，這個(gè)集合包含了兩個(gè)文檔中出現(xiàn)頻率相近的詞項(xiàng)。若詞項(xiàng)Wi∈c( D1，D2) ，則需滿足下列條件:

其中∈為預(yù)設(shè)參數(shù)，取值范圍為∈ = ( 2 + ，∞ ) ，取值越大則寬容度越高，F(xiàn)i( D1) 表示文檔D1中第i個(gè)詞項(xiàng)的頻次。然后定義文檔D1為D2的子集的計(jì)算方法如下:

該公式實(shí)質(zhì)上是余弦相似度計(jì)算的改進(jìn)版本。但是在對(duì)分子進(jìn)行歸一化處理時(shí)僅依據(jù)D1文檔的長度，并且僅計(jì)算在類似集合中出現(xiàn)的單詞，可以有效地識(shí)別一篇文檔是另外一篇文檔的子集的情況。然后通過如下簡單的計(jì)算得出文檔D1和K2的相似度:

當(dāng)sim( D1，D2 ＞ 1，則取sim( D1，D2) = 1，由于大于1 表明了一種包含關(guān)系，而這大于1 本身就代表高度相關(guān)，而為了便于系統(tǒng)計(jì)算，則統(tǒng)一取1 以符合相似度從0 到100%的范圍。上述的向量空間模型和相對(duì)頻率模型，實(shí)質(zhì)上是對(duì)于給定的待檢文檔進(jìn)行樸素K 最近鄰搜索，對(duì)于一個(gè)含有n 個(gè)文檔的文檔集，每篇待檢文檔都需要掃描全部的文檔內(nèi)容，而在真實(shí)的系統(tǒng)中，注冊(cè)服務(wù)器里往往存有千萬級(jí)別的數(shù)據(jù)，因此對(duì)全部文檔進(jìn)行計(jì)算是

不可行的［17］，國內(nèi)學(xué)者孫偉等［22］也僅針對(duì)小數(shù)據(jù)對(duì)該算法進(jìn)行了改進(jìn)驗(yàn)證。

潛在語義分析模型

S． Deerwester 等［23］ 提出的潛在語義分析( latentsemantic analysis，LSA) 模型是一種強(qiáng)大的詞項(xiàng)－ 文檔矩陣降維模型。它通過對(duì)矩陣進(jìn)行奇異值分解，可以將矩陣分解成兩個(gè)正交矩陣與奇異值矩陣的乘積，然

后通過放棄奇異值數(shù)量級(jí)較小的部分形成一個(gè)對(duì)原矩陣的最佳估計(jì)，這個(gè)矩陣的秩遠(yuǎn)低于原矩陣的秩，從而達(dá)到降維的目的。

Z． Ceska［24］基于潛在語義分析提出了SVDPlag 方法。他首先將預(yù)處理后的950 篇文檔形成一個(gè)n* m矩陣A，其中行代表文檔，列代表詞項(xiàng)權(quán)重，詞項(xiàng)的權(quán)重使用一種改進(jìn)的TF-IDF 權(quán)重。然后對(duì)其進(jìn)行奇異值分解，得A = U ×Σ × VT。其中VT 是一個(gè)正交矩陣，為了使數(shù)據(jù)接近原始矩陣，還必須將奇異值重新帶入，即B =Σ × VT。然后得到相似度矩陣:

這個(gè)相似度矩陣的任何一個(gè)元素( D1，D2) 即為D1和D2的文檔相似度。實(shí)驗(yàn)證明，該模型在對(duì)950 篇文檔的實(shí)驗(yàn)中F1度量值高于其他的基于向量空間模型的方法，相似度識(shí)別能力很強(qiáng)。然而該方法的弊端在于，對(duì)于數(shù)量級(jí)較

大的文檔集處理幾乎無能為力。奇異值分解作為20世紀(jì)90 年代矩陣領(lǐng)域興起的研究重點(diǎn)，一直未在信息檢索領(lǐng)域大有作為的一個(gè)重要原因在于奇異值分解對(duì)于計(jì)算機(jī)的要求相當(dāng)高，并且一直未能出現(xiàn)一種可以分布式計(jì)算的方法造成該模型只能停留在理論上。前谷歌科學(xué)家吳軍在《數(shù)學(xué)之美》［25］一書中透露谷歌已經(jīng)實(shí)現(xiàn)了奇異值分解基于Map-Ｒeduce 的分布式計(jì)算，然而這項(xiàng)技術(shù)并未公開。而從Z． Ceska［24］在對(duì)文檔集預(yù)處理時(shí)使用文檔頻率大量去除詞項(xiàng)也可以看出數(shù)量級(jí)對(duì)于計(jì)算的影響之大。隨著海量數(shù)據(jù)處理的發(fā)展，希望在不久的將來潛在語義分析能真正應(yīng)用于海量文檔的處理。

KD-Tree K 最近鄰模型

除了對(duì)詞袋模型進(jìn)行統(tǒng)計(jì)，Ｒ． A． Finkel［26］還提出了一種基于文檔文體學(xué)特征的計(jì)算模型。他提出可以將文獻(xiàn)的文體特征作為統(tǒng)計(jì)量進(jìn)行計(jì)算，例如單詞平均音節(jié)數(shù)、被動(dòng)語態(tài)的出現(xiàn)頻率、從句的數(shù)量、常見詞( the、and 和but 等) 的數(shù)量。國內(nèi)學(xué)者金博等［27］也提出了一種基于篇章結(jié)構(gòu)的模型，將篇章標(biāo)題的結(jié)構(gòu)作為特征向量，每一個(gè)統(tǒng)計(jì)量作為文檔特征向量的一個(gè)維度分量，對(duì)于一個(gè)文檔F 定義它的文檔特征向量為P( F) ，則文檔D1和D2的多維相似度表示為m( D1，D2) = distance( P( D1) ，P( D2) ) 。然后使用KD-Tree 數(shù)據(jù)結(jié)構(gòu)保存全部文檔特征向量，則查找其中任何一個(gè)文檔的相似文檔就變?yōu)椴檎以撐臋n向量的K 個(gè)最近鄰。使用KD-Tree 這種數(shù)據(jù)結(jié)構(gòu)，是因?yàn)樗腥缦绿攸c(diǎn): 首先，作為一種二叉查找樹，由于在初始構(gòu)造時(shí)已經(jīng)有了大量注冊(cè)文檔，因此最終可以形成一個(gè)平衡樹，并且此樹可以不斷地增加新的節(jié)點(diǎn); 其次，KD-Tree 可以方地進(jìn)行存儲(chǔ); 再次，使用該樹增加一個(gè)向量的時(shí)間復(fù)雜度為O( k logn) ，而查找一個(gè)向量的最近鄰的時(shí)間復(fù)雜度亦為O( k logn) ，這樣就大大提高了匹配效率。

基于數(shù)字指紋的方法

一個(gè)文檔的數(shù)字指紋是指文檔的關(guān)鍵內(nèi)容的整形數(shù)字( integer) 表示的一個(gè)集合，每一個(gè)整形數(shù)字稱為一個(gè)特征( minutia) 。一般地，先從文本中選取子字符串，然后將該子字符串通過一個(gè)hash 函數(shù)映射到一個(gè)整形表示，這個(gè)整形數(shù)字表示叫做指紋。然后將這些生成的指紋存入索引以供對(duì)比查詢［21］。當(dāng)一個(gè)查詢文檔( query) 需要與索引中的文檔指紋做對(duì)比時(shí)，先按照同樣的方式為此查詢文檔生成指紋，然后將該指紋中的每一個(gè)特征分別與索引庫中的指紋進(jìn)行比對(duì)。特征找到匹配的量占特征數(shù)量的比值即為相似文檔的相似度估計(jì)。在設(shè)計(jì)數(shù)字指紋的過程中，一般需要考慮以下4個(gè)方面［21］: ①指紋生成算法，即映射子字符串到整形的hash 函數(shù)。②指紋顆粒度，即從文檔中提取的子字符串的大小。③指紋分辨率，即每個(gè)文檔指紋所含的特征的數(shù)量。④子字符串選取策略，即從文檔中選取子字符串的策略。

指紋生成算法

將字符串轉(zhuǎn)化為整形數(shù)字表示( 特征值) 的函數(shù)對(duì)于數(shù)字指紋有很大的影響。為了保證指紋生成的速度和精確度，一個(gè)指紋生成函數(shù)需要滿足以下幾個(gè)要求: 首先，生成的指紋必須是可再生成的，對(duì)于同樣的一個(gè)子字符串，所生成的特征值必須完全相同［28］; 其次，特征值的分布要盡可能地接近均勻分布［8］。對(duì)于任何數(shù)字指紋生成函數(shù)，不同子字符串生成相同特征值的情況( 散列碰撞Hash Collision) 理論上無法避免，而均勻分布的特征值可以將散列碰撞的發(fā)生概率降至最低; 最后函數(shù)的速度也非常重要，當(dāng)創(chuàng)建初始索引或是查詢文檔集時(shí)，需要生成大量的特征值。

M． Ｒabin［29］于1981 年提出了一種可行的字符串指紋生成算法用于字符串匹配和文件驗(yàn)證，算法如下:選取一個(gè)較小的素?cái)?shù)k( k( 17， 19…31， 61) ) ，然后從有限域GF( 2k ) 中2k － 2k個(gè)不可約多項(xiàng)式中隨機(jī)選取一個(gè)不可約多項(xiàng)式p( t) ∈Z2［t］，該多項(xiàng)式的次數(shù)顯然為k，該多項(xiàng)式可以表示為p( t) = tk + b1 tk － 1 + … + bk。對(duì)于長度為n 的字符串，使用x1，x2…xn表示每個(gè)字符的整形表示( ASCII) ，則這個(gè)字符串可以表示為多項(xiàng)式g( t) = x1 tn － 1 + x2 tn － 2 +… + xn。令gi( t) = x1 ti － 1 +… +xi，1≤i≤n，則有g(shù)i + 1 = gi* t + xi + 1，1≤i≤n － 1。然后定義余部珔g( t) 為多項(xiàng)式g( t) 模p 的余部Ｒes( g，p) ，這個(gè)余部可以表示為c1 kk － 1 +… + ck。則有:

通過上式可以看出，只有第一次計(jì)算需要對(duì)字符串的每一個(gè)文本單元( text symbol) 進(jìn)行計(jì)算，從第二個(gè)連續(xù)的字符串開始，則只需要進(jìn)行一次乘法運(yùn)算和一次加法運(yùn)算，然后再進(jìn)行模p( t) 的運(yùn)算即可，這樣每個(gè)字符串的計(jì)算都是實(shí)時(shí)的( in real time) 。M． Ｒabin 指出該算法對(duì)于兩篇長度分別為m 和n的文檔，若k ＞ log2nm∈－ 1，可以將散列碰撞所產(chǎn)生的錯(cuò)誤發(fā)生率控制在一個(gè)給定的參數(shù)∈下，即:

上述算法的一個(gè)缺點(diǎn)是隨機(jī)選取一個(gè)不可約多項(xiàng)式需要大量的運(yùn)算，一個(gè)較好的解決辦法是將所有低次的不可約多項(xiàng)式做成表，然后隨機(jī)地從表中抽取即可。隨后Ｒ． M． Karp 和Ｒabin［30］簡化了這套算法，而第一個(gè)將該數(shù)字指紋算法應(yīng)用于大型文檔集的是U．Manber［28］，他獨(dú)立發(fā)現(xiàn)了M． Ｒabin 的算法并將其用于相似文檔的檢測(cè)。其做法如下: 令t1，t2…tn表示字符串中的連續(xù)字節(jié)，則前50 個(gè)字字符串的指紋為:

而當(dāng)需要計(jì)算F2時(shí)，只需要添加最后一項(xiàng)的系數(shù)并刪除第一項(xiàng)即可:

由于每次運(yùn)算都需要計(jì)算( Ti·p49 ) mod M，因此可以提前將256 個(gè)值的結(jié)果進(jìn)行計(jì)算并制作成表，以大大提高計(jì)算效率。

指紋顆粒度

指紋顆粒度，即從文檔中提取的子字符串的大小。此變量對(duì)于指紋的精確度有著很大影響［31］。精細(xì)的指紋顆粒度可以減少偽匹配的數(shù)量，而粗糙的指紋顆粒度會(huì)對(duì)細(xì)小的修改過于敏感［8］。例如我們使用100個(gè)字作為顆粒度時(shí)，則對(duì)于100 個(gè)字的任意改動(dòng)都會(huì)影響指紋的產(chǎn)生，而事實(shí)上當(dāng)100 個(gè)字中僅有少量改動(dòng)時(shí)我們依然希望能夠?qū)⑵渥R(shí)別為一種抄襲。反之，當(dāng)使用1 或2 個(gè)字作為顆粒度時(shí)，我們會(huì)發(fā)現(xiàn)大量的匹配，而這其中的大多數(shù)往往只是常見的詞，對(duì)于抄襲無明顯的指示作用。U． Manber［28］在開發(fā)sif 系統(tǒng)時(shí)使用了50 個(gè)字節(jié)的顆粒度。S． Brin［3］沒有使用固定的顆粒度，而是以一個(gè)句子為單位。N． Shivakumar［32］的實(shí)驗(yàn)驗(yàn)證了使用句子作為顆粒度可以取得最好的效果，而N． Heintze［8］則使用30 － 45 個(gè)字符作為顆粒度。T．C． Hoad 等［21］的實(shí)驗(yàn)結(jié)果表明，上述的顆粒度都能保證較低的最高偽匹配( highest false match) ，但是在差別(separation) 指標(biāo)這一項(xiàng)，上述顆粒度的效果都不太理想，最終T． C． Hoad 提出了以3 或5 個(gè)單詞作為顆粒度。

指紋分辨率

指紋分辨率，即每個(gè)文檔指紋所含的特征的數(shù)量。理論上，指紋分辨率越大，對(duì)于抄襲識(shí)別的可提供的信息就越多，而結(jié)果也越準(zhǔn)確。但受限于文檔集的大小以及硬件機(jī)能，指紋分辨率往往不能設(shè)置過大，否則會(huì)給系統(tǒng)造成很大的壓力。常見的分辨率包括定量分辨率和定比例分辨率［8］: 定量分辨率是指每個(gè)文檔都含有特定量的指紋，而這個(gè)量不受文檔長度的影響，定量分辨率可提高系統(tǒng)的可擴(kuò)展性，缺點(diǎn)是對(duì)于大型文檔不能很好地表示其特征; 定比例分辨率是指按照文檔長度的不同選擇保存相應(yīng)數(shù)量的指紋，雖然這有助于提高特征表示的完整性，但是對(duì)于一篇數(shù)十萬詞的文檔，按照1∶ 100 的比例也需要保存幾千個(gè)指紋，對(duì)存儲(chǔ)和比對(duì)計(jì)算都提出了更高的要求。A． Chowdhury等［16］在I-Match 系統(tǒng)中使用了一種創(chuàng)新的指紋分辨率，即一篇文檔只生成一個(gè)指紋。I-Match 首先依據(jù)逆文檔頻率( inverse document frequency) 將文檔中最常用的詞和最不常用的詞全部剔除然后將剩余的詞按照unicode 編碼順序排列，然后使用SHA1 算法生成一個(gè)指紋。此技術(shù)的優(yōu)勢(shì)在于可以快速地識(shí)別兩篇幾乎類似的抄襲，但是對(duì)于包含關(guān)系則幾乎起不到作用。此技術(shù)可被應(yīng)用于抄襲檢測(cè)的預(yù)處理，協(xié)助劃定抄襲文檔的范圍，減少比對(duì)次數(shù)。A． Chowdhury 的實(shí)驗(yàn)表明利用I-Match 的指紋技術(shù)可比其他指紋技術(shù)節(jié)省4 /5的時(shí)間。

子字符串選取策略

選取全部數(shù)字指紋該策略最為簡單，并且匹配效果也最好，能夠保證識(shí)別出所有的抄襲［8］。該策略在存儲(chǔ)空間上對(duì)每篇文檔要求至少l － α + 1* | hashcode | 個(gè)字節(jié)，而每兩篇長度分別為m 和n 的文檔進(jìn)行對(duì)比的時(shí)間復(fù)雜度是O( mn) ，從存儲(chǔ)空間占用和計(jì)算時(shí)間上看，該方法并不能很好地應(yīng)用到生產(chǎn)環(huán)境，但是對(duì)于系統(tǒng)性能的評(píng)估，該方法還是較好的選擇。每隔i 個(gè)取一個(gè)數(shù)字指紋該策略明顯比選取全部數(shù)字指紋策略要占用更少的存儲(chǔ)空間，并且由于指紋數(shù)量的減少，兩個(gè)文檔進(jìn)行對(duì)比時(shí)所耗費(fèi)的時(shí)間也更少。但是該策略在一個(gè)文檔出現(xiàn)如下情況時(shí)缺乏魯棒性，包括打亂文檔的內(nèi)部順序、在文檔中插入內(nèi)容或刪除文檔中的一段內(nèi)容。事實(shí)上，只要文檔中插入一個(gè)字符就會(huì)造成所有的k-gram 發(fā)生一個(gè)字節(jié)的位移，導(dǎo)致所生成的數(shù)字指紋與插入前所生成的數(shù)字指紋完全不同。

錨文本( anchor) 定位數(shù)字指紋該策略由U．Manber［28］提出，使用特定的文本對(duì)原文進(jìn)行劃分并生成指紋。該策略的優(yōu)勢(shì)在于不受文檔重排序、插入或者刪除的影響，但是該策略會(huì)嚴(yán)重依賴錨文本的選擇，應(yīng)盡量選取那些常見但又不至于過于常見的錨文本。優(yōu)秀的錨文本選擇策略會(huì)使所選取的字符串分布較為平均，而失敗的錨文本選擇策略則會(huì)直接導(dǎo)致系統(tǒng)的失效。由于該策略對(duì)于錨文本的選擇依賴性很強(qiáng)，因此對(duì)于某一個(gè)文檔庫合適的錨文本對(duì)另外一個(gè)文檔庫則不見得合適，例如法律領(lǐng)域的文檔庫中的錨文本一般無法應(yīng)用于情報(bào)學(xué)領(lǐng)域的文檔庫中。在確定了字符串選取策略后，可應(yīng)用Ｒ． A． Finkel［26］提出的選取策略，具體策略參見哈希斷點(diǎn)數(shù)字指紋。

哈希斷點(diǎn)數(shù)字指紋該策略由U． Manber［28］提出，將錨文本變?yōu)樘囟ǖ臄?shù)字。該策略的不足之處在于，當(dāng)一個(gè)常見的字符串模p 為0 時(shí)，則會(huì)造成選取的字符串非常短，若所選擇的p 恰巧不能使任何字符串模p 為0，則會(huì)造成將全文作為一個(gè)字符串進(jìn)行指紋生成。此外國內(nèi)學(xué)者劉韻毅［33］也提出了相似的指紋選取策略。在確定了如何分割文檔后，Ｒ． A． Finkel［26］提出了兩種選擇策略，這兩種策略都基于保留適當(dāng)長度的數(shù)字指紋，過短的數(shù)字指紋匹配并不代表抄襲，而長數(shù)字指紋匹配雖然很有可能意味著抄襲，但很少有抄襲者在不改原文的情況下大段抄襲，因此應(yīng)該去掉那些較長的和較短的數(shù)字指紋而僅保留長度適中的數(shù)字指紋。首先令n 為分割后生成數(shù)字指紋的數(shù)量，m 為數(shù)字指紋長度的中位數(shù)，s 為數(shù)字指紋長度的標(biāo)準(zhǔn)差，b 為常數(shù)，L 為任意數(shù)字指紋的長度，則可使用如下兩種選取策略: 開方法，即保留|槡n | 個(gè)長度L 最接近m的數(shù)字指紋; 方差法，所保留的數(shù)字指紋需滿足| L － m|≤bs，b 設(shè)為0． 1，然后逐漸增大，直至選擇|槡n| 個(gè)。

選取n 個(gè)最小數(shù)字指紋該策略由N．Heintze［8］提出。首先對(duì)文檔的所有子字符串生成數(shù)字指紋，然后對(duì)同一個(gè)文檔的全部指紋進(jìn)行升序排列，并選取最小的n 個(gè)數(shù)字指紋。這個(gè)策略的優(yōu)勢(shì)在于，一個(gè)文檔所需要選取的指紋數(shù)是確定的，因此系統(tǒng)可以不必受限制于短小的文檔，對(duì)于大型文檔系統(tǒng)也可以進(jìn)行注冊(cè)，系統(tǒng)的可擴(kuò)展性增強(qiáng)。但是也正是由于這個(gè)原因，導(dǎo)致該策略對(duì)于大型文檔只能識(shí)別出相似，無法識(shí)別出抄襲，需要進(jìn)一步識(shí)別

Winnowing 選取算法該算法由S． Schleimer等［15］提出，國內(nèi)學(xué)者鄒杜等［35］也對(duì)此算法做了深入研究。首先定義兩個(gè)參數(shù)t、k，假如一個(gè)子字符串匹配至少t 長度，則判定為一個(gè)抄襲，假如一個(gè)子字符串匹配

的長度小于k，則忽略。對(duì)一個(gè)文檔的全部k-gram 生成hash 序列h1…h(huán)n，然后令滑窗大小w = t － k + 1。對(duì)于hash 序列中的一個(gè)位置i 滿足1≤i≤n － w + 1 定義了一個(gè)hash 滑窗hi…h(huán)i + w-1。每個(gè)滑窗中至少取一個(gè)hash 值作為文檔的指紋，在選取時(shí)選擇滑窗中最小的hash 值，若出現(xiàn)兩個(gè)相同的最小hash 值，則選擇最右邊的一個(gè)。該算法最大的優(yōu)勢(shì)在于，最大限度地減小了各數(shù)字指紋之間的距離，因此可以實(shí)現(xiàn)數(shù)字指紋在文檔中的均勻分布。

基于語義詞典的中文抄襲識(shí)別

目前的抄襲檢測(cè)主要針對(duì)文本的改寫、組的抄襲檢測(cè)，即所謂的外部抄襲檢測(cè)( extrinsicplagiarism detection) ，與之相對(duì)應(yīng)的是近幾年的研究熱點(diǎn)集中在內(nèi)在抄襲檢測(cè)( intrinsic plagiarismdetection) ［13］。內(nèi)在抄襲檢測(cè)與作者驗(yàn)證( authorshipverification) 等使用類似的技術(shù)，均是對(duì)文檔的作品風(fēng)格特征進(jìn)行統(tǒng)計(jì)分析，例如判定各個(gè)段落的詞匯豐富度、文體復(fù)雜度等，E． Stamatatos［45］和B． Stein 等［46］對(duì)當(dāng)前內(nèi)在抄襲檢測(cè)的研究現(xiàn)狀做了全面細(xì)致的分析總結(jié)。而隨著抄襲的越來越隱蔽，抄襲者對(duì)于思想的抄襲等越來越多，內(nèi)在抄襲檢測(cè)將發(fā)揮其作用。筆者認(rèn)為，內(nèi)在抄襲檢測(cè)也將是未來的研究重點(diǎn)。合、調(diào)整順序等的識(shí)別，而基于語義詞典的中文識(shí)別發(fā)展緩慢，將是今后的發(fā)展重點(diǎn)。普林斯頓大學(xué)于1995 年推出了第一個(gè)英語詞關(guān)系詞典WordNet［36］，為研究者做語義級(jí)別的研究提供了基本工具。E． Agirre［37］于同一年利用WordNet 提出了一種語義消歧方法，選擇所有開放性詞類，并取5 個(gè)單詞的窗口大小( window size) ，以周圍4 個(gè)單詞作為上下文，對(duì)中間第3 個(gè)詞進(jìn)行消歧處理，為基于語義的識(shí)別提供了消歧的基礎(chǔ)。隨后J．J． Jiang［38］于1997 年提出了一種基于WordNet 單詞距離和單詞節(jié)點(diǎn)信息量的混合相似度計(jì)算法，使語義消歧能力得到了提高。國內(nèi)學(xué)者王瑞琴［39］、田久樂［40］等也基于同義詞詞典做了相關(guān)的消歧研究。而目前尚未出現(xiàn)成熟的中文詞關(guān)系詞典，東北大學(xué)的張俐等［41］于2003 年提出了一種中文WordNet 制作方法，該方法通過翻譯實(shí)現(xiàn)了一種從英文版到中文版的映射，但準(zhǔn)確性不高，不足以應(yīng)付實(shí)際生產(chǎn)環(huán)境。筆者認(rèn)為，在今后一段時(shí)間，隨著各類中文關(guān)系詞典的建設(shè)，基于類似詞典的抄襲識(shí)別研究將是研究重點(diǎn)。

基于數(shù)字指紋的大規(guī)模中文抄襲檢測(cè)

由于數(shù)字指紋的匹配主要依靠排序算法，而由排序算法( quicksort) 的時(shí)間復(fù)雜度O( nLgn) 可知指紋數(shù)量的多少對(duì)計(jì)算效率的影響很大。N． Shivakumar［31］對(duì)150GB 的文檔使用數(shù)字指紋方法進(jìn)行復(fù)制檢驗(yàn)，針對(duì)上述問題，提出了一種基于概率統(tǒng)計(jì)的高效識(shí)別方法。該方法需要分別對(duì)全文和子字符串生成指紋，首先通過掃描全文指紋剔除完全相同的文檔，然后對(duì)剩余文檔的子字符串指紋使用CoarseCount 算法進(jìn)行掃描識(shí)別。對(duì)于識(shí)別出粗糙結(jié)果，通過二次掃描剔除偽匹配。對(duì)于不同的指紋選取策略，該方法能提高22% －33%的效率，這得利于排序階段排序量的減少。而隨著Hadoop 等Map-Ｒeduce 平臺(tái)的出現(xiàn)，在Partitioning階段自動(dòng)完成了上述所需的排序，大大提高了運(yùn)算效率。

然而，上述基于數(shù)字指紋的大規(guī)模抄襲檢測(cè)，僅僅停留在完全抄襲的檢測(cè)上，對(duì)于修改后的抄襲，傳統(tǒng)的數(shù)字指紋幾乎無法識(shí)別。而Charikar［43］ 提出的Ｒounding Algorithm 為細(xì)微修改后的數(shù)字指紋抄襲檢測(cè)奠定了理論基礎(chǔ)。Google 公司的G． S． Manku等基于Ｒounding Algorithm 提出了一種大規(guī)模識(shí)別英文雷同網(wǎng)頁的數(shù)字指紋，該方法已經(jīng)被成功應(yīng)用于Google搜索引擎。而在中文方面，目前缺乏類似的研究，筆者認(rèn)為，基于數(shù)字指紋的大規(guī)模中文抄襲檢測(cè)也將是今后的研究重點(diǎn)。

內(nèi)在抄襲檢測(cè)

上述傳統(tǒng)的抄襲檢測(cè)技術(shù)均是基于文檔注冊(cè)機(jī)制的抄襲檢測(cè)，即所謂的外部抄襲檢測(cè)( extrinsicplagiarism detection) ，與之相對(duì)應(yīng)的是近幾年的研究熱點(diǎn)集中在內(nèi)在抄襲檢測(cè)(intrinsic plagiarismdetection) ［13］。內(nèi)在抄襲檢測(cè)與作者驗(yàn)證( authorshipverification) 等使用類似的技術(shù)，均是對(duì)文檔的作品風(fēng)格特征進(jìn)行統(tǒng)計(jì)分析，例如判定各個(gè)段落的詞匯豐富度、文體復(fù)雜度等，E．Stamatatos［45］和B． Stein 等［46］對(duì)當(dāng)前內(nèi)在抄襲檢測(cè)的研究現(xiàn)狀做了全面細(xì)致的分析總結(jié)。而隨著抄襲的越來越隱蔽，抄襲者對(duì)于思想的抄襲等越來越多，內(nèi)在抄襲檢測(cè)將發(fā)揮其作用。筆者認(rèn)為，內(nèi)在抄襲檢測(cè)也將是未來的研究重點(diǎn)。本文總結(jié)了當(dāng)前學(xué)術(shù)抄襲檢測(cè)的現(xiàn)狀，對(duì)于基于向量空間的算法和基于指紋識(shí)別的算法進(jìn)行了細(xì)致的分析。通過分析可以看出，向量空間模型、相對(duì)頻率模型、潛在語義分析模型、KD-Tree 模型等信息檢索領(lǐng)域常見的算法模型都已被應(yīng)用到了抄襲檢測(cè)中。而與之相比，各種基于數(shù)字指紋的算法的引入也大大提高了計(jì)算效率。通過分析可以看出，抄襲檢測(cè)自出現(xiàn)以來已經(jīng)吸引了越來越多的科研者關(guān)注，得到了長足的發(fā)展?？偟膩碚f，在當(dāng)前的學(xué)術(shù)環(huán)境下，學(xué)術(shù)抄襲檢測(cè)依然是必不可少的，這就要求抄襲檢測(cè)必須不斷提高檢測(cè)的能力。當(dāng)前的抄襲檢測(cè)基本是基于文本字面的，并未達(dá)到語義級(jí)別的抄襲檢測(cè)。而現(xiàn)如今，在學(xué)術(shù)界卻存在著大量思想抄襲而未被發(fā)現(xiàn)的情況，這主要是由于學(xué)者沒有充足的時(shí)間去長期追蹤自己的觀點(diǎn)，而出版商也沒有非常好的方法去識(shí)別這類抄襲。因此，對(duì)于語義級(jí)別的抄襲檢測(cè)將是今后研究的重點(diǎn)。除此之外，文章的結(jié)構(gòu)化特征提取與利用、內(nèi)在抄襲檢測(cè)研究也將為抄襲檢測(cè)提供更加豐富的參考。