基于編輯距離的自適應反饋程序評測方法

薄鈞戈，喬亞男，齊 琪，黃 鑫，房琛琛

(西安交通大學 計算機科學與技術學院，陜西 西安 710049)

0 引 言

程序設計類課程是計算機類專業的專業基礎課，是數據結構、算法設計與分析等計算機核心課程的先修課[1]。程序設計類課程教學目標是培養學生應用計算機去求解實際問題的能力，為了達到此目標，同學們需要反復的上機編程訓練。由于傳統的程序設計類課程考核方式(紙面試卷)有很多缺點，比如教師需要花大量的時間和精力來批改作業、學生無法及時獲得學習效果反饋、缺乏在編程中的自我判斷能力等，導致學習興趣逐漸減退[2-3]，因此近幾年有不少高水平本科院校程序設計類課程將程序在線評測系統(Online Judge，OJ)引入到實踐教學環節中[4-5]，以提高學生編程熱情和壓力情況下解決編程問題的能力，以正確的計算思維去理解和構建復雜的程序系統[6-7]。

對于編程題的自動評閱，目前主要有兩種方法，一種是將學生程序代碼編譯為可執行文件，然后輸入“預設測試用例輸入”，得出“學生代碼輸出”，再和“預設測試用例輸出”比對，給出相應得分情況，該方法在基礎教學和算法競賽中皆有長時間廣泛而成熟的應用[8]；另一種是結合程序代碼特征和復雜性度量，如學生代碼的行數、變量個數、復雜度以及語法樹等去評價學生程序代碼的質量并給出得分[9-10]，并結合一些分類、聚類、可視化等數據挖掘的方法進行圖表顯示[11-13]，這兩種方法都有明顯的缺點：當學生代碼編譯錯誤，或者測試用例評測不對，在沒有得全分的情況下，面對編譯、運行等問題，學生還是很難改對代碼；尤其是在編譯通過而測試用例不通過的情況下，學生在修改代碼時有可能只是因為測試用例輸出的大小寫出錯、缺失標點符號、順序出錯、有無空格等簡單格式問題而花費大量時間進行調試(為了保證測試用例的安全，測試用例不能公開)。

