一種改進(jìn)的KMP算法及其在主觀題評分中的應(yīng)用

◆姚秀情

（陽光學(xué)院 福建 350015）

1 引言

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

2 問題分析及相關(guān)研究

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

3 主觀題評分的基本實現(xiàn)過程

3.1 數(shù)據(jù)庫的設(shè)計和連接

在本文中采用開發(fā)環(huán)境的是vb 和access 數(shù)據(jù)庫相結(jié)合的方式來實現(xiàn)對主觀題的自動評分的，在創(chuàng)建數(shù)據(jù)庫后，接下來需要考慮的是如何使用vb 的控件對其進(jìn)行存取和管理，在此使用ado 數(shù)據(jù)庫引擎來創(chuàng)建數(shù)據(jù)庫與VB 的數(shù)據(jù)連接，首先得進(jìn)行的步驟采用“工程” “引用”中的 ADO 即 Microsoft ActiveX Data Objects 2.X Library（建議用2.6 往上）），其ADO 數(shù)據(jù)庫引擎創(chuàng)建的數(shù)據(jù)庫連接的格式為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 參數(shù)是數(shù)據(jù)庫的實際路徑。從哪里開始，從而避免重新檢查先前匹配的字符，在某種程度上提高了算法的效率，但對于大多數(shù)的學(xué)習(xí)者來說理解起來困難，把它運(yùn)用于實際應(yīng)用中，那更是難上加難，在這里將其做了一點(diǎn)點(diǎn)改進(jìn)，理解上將更加容易，其改進(jìn)的算法的過程如下：

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

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

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

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

圖1 實現(xiàn)過程

3.2 主要界面的設(shè)計

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

3.3 關(guān)鍵技術(shù)的分析

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

3.4 算法實現(xiàn)過程

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

3.5 運(yùn)行結(jié)果如圖2：

圖2 運(yùn)行結(jié)果

4 結(jié)束語

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