朱 波, 鄭 虹, 孫琳琳

(長春工業(yè)大學(xué) 計算機科學(xué)與工程學(xué)院， 吉林 長春 130012)

代碼抄襲檢測中串匹配算法的比較

朱 波, 鄭 虹*, 孫琳琳

(長春工業(yè)大學(xué) 計算機科學(xué)與工程學(xué)院， 吉林 長春 130012)

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

字符串匹配算法； 抄襲檢測； 最長公共字串； GST

0 引 言

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

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

1 相關(guān)定義

在程序代碼抄襲檢測過程中，程序之間的相似程度可以通過相似度的值來判定。程序間的相似度越高，程序間存在抄襲的可能性也就越大；相反，相似度越低，抄襲的可能性就越小。但是，不能僅僅因為個別語句的相同就判定為抄襲，只有當相似度的值超過某個設(shè)定的閾值時，才能判定為抄襲。

1.1基本概念

簡單介紹幾個在算法中用到的概念：

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

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

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

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

1.2相似度定義

Yamamoto T[5]等給出兩個軟件系統(tǒng)的相似度的定義。對于兩個軟件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表示所有的匹配對(Pi,Xj),其中Rs?P×X，則P和X的相似性S的定義為：

(1)

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

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

2 常見串匹配算法比較研究

2.1 B-F算法

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

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

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

2.2KMP算法

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

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

在第一輪匹配過程中,當文本串第3個字符和模式串中第3個字符不相等時,模式串向右“滑動”。在第二輪匹配中就是用模式串P的第1個字符代替第3個字符與文本串的第3個字符進行比較，依次完成匹配過程。

圖1 KMP算法匹配過程

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

2.3LCS算法

LCS算法,又稱最長公共子序列算法[6-7]，其主要用于解決LCS問題。

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

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

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

(2)

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

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

2.4動態(tài)程序設(shè)計

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

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

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

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

2.5 Rabin-Karp算法

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

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

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

2.6 GST算法

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

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

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

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

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

(3)

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

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

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

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

3 結(jié) 語

綜上所述，B-F算法和KMP算法屬于精確字符串匹配算法，對匹配的精準度要求較高，在程序代碼抄襲檢測中的應(yīng)用范圍也相對較小。LCS算法和動態(tài)程序設(shè)計算法屬于近似字符串匹配算法，其匹配檢測效率較高。但因為是基于有序的匹配算法，在檢測改變順序的字符串匹配問題時，匹配效率會受一定的影響。所以在程序抄襲檢測中，由于LCS算法得到的公共子序列是嚴格有序的,對于改變代碼塊的順序、語句的順序、操作符和操作數(shù)的順序等程序抄襲手段檢測效率較低。

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

[1] 鄧愛萍,徐國梁,肖奔.基于串匹配方法的源代碼復(fù)制檢測技術(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] 薛曄偉,沈鈞毅,張云.一種編輯距離算法及其在網(wǎng)頁搜索中的應(yīng)用[J].西安交通大學(xué)學(xué)報,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é)基金資助項目(20130101060JC)； 吉林省教育廳“十二五”科學(xué)技術(shù)研究項目(2014132, 2014125)

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

TP 301.6

A

1674-1374(2014)06-0672-05