基于局部最大相似設(shè)想的串匹配算法

劉 鷹

（西安文理學(xué)院 陜西 西安 710065 ）

在機考自動判卷系統(tǒng)中，如何判斷考生輸入答案與范文的相似程度是一個核心問題，這可以歸結(jié)為文本比較算法的設(shè)計。

比較兩個文本的相似程度，常用的算法有模糊哈希（Fuzzy Hashing）算法、列文斯頓距離（Levenshtein Distance）算法等。

模糊哈希算法主要用于文件的相似性比較，又稱基于內(nèi)容分割的分片哈希算法（Context Triggered Piecewise Hashing，CTPH）。

2006年，Jesse Kornblum[1]提出了模糊哈希算法并給出了一個算法實例。隨后，Jason Sherman又開發(fā)了一個名為ssdeep的工具軟件以實現(xiàn)這一算法。該算法最初用于計算機取證，后來又被用于惡意代碼檢測，最近又有用于開源軟件漏洞挖掘等。

模糊哈希算法的主要原理是使用一個弱哈希函數(shù)計算文件局部內(nèi)容，在特定條件下對文件進行分片，然后使用一個強哈希函數(shù)對文件的每個片段計算哈希值，取這些值的一部分并連接起來，與分片條件一起構(gòu)成一個模糊哈希結(jié)果。使用一個字符串相似性對比算法判斷兩個模糊哈希值的相似度有多少，從而判斷兩個文件的相似程度。

對文件的部分變化（包括在多處修改、增加、刪除部分內(nèi)容），使用模糊哈希均能發(fā)現(xiàn)其與源文件的相似關(guān)系，是目前判斷相似性較好的一種方法。

列文斯頓距離（Levenshtein Distance）算法[2]用來計算從原串（s）轉(zhuǎn)換到目標串（t）所需要的最少的插入、刪除和替換數(shù)目。列文斯頓距離亦稱編輯距離（Phrase Edit Distance），最早由俄國數(shù)學(xué)家列文斯頓（Vladimir Levenshtein）提出，在自然語言處理（Natural Language Processing，NLP）中應(yīng)用比較廣泛。

列文斯頓距離算法可以看作一個動態(tài)規(guī)劃，其思路是從兩個字符串的左邊開始比較，記錄已經(jīng)比較過的子串相似度（即距離），然后進一步得到下一個字符位置時的相似度。

其他文本比較算法還有KMP算法（Knuth-Morris-Pratt)[3]和BM（Boyer-Moore）[4]算法。這兩個算法主要用于精確查找。

國內(nèi)也有一些對文本或字符串比較算法的研究，如北京交通大學(xué)的王艷清等[5]和武漢大學(xué)信息資源研究中心的李剛等[6]，分別討論了具體應(yīng)用環(huán)境下的文本或字符串比較算法。

雖然上述算法都是成熟的文本比較算法，也都有廣泛的應(yīng)用，但就盲打機考機考系統(tǒng)的具體問題，都還存在各種具體問題，如模糊哈希算法主要用于文件比較，列文斯頓距離算法用于盲打機考判分時結(jié)果不夠直觀等，對于盲打機考評判這一任務(wù)，尚無特別有效的算法可供選擇。

因此，在本文引入了最大相似程度的概念，其出發(fā)點是認為考生在做打字測試時總是力圖犯最少的錯誤，從而爭取更高的分數(shù)。據(jù)此我們設(shè)計了基于局部最大相似設(shè)想的串匹配算法。

1 匹配錯誤產(chǎn)生的原因及其判定算法

在逐字比較范文字符串s和拷貝字符串a(chǎn)的匹配過程中，如果發(fā)現(xiàn)拷貝中的某字符ai與范文中的對應(yīng)字符sj不符，則其原因不外是:

1）復(fù)制時誤發(fā)字符，即本應(yīng)為sj字符而錯發(fā)為ai字符。驗證方法為跳過ai和sj，比較ai+1和sj+1。若有ai+1= sj+1，則可確認為誤發(fā)字符(假定錯發(fā)字符后的復(fù)制正確，下同)。

