引言

剽竊他人研究成果，篡改或偽造數(shù)據(jù)并繼續(xù)發(fā)表，給學(xué)術(shù)研究帶來嚴(yán)重危害。建立一種快速、準(zhǔn)確的論文抄襲檢測模型具有現(xiàn)實(shí)意義，論文抄襲檢測算法已成為當(dāng)前研究的熱點(diǎn)。與英文學(xué)術(shù)論文不同，中文學(xué)術(shù)論文語法形式靈活多變，語用歧義性大，且詞與詞之間無明顯分隔，所以檢測難度較大。目前針對(duì)中文的檢測方法主要包括篇章結(jié)構(gòu)相似度方法、段落相似度方法和句子相似度方法[1]。其中句子相似度方法結(jié)構(gòu)劃分合理，檢測精度較高，較其他方法有明顯優(yōu)勢。句子相似度的計(jì)算方法主要有詞頻統(tǒng)計(jì)方法、語義詞典方法、依存樹方法和編輯距離方法。詞頻統(tǒng)計(jì)方法[2]采用基于向量空間模型的TF-IDF 方法，將句子看作由獨(dú)立詞條組成的向量空間，用點(diǎn)積法和余弦法計(jì)算相似度。該方法丟失文檔結(jié)構(gòu)信息，且檢測速度較低。語義詞典方法[3]主要利用語義資源，通過計(jì)算句中詞語相似度來計(jì)算句子的相似度。該方法對(duì)于一些存在對(duì)義或反義的詞語識(shí)別率較低，不利于詞語的極性判斷。依存樹方法[4]的句法結(jié)構(gòu)用句子謂語中心詞及其直接支配成分來表示，分析結(jié)果可看作一棵簡化了的依存樹，以此計(jì)算依存樹之間的相似度。該方法對(duì)句子各成分間依存關(guān)系分析的準(zhǔn)確率不高，導(dǎo)致實(shí)際應(yīng)用性不強(qiáng)。編輯距離方法[5]以普通編輯距離算法為基礎(chǔ)，用詞語取代單個(gè)的漢字或字符作為基本的編輯單元參與運(yùn)算，加入詞語的語義相似信息確定詞語之間的替換代價(jià)。該方法沒有考慮句子中不同詞語對(duì)整體文檔貢獻(xiàn)的不一致，也未能兼顧歸一化問題。上述算法適用于詞條空間維數(shù)小且依賴程度較高的樣本，側(cè)重理解句子的語義信息，計(jì)算代價(jià)較高。

本文提出了一種新的論文抄襲檢測模型，首先通過局部詞頻指紋算法（Local Word-Frequency Fingerprint，LWFF）對(duì)大規(guī)模文檔進(jìn)行快速檢測，找出疑似抄襲文檔。然后利用最長有序公共子序列算法（Longest Sorted Common Subsequence，LSCS）對(duì)疑似抄襲文檔內(nèi)容進(jìn)行精確檢測，標(biāo)注抄襲細(xì)節(jié)。該模型改進(jìn)了前面幾種檢測方法結(jié)構(gòu)不合理、精度不高等問題，在標(biāo)準(zhǔn)中文數(shù)據(jù)集SOGOU-T上進(jìn)行的實(shí)驗(yàn)表明，該算法具有較高的準(zhǔn)確率和召回率。

局部詞頻指紋算法

局部詞頻指紋算法的思想是將句子看成文檔的基本構(gòu)成元素，對(duì)其進(jìn)行有效關(guān)鍵詞提取，并排序重構(gòu)，根據(jù)編碼和詞頻聯(lián)合方式獲取句子指紋，以此計(jì)算文本間相似度。以句子為單位生成向量空間模型，將一篇文檔看作若干句子的集合D，D=i = 1NSi 。其中，N 為句子個(gè)數(shù)，Si = (w1....w2....wj....wn) ，wj 為句子Si 中第j 個(gè)非重復(fù)關(guān)鍵詞的權(quán)重，根據(jù)公式（1）計(jì)算

權(quán)重。

其中，Enc(kj) 為關(guān)鍵字詞kj 的編碼，tfj(S) 為關(guān)鍵詞kj 在句子中出現(xiàn)的頻率，N 為文檔中句子的總數(shù)，nj 為kj 出現(xiàn)的次數(shù)。根據(jù)公式（2）計(jì)算每個(gè)向量的指紋fpi 。

其中，n 為句子Si 中非重復(fù)關(guān)鍵詞的個(gè)數(shù)，p 為一個(gè)32 位或64位的大質(zhì)數(shù)。選取全指紋，將待檢測文檔與樣本庫中每一文檔進(jìn)行檢測。利用公式（3）計(jì)算文檔相似度[6]。

