朱 波, 鄭 虹, 孫琳琳

(長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 吉林 長(zhǎng)春 130012)

代碼抄襲檢測(cè)中串匹配算法的比較

朱 波, 鄭 虹*, 孫琳琳

(長(zhǎng)春工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院， 吉林 長(zhǎng)春 130012)

對(duì)程序代碼抄襲檢測(cè)中多種字符串匹配算法的實(shí)現(xiàn)原理進(jìn)行了描述,給出匹配算法計(jì)算相似度的公式以及相對(duì)應(yīng)的時(shí)間復(fù)雜度。由于字符串匹配算法在程序代碼抄襲檢測(cè)中應(yīng)用較為廣泛，對(duì)其中的B-F(Brute-Force)樸素算法、LCS(Longest Common Subsequence)最長(zhǎng)公共字串算法、GST(Greedy String Tiling)貪心字符串匹配算法等經(jīng)典算法的總結(jié)比較是一件有意義的研究工作。

字符串匹配算法； 抄襲檢測(cè)； 最長(zhǎng)公共字串； GST

0 引 言

隨著信息社會(huì)的發(fā)展，眾多應(yīng)用領(lǐng)域中都涉及到了字符串的匹配研究，如在程序抄襲檢測(cè)[1]、知識(shí)產(chǎn)權(quán)保護(hù)[2]、網(wǎng)頁(yè)搜索[3]等領(lǐng)域都有串匹配算法的應(yīng)用。在程序類設(shè)計(jì)課程中，作業(yè)抄襲現(xiàn)象普遍存在。澳大利亞蒙納什(Monash)大學(xué)對(duì)其學(xué)生中的代碼抄襲現(xiàn)象進(jìn)行調(diào)查統(tǒng)計(jì)顯示：高達(dá)85.4%的學(xué)生承認(rèn)抄襲過(guò)他人的作業(yè)[4]。為扼制計(jì)算機(jī)課程教學(xué)中的不良學(xué)風(fēng)，高效率的代碼抄襲檢測(cè)研究日趨重要。而字符串相似性匹配算法的研究以及相似度的計(jì)算是抄襲檢測(cè)中的關(guān)鍵問(wèn)題。

目前，字符串相似性匹配算法有很多，如B-F算法、KMP算法、動(dòng)態(tài)程序設(shè)計(jì)算法、GST算法等。這些匹配算法因?yàn)槠鋵?shí)現(xiàn)的原理不同，算法效率和應(yīng)用的領(lǐng)域也有一些差異。

1 相關(guān)定義

在程序代碼抄襲檢測(cè)過(guò)程中，程序之間的相似程度可以通過(guò)相似度的值來(lái)判定。程序間的相似度越高，程序間存在抄襲的可能性也就越大；相反，相似度越低，抄襲的可能性就越小。但是，不能僅僅因?yàn)閭€(gè)別語(yǔ)句的相同就判定為抄襲，只有當(dāng)相似度的值超過(guò)某個(gè)設(shè)定的閾值時(shí)，才能判定為抄襲。

1.1基本概念

簡(jiǎn)單介紹幾個(gè)在算法中用到的概念：

1)文本串(也稱為主串)：主要是指在其中查找子字符串的相對(duì)較長(zhǎng)的字符串T。

2)模式串(也稱為模式)：主要是指在文本串T 中查找的需要驗(yàn)證匹配的字符串P。

3)精確串匹配算法：查找與模式串完全相等的子串的出現(xiàn)位置的算法。

4)近似串匹配算法：查找與特定模式串在一定范圍內(nèi)相似的所有子串的算法。

1.2相似度定義

Yamamoto T[5]等給出兩個(gè)軟件系統(tǒng)的相似度的定義。對(duì)于兩個(gè)軟件P和X，軟件P是由元素P1,P2,…,Pm組成，P的集合構(gòu)成表示為：{P1,P2,…,Pm}。同樣，軟件X由元素X1,X2,…,Xn組成,其元素的集合表示為{X1,X2,…,Xn}。其中P，X中的元素可以表示軟件P和X中的文件或者代碼行。

假設(shè)能夠求出Pi與Xj(1≤i≤m且1≤j≤n)間的匹配，用集合Rs表示所有的匹配對(duì)(Pi,Xj),其中Rs?P×X，則P和X的相似性S的定義為：

