基于RKRGST的算法分析

西南民族大学学报.自然科学版第36卷第5期Sep. 2010Jourmal of Southwest University for Nationalities Natural Science Edition文章编号: 1003-2843(2010)05-0836-05基于RKRGST的算法分析肖丽，校景中(西南民族大计算机科学与技术学院,四川成都610041)摘要:在各大高校,剽窃检测系统已经被广泛的使用,用于检测学生在学生中出现的不诚实现象.对于这种剽窃检测系统,其核心就是对两个学生的作业进行相似度度量,当达到一个高的相似度,就具有剽窃的嫌疑,为老师公正的作出评判提供依据.本文研究了一种在各大剽窃检测系统中广泛使用的RKRGST算法,该算法结合了KR算法和GST算法,通过分析发现该算法在计算字符串相似度时具有较高的效率.关键字:相似度; RKRGST: KR; GST中图分类号: TP31文献标识码: A1引言在源码剽窃检测技术中,最核心的部分是对于两个源程序相似度的计算,到底两个程序在多大程度上相似?为了得到这个相似值，人们想尽了办法,提出了很多算法.最简单的相似度算法集中在简单的串匹配上.因为目前几乎所有的源码剽窃检测技术都是先将源程序转换为token流的形式,然后用串匹配的方式对token流|"进行匹配，计算器相似度.常用的串匹配算法有: KMP算法、BM算法、RK算法*.本文研究- -种基于RK和GST的RKRGST算法.事实上, Wise提出的RKRGST几乎已经成为当前很多剽窃检测系统的标准算法,如YAPIHI和Jplag'].2.相关技术2.1 GST算法贪心串覆盖(Greedy String Tiling)是另- -种基于token的计算相似度的度量方法,简称GST,类似于LCS,它最大的值是，当两个串完全相等时，等于-个串的长度;最小的值是,当两个串完全不匹配时，为0.在说明这个算法之前，首先对几个概念达成共识.当给定两个特征串时,通常把较短的串称作模式串,较长的串作为文本串.令P为模式串, T为文本串,最大匹配maximal-match是当一个模式串从p开始的子串Pp与文本串中从t开始的子串T,每一-项都匹配时.这个匹配要尽可能的长，直到遇到了不匹配的项或遇到文件结束或遇到了-一个事先标记的token. - 一个最大匹配被表示为-一个三元组: max _match(,t,s), 其中s是匹配的长度.最大匹配是临时的,而且通常不是唯一-相关的，也就是说-一个包含最大匹配的子串可能是其他最大匹配的构成部分.-一个覆盖tile表示-一个与P、T中相匹配的固定和唯-相关的子串,在-个最大匹配中形成-一个覆盖的过程中, P、T中相匹配的两个子串中的token被标记,在后面的匹配中这些标记过的token变得不可用-个模式串P从p开始的子串Pp与文本串T中从t开始的子串T,最大匹配长度为s时的覆盖表示为: til(pt,s).值得注意的是,在很多情况下，短的最大匹配可以先忽略掉.例如,在计算机语言中,对于长度为1或2的中国煤化工收稿日期: 2010-07-03作者简介:肖丽(1976-),女，西南民族大计算机科学与技术学院讲师.MYHCNMHG第5期肖丽等:基于RKRGST的算法分析83最大匹配是没有多大意义的.因此有了下面关于最小四配长度的定义.最小匹配长度(minimum-match-length)是在计算最大匹配时,小于最小匹配长度的最大匹配都被忽略.理想情况下，这个算法得到的是P和T中的最大覆盖,也就是T与P中匹配的包含最多token的子串的覆盖遗憾的是,在多项式时间内产生和计算最大覆盖是-个开放问题.部分原因在于多个小的覆盖共同联合起来标记的token数量可能比少量大的覆盖标记的token 多.但是，大的覆盖更能反映源代码中的相似段,而小的覆盖很多时候可能只是偶然的相似，不具备说服力.于是在创建覆盖时,先创建更大的覆盖,小的覆盖放到后面处理.这样就可以解决上述提到的问题.通过观察发现,如果P中的- -个token与T中的任意位置的token匹配,那这里至少会找到一个覆盖的长度为1的部分.因此,任何参与到-一个覆盖中的token, 它- -定是在-个覆盖面积最大的覆盖中.为了获取度量值，需要简单的将剩下的未被覆盖的token进行最小化,如果是完全匹配的两个串的话，这个度量值将为0.然而，如果强制要求一个匹配的最小匹配长度要高于1, 就可能导致一个次优的结果(只能计算到一个近似的度量值).例如，如果-个最小匹配长度(minimum-match-length)为2,有以下两个串: .P=cabaa贪心算法会选择P的子串(aabaa)与 T进行匹配---匹配长度为 5,而不是选择另外两个子串(caa)和(aad)--- _匹配长度为 7.这个例子说明，当一个最小匹配长度大于1时,由GST返回的值是最优值的一一个近似值，最优值是当最小匹配长度为1时计算得到的.在GST算法描述的每一个循环的两个阶段中, 第-一个阶段用于寻找最大匹配maxmatch,第二个阶段用于创建最大覆盖.在这里,第-一个阶段的代价更大，原因是，在这里可能有最多(TI- L)<(PI- L)个的最大匹配(L表示找到的最大maximal-match的长度),但最多只可能创建IP/L个覆盖(创建覆盖的开销是线性的).所有其他的最大匹配将很快的被淘汰;阻塞将通过- -对简单的测试解决.而且，在-一个循环中形成的覆盖越多,遗留给后续循环处理的未标记的子串就越短.最坏的情况是每一一次迭代只能找到一个最大匹配，而这个最大匹配只比上一次迭代中找到的匹配长度小-一个token,最后-次迭代中找到的-定是长度为minimum_ match_ length 的匹配.如果假设|P=T]=n,那么与长度n对应的不同长度的不同子串的最大数量大约为√2n.同时假设所有已标记的子串必须在P和T串的一-端那么,最后长度为1(这里假设minimum_ match. length 的值为1)的最大匹配将在P和T中只出现-一次,这只需要- -次简单比较;长度为2的最大匹配将会放入3个位置，也就是说,长度为2的有2种选择,22个比较对或者2x2个token比较.长度为3的最大匹配在P和T中将有4个可能的位置，这意味着长度为3的有42个比较对.通常,对于长度为k的最大匹配，有k(Ek-1+1}2个token比较. - (k2k<+2)户以kn?作为上限,所有的串都小于或等于√2n .将所有从1到V2n的最大匹配数相加，结果为0(n).2.2KR算法.对长为m的字符串赋以-个散列函数,在正文中由于只有那些与模式具有相同散列函数值的子段才有可能与模式匹配,这样就不必考察正文中的长为m的全部子段.在进行串匹配时,先在正文中找到和模式串的散列函数值相同的子段，再进行匹配检查,以此类推,直到最后-个子串. 下面是对该算法的描述:d是正文和模式中可能出现的不同字符个数,本书中取d=32.正文与模式中每个字符对应于-一个0到d-1 之间的数.则子段a[ i,i+m-1]可以表示为下列整数: .x, =orda[])d"'+ oda(i+1])d -2+ .... ordati+m-])x。=0其中ord -个映射,它将P和T中的字符映射到{0,1,2, ...中国煤化工散列函数: h(x)=x mod qYHCNMHG838西南民族大学学报.自然科学版第36卷其中,x是一整数, q是适当大的素数.所以长度为m的字符段的散列函数值的递推公式为:h(x, ()=(h( x )-x*ord(" )*d + ord(a[i+m]) mod q其中x=d~- mod q3 RKRGST调整后的GST的时间复杂度超过0(n),这也许是可以接受的,但是最长的文本和分组始终还是太高,基于这个思想，Wise提出了一个完全不同的算法,这个新的算法是基于KR串匹配法:如果-个哈希值是为- -个从t开始的长度为s的串存在,那么-一个从t+1开始的长度为s的串的哈希值就可以通过-个简单的递推计算出来.特别的，如果模式串的长度为P|,那么每一个在文本串中长度为IP|的子串的哈希值都与模式串P的哈希值进行比较,如果是相等的，这个模式串和这个文本子串进行进一一步的逐项比较. 注意:如果没有匹配的子串,两个串和起来的复杂度是线性的.更重要的是,当所有匹配子串都找到的时候,复杂度为0(n),可以看到这个复杂度仍然是接近线性的. RKR-GST算法针对KR串匹配法具体的修正策略如下:1) 不是对整个模式赋予-一个单独的哈希值,而是对模式和正文中所有长度为m的子串赋予一个哈希值.2)模式中的每一个哈希值都 与正文中的哈希值进行比较;对于哈希值相同的每一对模式和正文子串,再对它们进行逐个token的比较.3) 正文中的所有哈希值由一个专门的哈希表来存放,引入这个哈希表的目的是为了减少在匹配时的时间复杂度.这样处理的话,在正文中查找与模式子串哈希值对应的子串时，不用扫描整个正文，而是查找正文对应的哈希表,然后会返回所有要查找的子串的开始位置.注意:在将Karp-Rabin哈希值与实际子串匹配成功后,还要继续对匹配进行扩展,最后产生最大匹配.4) 用于查找的匹配长度s, 在每一次循环中都会减少，直到达到最小匹配长度minimum-match-length.这里的s是在一次循环中用于查找的最小匹配长度，被称作查找长度search-length. 设计一个名为scanpattem函数,该函数的主要功能就是找出匹配的子串. scanpattern的算法描述如下:对于从T的第一个未标记的token开始的每-一个 T,deif与下一个覆盖的距离小于等于sthen在下一次覆盖后将t提前到第一个未标记的token为从T,到TI的子中创建KR哈希值并添加到哈希表中对于从P的第-一个未标记的token开始的每一一个 P, do ,在下一次覆盖后将p提前到第一个未标记的tokenelse为从Pp。到Ppe的子申创建KR哈希值检测哈希表中用于哈希的KR哈希值对于哈希表中与KR哈希值相同的每一-项dif从0到s.1 的所有j都有Pp=Tmn中国煤化工while Ppre Tre AND umarked(Ppr) AND:TYHCNMHGk:=k+1第5期肖丽等:基于RKRGST的算法分析839if k>2*s then retum()else记录新的最大匹配Rctum(最长的最大匹配的长度)用于记录最大匹配的结构是一个队列的双向链接列表.每-一个队列记录相同长度的最大匹配.整个列表以递减顺序排序.有一个指针指向最近追加进来的最大匹配的队列，因为下一个最大匹配与最近进入的最大匹配的长度相同的可能性很高，可将下一个最大匹配直接加入到当前的这个队列中.上述算法的问题在于,传递给scapattern的参数s应该是一一个怎样的值才合适?更准确地说, s的初值是多少?它的值如何变化?有人认为s的值等于P长度的一半比较合适,事实证明比P的-半小的值就可以满足要求.有两个理由，首先，特别长的最大匹配是比较少见的，所以如果给s设置-一个较大的初值,会导致scanpattern在找到一个匹配之前进行很大规模的无结果的搜索. 另外,如果找到一个长的最大匹配(假设这个最大匹配的长度ke =2*s),为这样的串创建覆盖后,会标记大量的模式和正文中的token. 因此在这个时候有必要将当前的扫描停止然后重新开始-一个以 k作为查找长度的特殊扫描,也就是让s=k.这意味着初始查找长度可以设置为一个较小的常量值,而不是依赖于串长度的一个值.再设计-一个markarrays函数,该函数的功能是创建覆盖并标记覆盖中的token.函数markarrays的算法与调整GST算法很相似,唯- -不同的是它是应用到一一个队列列表上,而不是-个单独的队列上.这里的每-一个队列包含长度相同的所有最大匹配.这个markarrays版本也有参数s---查找长度, 如下所示: .从队列头开始,如果是非空队列do .if当前的队列是空的then跳到下一个队列else从队列中 删除match(p,tL)/*假设当前队列中最大匹配的长度为L*/if匹配没有被阻塞thenif对于从0到s.1 的每-个j都满足Ppr=THjthen对于从0到L的每一个j domark_ token(Ppm)mark. token(T+)length_ of _tokens_ tiled:=length. of_ tokens_ jiled+Lelse if Llocer>=sthen替换在队列列表中未被标记的部分首先要注意的是，在scanpattemn中的KR哈希后已经查找出一个潜在的子串匹配,如下的成对测试:if从0到s-1的所有j都有Ppr=Trj then .... .可以被延迟，直到markarrays.有两个理由.首先,失败的KR哈希是很少见的;其次,大量由KR哈希得出的匹配,不论真假,都会被兄弟覆盖阻塞.因此有必要将这些子串的成对比较延迟到即将进行的新覆盖创建的时候.4结论通过分析后发现, RKRGST算法结合了GST算法的贪心算法策略,最大限度的寻找出最大匹配并创建覆盖,对token进行标记;同时结合了KR算法的思想,通过引入哈希表中国煤化工间的相似度时，用于进行匹配的子串的数量大大减少,效率得到了极大提升;最YHCNMH G下情况下为0(n)的GST,变为了在实际运行中时间复杂度控制在接近线性的RKRGs1. AnkusI异么口前已红应用到各个领域，除840西南民族大学学报.自然科学版第36卷了剽窃检测领域,还有DNA序列匹配等领域,该算法的前景非常宽广.参考文献:[] TOSHIHIRO K, SHINI K, KATSURO I. CCFinder:A mutilinuistic token based code clone detection system for large scale sourcecode[J]. Transactions on Software Engnereng.2002.28<(7;654-670.2] KARP, RICHARD M. and Michael O. Rabin, Efficient Randomized Pattem-Matching Algorithms[]. IBM Joumal of Research andDevelopment, 31(2): 249-260.[3] MICHAEL J. WISE. String similarity via greedy string tiling and running Karp-Rabin matching[J/OL]. ://p.cs.s.oz.cumichaclw/doc/RKR GST.pS, Dept. of CS, University of Sydney, December 1993.[4] WISE MJ. YAP3: Improved detection of silrities in computer programs and other texts[J/OL]. In: Proceedings of the SIGCSE'96.1996, 130-134. ht:t:itesecr.xj.ec.c com/wise96yap.html.[$] PRECHELT L, MALPOHL G, PHILIPPSEN M. Finding plagiarism among a set of programs with Jplag[小]. Joumal of UniversalComputer Science, 2002,8(1 1):1016-1038.Research of RKRGST algorithmXIAO Li, XIAO Jing zhong(Schoo of Computer Science and Technology, Southwest University for Nationalities, Chengdu 610041, P.R.C.)of students in studying. The most important thing for the plagiarism detection system is to calculate the similarity of theassignment of two students or more. When the similarity is high enough, it is suspicious to have a plagiarism, which gives anevidence for the teacher to judge. This paper introduces an RKRGST algorithm used in many plagiarism systems. Thisalgorithm combines the Karp-Rabin algorithm with the Greedy String Tiling algorithm. Alfter analysis, it is found that theRKRGST algorithm is high-performace in calculating the similarity of the stings.Key words: similarity; RKRGST; Karp-Rabin; greedy string tiling中国煤化工MYHCNMHG