基于近似串匹配算法的評分優化設計

李少芳

（莆田學院 信息工程學院，福建 莆田351100）

1 無紙化考試與自動評分算法

傳統考試的組考流程中每一個環節都是人工操作的，從組織命題到公布成績不僅周期較長，而且安全性也難以得到保證。無紙化考試不僅可以縮短組考周期，節約考試成本，更因為機器自動閱卷，一定程度上減少了人為閱卷的主觀誤差，使考試成績更客觀、更公正。無紙化考試已經在很多領域得到應用和開發[1]，比如教育部的全國計算機等級考試，勞動與社會保障部的全國計算機信息高新技術考試，會計、銀行等行業從業資格考試，機動車駕駛人科目一（理論）考試，高校公共計算機課程網絡無紙化考試等，試題中可包括文本、語音、視頻等交互信息。

計算機自動閱卷評分速度快且準確性高，基本上避免了人工評卷的誤差。由于客觀題有統一規范的答案，其自動閱卷實現較為簡單。對于短文類主觀題，可以直接通過參考答案和學生答案的匹配度來評分；對于相對長的作文類主觀題，通常采用提取淺層結構信息或語義信息，然后根據遣詞造句評分，或者通過與設置的模板匹配來評分。目前計算機自動評分算法有很多，有近似串匹配算法[2]、基于語義脈絡的主觀題自動評分算法[3]、基于分詞匹配的主觀題自動評閱技術[4]、基于文本相似度計算的主觀題自動閱卷技術[5，6]、以關鍵詞匹配為主、語意貼近度計算為輔的參數可調主觀題自動閱卷技術[7],等等。

2 上下文精確匹配的評分示例

以漢字錄入題的評分為例，評分的關鍵在于如何計算錄入的正確字數。通常采用的是簡單的上下文比照對應位置的精確匹配來判斷正確性，在操作界面上要求考生參照標準文本依次錄入漢字，有不會的字符必須用空格占位，并用文字的顏色實時提醒考生所輸入字符的正誤，例如紅色表示錄入正確，藍色表示錄入錯誤，黑色表示尚未錄入。設N 為比較的文字總數，M 為正確的文字數，則文字錄入的正確率為M/N，得分就是M/N*100 取整。如圖1中由于多錄入“首席”兩個字后，后面的錄入雖然看似正確，但全被判為錯誤，顯然這是對添字、漏字等情況的不合理評分，必須加以改進。

圖1 精確匹配算法對添字、漏字等近似串的不合理評分

對于純文本錄入進行自動評分看似簡單，其實要評好評快并不易。目前在許多為考核計算機初級應用能力的計算機上機考試中都包含有采用上下文比照的限時文字錄入題，如果采用的也是這種精確匹配算法進行字符串一一對應來評分的話，實現起來很簡單，然而一旦考生多輸或漏輸一個字符，將導致剩余字符的誤判，顯然這樣的評分方法是不合適的。由于一般機器自動評分的細節不公開，考生是無從了解其合理性的，這里不作評論。

3 近似串匹配算法的VB 實現

近似串匹配(string matching, pattern matching)是一種允許誤差的串匹配，目前已有上百種串匹配算法出現[8]，其廣泛應用于文本檢索、OCR 糾錯和生物信息學等領域。近似串匹配算法實現中，模式串與文本之間的誤差通常用編輯距離來表示，具體操作包括：①刪除，②插入，③替換[9]。例如，給定文本T=”aproxiomally”，P=”approximatly”，從P 到T 要經過一次刪除操作，一次插入操作和一次替換操作，如圖2 所示，因此編輯距離為3。近似串匹配算法的VB 實現代碼如下：

圖2 近似串匹配的三種差別操作(①刪除②插入③替換)

Private Function strmatch (p ( ) As String, t ( ) As

String, m As Integer, n As Integer)

Dim i As Integer，j As Integer, mink As Integer

ReDim d(m，n) As Integer

For j=0 To n

d(0, j)= 0

Next j

For i=0 To m

d(i，0)=i

Next i

For j=1 To n

