西南民族大學學報.自然科學版第36卷第5期Sep. 2010Jourmal of Southwest University for Nationalities Natural Science Edition文章編號: 1003-2843(2010)05-0836-05基于RKRGST的算法分析肖麗，校景中(西南民族大計算機科學與技術學院,四川成都610041)摘要:在各大高校,剽竊檢測系統(tǒng)已經被廣泛的使用,用于檢測學生在學生中出現(xiàn)的不誠實現(xiàn)象.對于這種剽竊檢測系統(tǒng),其核心就是對兩個學生的作業(yè)進行相似度度量,當達到一個高的相似度,就具有剽竊的嫌疑,為老師公正的作出評判提供依據(jù).本文研究了一種在各大剽竊檢測系統(tǒng)中廣泛使用的RKRGST算法,該算法結合了KR算法和GST算法,通過分析發(fā)現(xiàn)該算法在計算字符串相似度時具有較高的效率.關鍵字:相似度; RKRGST: KR; GST中圖分類號: TP31文獻標識碼: A1引言在源碼剽竊檢測技術中,最核心的部分是對于兩個源程序相似度的計算,到底兩個程序在多大程度上相似?為了得到這個相似值，人們想盡了辦法,提出了很多算法.最簡單的相似度算法集中在簡單的串匹配上.因為目前幾乎所有的源碼剽竊檢測技術都是先將源程序轉換為token流的形式,然后用串匹配的方式對token流|"進行匹配，計算器相似度.常用的串匹配算法有: KMP算法、BM算法、RK算法*.本文研究- -種基于RK和GST的RKRGST算法.事實上, Wise提出的RKRGST幾乎已經成為當前很多剽竊檢測系統(tǒng)的標準算法,如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的子串的覆蓋遺憾的是,在多項式時間內產生和計算最大覆蓋是-個開放問題.部分原因在于多個小的覆蓋共同聯(lián)合起來標記的token數(shù)量可能比少量大的覆蓋標記的token 多.但是，大的覆蓋更能反映源代碼中的相似段,而小的覆蓋很多時候可能只是偶然的相似，不具備說服力.于是在創(chuàng)建覆蓋時,先創(chuàng)建更大的覆蓋,小的覆蓋放到后面處理.這樣就可以解決上述提到的問題.通過觀察發(fā)現(xiàn),如果P中的- -個token與T中的任意位置的token匹配,那這里至少會找到一個覆蓋的長度為1的部分.因此,任何參與到-一個覆蓋中的token, 它- -定是在-個覆蓋面積最大的覆蓋中.為了獲取度量值，需要簡單的將剩下的未被覆蓋的token進行最小化,如果是完全匹配的兩個串的話，這個度量值將為0.然而，如果強制要求一個匹配的最小匹配長度要高于1, 就可能導致一個次優(yōu)的結果(只能計算到一個近似的度量值).例如，如果-個最小匹配長度(minimum-match-length)為2,有以下兩個串: .P=cabaa貪心算法會選擇P的子串(aabaa)與 T進行匹配---匹配長度為 5,而不是選擇另外兩個子串(caa)和(aad)--- _匹配長度為 7.這個例子說明，當一個最小匹配長度大于1時,由GST返回的值是最優(yōu)值的一一個近似值，最優(yōu)值是當最小匹配長度為1時計算得到的.在GST算法描述的每一個循環(huán)的兩個階段中, 第-一個階段用于尋找最大匹配maxmatch,第二個階段用于創(chuàng)建最大覆蓋.在這里,第-一個階段的代價更大，原因是，在這里可能有最多(TI- L)<(PI- L)個的最大匹配(L表示找到的最大maximal-match的長度),但最多只可能創(chuàng)建IP/L個覆蓋(創(chuàng)建覆蓋的開銷是線性的).所有其他的最大匹配將很快的被淘汰;阻塞將通過- -對簡單的測試解決.而且，在-一個循環(huán)中形成的覆蓋越多,遺留給后續(xù)循環(huán)處理的未標記的子串就越短.最壞的情況是每一一次迭代只能找到一個最大匹配，而這個最大匹配只比上一次迭代中找到的匹配長度小-一個token,最后-次迭代中找到的-定是長度為minimum_ match_ length 的匹配.如果假設|P=T]=n,那么與長度n對應的不同長度的不同子串的最大數(shù)量大約為√2n.同時假設所有已標記的子串必須在P和T串的一-端那么,最后長度為1(這里假設minimum_ match. length 的值為1)的最大匹配將在P和T中只出現(xiàn)-一次,這只需要- -次簡單比較;長度為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的最大匹配數(shù)相加，結果為0(n).2.2KR算法.對長為m的字符串賦以-個散列函數(shù),在正文中由于只有那些與模式具有相同散列函數(shù)值的子段才有可能與模式匹配,這樣就不必考察正文中的長為m的全部子段.在進行串匹配時,先在正文中找到和模式串的散列函數(shù)值相同的子段，再進行匹配檢查,以此類推,直到最后-個子串. 下面是對該算法的描述:d是正文和模式中可能出現(xiàn)的不同字符個數(shù),本書中取d=32.正文與模式中每個字符對應于-一個0到d-1 之間的數(shù).則子段a[ i,i+m-1]可以表示為下列整數(shù): .x, =orda[])d"'+ oda(i+1])d -2+ .... ordati+m-])x。=0其中ord -個映射,它將P和T中的字符映射到{0,1,2, ...中國煤化工散列函數(shù): h(x)=x mod qYHCNMHG838西南民族大學學報.自然科學版第36卷其中,x是一整數(shù), q是適當大的素數(shù).所以長度為m的字符段的散列函數(shù)值的遞推公式為: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哈希值與實際子串匹配成功后,還要繼續(xù)對匹配進行擴展,最后產生最大匹配.4) 用于查找的匹配長度s, 在每一次循環(huán)中都會減少，直到達到最小匹配長度minimum-match-length.這里的s是在一次循環(huán)中用于查找的最小匹配長度，被稱作查找長度search-length. 設計一個名為scanpattem函數(shù),該函數(shù)的主要功能就是找出匹配的子串. scanpattern的算法描述如下:對于從T的第一個未標記的token開始的每-一個 T,deif與下一個覆蓋的距離小于等于sthen在下一次覆蓋后將t提前到第一個未標記的token為從T,到TI的子中創(chuàng)建KR哈希值并添加到哈希表中對于從P的第-一個未標記的token開始的每一一個 P, do ,在下一次覆蓋后將p提前到第一個未標記的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(最長的最大匹配的長度)用于記錄最大匹配的結構是一個隊列的雙向鏈接列表.每-一個隊列記錄相同長度的最大匹配.整個列表以遞減順序排序.有一個指針指向最近追加進來的最大匹配的隊列，因為下一個最大匹配與最近進入的最大匹配的長度相同的可能性很高，可將下一個最大匹配直接加入到當前的這個隊列中.上述算法的問題在于,傳遞給scapattern的參數(shù)s應該是一一個怎樣的值才合適?更準確地說, s的初值是多少?它的值如何變化?有人認為s的值等于P長度的一半比較合適,事實證明比P的-半小的值就可以滿足要求.有兩個理由，首先，特別長的最大匹配是比較少見的，所以如果給s設置-一個較大的初值,會導致scanpattern在找到一個匹配之前進行很大規(guī)模的無結果的搜索. 另外,如果找到一個長的最大匹配(假設這個最大匹配的長度ke =2*s),為這樣的串創(chuàng)建覆蓋后,會標記大量的模式和正文中的token. 因此在這個時候有必要將當前的掃描停止然后重新開始-一個以 k作為查找長度的特殊掃描,也就是讓s=k.這意味著初始查找長度可以設置為一個較小的常量值,而不是依賴于串長度的一個值.再設計-一個markarrays函數(shù),該函數(shù)的功能是創(chuàng)建覆蓋并標記覆蓋中的token.函數(shù)markarrays的算法與調整GST算法很相似,唯- -不同的是它是應用到一一個隊列列表上,而不是-個單獨的隊列上.這里的每-一個隊列包含長度相同的所有最大匹配.這個markarrays版本也有參數(shù)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哈希得出的匹配,不論真假,都會被兄弟覆蓋阻塞.因此有必要將這些子串的成對比較延遲到即將進行的新覆蓋創(chuàng)建的時候.4結論通過分析后發(fā)現(xiàn), RKRGST算法結合了GST算法的貪心算法策略,最大限度的尋找出最大匹配并創(chuàng)建覆蓋,對token進行標記;同時結合了KR算法的思想,通過引入哈希表中國煤化工間的相似度時，用于進行匹配的子串的數(shù)量大大減少,效率得到了極大提升;最YHCNMH G下情況下為0(n)的GST,變?yōu)榱嗽趯嶋H運行中時間復雜度控制在接近線性的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