2）復(fù)制時多發(fā)一字符，即在正確字符前誤發(fā)某字符。驗證方法為跳過ai，比較ai+1和sj。若有ai+1= sj，則可確認為多發(fā)字符。

3）復(fù)制時漏發(fā)一字符，即本該發(fā)某字符而未發(fā)。驗證方法為跳過sj，比較ai和sj+1，若有ai= sj+1，則可確認為漏發(fā)字符。

考慮到上述誤發(fā)、多發(fā)和漏發(fā)字符均可能連續(xù)發(fā)生，因此需修正上述驗證方法。為此提出下列驗證算法。

算法1 求誤發(fā)字符個數(shù)。

errnum1 := 0;

while (ai≠ sj且 i＜alen 且 j＜slen)

{ errnum1 := errnum1+1;

i := i+1; j := j+1;

}

其中slen和alen分別為范文字符串和拷貝字符串的長度。算法結(jié)束后，errnum1中存放有誤發(fā)字符個數(shù)。

算法2 求多發(fā)字符個數(shù)。

errnum2 := 0;

while (ai≠ sj且 i＜alen)

{ errnum2 := errnum2+1;

i := i+1;

}

算法結(jié)束后，errnum2中存放有多發(fā)字符個數(shù)。

算法3 求漏發(fā)字符個數(shù)。

errnum3 := 0;

while (ai≠ sj且 j＜slen)

{ errnum3 := errnum3+1;

j := j+1;

}

算法結(jié)束后，errnum3中存放有漏發(fā)字符個數(shù)。

上述3個比較算法結(jié)束后，都應(yīng)有ai= sj，此時可以繼續(xù)進行匹配；或者已經(jīng)達到了范文字符串或拷貝字符串的尾部，此時匹配結(jié)束。

2 最大相似設(shè)想及其算法

在實際的復(fù)制過程中，上述3種錯誤可能單獨出現(xiàn)，也可能連續(xù)發(fā)生，還可能以各種方式結(jié)合出現(xiàn)。在這種情況下，要確定采用哪個算法來確定實際的錯誤數(shù)并不容易。因此，我們以最大相似設(shè)想來指導(dǎo)匹配算法的設(shè)計。即在匹配過程中，任何時候如果發(fā)現(xiàn)不匹配字符（即 ai≠ sj），則分別按誤發(fā)、多發(fā)和漏發(fā)情況進行統(tǒng)計，分別得出假設(shè)錯誤為誤發(fā)字符時，誤發(fā)字符個數(shù)errnum1，假設(shè)錯誤為多發(fā)字符時，多發(fā)字符個數(shù)errnum2， 已經(jīng)假設(shè)錯誤為漏發(fā)字符時的漏發(fā)字符個數(shù)errnum3。然后，選擇errnum1，errnum2，和errnum3中最小的那一個確定實際的錯誤類型，并跳過發(fā)生錯誤的部位，繼續(xù)進行匹配。也就是說，總是假定復(fù)制過程中復(fù)制操作是盡量準確的，在錯誤出現(xiàn)時，要按最好情況（錯誤最少）考慮。

算法4 基于最大相似設(shè)想的串匹配算法

i := 0; j := 0; k := 0; err := 0; r = 0;

while(i＜alen 且 j＜slen)

{ if (ai = sj)

{ i := i + 1; j := j + 1; k := k + 1;

}

else

{ 分別求出誤發(fā)字符數(shù)err1，多發(fā)字符數(shù)err2和漏發(fā)字符數(shù)err3;

if(誤發(fā)字符數(shù)err1最小)

{ err := err + err1;

i := i + err1; j = j + err1;

}

else if(多發(fā)字符數(shù)err2最小)

{ err := err + err2;

i := i + err2;

}

else if(漏發(fā)字符數(shù)err3最小)

{ err := err + err3;

j := j + err3;

}

}

}

r := 100 * (slen – err) / slen;

