冷強奎，劉雨晴，秦玉平

(1.渤海大學 信息科學與技術(shù)學院，遼寧 錦州 121000；2.渤海大學 工學院，遼寧 錦州 121000)

0 引 言

在高校的工科專業(yè)中，C語言均被列為一門重要的必修基礎(chǔ)課程。由于學習人數(shù)眾多，對學生程序的人工評分需要教師付出大量勞動，效率低下。并且學生提交程序后不能即時得到分數(shù)反饋，這也影響學生期末階段的狀態(tài)。另外，人工評分還要受到評卷教師水平、經(jīng)驗、個性甚至道德水準的影響[1]，因此設(shè)計一種智能的自動評分方法顯得十分重要。

目前，已經(jīng)存在一些自動評分方法，主要包括三大類[2-3]：動態(tài)測試方法、軟件質(zhì)量度量方法和源程序分析比較方法。動態(tài)測試方法[4-5]是一種黑盒測試方法，在程序運行期間通過構(gòu)造大量數(shù)據(jù)進行飽和測試，并根據(jù)運行結(jié)果與期望結(jié)果的差異來進行評分。但這種方法所使用的飽和測試沒有理論上的保證，它往往更取決于測試人員的經(jīng)驗。軟件質(zhì)量度量方法[6-7]是從靜態(tài)分析角度來進行評分。該方法考慮，如果兩個程序使用相同的評分標準，并且得到的分數(shù)相似，那么它們可能具有相似的結(jié)構(gòu)、數(shù)據(jù)流及控制流特征。然而，這對共用評分標準的制定提出了巨大的挑戰(zhàn)，即該標準既要能夠計算相似，又要準確區(qū)分不同。第三類方法是源程序分析比較方法[8-11]，它克服了前兩類方法無法衡量學生程序與參考答案的接近程度的問題，并且能夠做到對程序進行語句理解，因此具有不錯的發(fā)展前景。

對于學生程序中的兩種極端情況，即無結(jié)果無源程序(空白卷)和編譯成功結(jié)果正確(滿分卷)，自動評分系統(tǒng)是很容易就能夠判對的。因為只要對編程題目進行合理設(shè)置，總能夠得到分步驟的輸出結(jié)果(通常以文件形式寫入外存)，這樣就能夠精確檢測學生做題的步驟并防止直接寫外存。而對于編譯不通過或結(jié)果不正確的情況，評分過程則要復雜得多。文中要解決學生程序不完全正確下的自動評分問題，使用二元模糊匹配模型將學生程序與參考答案進行匹配，并根據(jù)匹配結(jié)果計算分數(shù)。最后通過仿真實驗來對該匹配模型進行評測，以檢驗其在不同情況下的評分能力。

1 一元結(jié)構(gòu)匹配

所謂一元結(jié)構(gòu)匹配，即首先要檢測學生程序與標準參考答案之間在結(jié)構(gòu)方面的相似程度。答案的結(jié)構(gòu)根據(jù)具體題目會略有不同，但通常分為主函數(shù)結(jié)構(gòu)與輔助函數(shù)結(jié)構(gòu)。每種結(jié)構(gòu)又包含若干個小項，具體如圖1所示。

圖1 結(jié)構(gòu)匹配示意圖

在檢測主函數(shù)的結(jié)構(gòu)時，重點考查學生程序中是否存在數(shù)據(jù)輸入、函數(shù)調(diào)用和結(jié)果輸出等三個方面的內(nèi)容。然后進行輔助函數(shù)結(jié)構(gòu)的檢測，這個階段的檢測要比主函數(shù)結(jié)構(gòu)的檢測復雜一些，因為它不但包含項目是否存在，還要考查各項目的體量(即數(shù)量)問題。比如，既要檢查參數(shù)是否存在，還要檢查參數(shù)的個數(shù)。同樣的，也要檢查分支結(jié)構(gòu)和循環(huán)結(jié)構(gòu)的數(shù)量。

下面以題目“編程將一維整型數(shù)組IntArray逆置”為例，詳細解釋結(jié)構(gòu)匹配的操作過程。

試題分析：該題目的核心功能是逆置，而操作對象是一維整型數(shù)組IntArray。由于C語言的特點，當參數(shù)為數(shù)組時，需要再添加輔助參數(shù)—數(shù)組的規(guī)模n，因此能夠確定形式參數(shù)由IntArray和n聯(lián)合組成。在教學過程中，教師通常要求學生程序風格盡量模塊化，所以在該題目中可以實現(xiàn)輸入輸出功能的函數(shù)化。

參考答案：教師在給出試題的同時，也需要提供相應的參考答案，并且為了評分更智能，通常會給出幾份參考答案。當學生程序與其中的一份參考答案相匹配時，學生便會獲得相應的分數(shù)。對于“數(shù)組逆置”這個題目，可以提供的參考答案如圖2所示。

圖2 參考答案示意圖

學生程序：學生根據(jù)自身對題目的理解進行自由程序設(shè)計。在程序結(jié)構(gòu)上可能會與參考答案存在一定的差異。例如，部分學生可能會認為不需要寫輸入輸出函數(shù)，這部分功能在主函數(shù)中完成即可。部分學生認為需要更多的變量聲明，才能表達清楚程序的功能。另外，學生還會存在程序設(shè)計習慣的問題，有的同學喜歡使用for循環(huán)，而另外的同學則喜歡使用while循環(huán)。因此，在檢測學生程序與參考答案之間的結(jié)構(gòu)相似性時，只需要檢查每種結(jié)構(gòu)是否存在以及體量問題，而對該結(jié)構(gòu)具體的表達則不必處理。學生提供的可能答案如圖3所示。

