代码抄袭检测中串匹配算法的比较

朱 波, 郑 虹, 孙琳琳

(长春工业大学 计算机科学与工程学院， 吉林 长春 130012)

代码抄袭检测中串匹配算法的比较

朱 波, 郑 虹*, 孙琳琳

(长春工业大学 计算机科学与工程学院， 吉林 长春 130012)

对程序代码抄袭检测中多种字符串匹配算法的实现原理进行了描述,给出匹配算法计算相似度的公式以及相对应的时间复杂度。由于字符串匹配算法在程序代码抄袭检测中应用较为广泛，对其中的B-F(Brute-Force)朴素算法、LCS(Longest Common Subsequence)最长公共字串算法、GST(Greedy String Tiling)贪心字符串匹配算法等经典算法的总结比较是一件有意义的研究工作。

字符串匹配算法； 抄袭检测； 最长公共字串； GST

0 引 言

随着信息社会的发展，众多应用领域中都涉及到了字符串的匹配研究，如在程序抄袭检测[1]、知识产权保护[2]、网页搜索[3]等领域都有串匹配算法的应用。在程序类设计课程中，作业抄袭现象普遍存在。澳大利亚蒙纳什(Monash)大学对其学生中的代码抄袭现象进行调查统计显示：高达85.4%的学生承认抄袭过他人的作业[4]。为扼制计算机课程教学中的不良学风，高效率的代码抄袭检测研究日趋重要。而字符串相似性匹配算法的研究以及相似度的计算是抄袭检测中的关键问题。

目前，字符串相似性匹配算法有很多，如B-F算法、KMP算法、动态程序设计算法、GST算法等。这些匹配算法因为其实现的原理不同，算法效率和应用的领域也有一些差异。

1 相关定义

在程序代码抄袭检测过程中，程序之间的相似程度可以通过相似度的值来判定。程序间的相似度越高，程序间存在抄袭的可能性也就越大；相反，相似度越低，抄袭的可能性就越小。但是，不能仅仅因为个别语句的相同就判定为抄袭，只有当相似度的值超过某个设定的阈值时，才能判定为抄袭。

1.1基本概念

简单介绍几个在算法中用到的概念：

1)文本串(也称为主串)：主要是指在其中查找子字符串的相对较长的字符串T。

2)模式串(也称为模式)：主要是指在文本串T 中查找的需要验证匹配的字符串P。

3)精确串匹配算法：查找与模式串完全相等的子串的出现位置的算法。

4)近似串匹配算法：查找与特定模式串在一定范围内相似的所有子串的算法。

1.2相似度定义

Yamamoto T[5]等给出两个软件系统的相似度的定义。对于两个软件P和X，软件P是由元素P1,P2,…,Pm组成，P的集合构成表示为：{P1,P2,…,Pm}。同样，软件X由元素X1,X2,…,Xn组成,其元素的集合表示为{X1,X2,…,Xn}。其中P，X中的元素可以表示软件P和X中的文件或者代码行。

假设能够求出Pi与Xj(1≤i≤m且1≤j≤n)间的匹配，用集合Rs表示所有的匹配对(Pi,Xj),其中Rs⊆P×X，则P和X的相似性S的定义为：

(1)

根据式(1)可以看出,相似性S为一个比值，它是由Rs中元素的个数比上P和X中元素的个数和所得。如果Rs较小，相应的S也较小。当Rs=Ø时，S=0；当P和X完全相等的时候，此时S=1，则说明软件P和X存在抄袭现象。

目前对于相似度没有统一的定义，而程序代码的相似度与上述软件系统的相似度相同，故可将相似度定义为：定量的比较两个程序源代码之间的相关性，其结果一般用一个具体的数值来表示。

2 常见串匹配算法比较研究

2.1 B-F算法

B-F匹配算法(朴素算法)即蛮力匹配算法，算法比较简单，很适合应用于一些小规模的串匹配。

B-F算法是将模式串和文本串的字符元素分别放置在数P[m-1],T[n-1]中，数组下标从0开始,并且有n≥m。从文本串T=“T0,T1,Tn-1”的第一个字符T0开始与模式串P=“P0,P1,…,Pm-1”的第一个字符P0对应比较，如果相等，就继续比较T和P后面的字符；如果不相等，从文本串的第二个字符P1开始重新与模式串的第一个字符P0进行比较，如此循环往复直至匹配结束。如果到匹配结束时，存在模式串与文本串中有一段连续的字符序列，则表示匹配成功，此时返回模式串P中第一个匹配字符在文本串中的起始匹配位置下标；如果直到匹配结束时，不存在一个和模式串相同的字符串，则代码匹配不成功，返回一个-1。