(1)

根據(jù)式(1)可以看出,相似性S為一個(gè)比值，它是由Rs中元素的個(gè)數(shù)比上P和X中元素的個(gè)數(shù)和所得。如果Rs較小，相應(yīng)的S也較小。當(dāng)Rs=?時(shí)，S=0；當(dāng)P和X完全相等的時(shí)候，此時(shí)S=1，則說(shuō)明軟件P和X存在抄襲現(xiàn)象。

目前對(duì)于相似度沒(méi)有統(tǒng)一的定義，而程序代碼的相似度與上述軟件系統(tǒng)的相似度相同，故可將相似度定義為：定量的比較兩個(gè)程序源代碼之間的相關(guān)性，其結(jié)果一般用一個(gè)具體的數(shù)值來(lái)表示。

2 常見(jiàn)串匹配算法比較研究

2.1 B-F算法

B-F匹配算法(樸素算法)即蠻力匹配算法，算法比較簡(jiǎn)單，很適合應(yīng)用于一些小規(guī)模的串匹配。

B-F算法是將模式串和文本串的字符元素分別放置在數(shù)P[m-1],T[n-1]中，數(shù)組下標(biāo)從0開(kāi)始,并且有n≥m。從文本串T=“T0,T1,Tn-1”的第一個(gè)字符T0開(kāi)始與模式串P=“P0,P1,…,Pm-1”的第一個(gè)字符P0對(duì)應(yīng)比較，如果相等，就繼續(xù)比較T和P后面的字符；如果不相等，從文本串的第二個(gè)字符P1開(kāi)始重新與模式串的第一個(gè)字符P0進(jìn)行比較，如此循環(huán)往復(fù)直至匹配結(jié)束。如果到匹配結(jié)束時(shí)，存在模式串與文本串中有一段連續(xù)的字符序列，則表示匹配成功，此時(shí)返回模式串P中第一個(gè)匹配字符在文本串中的起始匹配位置下標(biāo)；如果直到匹配結(jié)束時(shí)，不存在一個(gè)和模式串相同的字符串，則代碼匹配不成功，返回一個(gè)-1。

由算法的描述可知，算法的時(shí)間復(fù)雜度為O(m(n-m+1))，算法效率并不是太高。因?yàn)锽-F算法屬于精確字符串匹配算法，其多應(yīng)用于小規(guī)模的文本檢測(cè)等精準(zhǔn)度要求較高的領(lǐng)域。

2.2KMP算法

KMP(Knuth-Morris-Pratt)算法是對(duì)B-F算法的一種改進(jìn)算法，由DEKnuth，JHMorris和VRPratt在1977年提出。

KMP算法主要是對(duì)樸素算法做了一些改進(jìn)，當(dāng)發(fā)現(xiàn)文本串和模式串字符的某次匹配比較不相等的時(shí)候，文本串的查找指針不需要回溯到串起始位置，而是通過(guò)已經(jīng)得到的“部分匹配”結(jié)果將模式串向右進(jìn)行滑動(dòng)若干距離，然后再?gòu)幕瑒?dòng)后的新位置繼續(xù)進(jìn)行比較。例如，文本串T=“acacbbc”,模式串P=“acbb”，利用KMP算法匹配過(guò)程如圖1所示。

在第一輪匹配過(guò)程中,當(dāng)文本串第3個(gè)字符和模式串中第3個(gè)字符不相等時(shí),模式串向右“滑動(dòng)”。在第二輪匹配中就是用模式串P的第1個(gè)字符代替第3個(gè)字符與文本串的第3個(gè)字符進(jìn)行比較，依次完成匹配過(guò)程。

圖1 KMP算法匹配過(guò)程

通過(guò)對(duì)KMP算法的描述可知，算法的時(shí)間復(fù)雜度近似為O(m+n)，其最大的特點(diǎn)是文本串不需要回溯，具有很高的時(shí)間優(yōu)越性。在文本檢測(cè)和網(wǎng)絡(luò)安全方面都有應(yīng)用，是一種效率較高的精確串匹配算法。

2.3LCS算法

LCS算法,又稱最長(zhǎng)公共子序列算法[6-7]，其主要用于解決LCS問(wèn)題。