為了解決上述問題，該文提出一種基于編輯距離的自適應反饋程序評測方法，通過檢測學生代碼的編譯信息和測試用例信息，應用編輯距離，自適應給出學生代碼出錯原因并給出反饋指導，幫助學生快速找到代碼出錯位置并有針對的進行修改。該方法應用到了本校面向大面積計算機基礎課程的作業系統中(該系統由教學團隊自主研發，相關界面見圖1)，該系統基于ASP.NET MVC框架開發，主要有題庫管理、在線練習、實時評測、系統監控、學習預警等功能。學生注冊后，根據題目在線提交多種編程語言(C，C++，C#等)源代碼，系統編譯源代碼后執行，采用黑盒測試的方式，通過和預設測試用例的比對來檢驗源代碼編譯和運行的正確性。

圖1 計算機基礎課程作業系統截圖

實踐證明，通過結合自適應反饋程序評測方法的OJ系統，可以有效促進程序設計類課程的教學質量[14]。

1 研究方法和過程

該文提出的基于編輯距離的自適應反饋程序評測方法，整體的步驟如圖2所示[8]。

圖2 自適應反饋程序評測方法步驟

第一步，教師端布置編程題目信息，如題目描述、參考答案、開始完成和截止時間、預設測試用例等，其中測試用例根據題目考察點，可設置多個測試用例；

第二步，學生根據題目要求通過在線編輯器完成題目編寫并上傳至代碼評測服務器，其中在線編輯器有代碼高亮顯示、折疊、縮進等模擬真實開發環境功能；

第三步，在評測學生程序代碼之前，需檢測過濾學生程序，對學生程序中出現不安全代碼進行過濾，所述不安全代碼包括fdisk-硬盤分區、format-格式化、shutdown-關機等命令，防止惡意代碼；

第四步，編譯學生程序，代碼中如果由于語法錯誤導致編譯失敗，獲取編譯錯誤信息，如圖3所示，通過對編譯器返回的編譯錯誤信息進行篩選整理，分別獲得下面信息：

圖3 獲取編譯錯誤信息

(1)編譯錯誤代碼，通過編譯錯誤代碼，彈出相應錯誤代碼幫助文檔，如MSDN文檔，或者打開相應錯誤代碼幫助網頁；

(2)編譯錯誤行號，通過編譯錯誤行號，學生可以快速定位找到程序錯誤位置；

(3)編譯錯誤詳細說明，通過編譯錯誤詳細說明，可以幫助學生理解編譯錯誤原因，有針對地修改錯誤代碼。

第五步，如果學生程序編譯通過，而運行不通過，則表示學生程序通過“預設測試用例的輸入”生成的輸出結果和“預設測試用例輸出”兩段文本不相等。因此，如果需要提供給學生一個比較準確的錯誤反饋信息，則需比對分析學生程序的輸出和“預設測試用例輸出”的異同，然而，學生編寫練習的程序和一般軟件產品不同，比如結構簡單，大多數有固定的算法模塊，如果編譯通過而運行不通過，大概率總有這樣的情況：學生代碼通過“預設測試用例的輸入”生成的輸出總是朝著“預設測試用例輸出”靠近。因此對于學生代碼編譯通過而運行不通過的錯誤原因可能是常見簡單錯誤，所述常見簡單錯誤包括：學生代碼輸出結果大小寫出錯、中英文標點符號錯誤、缺失或存在多余的空格、順序出錯、錯位問題、數值間存在倍數擴大或縮小等。

該文將重點討論第五步 “程序編譯通過而運行不通過” 這種情況，將在下一小節詳細介紹。

2 基于編輯距離的自適應反饋程序評測方法

2.1 判斷測試用例考察類型

基于編輯距離的自適應反饋程序評測方法首先判斷測試用例考察類型，可以結合“預設測試用例輸出”，得出測試用例考察類型，根據程序設計類課程歷史中同學們常見問題總結考察類型為四種，分別為：“單一字符串型”、“多個字符串型”、“單一純數值型”、“多個純數值型”。測試用例考察類型確定方法如圖4所示。

圖4 測試用例考察類型判斷方式

當預設測試用例輸出文本內容有字符或符號時，且字符串間沒有空格隔開，判斷測試用例類型為“單一字符串型”；

當預設測試用例輸出文本內容有字符或符號時，且字符串間以空格隔開，判斷測試用例類型為“多個字符串型”；

當預設測試用例輸出文本內容只有純數值(包括小數)時，判斷測試用例類型為“單一純數值型”；

當預設測試用例輸出文本內容只有純數值或小數點或空格，并數值間以空格隔開時，判斷測試用例類型為“多個純數值型”。

2.2 計算編輯距離

對于四種不同的測試用例考察類型，需要計算學生代碼的輸出結果和“預設測試用例輸出”的編輯距離(Minimum Edit Distance，MED)。

編輯距離是由俄羅斯科學家Vladimir Levenshtein在1965年提出的，因此編輯距離也稱為 Levenshtein Distance。在信息論、語言學和計算機科學領域，編輯距離是用來度量兩個序列相似程度的指標。簡單的說編輯距離就是指在兩個單詞之間，由其中一個單詞A轉換為另一個單詞B所需要的最少單字符編輯操作次數[15]。

在自然語言中的拼寫檢查時，根據一個拼錯的字符串和其他正確的字符串的編輯距離，可以判斷哪一個或哪幾個是比較可能的字符串。對于兩段字符串A和B，其中字符串A的長度為m，字符串B的長度為n，其計算方法如下：

d[0][0]=0

d[i][0]=0, 1≤i≤m

d[0][j]=0, 1≤j≤n

d[i][j]=

其中，d表示一個[m+1][n+1]大小的二維數組(d的數組比字符串長度長1個，是因為需要一個[1][1]大小的數組記錄其編輯距離為0)，d[i][j]表示完成從A(0,i)到B(0,j)的編輯次數。wdel(ai)表示把A[i]刪除的一次操作，wins(bj)表示把B[j]插到A[i]的一次操作，wsub(ai,bj)表示把A[i]用B[j]替換的一次操作。

相應的符號如圖5所示。

圖5 文中相應的符號及表示內容

2.3 “單一字符串型”用例結果錯誤

對于測試用例考察類型為“單一字符串型”，首先判斷學生代碼輸出結果和預設測試用例輸出長度是否相等。

(1)學生代碼輸出結果字符串和預設測試用例輸出字符串長度相等時，依次做如下處理：

將學生代碼輸出結果字符串大、小寫轉換(大寫字符轉為小寫字符、小寫字符轉為大寫字符、全部轉為大寫字符、全部轉為小寫字符)后和預設測試用例輸出字符串比較是否相等，如果相等，則中英文反饋指導學生由于“字符大小寫問題”導致運行不通過；

將學生代碼輸出結果字符串標點符號中英文轉換后和預設測試用例輸出字符串比較是否相等，如果相等，則中英文反饋指導學生由于“標點符號中英文問題”導致運行不通過；

調整修改學生代碼輸出結果字符串的順序后和預設測試用例輸出字符串比較是否相等，如果相等，則中英文反饋指導學生由于“順序錯誤”導致運行不通過；

將學生代碼輸出結果字符串旋轉(從首字符到最后一個字符進行多次旋轉)后和預設測試用例輸出字符串比較是否相等，如果相等，則中英文反饋指導學生由于“存在輸出錯位問題”導致運行不通過；

計算學生代碼輸出結果字符串和預設測試用例輸出字符串的編輯距離edit_Dis，以及編輯距離計算中刪除字符次數Ndel，編輯距離計算中添加字符次數Nins，且計算編輯距離占預設測試用例輸出比例R=edit_Dis/Lt，其中Lt為預設測試用例輸出字符串的長度，如果R<0.5，則中英文反饋指導學生由于“輸出與測試用例輸出長度相等，但是一半的字符無法匹配”導致運行不通過；如果編輯距離edit_Dis和預設測試用例輸出字符串長度相等，則中英文反饋指導學生由于“輸出與測試用例輸出長度相等，但是所有字符均無法匹配”導致運行不通過。

(2)學生代碼輸出結果字符串和預設測試用例輸出字符串長度不相等時，依次做如下處理：

刪除學生代碼輸出結果字符串中所有標點符號(主要是空格、回車等)后和預設測試用例輸出字符串比較是否相等，如果相等，則中英文反饋指導學生由于“輸出了多余的標點符號”導致運行不通過；

刪除預設測試用例輸出字符串中所有標點符號(主要是空格、回車等)后和學生代碼輸出結果字符串比較是否相等，如果相等，則中英文反饋指導學生由于“缺少某些標點符號”導致運行不通過；

計算學生代碼輸出結果字符串和預設測試用例輸出字符串的編輯距離edit_Dis，以及編輯距離計算中刪除字符次數Ndel，如果編輯距離edit_Dis和刪除字符次數Ndel相等，則中英文反饋指導學生由于“多輸出了某些字符，與預設測試用例輸出無法匹配”導致運行不通過；

計算學生代碼輸出結果字符串和預設測試用例輸出字符串的編輯距離edit_Dis，以及編輯距離計算中添加字符次數Nins，如果編輯距離edit_Dis和添加字符次數Nins相等，則中英文反饋指導學生由于“少輸出了某些字符，與預設測試用例輸出無法匹配”導致運行不通過；

計算學生代碼輸出結果字符串和預設測試用例輸出字符串的編輯距離edit_Dis，以及計算編輯距離占預設測試用例輸出比例R=edit_Dis/Lt，其中Lt為預設測試用例輸出字符串的長度，如果R<0.5，則中英文反饋指導學生由于“輸出與測試用例輸出長度不相等，且一半的字符無法匹配”導致運行不通過；否則顯示“輸出與測試用例輸出長度不相等，且超過一半的字符無法匹配”導致運行不通過。

2.4 “多個字符串型”用例結果錯誤

對于測試用例考察類型為“多個字符串型”，需先判斷學生代碼輸出結果字符串個數Ns(以空格隔開)和預設測試用例輸出字符串個數Na(以空格隔開)是否相等。

(1)學生代碼輸出結果字符串個數和預設測試用例輸出字符串個數相等時，依次做如下處理：

判斷刪除學生代碼輸出結果字符串空格、回車后和預設測試用例輸出字符串比較是否相等，如果相等，則中英文反饋指導學生由于“輸出內容與測試用例要求大體一致，有多余的空格、回車”導致運行不通過；

判斷刪除預設測試用例輸出字符串空格、回車后和學生代碼輸出結果字符串比較是否相等，如果相等，則中英文反饋指導學生由于“輸出內容與測試用例要求大體一致，缺失題目要求的空格或回車(可在輸出頭、尾檢查)”導致運行不通過；

將學生代碼輸出結果字符串大、小寫轉換(大寫字符轉為小寫字符、小寫字符轉為大寫字符、全部轉為大寫字符、全部轉為小寫字符)后和預設測試用例輸出字符串比較是否相等，如果相等，則中英文反饋指導學生由于“字符大小寫問題”導致運行不通過；

將學生代碼輸出結果字符串標點符號中英文轉換后和預設測試用例輸出字符串比較是否相等，如果相等，則中英文反饋指導學生由于“標點符號中英文問題”導致運行不通過；

調整修改學生代碼輸出結果字符串的順序后和預設測試用例輸出字符串比較是否相等，如果相等，則中英文反饋指導學生由于“順序錯誤”導致運行不通過；

將學生代碼輸出結果字符串旋轉(從第一個字符串到最后以個字符串進行多次旋轉)后和預設測試用例輸出字符串比較是否相等，如果相等，則中英文反饋指導學生由于“存在輸出錯位問題”導致運行不通過。

(2)學生代碼輸出結果字符串個數和預設測試用例輸出字符串個數不相等時，依次做如下處理：

學生代碼輸出結果字符串個數Ns大于預設測試用例輸出字符串個數Na時，判斷學生代碼輸出結果字符串中前Na個字符串是否和預設測試用例輸出字符串相等，如果相等，則中英文反饋指導學生由于“前Na個字符串和預設測試用例輸出匹配，但多輸出了某些字符串”導致運行不通過；

學生代碼輸出結果字符串個數Ns小于預設測試用例輸出字符串個數Na時，判斷學生代碼輸出結果字符串中前Ns個字符串是否和預設測試用例輸出字符串相等，如果相等，則中英文反饋指導學生由于“前Ns個字符串和預設測試用例輸出匹配，但少輸出了某些字符串”導致運行不通過；

將學生代碼輸出結果調整順序后，判斷學生代碼輸出結果字符串中前min{Ns,Na}個字符串是否和預設測試用例輸出字符串相等，如果相等，則中英文反饋指導學生由于“輸出字符串個數有誤，且存在輸出順序問題”導致運行不通過；

將學生代碼輸出結果按照字符串間隔旋轉后和預設測試用例輸出字符串比較是否部分相等，如果相等，則中英文反饋指導學生由于“輸出字符串個數有誤，且存在輸出錯位問題”導致運行不通過；

去除掉學生代碼輸出結果字符串和預設測試用例輸出中的所有空格，并計算學生代碼輸出結果字符串和預設測試用例輸出字符串的編輯距離edit_Dis，以及計算編輯距離占預設測試用例輸出比例R=edit_Dis/Lt，其中Lt為去除掉空格后的預設測試用例輸出字符串的長度，如果R<0.5，則中英文反饋指導學生由于“輸出字符串個數與測試用例輸出字符串個數不相等，且一半的字符無法匹配”導致運行不通過；否則顯示“輸出字符串個數與測試用例輸出字符串個數不相等，且超過一半的字符無法匹配”導致運行不通過。

2.5 “單一純數值型”用例結果錯誤

對于測試用例考察類型為“單一純數值型”，依次做如下處理：

將學生代碼輸出結果字符串和和預設測試用例輸出字符串轉為數值型，按照10的倍數放大或縮小學生代碼輸出結果，再與預設測試用例輸出比較，如果相等，則中英文反饋指導學生由于“輸出字符串與預設測試用例輸出無法匹配，但是存在10的倍數關系”導致運行不通過；

判斷學生代碼輸出結果字符串和和預設測試用例輸出字符串長度是否相等，如果不相等，計算學生代碼輸出結果字符串和和預設測試用例輸出字符串的編輯距離edit_Dis，再比較前min{Ls-edit_Dis, Lt-edit_Dis}(Ls為學生代碼輸出結果字符串長度，Lt為預設測試用例輸出字符串長度)個學生代碼輸出結果字符串是否和預設測試用例輸出字符串相等，如果相等，則中英文反饋指導學生由于“輸出字符串與預設測試用例輸出無法匹配，但是有效位保留出錯”導致運行不通過。

2.6 “多個純數值型”用例結果錯誤

對于測試用例考察類型為“多個純數值型”，需先判斷學生代碼輸出結果數值個數Ns(以空格隔開)和預設測試用例輸出數值個數Na(以空格隔開)是否相等。

(1)學生代碼輸出結果數值個數和預設測試用例輸出數值個數相等時，依次做如下處理：

判斷刪除學生代碼輸出結果字符串空格、回車后和預設測試用例輸出字符串比較是否相等，如果相等，則中英文反饋指導學生由于“輸出內容與測試用例要求大體一致，有多余的空格、回車”導致運行不通過；

判斷刪除預設測試用例輸出字符串空格、回車后和學生代碼輸出結果字符串比較是否相等，如果相等，則中英文反饋指導學生由于“輸出內容與測試用例要求大體一致，缺失題目要求的空格或回車(可在輸出頭、尾檢查)”導致運行不通過；

調整修改學生代碼輸出結果數值的順序后和預設測試用例輸出數值比較是否相等，如果相等，則中英文反饋指導學生由于“多個數值間存在輸出順序錯誤”導致運行不通過；

將學生代碼輸出結果多個數值進行旋轉(從第一個數值到最后一個數值進行多次旋轉)后和預設測試用例輸出數值比較是否相等，如果相等，則中英文反饋指導學生由于“多個數值間存在輸出錯位問題”導致運行不通過。

(2)學生代碼輸出結果數值個數和預設測試用例輸出數值個數不相等時，依次做如下處理：

學生代碼輸出結果數值個數Ns大于預設測試用例輸出中數值個數Na時，判斷學生代碼輸出結果數值中前Na個數值是否和預設測試用例輸出相等，如果相等，則中英文反饋指導學生由于“前Na個數值和預設測試用例輸出匹配，但多輸出了某些數值”導致運行不通過；

學生代碼輸出結果數值個數Ns小于預設測試用例輸出中數值個數Na時，判斷學生代碼輸出結果數值中前Ns個數值是否和預設測試用例輸出相等，如果相等，則中英文反饋指導學生由于“前Ns個數值和預設測試用例輸出匹配，但多輸出了某些數值”導致運行不通過；

將學生代碼輸出結果調整順序后，判斷學生代碼輸出結果中前min{Ns,Na}個數值是否和預設測試用例輸出相等，如果相等，則中英文反饋指導學生由于“輸出數值個數有誤，且存在輸出順序問題”導致運行不通過；

將學生代碼輸出結果按照數值間隔旋轉后和預設測試用例輸出比較是否部分相等，如果相等，則中英文反饋指導學生由于“輸出數值個數有誤，且存在輸出錯位問題”導致運行不通過。

3 自適應反饋程序評測方法的實施與成效分析

將基于編輯距離的自適應反饋程序評測方法引入到本校面向大面積計算機基礎課程的作業系統中，學生使用該系統的相關截圖如圖6和圖7所示。通過連續3年的應用，發現學生在線提交作業后，由于自適應的指導反饋，可以有效提高學生編程的積極性。通過該系統學生不再局限于時間和地點的約束，并且系統有學習狀況分析功能，能夠看到同班級學生的完成情況，營造競爭和激勵的良好學習氛圍，也有利于同學們的自主學習。同時，教師從傳統的向學生傳授知識轉變為協助學生解決任務，有利于教師提前發現充滿熱情的學生，對其進行有針對性的培養。

圖6 編譯不通過反饋提示界面

基于編輯距離的自適應反饋程序評測方法除了在本校大面計算機基礎課程的教學有應用外，還用于競賽的培訓，實現有效銜接。課程組老師指導的學生多次獲得ACM國際大學生程序設計競賽、“藍橋杯”全國軟件和信息技術專業人才大賽以及團體程序設計天梯賽獎項。在2019-2021年，本校連續三屆均有團隊獲得全國總決賽團隊一等獎。

圖7 編譯通過運行不通過反饋提示界面

4 結束語

近年來，團隊老師在計算機基礎課程體系、能力培養模式、教學資源、人才培養等方面取得了重要成果，應用效果顯著。對于其他兄弟院校、專業開設程序設計課程和實踐能力培養具有較好的借鑒和示范作用。

實踐證明，結合自適應反饋程序評測方法的在線評測系統，可以有效激發學生的學習熱情，通過在實踐中學習掌握正確的計算機思維和行動方法，促進程序設計類課程的教學質量。同時，系統引入了線上學習新的教學評價體系和學習成績考核機制，取得了良好的教學效果。另一方面，在實際的應用過程中，也存在一些不足和不完善的地方，例如系統沒有考慮到學生的自律性和主動性存在差異，以及如何擴展學習深度和難度，為更優秀的學生提供深層次的教學擴展等，這些不足還需要在后續研究和應用中進一步改進和探索。