由算法的描述可知，算法的时间复杂度为O(m(n-m+1))，算法效率并不是太高。因为B-F算法属于精确字符串匹配算法，其多应用于小规模的文本检测等精准度要求较高的领域。

2.2KMP算法

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

KMP算法主要是对朴素算法做了一些改进，当发现文本串和模式串字符的某次匹配比较不相等的时候，文本串的查找指针不需要回溯到串起始位置，而是通过已经得到的“部分匹配”结果将模式串向右进行滑动若干距离，然后再从滑动后的新位置继续进行比较。例如，文本串T=“acacbbc”,模式串P=“acbb”，利用KMP算法匹配过程如图1所示。

在第一轮匹配过程中,当文本串第3个字符和模式串中第3个字符不相等时,模式串向右“滑动”。在第二轮匹配中就是用模式串P的第1个字符代替第3个字符与文本串的第3个字符进行比较，依次完成匹配过程。

图1 KMP算法匹配过程

通过对KMP算法的描述可知，算法的时间复杂度近似为O(m+n)，其最大的特点是文本串不需要回溯，具有很高的时间优越性。在文本检测和网络安全方面都有应用，是一种效率较高的精确串匹配算法。

2.3LCS算法

LCS算法,又称最长公共子序列算法[6-7]，其主要用于解决LCS问题。

LCS算法是将给定的两个字符串(文本串和模式串)分别删去零个或者多个字符，在不改变剩余字符顺序的同时，所得到的长度最长的相同字符序列。LCS即为文本串和模式串的最长公共子序列，除它之外，再也无法找出比它更长的子串。因为在匹配时两个串可以有多个长度相同的最大公共子序列，所以LCS可以有多个。例如，文本串T=“abcdefghmnopq”,模式串P=“mabxypqfgh”，利用LCS算法匹配结果如图2所示。

图2 LCS算法匹配结果

根据式(1)得到LCS算法相似度计算式(2)，并根据公式计算得到文本串T和模式串P的相似度S为：

(2)

由算法相关描述可知，LCS算法的时间复杂度为O(m+n)，已经证明LCS算法的时间复杂度不能小于O(mlog(n))[8]。

LCS算法是有序的，也就是说得到的所有子串都是严格有序的，这就对于改变书写顺序的模式串的检测失去了作用。LCS算法多应用于文件版本比较以及疾病监测等领域。

2.4动态程序设计

动态程序设计(Dynamic Programming)[9]曾应用于YAP2系统中对两个标记串进行分析比较。该算法也属于LCS算法，可解决LCS问题。

动态程序设计算法是对于将要进行匹配分析的字符串(模式串)，在其字符中间插入空格，以此进行排列操作。经过处理后，就能得到一系列的排列。然后再将处理后得到的排列进行比较分析，最终得到比较后的最大匹配结果。例如，文本串T=“chinena”,模式串P=“china”，是两个长度不同的字符串，可以通过插入空格的方式让文本串和模式串的长度相同。即在模式串P中插入空格，让其和文本串T的长度相同，如此可以有多种不同的排列。

用sequence表示此时排列中得到最大匹配值的字符序列。则对于上述两个排列“chin”和“na”为两个最大的sequence,对应的值分别为4,2。

利用动态程序设计对文本串T=“abcdefghmnopq”，模式串P=“mabxypqfgh”进行匹配操作的结果和LCS算法相同，计算得到的相似度也一样。

2.5 Rabin-Karp算法

Rabin-Karp是一个用于解决字符串匹配问题的随机算法[10]。Rabin-Karp算法相对于朴素算法的改进之处是有点使用hash的思想。把模式字符串进行预处理，并进行求mod操作，文本串进行逐个简单的hash映射，然后进行mod比较。

Rabin-Karp算法首先是定义一个散列函数，同时得到模式串的散列值，故在文本串中，只有那些与模式串具有相同散列值的子串才有可能与模式串相匹配，此时就没有必要考察文本串中同等长度的所有子串。只有当两者的散列值相等时，才进行模式串和文本子串逐个字符的比较。故Rabin-Karp算法首先要进行预处理，生成散列值，这需要一定的时间代价。