LCS算法是將給定的兩個(gè)字符串(文本串和模式串)分別刪去零個(gè)或者多個(gè)字符，在不改變剩余字符順序的同時(shí)，所得到的長(zhǎng)度最長(zhǎng)的相同字符序列。LCS即為文本串和模式串的最長(zhǎng)公共子序列，除它之外，再也無(wú)法找出比它更長(zhǎng)的子串。因?yàn)樵谄ヅ鋾r(shí)兩個(gè)串可以有多個(gè)長(zhǎng)度相同的最大公共子序列，所以LCS可以有多個(gè)。例如，文本串T=“abcdefghmnopq”,模式串P=“mabxypqfgh”，利用LCS算法匹配結(jié)果如圖2所示。

圖2 LCS算法匹配結(jié)果

根據(jù)式(1)得到LCS算法相似度計(jì)算式(2)，并根據(jù)公式計(jì)算得到文本串T和模式串P的相似度S為：

(2)

由算法相關(guān)描述可知，LCS算法的時(shí)間復(fù)雜度為O(m+n)，已經(jīng)證明LCS算法的時(shí)間復(fù)雜度不能小于O(mlog(n))[8]。

LCS算法是有序的，也就是說(shuō)得到的所有子串都是嚴(yán)格有序的，這就對(duì)于改變書(shū)寫(xiě)順序的模式串的檢測(cè)失去了作用。LCS算法多應(yīng)用于文件版本比較以及疾病監(jiān)測(cè)等領(lǐng)域。

2.4動(dòng)態(tài)程序設(shè)計(jì)

動(dòng)態(tài)程序設(shè)計(jì)(Dynamic Programming)[9]曾應(yīng)用于YAP2系統(tǒng)中對(duì)兩個(gè)標(biāo)記串進(jìn)行分析比較。該算法也屬于LCS算法，可解決LCS問(wèn)題。

動(dòng)態(tài)程序設(shè)計(jì)算法是對(duì)于將要進(jìn)行匹配分析的字符串(模式串)，在其字符中間插入空格，以此進(jìn)行排列操作。經(jīng)過(guò)處理后，就能得到一系列的排列。然后再將處理后得到的排列進(jìn)行比較分析，最終得到比較后的最大匹配結(jié)果。例如，文本串T=“chinena”,模式串P=“china”，是兩個(gè)長(zhǎng)度不同的字符串，可以通過(guò)插入空格的方式讓文本串和模式串的長(zhǎng)度相同。即在模式串P中插入空格，讓其和文本串T的長(zhǎng)度相同，如此可以有多種不同的排列。

用sequence表示此時(shí)排列中得到最大匹配值的字符序列。則對(duì)于上述兩個(gè)排列“chin”和“na”為兩個(gè)最大的sequence,對(duì)應(yīng)的值分別為4,2。

利用動(dòng)態(tài)程序設(shè)計(jì)對(duì)文本串T=“abcdefghmnopq”，模式串P=“mabxypqfgh”進(jìn)行匹配操作的結(jié)果和LCS算法相同，計(jì)算得到的相似度也一樣。

2.5 Rabin-Karp算法

Rabin-Karp是一個(gè)用于解決字符串匹配問(wèn)題的隨機(jī)算法[10]。Rabin-Karp算法相對(duì)于樸素算法的改進(jìn)之處是有點(diǎn)使用hash的思想。把模式字符串進(jìn)行預(yù)處理，并進(jìn)行求mod操作，文本串進(jìn)行逐個(gè)簡(jiǎn)單的hash映射，然后進(jìn)行mod比較。

Rabin-Karp算法首先是定義一個(gè)散列函數(shù)，同時(shí)得到模式串的散列值，故在文本串中，只有那些與模式串具有相同散列值的子串才有可能與模式串相匹配，此時(shí)就沒(méi)有必要考察文本串中同等長(zhǎng)度的所有子串。只有當(dāng)兩者的散列值相等時(shí)，才進(jìn)行模式串和文本子串逐個(gè)字符的比較。故Rabin-Karp算法首先要進(jìn)行預(yù)處理，生成散列值，這需要一定的時(shí)間代價(jià)。

