基于改進(jìn)GST算法的字符串相似度檢測(cè)*

孫宇揚(yáng)，歐 云，奉松綠，周愷卿

(吉首大學(xué)信息科學(xué)與工程學(xué)院，湖南 吉首 416000)

字符串相似度檢測(cè)是計(jì)算機(jī)領(lǐng)域的基礎(chǔ)研究問題之一，在抄襲檢測(cè)系統(tǒng)[1]、防代碼剽竊系統(tǒng)[2]、自動(dòng)評(píng)分系統(tǒng)和生物DNA序列匹配[3]等領(lǐng)域都有非常廣泛的應(yīng)用.字符串近似匹配算法有編輯距離算法(Levenshtein Distance，LD)、最長公共子串算法(Longest Common Subsequence，LCS)、貪婪串匹配算法( Greedy String Tiling，GST)[4]等.

GST是字符串近似匹配的經(jīng)典算法的代表[5].該算法設(shè)計(jì)的目的是為了檢測(cè)2個(gè)字符串的相似度.由于算法執(zhí)行過程中采取字符串逐個(gè)比較的機(jī)制，因而GST存在效率低、時(shí)間復(fù)雜度較大、掃描時(shí)間長等缺陷[6].徐黎明等[4]提出了一種將克努特-莫里斯-普拉特算法(Knuth-Morria-Pratt，KMP)和GST算法相結(jié)合的改進(jìn)算法來提升GST算法的掃描速度.巫喜紅等[7]采用2次Hash函數(shù)和雙向并行匹配方法改進(jìn)隨機(jī)串匹配(Karp-Rabin，KR)算法，提高了模式匹配速度.金恩海等[8]將LCS算法應(yīng)用到GST算法中的數(shù)據(jù)預(yù)處理階段，提升了算法的準(zhǔn)確性.受以上研究啟發(fā)，筆者擬設(shè)計(jì)一種改進(jìn)的雙向的KR算法，并將其應(yīng)用到GST算法中的掃描階段，以期減少字符的比較次數(shù)，提高字符串相似度檢測(cè)算法的運(yùn)行效率.

1 相關(guān)概念和技術(shù)

1.1 GST算法

GST算法通過反復(fù)對(duì)模式串和文本串遍歷搜索來實(shí)現(xiàn)字符串匹配功能，其中較短的字符串被稱為模式串，較長的字符串則被稱為文本串[5].GST算法的基本原理為：若比較的2個(gè)字符串相同，則返回一個(gè)與較短字符串的長度相同的值，反之，則返回最小值0.

1.2 KR算法

KR算法是使用散列函數(shù)從文本中搜尋單個(gè)模式串的字符串搜索算法[6].其算法思想為：定義一個(gè)Hash函數(shù)，利用Hash函數(shù)先對(duì)模式串進(jìn)行數(shù)值化，得到一個(gè)散列碼；將文本串中與模式串長度相同的每個(gè)子串進(jìn)行數(shù)值化，得到相應(yīng)的多個(gè)散列碼；用模式串的散列值依次與文本串的散列值進(jìn)行兩兩比較，若相等，則判斷其對(duì)應(yīng)字符是否相等，進(jìn)而確定字符串是否匹配[7].

2 算法的改進(jìn)

2.1 改進(jìn)算法的思路

首先，對(duì)KR算法進(jìn)行改進(jìn)，在計(jì)算字符串的哈希值時(shí)，從文本串和模式串的開頭和結(jié)尾兩端同時(shí)求哈希值，并進(jìn)行比較，判斷字符串是否匹配.

其次，將改進(jìn)KR算法應(yīng)用到GST算法的掃描階段，搜索所有相同子串.

2.2 改進(jìn)算法的流程

Step1首先假設(shè)2個(gè)字符串分別為T和P，定義隊(duì)列tiles，最小匹配長度為Lmin，最大匹配長度Lmax，搜索長度s.

Step2判斷當(dāng)前s和Lmin的大小關(guān)系，若s

Step3遍歷字符串T，若當(dāng)前下標(biāo)的字符沒有被標(biāo)記(初始狀態(tài)均為未標(biāo)記)，若s小于Lmax，則移動(dòng)下標(biāo)，否則使用改進(jìn)KR算法計(jì)算出T串的散列值.

Step4遍歷字符串P，若當(dāng)前下標(biāo)的字符沒有被標(biāo)記(初始狀態(tài)均為未標(biāo)記)，則使用改進(jìn)KR算法計(jì)算出該串中長度為s的子串的散列值；若T和P的散列值相等且當(dāng)前下標(biāo)的字符相等，則同時(shí)往后尋找一位，重新計(jì)算并比較散列值，直到T和P當(dāng)前位置的散列值不同.此時(shí)若搜索長度s大于2倍的Lmax，則更新最大匹配長度并返回step 3.

Step5記錄最大匹配，每個(gè)隊(duì)列記錄相同長度的最大匹配，隊(duì)列列表的次序按照長度依次遞減.針對(duì)隊(duì)列中的tile，循環(huán)最大匹配長度，對(duì)已經(jīng)匹配的長度進(jìn)行標(biāo)記.若最大匹配中還有未做記號(hào)的部分，則替換列表隊(duì)列上的未標(biāo)記部分.

Step6若當(dāng)前搜索長度s大于2倍的最小匹配長度Lmin，則將s更新為s的一半，跳轉(zhuǎn)到step 2；否則，若當(dāng)前搜索長度大于最小匹配長度Lmin，則將s更新為最小匹配長度，跳轉(zhuǎn)到step 2.

Step7輸出匹配結(jié)果，算法結(jié)束.

改進(jìn)算法的流程如圖1所示.

圖1 改進(jìn)算法的流程Fig. 1 Improved Algorithm Flow

3 實(shí)驗(yàn)結(jié)果與討論

表1 部分?jǐn)?shù)據(jù)

表2 查重結(jié)果

由表2可知，模式串7抄襲的可能性較大，其他模式串抄襲的可能性較小.

在相同的數(shù)據(jù)集上進(jìn)行代碼查重實(shí)驗(yàn)，改進(jìn)算法和GST算法的字符串比較次數(shù)結(jié)果見表3.

表3 2種算法的比較次數(shù)

由表3可知，改進(jìn)算法相比GST算法，在運(yùn)行次數(shù)上有了大幅度的降低，從而提高了算法的整體運(yùn)行效率.

4 結(jié)語

GST算法在運(yùn)行過程中存在時(shí)間復(fù)雜度高、效率低等缺點(diǎn)，為了克服這些缺點(diǎn)，提出了一種改進(jìn)的KR算法.通過對(duì)KR算法采取雙向并行搜索方式，來提高KR算法的匹配速度，進(jìn)而將其應(yīng)用在GST算法中的掃描階段，提升GST算法的搜索效率.學(xué)生作業(yè)源代碼為實(shí)驗(yàn)數(shù)據(jù)對(duì)改進(jìn)算法和GST算法進(jìn)行了性能測(cè)試，結(jié)果表明改進(jìn)算法減少了匹配次數(shù)，降低了算法運(yùn)行時(shí)間，提高了代碼查重的效率.后續(xù)將從查重精度方面進(jìn)一步改進(jìn)算法.