其中，F(xiàn)P(Ax) 和FP(Bx) 為文檔A、B 生成的指紋集合。利用d(AB) = 1 - sim(AB) 計(jì)算文檔之間的相似距離，根據(jù)相似距離d(AB) 確定文檔抄襲程度。

LWFF算法能夠從大規(guī)模樣本中快速檢測出疑似抄襲文檔，但并未對(duì)局部語句相似作進(jìn)一步研究，沒有給出抄襲細(xì)節(jié)，而對(duì)句子相似度的檢測能夠解決這個(gè)問題。由LWFF算法確定被檢測目標(biāo)文檔屬于抄襲后，利用最長有序公共子序列算法來計(jì)算句子相似度，標(biāo)注抄襲細(xì)節(jié)。

基于最長有序公共子序列的句子相似度檢測算法

最長公共子序列

最長公共子序列[7]是計(jì)算文檔句子相似度的有效手段，解最長公共子序列問題的常規(guī)方法是窮舉搜索法，但該方法需要指數(shù)時(shí)間。最長公共子序列問題存在最優(yōu)子結(jié)構(gòu)性質(zhì)[8]，設(shè)序列X =< x1x2xm > 和Y =< y1y2yn > 的一個(gè)最長公共子序列Z =< z1z2zk > ，則：

若xm = yn ，則zk = xm = yn 且zk - 1 是Xm- 1 和Yn - 1 的最長公共子序列；

若xm 1 yn 且zk 1 xm ，則Z 是Xm- 1 和Y 的最長公共子序列；

若xm 1 yn 且zk 1 yn ，則Z 是X 和Yn - 1 的最長公共子序列。

其中Xm- 1 =< x1,x2,....xm- 1 >，Yn - 1 =< y1,y2,.....y n - 1>，Zk - 1 =< z1z2.....z k - 1> 。

要找出X =< x1x2xm > 和Y =< y1y2yn > 的最長公共子序列，可按以下方式遞歸地進(jìn)行：當(dāng)xm = yn 時(shí)，找出Xm- 1和Yn - 1 的最長公共子序列，然后在其尾部加上xm 或yn 即可得到。當(dāng)xm 1 yn 時(shí)，必須解兩個(gè)子問題，即找出Xm- 1 和Y 的個(gè)最長公共子序列及X 和Yn - 1 的一個(gè)最長公共子序列，這兩個(gè)公共子序列中較長者即為X 和Y 的一個(gè)最長公共子序列。由于在所考慮的子問題空間中，總共有θ(m′ n) 個(gè)不同的子問題，算法的時(shí)間復(fù)雜度要達(dá)到O(mn) 。

用動(dòng)態(tài)規(guī)劃算法自底向上計(jì)算最優(yōu)值能提高算法的效率，將待求解的問題分解成若干個(gè)相互聯(lián)系的子問題，先求解子問題，然后從m′ n 個(gè)子問題的解得到原問題的解。對(duì)于重復(fù)出現(xiàn)的子問題，只在首次出現(xiàn)時(shí)對(duì)它求解，并將結(jié)果保存，當(dāng)再次遇到時(shí)直接引用結(jié)果，利用動(dòng)態(tài)規(guī)劃算法可將時(shí)間復(fù)雜度減少至O(m′ n) 。

通過計(jì)算兩個(gè)句子的最長公共子序列，可以獲取語句間的重復(fù)信息，但動(dòng)態(tài)規(guī)劃算法計(jì)算代價(jià)較高，不適合用于大規(guī)模文檔檢測，為此本文提出了一種有序的最長公共子序列算法。

有序的最長公共子序列匹配算法

定義1 經(jīng)過LWFF算法檢測屬于抄襲的文檔稱為目標(biāo)文檔（Destination Text，DT）。作為檢測依據(jù)的文檔稱為源文檔（Source Text，ST）。

設(shè)DT 中任一語句塊X =< x1x2xm > 和ST 中任一語句塊Y =< y1y2yn > 已具有相同次序，其中xi(i = 12m)和yj( j = 12n) 分別為語句塊X 和Y 中的有效詞元素，并已按關(guān)鍵詞詞性ID[9]排序。接下來計(jì)算X 和Y 的最長公共子序列。此問題歸結(jié)為串匹配問題，一個(gè)典型的計(jì)算方法是Brute-Force 方法，從目標(biāo)串S = "s0s1sn - 1" 的第一個(gè)字符開始和模式串T = "t0t1tm- 1" 中的第一個(gè)字符比較，若相等，則繼續(xù)逐個(gè)比較后續(xù)字符，否則，從目標(biāo)串S 的第2 個(gè)字符開始重新與模式串T 的第一個(gè)字符進(jìn)行比較，依次類推，若從模式串S的第i 個(gè)字符開始，每個(gè)字符依次和目標(biāo)串T 中的對(duì)應(yīng)字符相等，則匹配成功，否則失敗。由于已對(duì)語句塊元素進(jìn)行排序，所以不存在指針回溯問題，使該算法效率大大提高，時(shí)間復(fù)雜度可以達(dá)到O(m+ n) 。