通過(guò)對(duì)Rabin-Karp算法的描述，Rabin-Karp算法的預(yù)處理時(shí)間為O(m),其匹配時(shí)間在最壞的情況下為O(m(n-m+1))。雖然Rabin-Karp算法在最壞的情況下時(shí)間復(fù)雜度和樸素算法相同，但它的平均時(shí)間復(fù)雜度卻接近線性，在實(shí)際應(yīng)用中往往比樸素算法快很多，應(yīng)用范圍還是很廣的。

2.6 GST算法

GST算法是一種貪婪字符串匹配算法[11],算法是由澳大利亞悉尼大學(xué)的Wise[12]最先提出的,用于解決字符串的相似問(wèn)題。在說(shuō)明GST算法之前，首先給出幾個(gè)基本概念。

1)最大匹配(Max-Match)：是指在匹配過(guò)程中,從i處開(kāi)始的模式串子串Pi與從j處開(kāi)始的文本串子串Tj的最長(zhǎng)可能匹配。

2)Tiles：表示模式串P和文本串T的最大匹配的集合，每個(gè)tile都是唯一不能重復(fù)的包含同一個(gè)位置的字符。

3)最小匹配長(zhǎng)度(Min-Match-Length)：GST算法進(jìn)行串匹配時(shí)設(shè)定所允許的最小值，如果匹配長(zhǎng)度小于該值，則舍棄。其一般取大于1的整數(shù)。

GST算法的基本思想是首先通過(guò)嵌套循環(huán)，盡可能的擴(kuò)展文本串和字符串中未加標(biāo)記的字符，將每次的匹配長(zhǎng)度和上次記錄進(jìn)行比較，直至匹配過(guò)程結(jié)束。將所有Max-Match集合中的元素放入到tiles中，該集合包含所有大于最小匹配長(zhǎng)度的文本串和模式串的匹配子串。將所有匹配字符串的長(zhǎng)度和記為sum,模式串和文本串相似度使用式(3)計(jì)算,其中P.length和T.length分別為模式串和文本串的長(zhǎng)度。

(3)

例如：對(duì)于文本串T=“abcdefghmnopq”,模式串P=“mabxypqfgh”，利用GST算法匹配結(jié)果如圖3所示。

圖3 GST算法匹配結(jié)果

根據(jù)式(3)計(jì)算文本串T和模式串P的相似度S(P,T)=0.348,與LCS算法的結(jié)果比較可知GST算法的匹配分析因不再受字符串順序的制約，具有較高的匹配準(zhǔn)確性。

由上述GST算法的描述可知，GST算法在最好的情況下時(shí)間復(fù)雜度為O(n2)，最壞的情況下時(shí)間復(fù)雜度為O(n3)。即使兩個(gè)字符串順序改變了，GST仍能進(jìn)行相關(guān)的查找匹配。目前在抄襲檢測(cè)系統(tǒng)中應(yīng)用較為廣泛，但因?yàn)镚ST算法采用兩個(gè)串逐個(gè)字符比較的方法，算法的時(shí)間復(fù)雜度較大。故為了節(jié)約時(shí)間開(kāi)銷，引入KR算法對(duì)GST算法進(jìn)行改進(jìn)，改進(jìn)后的RKR-GST算法在最好的情況下時(shí)間復(fù)雜度變?yōu)镺(n),而最壞的情況下時(shí)間復(fù)雜度仍為O(n3)。

3 結(jié) 語(yǔ)

綜上所述，B-F算法和KMP算法屬于精確字符串匹配算法，對(duì)匹配的精準(zhǔn)度要求較高，在程序代碼抄襲檢測(cè)中的應(yīng)用范圍也相對(duì)較小。LCS算法和動(dòng)態(tài)程序設(shè)計(jì)算法屬于近似字符串匹配算法，其匹配檢測(cè)效率較高。但因?yàn)槭腔谟行虻钠ヅ渌惴ǎ跈z測(cè)改變順序的字符串匹配問(wèn)題時(shí)，匹配效率會(huì)受一定的影響。所以在程序抄襲檢測(cè)中，由于LCS算法得到的公共子序列是嚴(yán)格有序的,對(duì)于改變代碼塊的順序、語(yǔ)句的順序、操作符和操作數(shù)的順序等程序抄襲手段檢測(cè)效率較低。