For i=1 To m

If p(i)=t(j) Then

d(i，j)=mint(d(i-1，j-1)，d(i-1，j)+1，d(i，j-1)+1)Else

d(i，j)=mint(d(i-1，j-1)+1，d(i-1，j)+1，d(i，j-1)+1)End If

Next i

Next j

mink=d(m, 1)

For j=2 To n

If mink＞=d(m, j) Then mink = d(m, j)

Next j

strmatch=mink

End Function

近似串匹配算法對上下文進行匹配比較后，會得到兩段比較文本的最小編輯距離mink，設mink=14，表示有7 處漢字錄入錯誤。

4 近似串匹配算法的評分效果

4.1 對添字情況的合理評分示例

圖3 近似串匹配算法對添字情況的合理評分示例

如圖3 所示，由于多了一個“工”字，后面的錄入雖然看是正確，按上下文一一對應精確匹配的評分算法，一律判為錯誤輸入，顯示為與對照的上文不符的藍色。但采用近似串匹配算法計算后，顯示正確字數為182，僅判斷多出的“工”字和末尾因長度限制無法輸入的句號“。”這兩個字是錯誤的，顯然這樣的判分算法更符合實際情況，更為合理。

4.2 對漏字情況的合理評分示例

圖4 近似串匹配算法對漏字情況的合理評分示例

對于漏字情況，如圖4 所示，由于錄入過程中，漏掉“驚艷的”3 個字，導致后面錄入文字的誤判，顯示為藍色，但采用近似串匹配算法計算后，顯示正確字數為270，僅漏掉的“驚艷的”3 個字被判為錯誤。

5 結束語

圖5 近似串匹配算法對中英文混合文本的評分優化效果圖

以文本錄入評分為例，分析上下文精確匹配評分的不足，運用了近似串匹配算法進行自動評分，大大改進了評分效果，對于添字、漏字、替換錄入等情況的評分都更客觀、更合理。對于中英文混合文本的評分效果如圖5 所示，顯示藍色的字符有8個，但從實錄字數與正確字數的比較可以看出，運用串匹配后，顯示為6 個錯誤，“think”中的“in”是正確的。在實際評分中，對于較大段落的文字的評分，可以按句子劃分后分段測試，以避免耗費很大的空間來存儲對照樣本字符串和待匹配的錄入文字。當然，除對比上下文精確匹配算法評分外，可以嘗試對比如最長公共子序列等其他算法或改進的中文近似字符串匹配算法[10]的評分效果，進一步優化評分設計。快速、客觀、合理的機器自動評分，最大限度地減少人為因素的不利影響，且可能提供即時、豐富的反饋信息，對促進考試的規范化和科學化有著積極的意義。

[1]丁亞濤.無紙化考試平臺構建技術 [J].巢湖學院學報,2007，9(3):32-35.

[2]王紅梅.算法設計與分析[M].北京：清華大學出版社,2006:132-134.

[3]馬昌威.基于語義脈絡的主觀題自動評分算法探討[J].淮海工學院學報(自然科學版)，2013(1):26-29.

[4]馮光,喬丹丹,常靜怡.基于分詞匹配的主觀題自動評閱技術研究[J].計算機與現代化，2013(3):212-214,219.

[5]張添一.基于文本相似度計算的主觀題自動閱卷技術研究[D].長春：東北師范大學，2011：9-23.

[6]楊巍巍.相似度模型在主觀題自動閱卷中的應用[J].數字技術與應用,2013(5):77-78.

[7]倪應華,于莉,呂君可.一種參數可調的主觀題自動閱卷實現[J].浙江師范大學學報(自然科學版)，2008(4):428-431.

[8]劉萍，劉燕兵，郭莉，等.串匹配算法中模式串與文本之間關系的研究[J].軟件學報，2010,21(7):1503-1514.

[9]李少芳，車艷.近似串匹配算法在自動評分系統中的應用[J].東莞理工學院學報，2008,15(3):25-28.

[10]范立新.改進的中文近似字符串匹配算法[J].計算機工程與應用,2006(34)：173-174，207.