圖3 學生程序示意圖

主函數(shù)和輔助函數(shù)檢查完畢后，根據(jù)檢查結(jié)果給出結(jié)構(gòu)匹配的分數(shù)。由于該匹配主要關(guān)注學生程序中是否存在相應的結(jié)構(gòu)，而不關(guān)心這些結(jié)構(gòu)的先后順序和精確表達，因此稱這種匹配是模糊的。從結(jié)構(gòu)匹配的過程可以看出，它的操作很簡單，只是對學生程序的一個初級評判，目的是快速確定學生程序中是否存在關(guān)鍵的采分點。

2 二元詞語匹配

在一元結(jié)構(gòu)匹配的基礎(chǔ)上，接下來要進行關(guān)鍵的二元詞語匹配。它包含變量歸一化、詞頻統(tǒng)計、生成向量空間模型、相似度計算等幾個步驟，如圖4所示。

圖4 詞語匹配示意圖

變量歸一化：由于學生自定義的變量名與對應試題無實質(zhì)性關(guān)聯(lián)，因此為了檢測學生程序中變量的類型和體量，對變量名作歸一化處理。具體的處理方法是“類型+序號”，比如在程序中第一個出現(xiàn)的雙精度浮點型變量，歸一化后的名稱為“double1”。

詞頻統(tǒng)計：變量歸一化后，可以對答案中出現(xiàn)的詞語進行詞頻統(tǒng)計，以決定該詞的權(quán)重。這里的統(tǒng)計方法使用自然語言處理中的經(jīng)典方法，即詞頻-逆文檔頻率(term frequency - inverse document frequency，TF-IDF)[12-13]。對于某一特定文件中的詞ti來說，它的TF值計算公式如下：

(1)

ti的IDF值計算公式如下：

(2)

其中，|D|為語料庫中的文件總數(shù)，1+|{j:ti∈dj}|為包含詞ti的文件數(shù)目。

最終ti的詞頻可計算如下：

tf-idfi,j=tfi,j×idfi

(3)

TF-IDF表明詞的重要性隨著它在文件中出現(xiàn)的次數(shù)成正比增加，但同時會隨著它在語料庫中出現(xiàn)的頻率成反比下降。目前的語料庫(即試題庫)中文件的數(shù)量為20，每個文件提供5套參考答案，因此|D|=100。

生成VSM：經(jīng)過詞頻統(tǒng)計得到詞的權(quán)重后，每個學生程序可以得到一個對應的向量空間模型(vector space model，VSM)[14-15]。模型結(jié)構(gòu)如表1所示，S1～S5是對應題目的參考答案，A為學生答案。

表1 向量空間模型

(4)

對于每個學生答案，要分別與5套參考答案進行相似度匹配，最終的相似度取5次匹配的平均值。與一元結(jié)構(gòu)匹配類似，二元詞語匹配也不關(guān)心具體詞語的先后順序和是否為精確表達，因此它也是模糊的。

3 智能評分框架

圖5給出了整個評分系統(tǒng)的框架和流程。對于兩種極端情況，即空白卷和滿分卷，系統(tǒng)直接得出分數(shù)。如果介于兩者之間，則需要進行二元模糊匹配，進行智能評分。

圖5 評分系統(tǒng)框架

4 仿真實驗

實驗中所用語料庫包含不同知識點的編程試題20套，每套試題配置5份參考答案，這樣語料庫規(guī)模為100。為了評估不同情況下該評分模型的有效性，從每套試題的參考答案中隨機抽取1份，然后對其進行6種修改操作(modify operation，MO)，具體修改操作如表2所示。

表2 修改操作的種類

這樣得到了120份的模擬學生程序，然后使用二元模糊匹配模型對這些程序進行評分，并將評分與人工評分進行對比，最終得到了兩者之間的差值，如表3所示。

表3 智能評分與人工評分的差值(按百分計算)

從實驗結(jié)果中可以看出，當修改類型為MO1時，二元模糊匹配能夠得到與人工評分相類似的分數(shù)。這是因為評分系統(tǒng)首先對學生程序進行了歸一化預處理。當修改類型為MO2、MO3、MO4時，智能評分與人工評分的差值也比較小，盡管一些結(jié)構(gòu)已經(jīng)進行了替換，但在智能評分時，每個學生程序會對照5份參考答案，也就是說，結(jié)構(gòu)替換后，它可能與其中的某一份答案更加類似，從而提高了它的分數(shù)。當修改類型為MO5時，智能評分與人工評分則出現(xiàn)了較大的差值。原因在于，如果刪除操作去掉了重要詞語，那么勢必會對結(jié)果產(chǎn)生較大的影響。當修改類型為MO6時，智能評分也距人工評分有較大的差距。這是因為增加的冗余語句影響了某些詞的權(quán)重，使得計算余弦相似時出現(xiàn)了偏差。

但總體來看，智能評分能夠?qū)W生程序進行較為智能的檢測，克服了傳統(tǒng)方法只能評定有限個分類類型的缺陷，因此具有一定的現(xiàn)實意義。

5 結(jié)束語

提出了一種新的編程題自動評分方法，稱為二元模糊匹配模型，其中第一元是結(jié)構(gòu)模糊匹配，第二元是詞語相似匹配。在120份修改測試集上的實驗表明，該方法具有不錯的性能。特別是當學生程序與參考答案基本接近時，準確率更高。在大規(guī)模評分場景中，該方法具有一定的現(xiàn)實意義。