而GST算法因?yàn)閷儆跓o(wú)序匹配算法，能夠解決LCS算法存在的問(wèn)題，故具有較高的檢測(cè)效率,同時(shí)它也能解決重復(fù)出現(xiàn)的語(yǔ)句查找問(wèn)題。因此,就程序抄襲檢測(cè)這一應(yīng)用領(lǐng)域來(lái)說(shuō)GST算法具有較好的性能。此外，GST算法在信息檢索、文本編輯、信息提取等領(lǐng)域也有重要的應(yīng)用。而引入K-R算法思想對(duì)GST算法進(jìn)行改進(jìn)的RKR-GST算法也因其更加優(yōu)越的效率性能而被廣泛應(yīng)用。

[1] 鄧愛(ài)萍,徐國(guó)梁,肖奔.基于串匹配方法的源代碼復(fù)制檢測(cè)技術(shù)研究[J].科學(xué)技術(shù)與工程,2007,7(10):1671-1819.

[2] Schleimer S, Wilkerson D S, Aiken A. Winnowing: Local Algorithms for Document Fingerprinting[C]//Proc. of ACM SIGMOD International Conference on Management of Data. San Diego, California, USA:[s.n.],2003.

[3] 薛曄偉,沈鈞毅,張?jiān)?一種編輯距離算法及其在網(wǎng)頁(yè)搜索中的應(yīng)用[J].西安交通大學(xué)學(xué)報(bào),2008,42(12):1450-1454.

[4] Georgina C, Mike J. Source-code plagiarism: A UK academic perspective[R]. Research Report RR-422. Department of Computer Science,University of Warwick,2006.

[5] Yamamoto T, Matsushita M, Kamiya T. et al. Measuring similarity of large software systems based on source code correspondence[C]//6th Intl PROFES (Product Focused Software Process Improvement) conference, PROFES.2005.

[6] 于海英.字符串相似度度量中LCS和GST算法比較[J].電子科技,2011,4(2):101-103.

[7] Irvine V C, Samir Khuller. Design and Analysis of Algorithms Lecture Notes[R]. Dept. of Computer Science, University of Maryland,2003.

[8] Aho A V, Hirschberg D S, Ullman J D. Bounds on the complexity of the longest common subsequence problem[J]. J Assoc. Comput. Mach.,1976,23(1):1-12.

[9] David Gitchell, Nicholas Tran. Sim: A Utility for Detecting Similarity in Computer Programs[C]//Proceedings of the 30th SIGCSE Technical Symposium, March.1999.

[10] Richard M Karp, Michaelo Rabin. Efficient randomized pattern-matching algorithms[J]. IBMJ. Res. Develop,1987,31(2):249-260.

[11] Matthew Szuskiewicz. Automatic Plagiarism Detection in Software code[C]//Information and Communications Technology.2003.

[12] Michael J Wise. String Similarity Via Greedy String Tiling and Running Karp-Rabin Matching[D]:[Master’s Degree Thesis]. Sydney: University of Sydney,1993.

Comparative study of string matching algorithm for detecting plagiarism

ZHU Bo, ZHENG Hong*, SUN Lin-lin

(School of Computer Science & Engineering, Changchun University of Technology, Changchun 130012， China)

The program code plagiarism detection in a variety of string matching algorithm implementation principle are described, given the similarity matching algorithm formula and corresponding to a time complexity. The string matching algorithm is widely used in detecting plagiarism in program code, the B-F (Brute-Force) simple algorithm, LCS longest common string algorithms, GST greedy string matching algorithm summary is a meaningful comparison study.

string matching algorithm; copy detection; the longest common string; GST (Greedy String Tiling).

2014-05-25

吉林省科技廳自然科學(xué)基金資助項(xiàng)目(20130101060JC)； 吉林省教育廳“十二五”科學(xué)技術(shù)研究項(xiàng)目(2014132, 2014125)

朱 波(1988-)，男，漢族，山東五蓮人，長(zhǎng)春工業(yè)大學(xué)碩士研究生，主要從事軟件工程方向研究,E-mail:xuesong_502@126.com. *通訊作者：鄭 虹(1974-)，女，漢族，吉林長(zhǎng)春人，長(zhǎng)春工業(yè)大學(xué)副教授，博士，主要從事人工智能方向研究,E-mail:hollytz@126.com.

TP 301.6

A

1674-1374(2014)06-0672-05