孫宇揚，歐 云，奉松綠，周愷卿

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

字符串相似度檢測是計算機領(lǐng)域的基礎(chǔ)研究問題之一，在抄襲檢測系統(tǒng)[1]、防代碼剽竊系統(tǒng)[2]、自動評分系統(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è)計的目的是為了檢測2個字符串的相似度.由于算法執(zhí)行過程中采取字符串逐個比較的機制，因而GST存在效率低、時間復(fù)雜度較大、掃描時間長等缺陷[6].徐黎明等[4]提出了一種將克努特-莫里斯-普拉特算法(Knuth-Morria-Pratt，KMP)和GST算法相結(jié)合的改進算法來提升GST算法的掃描速度.巫喜紅等[7]采用2次Hash函數(shù)和雙向并行匹配方法改進隨機串匹配(Karp-Rabin，KR)算法，提高了模式匹配速度.金恩海等[8]將LCS算法應(yīng)用到GST算法中的數(shù)據(jù)預(yù)處理階段，提升了算法的準確性.受以上研究啟發(fā)，筆者擬設(shè)計一種改進的雙向的KR算法，并將其應(yīng)用到GST算法中的掃描階段，以期減少字符的比較次數(shù)，提高字符串相似度檢測算法的運行效率.

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

1.1 GST算法

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

1.2 KR算法

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

2 算法的改進

2.1 改進算法的思路

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

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

2.2 改進算法的流程

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

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

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

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

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

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

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

改進算法的流程如圖1所示.

圖1 改進算法的流程Fig. 1 Improved Algorithm Flow

3 實驗結(jié)果與討論

表1 部分數(shù)據(jù)

表2 查重結(jié)果

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

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

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

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

4 結(jié)語

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