算法步驟

步驟1 將源文檔ST 和目標(biāo)文檔DT 以句子為單位進(jìn)行預(yù)處理，分詞，去除虛詞和停用詞，保留部分記為關(guān)鍵詞。

步驟2 將每句看作一個(gè)語句塊，并按關(guān)鍵詞詞性ID 排序。

步驟3 從目標(biāo)文檔DT 中提取句子Xi ，從源文檔ST 中提取句子Yj 計(jì)算最長公共子序列Zk 。

步驟4 根據(jù)Zk ，計(jì)算Xi 和Yj 的相似度：

步驟5 句子相似度閾值為k ，若大于k ，則認(rèn)為兩句相似，輸出XiYj 以及公共序列Zk ；否則，認(rèn)為兩句不相似，進(jìn)行下一句判斷。

根據(jù)LSCS算法，能夠得到兩篇論文的語句相似信息和重復(fù)內(nèi)容依據(jù)，為檢測抄襲行為提供更細(xì)致的證據(jù)。

實(shí)驗(yàn)

本文實(shí)驗(yàn)所用語料為標(biāo)準(zhǔn)中文數(shù)據(jù)集SOGOU-T，從中選取800 篇文檔作為基礎(chǔ)數(shù)據(jù)集（Fundamental Datasets，F(xiàn)D），經(jīng)LWFF 算法預(yù)處理后形成指紋存入數(shù)據(jù)庫，作為抄襲檢測依據(jù)。測試文檔集由兩部分文檔組成：一部分從基礎(chǔ)數(shù)據(jù)集中選?。?00 篇），并作定不同種類的修改，構(gòu)成論文抄襲集（Mod-ify Texts，MT）；另一部分從SOGOU-T中隨機(jī)選?。?0 篇），構(gòu)成隨機(jī)測試集（Random Texts，RT）。定義2 RTn 表示從隨機(jī)集RT 中選取n 個(gè)文檔；MTin 表示從抄襲集MT 中選取n 個(gè)作第i 類修改的文檔，操作種類見表1 。

實(shí)驗(yàn)中采用通用的準(zhǔn)確率、召回率和F1 作為評(píng)價(jià)指標(biāo)[10]。

A =檢測相似且實(shí)際也相似的文檔數(shù)

B =檢測相似但實(shí)際不相似的文檔數(shù)

C =實(shí)際相似但檢測不相似的文檔數(shù)

實(shí)驗(yàn)環(huán)境為CPU Pentium 2.93 GHz ，內(nèi)存1 GB ，操作系統(tǒng)Windows XP。語句相似距離閾值k 取0.4 。表2 給出了本文模型在作不同修改測試集上進(jìn)行檢測的準(zhǔn)確率、召回率和F1 值。

表3 給出了本文模型和其他算法在準(zhǔn)確率、召回率和F1值三個(gè)檢測參數(shù)上的對(duì)比。

實(shí)驗(yàn)結(jié)果表明，本文模型較詞頻統(tǒng)計(jì)和語義詞典方法有較高的準(zhǔn)確率、召回率和F1 值，彌補(bǔ)了其他方法對(duì)語句表層信息挖掘能力的不足，實(shí)現(xiàn)了對(duì)目標(biāo)文檔的局部精確檢測，并對(duì)抄襲內(nèi)容作詳細(xì)標(biāo)注。檢測速度高于語義詞典，但略低于詞頻統(tǒng)計(jì)方法，其原因是本文模型除了詞頻統(tǒng)計(jì)外，還要作疑似抄襲文檔的精確檢測。

結(jié)束語

提出了一種基于句子相似度的論文抄襲檢測模型，首先用LWFF算法確定被檢測目標(biāo)文檔是否屬于抄襲，然后利用最長有序公共子序列算法來計(jì)算句子間相似度，實(shí)現(xiàn)了對(duì)目標(biāo)文檔（DT）抄襲細(xì)節(jié)的標(biāo)注。在一定程度上克服了其他算法對(duì)句子局部信息挖掘能力的不足，提高了檢測精度。在標(biāo)準(zhǔn)中文數(shù)據(jù)集SOGOU-T上的檢測結(jié)果驗(yàn)證了該模型的有效性，一定程度上優(yōu)于詞頻統(tǒng)計(jì)方法和語義詞典方法，但有些問題還有待進(jìn)一步研究，如構(gòu)建句子語義相似度快速檢測模型，以及求解某一語句唯一最長有序公共子序列等。

冷強(qiáng)奎1，秦玉平1，王春立2

1.渤海大學(xué)信息科學(xué)與工程學(xué)院，遼寧錦州121000

2.大連海事大學(xué)信息科學(xué)技術(shù)學(xué)院，遼寧大連116026