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

劉 鷹

（西安文理學院 陜西 西安 710065 ）

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

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

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

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

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

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

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

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

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

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

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

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

1 匹配錯誤產生的原因及其判定算法

在逐字比較范文字符串s和拷貝字符串a的匹配過程中，如果發現拷貝中的某字符ai與范文中的對應字符sj不符，則其原因不外是:

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

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

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

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

算法1 求誤發字符個數。

errnum1 := 0;

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

{ errnum1 := errnum1+1;

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

}

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

算法2 求多發字符個數。

errnum2 := 0;

while (ai≠ sj且 i＜alen)

{ errnum2 := errnum2+1;

i := i+1;

}

算法結束后，errnum2中存放有多發字符個數。

算法3 求漏發字符個數。

errnum3 := 0;

while (ai≠ sj且 j＜slen)

{ errnum3 := errnum3+1;

j := j+1;

}

算法結束后，errnum3中存放有漏發字符個數。

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

2 最大相似設想及其算法

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

算法4 基于最大相似設想的串匹配算法

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

{ 分別求出誤發字符數err1，多發字符數err2和漏發字符數err3;

if(誤發字符數err1最小)

{ err := err + err1;

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

}

else if(多發字符數err2最小)

{ err := err + err2;

i := i + err2;

}

else if(漏發字符數err3最小)

{ err := err + err3;

j := j + err3;

}

}

}

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

算法的結果r是復制的保真度。

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

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

算法5 片斷比較

same := true;

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

{

if (ai≠ sj)

{ same := false;

跳出循環結束比較;

}

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

}

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

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

3 算法效率

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

4 結 論

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

[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] 王艷清，王云維.監控文本文件內容變化的文本比較算法[J].計算機應用, 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].情報學報，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.