一種改進的KMP算法及其在主觀題評分中的應用

◆姚秀情

（陽光學院 福建 350015）

1 引言

在我國現有的教育制度下，考試仍然是衡量學校教學質量的一個重要途徑，而現今網絡技術的飛速發展使得在線考試系統越來越普及，它可以作為平常教學輔助的一種方式，對提高教學水平能提供強有力的幫助。而現有的在線考試系統大部分都只有客觀題，對于一些科目來說，只有客觀題無法全面體現學生的能力，主觀題要求學生能自己組織材料，并采用合適的方式表達陳述出來，通過這類試題的考試，可以全面了解學生對某門課程的知識點理解和掌握的程度，所以作為一種教學輔助手段，一個帶有主觀題并能自動評分的在線考試系統非常必要。

2 問題分析及相關研究

考試系統中客觀題的評判相對簡單，而對于主觀題我們只能通過模糊關鍵詞匹配[1]的方式實現主觀題的自動閱卷評分，這樣的關鍵詞模糊匹配可以通過字符串的匹配來實現，它是指從一個大字符串找到模式串出現的位置[2]。這種字符串匹配不僅可以用于英文字符的查找，對于中文文本也同樣適用，如：文本串P 串：計算機的發展經歷了哪幾個階段 S 串：發展經歷 找出S 串在P 串中出現的對應位置，這樣的算法有很多，其中有BF 算法，KMP 算法，Sunddy 算法等等，其中KMP 算法是一種經典的字符串匹配算法，此算法通過對模式串在不匹配時其本身就包含足夠的信息，來判斷其下一個匹配的字符將

3 主觀題評分的基本實現過程

3.1 數據庫的設計和連接

在本文中采用開發環境的是vb 和access 數據庫相結合的方式來實現對主觀題的自動評分的，在創建數據庫后，接下來需要考慮的是如何使用vb 的控件對其進行存取和管理，在此使用ado 數據庫引擎來創建數據庫與VB 的數據連接，首先得進行的步驟采用“工程” “引用”中的 ADO 即 Microsoft ActiveX Data Objects 2.X Library（建議用2.6 往上）），其ADO 數據庫引擎創建的數據庫連接的格式為Di m conn As New ADODB.Connection conn.Open "Provider=Micros oft.Jet.OLEDB.4.0；DataSource=E：aa.mdb；PersistSecurity Info=Fal se"，在此要特別注意data source 參數是數據庫的實際路徑。從哪里開始，從而避免重新檢查先前匹配的字符，在某種程度上提高了算法的效率，但對于大多數的學習者來說理解起來困難，把它運用于實際應用中，那更是難上加難，在這里將其做了一點點改進，理解上將更加容易，其改進的算法的過程如下：

（1）遵循KMP 算法的指導思想，主串s 與模式串t 匹配時，當發生失配時，尋找下一個與s 串失配字符匹配的t 串字符時，主串s的下標i 不回溯。

（2）改進的算法的基本思想是：當主串字符s[i]與模式串字符t[j]第一次匹配發生失配時，設置變量k 使得主串在k 位置上重新與模式串從頭開始進行新一輪的比較，若匹配成功則繼續比較剩余字符，若不成功，k 的值將大于i 的值，將跳出內部循環，將主串的K位置的字符與模式串t 的第一個字符重新進行下一輪的匹配，以此類推，直至結束。

（3）若模式串t 的下標j 大于模式串的長度時則表示在主串中找到了模式串。

改進的算法效率也是o（m+n），但它簡單明了，容易理解，其實現過程如圖1所示：

圖1 實現過程

3.2 主要界面的設計

在本例中的主要界面里采用label 設置了題號、題型、題目的內容，當它與數據庫中的題號、題型、題目的內容字段一致時，查詢其對應的標準答案，另外采用一個文本框用于考試者輸入答案，用一個命令按鈕觸發其評分動作，隨后將考試者在文本框中輸入的內容與標準答案中查詢出來的信息進行字符串匹配，無論有無得分點，都將最終的得分寫進數據庫中。

3.3 關鍵技術的分析

本文提出的主觀題自動閱卷的實現方法的關鍵點是：將標準答案與考試者輸入的答案進行字符串比對，但在比對前，需先在數據庫中將標準答案進行關鍵詞提取，關鍵詞之間用空格進行間隔，然后錄入，每個關鍵詞設置一個得分比例，要進行比對時，首先將標準答案讀取出來后，按空格提取其中的每一個關鍵詞，然后與考生的答案進行比較。在這里提出的關鍵詞匹配只是一種模糊的匹配，它不要求標準答案與考試者的答案完全匹配，考試者答案中出現關鍵詞的順序可以和標準答案的關鍵詞的順序不一樣，它的順序可以是跳躍性的，[3]只要找到關鍵詞，則按每個關鍵詞的比例得分，若答案中的每一個關鍵詞都找到，則本題得到全部分數。之所以采用這種關鍵詞模糊匹配算法，主要是因為中文的語法形式多樣，由于各種各樣的原因，比如人的語言習慣的不同，思考的方式的不同等，不同的表達方式但表達的意思卻能夠大致一樣，比如：“制作面包的主要原料是：面粉、水、酵母、鹽四種”的另一種表達方式為“面粉、酵母、水、鹽是制作面包的四種主要原料”，所以在制作標準答案時只需提取“制作面包、水、酵母、鹽、面粉”幾個關鍵詞與考試者輸入的答案進行近似比較，若有找到這些關鍵詞就表明考試者大概獲取了題目的關鍵信息，就能獲取到本題的得分。

3.4 算法實現過程

一個正常的考試系統必然會包括選擇題、填空題、判斷題、計算題、簡答題等，無論什么題型，我們在數據庫中必須設計數據庫表，表中包含了題號，題型，題目內容、標準答案、分值、本題得分等字段，除簡答題外其余題目只要將考生答案與標準答案比較后，判斷是否完全相等就可得到本題得分，而簡答題的判斷相對復雜，在這里關鍵詞模糊匹配的方法。首先使用ADO 引擎連接數據庫，接著使用sql語言查詢當lable的caption即題目序號和題目內容和數據庫表中的題號、題目內容相等時，sql 查詢語句具體如下 ：sql = "select * from ks where 題號='" & Label3.Caption & "'and 題目內容='" &Label2.Caption & "'"提取相對應的標準答案的字符串“采樣 量化 編碼”，由于標準答案字符串“采樣 量化 編碼”的每一個關鍵詞都用空格間隔，隨后用循環將其關鍵詞用split 函數逐個取出如先取出“采樣”，然后將與考試者在文本框中輸入的內容進行模糊比較，比較時用改進的算法，像英文字符串比較那樣把關鍵詞的每一中文用mid函數取出與考生輸入的答案比較，若找到相同的字符串則有得分，如在本例中，三個關鍵詞各設一分，本題分值3 分，若找到 “采樣”字符串便可得一分，隨后將循環提取出的關鍵詞“量化”和“編碼”依次進行字符串比較，若找到本題得分就累加一分直至結束，最后將累積的分數寫入數據庫中相對應的題目的本題得分字段，以便后期統計分數。其主要代碼如下所示：

3.5 運行結果如圖2：

圖2 運行結果

4 結束語

本文把改進的KMP算法應用于主觀題的智能閱卷功能中，其主要是通過關鍵詞模糊匹配的方式，從實驗過程中看，其效率和準確性都不低于KMP 算法，但中文語意語法博大精深，這種近似匹配的算法并不能包含近義詞等匹配，不能精確評判所有的題目，但大多數的科目還是適用的，對于進一步加強教學輔助手段，提高師生的教學質量上，有一定的幫助。