通过对Rabin-Karp算法的描述，Rabin-Karp算法的预处理时间为O(m),其匹配时间在最坏的情况下为O(m(n-m+1))。虽然Rabin-Karp算法在最坏的情况下时间复杂度和朴素算法相同，但它的平均时间复杂度却接近线性，在实际应用中往往比朴素算法快很多，应用范围还是很广的。

2.6 GST算法

GST算法是一种贪婪字符串匹配算法[11],算法是由澳大利亚悉尼大学的Wise[12]最先提出的,用于解决字符串的相似问题。在说明GST算法之前，首先给出几个基本概念。

1)最大匹配(Max-Match)：是指在匹配过程中,从i处开始的模式串子串Pi与从j处开始的文本串子串Tj的最长可能匹配。

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

3)最小匹配长度(Min-Match-Length)：GST算法进行串匹配时设定所允许的最小值，如果匹配长度小于该值，则舍弃。其一般取大于1的整数。

GST算法的基本思想是首先通过嵌套循环，尽可能的扩展文本串和字符串中未加标记的字符，将每次的匹配长度和上次记录进行比较，直至匹配过程结束。将所有Max-Match集合中的元素放入到tiles中，该集合包含所有大于最小匹配长度的文本串和模式串的匹配子串。将所有匹配字符串的长度和记为sum,模式串和文本串相似度使用式(3)计算,其中P.length和T.length分别为模式串和文本串的长度。

(3)

例如：对于文本串T=“abcdefghmnopq”,模式串P=“mabxypqfgh”，利用GST算法匹配结果如图3所示。

图3 GST算法匹配结果

根据式(3)计算文本串T和模式串P的相似度S(P,T)=0.348,与LCS算法的结果比较可知GST算法的匹配分析因不再受字符串顺序的制约，具有较高的匹配准确性。

由上述GST算法的描述可知，GST算法在最好的情况下时间复杂度为O(n2)，最坏的情况下时间复杂度为O(n3)。即使两个字符串顺序改变了，GST仍能进行相关的查找匹配。目前在抄袭检测系统中应用较为广泛，但因为GST算法采用两个串逐个字符比较的方法，算法的时间复杂度较大。故为了节约时间开销，引入KR算法对GST算法进行改进，改进后的RKR-GST算法在最好的情况下时间复杂度变为O(n),而最坏的情况下时间复杂度仍为O(n3)。

3 结 语

综上所述，B-F算法和KMP算法属于精确字符串匹配算法，对匹配的精准度要求较高，在程序代码抄袭检测中的应用范围也相对较小。LCS算法和动态程序设计算法属于近似字符串匹配算法，其匹配检测效率较高。但因为是基于有序的匹配算法，在检测改变顺序的字符串匹配问题时，匹配效率会受一定的影响。所以在程序抄袭检测中，由于LCS算法得到的公共子序列是严格有序的,对于改变代码块的顺序、语句的顺序、操作符和操作数的顺序等程序抄袭手段检测效率较低。

而GST算法因为属于无序匹配算法，能够解决LCS算法存在的问题，故具有较高的检测效率,同时它也能解决重复出现的语句查找问题。因此,就程序抄袭检测这一应用领域来说GST算法具有较好的性能。此外，GST算法在信息检索、文本编辑、信息提取等领域也有重要的应用。而引入K-R算法思想对GST算法进行改进的RKR-GST算法也因其更加优越的效率性能而被广泛应用。

[1] 邓爱萍,徐国梁,肖奔.基于串匹配方法的源代码复制检测技术研究[J].科学技术与工程,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] 薛晔伟,沈钧毅,张云.一种编辑距离算法及其在网页搜索中的应用[J].西安交通大学学报,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

吉林省科技厅自然科学基金资助项目(20130101060JC)； 吉林省教育厅“十二五”科学技术研究项目(2014132, 2014125)

朱 波(1988-)，男，汉族，山东五莲人，长春工业大学硕士研究生，主要从事软件工程方向研究,E-mail:xuesong_502@126.com. *通讯作者：郑 虹(1974-)，女，汉族，吉林长春人，长春工业大学副教授，博士，主要从事人工智能方向研究,E-mail:hollytz@126.com.

TP 301.6

A

1674-1374(2014)06-0672-05