算法的結(jié)果r是復(fù)制的保真度。

考慮一個特例，即拷貝字符串的長度為零（相當(dāng)于交白卷）。因為不會在拷貝字符串中找到錯誤，上述算法會給出100分！為了防止這種情況，在匹配開始前，如果拷貝字符串a(chǎn)長度小于范文字符串s，則用范文串中沒有出現(xiàn)過的字符（如特殊字符“#”等）添加到拷貝字符串后面，直到其長度與范文字符串s相同。

算法1、算法2和算法3在判斷錯誤是否結(jié)束時，僅檢查一個字符（ ai≠ sj）。實際上這并不可靠，在錯誤片斷中有個別字符和范文中相應(yīng)位置的字符相同的概率還是很大的，容易造成誤判。解決的方法是將檢查單個字符換成檢查一個連續(xù)的小片斷，即有：

算法5 片斷比較

same := true;

for (k := 0; k ＜ size 且 i ＜ slen 且 j ＜ alen; k++)

{

if (ai≠ sj)

{ same := false;

跳出循環(huán)結(jié)束比較;

}

i := i+1; j := j+1;

}

其中same是返回值，為真則表示比較成功。size 是預(yù)先給定的比較長度。

用上述算法替換算法1、算法2和算法3中的檢測條件ai≠ sj。經(jīng)試驗，就打字測試而言，將片斷長度size設(shè)置為3或4就可取得很好的結(jié)果。

3 算法效率

該算法無回溯，在發(fā)生錯誤時向前搜索。因此最壞情況的耗時時間為O(n2)，n為范文字符串長度。實際上，由于常用字符集有限，該算法效率非常高。經(jīng)實際測試，一般情況下比較運算次數(shù)遠小于范文字符串長度，即算法實際耗時接近O(n)。該算法無需額外存儲空間，即空間效率為O(n)。

4 結(jié) 論

對于給定兩個文本的相似程度比較，不同的算法會給出不同的結(jié)果。本文提出的基于最大相似設(shè)想的文本比較算法，對于在文本復(fù)制過程中出現(xiàn)的錯誤，總是選取最優(yōu)分數(shù)作為輸出結(jié)果。這是由研制開發(fā)自動改卷系統(tǒng)提出的問題，主要用于考生盲打試卷的自動評判。經(jīng)實驗，該算法的準確度很高，速度也很快。相信經(jīng)過適當(dāng)改進，也可用于數(shù)據(jù)傳輸質(zhì)量判斷等其他場合。采用本算法的自動判卷系統(tǒng)在 .NET 環(huán)境下用C#編程實現(xiàn)。

[1] Jesse Kornblum. Identifying almost identical files using context triggered piecewise hashing[J]. Digital Investigation，2006:91-97.

[2] Wagner，Robert A,Fischer，Michael J. The String-to-String Correction Problem[J]. Journal of the ACM 21,1974(1): 168-173.

[3] Knuth,Donald.The Art of Computer Programming，Volume 3:Sorting and Searching[M]. Second Edition.Reading,Massachusetts: Addison-Wesley, 1998.

[4] Robert S,Moore, Strother J .A Fast String Searching Algorithm[J]. Comm. ACM :New York, NY, USA: Association for Computing Machinery,1977,20 (10): 762-772.

[5] 王艷清，王云維.監(jiān)控文本文件內(nèi)容變化的文本比較算法[J].計算機應(yīng)用, 2010，30（S1）: 133-135.WANG Yan-qing, WANG Yun-wei. Text comparison algorithm for detecting content change in text files[J]. Journal of Computer Applications, 2010, 30(S1):133-135.

[6] 李綱，夏晨曦，鄭重.局部文本特征選取算法的比較和改進研究[J].情報學(xué)報，2008,27（4）: 506-511.LI Gang, XIA Chen-xi, ZHENG Zhong. A comparative and improving study of local feature selection algorithms in Text Categorization[J]. Journal of the China Society for Scientific and Technical Information, 2008, 27(4): 506-511.