基于RKRGST的算法分析

西南民族大學(xué)學(xué)報.自然科學(xué)版第36卷第5期Sep. 2010Jourmal of Southwest University for Nationalities Natural Science Edition文章編號: 1003-2843(2010)05-0836-05基于RKRGST的算法分析肖麗，校景中(西南民族大計算機科學(xué)與技術(shù)學(xué)院,四川成都610041)摘要:在各大高校,剽竊檢測系統已經(jīng)被廣泛的使用,用于檢測學(xué)生在學(xué)生中出現的不誠實(shí)現象.對于這種剽竊檢測系統,其核心就是對兩個(gè)學(xué)生的作業(yè)進(jìn)行相似度度量,當達到一個(gè)高的相似度,就具有剽竊的嫌疑,為老師公正的作出評判提供依據.本文研究了一種在各大剽竊檢測系統中廣泛使用的RKRGST算法,該算法結合了KR算法和GST算法,通過(guò)分析發(fā)現該算法在計算字符串相似度時(shí)具有較高的效率.關(guān)鍵字:相似度; RKRGST: KR; GST中圖分類(lèi)號: TP31文獻標識碼: A1引言在源碼剽竊檢測技術(shù)中,最核心的部分是對于兩個(gè)源程序相似度的計算,到底兩個(gè)程序在多大程度上相似?為了得到這個(gè)相似值，人們想盡了辦法,提出了很多算法.最簡(jiǎn)單的相似度算法集中在簡(jiǎn)單的串匹配上.因為目前幾乎所有的源碼剽竊檢測技術(shù)都是先將源程序轉換為token流的形式,然后用串匹配的方式對token流|"進(jìn)行匹配，計算器相似度.常用的串匹配算法有: KMP算法、BM算法、RK算法*.本文研究- -種基于RK和GST的RKRGST算法.事實(shí)上, Wise提出的RKRGST幾乎已經(jīng)成為當前很多剽竊檢測系統的標準算法,如YAPIHI和Jplag'].2.相關(guān)技術(shù)2.1 GST算法貪心串覆蓋(Greedy String Tiling)是另- -種基于token的計算相似度的度量方法,簡(jiǎn)稱(chēng)GST,類(lèi)似于LCS,它最大的值是，當兩個(gè)串完全相等時(shí)，等于-個(gè)串的長(cháng)度;最小的值是,當兩個(gè)串完全不匹配時(shí)，為0.在說(shuō)明這個(gè)算法之前，首先對幾個(gè)概念達成共識.當給定兩個(gè)特征串時(shí),通常把較短的串稱(chēng)作模式串,較長(cháng)的串作為文本串.令P為模式串, T為文本串,最大匹配maximal-match是當一個(gè)模式串從p開(kāi)始的子串Pp與文本串中從t開(kāi)始的子串T,每一-項都匹配時(shí).這個(gè)匹配要盡可能的長(cháng)，直到遇到了不匹配的項或遇到文件結束或遇到了-一個(gè)事先標記的token. - 一個(gè)最大匹配被表示為-一個(gè)三元組: max _match(,t,s), 其中s是匹配的長(cháng)度.最大匹配是臨時(shí)的,而且通常不是唯一-相關(guān)的，也就是說(shuō)-一個(gè)包含最大匹配的子串可能是其他最大匹配的構成部分.-一個(gè)覆蓋tile表示-一個(gè)與P、T中相匹配的固定和唯-相關(guān)的子串,在-個(gè)最大匹配中形成-一個(gè)覆蓋的過(guò)程中, P、T中相匹配的兩個(gè)子串中的token被標記,在后面的匹配中這些標記過(guò)的token變得不可用-個(gè)模式串P從p開(kāi)始的子串Pp與文本串T中從t開(kāi)始的子串T,最大匹配長(cháng)度為s時(shí)的覆蓋表示為: til(pt,s).值得注意的是,在很多情況下，短的最大匹配可以先忽略掉.例如,在計算機語(yǔ)言中,對于長(cháng)度為1或2的中國煤化工收稿日期: 2010-07-03作者簡(jiǎn)介:肖麗(1976-),女，西南民族大計算機科學(xué)與技術(shù)學(xué)院講師.MYHCNMHG第5期肖麗等:基于RKRGST的算法分析83最大匹配是沒(méi)有多大意義的.因此有了下面關(guān)于最小四配長(cháng)度的定義.最小匹配長(cháng)度(minimum-match-length)是在計算最大匹配時(shí),小于最小匹配長(cháng)度的最大匹配都被忽略.理想情況下，這個(gè)算法得到的是P和T中的最大覆蓋,也就是T與P中匹配的包含最多token的子串的覆蓋遺憾的是,在多項式時(shí)間內產(chǎn)生和計算最大覆蓋是-個(gè)開(kāi)放問(wèn)題.部分原因在于多個(gè)小的覆蓋共同聯(lián)合起來(lái)標記的token數量可能比少量大的覆蓋標記的token 多.但是，大的覆蓋更能反映源代碼中的相似段,而小的覆蓋很多時(shí)候可能只是偶然的相似，不具備說(shuō)服力.于是在創(chuàng )建覆蓋時(shí),先創(chuàng )建更大的覆蓋,小的覆蓋放到后面處理.這樣就可以解決上述提到的問(wèn)題.通過(guò)觀(guān)察發(fā)現,如果P中的- -個(gè)token與T中的任意位置的token匹配,那這里至少會(huì )找到一個(gè)覆蓋的長(cháng)度為1的部分.因此,任何參與到-一個(gè)覆蓋中的token, 它- -定是在-個(gè)覆蓋面積最大的覆蓋中.為了獲取度量值，需要簡(jiǎn)單的將剩下的未被覆蓋的token進(jìn)行最小化,如果是完全匹配的兩個(gè)串的話(huà)，這個(gè)度量值將為0.然而，如果強制要求一個(gè)匹配的最小匹配長(cháng)度要高于1, 就可能導致一個(gè)次優(yōu)的結果(只能計算到一個(gè)近似的度量值).例如，如果-個(gè)最小匹配長(cháng)度(minimum-match-length)為2,有以下兩個(gè)串: .P=cabaa貪心算法會(huì )選擇P的子串(aabaa)與 T進(jìn)行匹配---匹配長(cháng)度為 5,而不是選擇另外兩個(gè)子串(caa)和(aad)--- _匹配長(cháng)度為 7.這個(gè)例子說(shuō)明，當一個(gè)最小匹配長(cháng)度大于1時(shí),由GST返回的值是最優(yōu)值的一一個(gè)近似值，最優(yōu)值是當最小匹配長(cháng)度為1時(shí)計算得到的.在GST算法描述的每一個(gè)循環(huán)的兩個(gè)階段中, 第-一個(gè)階段用于尋找最大匹配maxmatch,第二個(gè)階段用于創(chuàng )建最大覆蓋.在這里,第-一個(gè)階段的代價(jià)更大，原因是，在這里可能有最多(TI- L)<(PI- L)個(gè)的最大匹配(L表示找到的最大maximal-match的長(cháng)度),但最多只可能創(chuàng )建IP/L個(gè)覆蓋(創(chuàng )建覆蓋的開(kāi)銷(xiāo)是線(xiàn)性的).所有其他的最大匹配將很快的被淘汰;阻塞將通過(guò)- -對簡(jiǎn)單的測試解決.而且，在-一個(gè)循環(huán)中形成的覆蓋越多,遺留給后續循環(huán)處理的未標記的子串就越短.最壞的情況是每一一次迭代只能找到一個(gè)最大匹配，而這個(gè)最大匹配只比上一次迭代中找到的匹配長(cháng)度小-一個(gè)token,最后-次迭代中找到的-定是長(cháng)度為minimum_ match_ length 的匹配.如果假設|P=T]=n,那么與長(cháng)度n對應的不同長(cháng)度的不同子串的最大數量大約為√2n.同時(shí)假設所有已標記的子串必須在P和T串的一-端那么,最后長(cháng)度為1(這里假設minimum_ match. length 的值為1)的最大匹配將在P和T中只出現-一次,這只需要- -次簡(jiǎn)單比較;長(cháng)度為2的最大匹配將會(huì )放入3個(gè)位置，也就是說(shuō),長(cháng)度為2的有2種選擇,22個(gè)比較對或者2x2個(gè)token比較.長(cháng)度為3的最大匹配在P和T中將有4個(gè)可能的位置，這意味著(zhù)長(cháng)度為3的有42個(gè)比較對.通常,對于長(cháng)度為k的最大匹配，有k(Ek-1+1}2個(gè)token比較. - (k2k<+2)戶(hù)以kn?作為上限,所有的串都小于或等于√2n .將所有從1到V2n的最大匹配數相加，結果為0(n).2.2KR算法.對長(cháng)為m的字符串賦以-個(gè)散列函數,在正文中由于只有那些與模式具有相同散列函數值的子段才有可能與模式匹配,這樣就不必考察正文中的長(cháng)為m的全部子段.在進(jìn)行串匹配時(shí),先在正文中找到和模式串的散列函數值相同的子段，再進(jìn)行匹配檢查,以此類(lèi)推,直到最后-個(gè)子串. 下面是對該算法的描述:d是正文和模式中可能出現的不同字符個(gè)數,本書(shū)中取d=32.正文與模式中每個(gè)字符對應于-一個(gè)0到d-1 之間的數.則子段a[ i,i+m-1]可以表示為下列整數: .x, =orda[])d"'+ oda(i+1])d -2+ .... ordati+m-])x。=0其中ord -個(gè)映射,它將P和T中的字符映射到{0,1,2, ...中國煤化工散列函數: h(x)=x mod qYHCNMHG838西南民族大學(xué)學(xué)報.自然科學(xué)版第36卷其中,x是一整數, q是適當大的素數.所以長(cháng)度為m的字符段的散列函數值的遞推公式為:h(x, ()=(h( x )-x*ord(" )*d + ord(a[i+m]) mod q其中x=d~- mod q3 RKRGST調整后的GST的時(shí)間復雜度超過(guò)0(n),這也許是可以接受的,但是最長(cháng)的文本和分組始終還是太高,基于這個(gè)思想，Wise提出了一個(gè)完全不同的算法,這個(gè)新的算法是基于KR串匹配法:如果-個(gè)哈希值是為- -個(gè)從t開(kāi)始的長(cháng)度為s的串存在,那么-一個(gè)從t+1開(kāi)始的長(cháng)度為s的串的哈希值就可以通過(guò)-個(gè)簡(jiǎn)單的遞推計算出來(lái).特別的，如果模式串的長(cháng)度為P|,那么每一個(gè)在文本串中長(cháng)度為IP|的子串的哈希值都與模式串P的哈希值進(jìn)行比較,如果是相等的，這個(gè)模式串和這個(gè)文本子串進(jìn)行進(jìn)一一步的逐項比較. 注意:如果沒(méi)有匹配的子串,兩個(gè)串和起來(lái)的復雜度是線(xiàn)性的.更重要的是,當所有匹配子串都找到的時(shí)候,復雜度為0(n),可以看到這個(gè)復雜度仍然是接近線(xiàn)性的. RKR-GST算法針對KR串匹配法具體的修正策略如下:1) 不是對整個(gè)模式賦予-一個(gè)單獨的哈希值,而是對模式和正文中所有長(cháng)度為m的子串賦予一個(gè)哈希值.2)模式中的每一個(gè)哈希值都 與正文中的哈希值進(jìn)行比較;對于哈希值相同的每一對模式和正文子串,再對它們進(jìn)行逐個(gè)token的比較.3) 正文中的所有哈希值由一個(gè)專(zhuān)門(mén)的哈希表來(lái)存放,引入這個(gè)哈希表的目的是為了減少在匹配時(shí)的時(shí)間復雜度.這樣處理的話(huà),在正文中查找與模式子串哈希值對應的子串時(shí)，不用掃描整個(gè)正文，而是查找正文對應的哈希表,然后會(huì )返回所有要查找的子串的開(kāi)始位置.注意:在將Karp-Rabin哈希值與實(shí)際子串匹配成功后,還要繼續對匹配進(jìn)行擴展,最后產(chǎn)生最大匹配.4) 用于查找的匹配長(cháng)度s, 在每一次循環(huán)中都會(huì )減少，直到達到最小匹配長(cháng)度minimum-match-length.這里的s是在一次循環(huán)中用于查找的最小匹配長(cháng)度，被稱(chēng)作查找長(cháng)度search-length. 設計一個(gè)名為scanpattem函數,該函數的主要功能就是找出匹配的子串. scanpattern的算法描述如下:對于從T的第一個(gè)未標記的token開(kāi)始的每-一個(gè) T,deif與下一個(gè)覆蓋的距離小于等于sthen在下一次覆蓋后將t提前到第一個(gè)未標記的token為從T,到TI的子中創(chuàng )建KR哈希值并添加到哈希表中對于從P的第-一個(gè)未標記的token開(kāi)始的每一一個(gè) P, do ,在下一次覆蓋后將p提前到第一個(gè)未標記的tokenelse為從Pp。到Ppe的子申創(chuàng )建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(最長(cháng)的最大匹配的長(cháng)度)用于記錄最大匹配的結構是一個(gè)隊列的雙向鏈接列表.每-一個(gè)隊列記錄相同長(cháng)度的最大匹配.整個(gè)列表以遞減順序排序.有一個(gè)指針指向最近追加進(jìn)來(lái)的最大匹配的隊列，因為下一個(gè)最大匹配與最近進(jìn)入的最大匹配的長(cháng)度相同的可能性很高，可將下一個(gè)最大匹配直接加入到當前的這個(gè)隊列中.上述算法的問(wèn)題在于,傳遞給scapattern的參數s應該是一一個(gè)怎樣的值才合適?更準確地說(shuō), s的初值是多少?它的值如何變化?有人認為s的值等于P長(cháng)度的一半比較合適,事實(shí)證明比P的-半小的值就可以滿(mǎn)足要求.有兩個(gè)理由，首先，特別長(cháng)的最大匹配是比較少見(jiàn)的，所以如果給s設置-一個(gè)較大的初值,會(huì )導致scanpattern在找到一個(gè)匹配之前進(jìn)行很大規模的無(wú)結果的搜索. 另外,如果找到一個(gè)長(cháng)的最大匹配(假設這個(gè)最大匹配的長(cháng)度ke =2*s),為這樣的串創(chuàng )建覆蓋后,會(huì )標記大量的模式和正文中的token. 因此在這個(gè)時(shí)候有必要將當前的掃描停止然后重新開(kāi)始-一個(gè)以 k作為查找長(cháng)度的特殊掃描,也就是讓s=k.這意味著(zhù)初始查找長(cháng)度可以設置為一個(gè)較小的常量值,而不是依賴(lài)于串長(cháng)度的一個(gè)值.再設計-一個(gè)markarrays函數,該函數的功能是創(chuàng )建覆蓋并標記覆蓋中的token.函數markarrays的算法與調整GST算法很相似,唯- -不同的是它是應用到一一個(gè)隊列列表上,而不是-個(gè)單獨的隊列上.這里的每-一個(gè)隊列包含長(cháng)度相同的所有最大匹配.這個(gè)markarrays版本也有參數s---查找長(cháng)度, 如下所示: .從隊列頭開(kāi)始,如果是非空隊列do .if當前的隊列是空的then跳到下一個(gè)隊列else從隊列中 刪除match(p,tL)/*假設當前隊列中最大匹配的長(cháng)度為L(cháng)*/if匹配沒(méi)有被阻塞thenif對于從0到s.1 的每-個(gè)j都滿(mǎn)足Ppr=THjthen對于從0到L的每一個(gè)j domark_ token(Ppm)mark. token(T+)length_ of _tokens_ tiled:=length. of_ tokens_ jiled+Lelse if Llocer>=sthen替換在隊列列表中未被標記的部分首先要注意的是，在scanpattemn中的KR哈希后已經(jīng)查找出一個(gè)潛在的子串匹配,如下的成對測試:if從0到s-1的所有j都有Ppr=Trj then .... .可以被延遲，直到markarrays.有兩個(gè)理由.首先,失敗的KR哈希是很少見(jiàn)的;其次,大量由KR哈希得出的匹配,不論真假,都會(huì )被兄弟覆蓋阻塞.因此有必要將這些子串的成對比較延遲到即將進(jìn)行的新覆蓋創(chuàng )建的時(shí)候.4結論通過(guò)分析后發(fā)現, RKRGST算法結合了GST算法的貪心算法策略,最大限度的尋找出最大匹配并創(chuàng )建覆蓋,對token進(jìn)行標記;同時(shí)結合了KR算法的思想,通過(guò)引入哈希表中國煤化工間的相似度時(shí)，用于進(jìn)行匹配的子串的數量大大減少,效率得到了極大提升;最YHCNMH G下情況下為0(n)的GST,變?yōu)榱嗽趯?shí)際運行中時(shí)間復雜度控制在接近線(xiàn)性的RKRGs1. AnkusI異么口前已紅應用到各個(gè)領(lǐng)域，除840西南民族大學(xué)學(xué)報.自然科學(xué)版第36卷了剽竊檢測領(lǐng)域,還有DNA序列匹配等領(lǐng)域,該算法的前景非常寬廣.參考文獻:[] 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