劉 鷹

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

errnum1 := 0;

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

{ errnum1 := errnum1+1;

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

}

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

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

errnum2 := 0;

while (ai≠ sj且 i＜alen)

{ errnum2 := errnum2+1;

i := i+1;

}

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

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

errnum3 := 0;

while (ai≠ sj且 j＜slen)

{ errnum3 := errnum3+1;

j := j+1;

}

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

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

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

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

算法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ù)制的保真度。

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

算法1、算法2和算法3在判斷錯(cuò)誤是否結(jié)束時(shí)，僅檢查一個(gè)字符（ ai≠ sj）。實(shí)際上這并不可靠，在錯(cuò)誤片斷中有個(gè)別字符和范文中相應(yīng)位置的字符相同的概率還是很大的，容易造成誤判。解決的方法是將檢查單個(gè)字符換成檢查一個(gè)連續(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ù)先給定的比較長(zhǎng)度。

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

3 算法效率

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

4 結(jié) 論

對(duì)于給定兩個(gè)文本的相似程度比較，不同的算法會(huì)給出不同的結(jié)果。本文提出的基于最大相似設(shè)想的文本比較算法，對(duì)于在文本復(fù)制過(guò)程中出現(xiàn)的錯(cuò)誤，總是選取最優(yōu)分?jǐn)?shù)作為輸出結(jié)果。這是由研制開(kāi)發(fā)自動(dòng)改卷系統(tǒng)提出的問(wèn)題，主要用于考生盲打試卷的自動(dòng)評(píng)判。經(jīng)實(shí)驗(yàn)，該算法的準(zhǔn)確度很高，速度也很快。相信經(jīng)過(guò)適當(dāng)改進(jìn)，也可用于數(shù)據(jù)傳輸質(zhì)量判斷等其他場(chǎng)合。采用本算法的自動(dòng)判卷系統(tǒng)在 .NET 環(huán)境下用C#編程實(shí)現(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].計(jì)算機(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ìn)研究[J].情報(bào)學(xué)報(bào)，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.