劉淇 李瑞陽 李雨盈 劉佳文

（1.華北電力大學(xué)控制與計(jì)算機(jī)工程學(xué)院 北京市 102209 2.華北電力大學(xué)電氣與電子工程學(xué)院 北京市 102209）

1 緒論

1.1 系統(tǒng)及研究對(duì)象

本系統(tǒng)是基于文字掃描識(shí)別技術(shù)，將學(xué)生提交的作業(yè)圖片轉(zhuǎn)化為文字后上傳至系統(tǒng)后臺(tái)的數(shù)據(jù)庫進(jìn)行存儲(chǔ)，結(jié)合相應(yīng)的算法以標(biāo)準(zhǔn)答案為參考，將學(xué)生作業(yè)與之進(jìn)行匹配，并得出作業(yè)評(píng)分的智能化批改系統(tǒng)。

在批改的科目上，該團(tuán)隊(duì)選擇了難度較低但任務(wù)量大的大學(xué)物理作為研究對(duì)象，從主觀題入手進(jìn)行實(shí)踐，通過該科目作業(yè)批改體系的建立，完成本系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)，后續(xù)可推廣至其他科目。

簡(jiǎn)單來說，本系統(tǒng)研究的主要方向是算術(shù)型理科主觀題的自動(dòng)批改。

1.2 背景意義

大量研究數(shù)據(jù)表明，合理有效的作業(yè)布置對(duì)學(xué)生的成績(jī)有很大的促進(jìn)作用，布置作業(yè)和批改作業(yè)不僅僅是教育和教學(xué)的重要環(huán)節(jié)，也是師生之間互相交流的直接橋梁。然而當(dāng)今的作業(yè)環(huán)節(jié)存在著許多問題。從教師角度來看，作業(yè)批改耗時(shí)長(zhǎng)、重復(fù)性高，是師資力量的一種浪費(fèi)；從學(xué)生角度來說，作業(yè)的缺漏、缺交、抄襲現(xiàn)象普遍，在缺乏作業(yè)監(jiān)督機(jī)制的現(xiàn)狀下難以被察覺，使得學(xué)生對(duì)作業(yè)更加不重視；從技術(shù)角度來看，現(xiàn)有的作業(yè)批改系統(tǒng)依舊是依靠人工力量進(jìn)行批改，并沒有解決根本問題；從時(shí)事的角度來說，學(xué)生在疫情期間不得不在家上網(wǎng)課，作業(yè)、考試等教學(xué)活動(dòng)均改為線上進(jìn)行，無疑是加大了老師的工作量，傳統(tǒng)的批改方式根本難以應(yīng)對(duì)。

在這種情況下，該團(tuán)隊(duì)提出了“基于文字掃描識(shí)別技術(shù)的作業(yè)自動(dòng)批改”這一構(gòu)想，在幫助老師減輕負(fù)擔(dān)的同時(shí)，促進(jìn)作業(yè)環(huán)節(jié)的教學(xué)質(zhì)量效率和效益的提高。作為教學(xué)工作的薄弱環(huán)節(jié)，該團(tuán)隊(duì)將作業(yè)批改同計(jì)算機(jī)互聯(lián)網(wǎng)與文字掃描識(shí)別技術(shù)相結(jié)合，為新技術(shù)的突破打下了良好的基礎(chǔ)，并在現(xiàn)有基礎(chǔ)上有了很大的突破，作業(yè)的機(jī)器化、智能化批改才真正得以實(shí)現(xiàn)。

1.3 研究現(xiàn)狀

作為信息錄入的方法之一，文字識(shí)別的速度遠(yuǎn)遠(yuǎn)高于人工錄入，而在科學(xué)技術(shù)飛速發(fā)展和進(jìn)步的今天，文字識(shí)別的應(yīng)用領(lǐng)域也得到相應(yīng)的擴(kuò)展，其中文字識(shí)別和數(shù)字識(shí)別的應(yīng)用最為廣泛。在這之中，文字識(shí)別成為一大主流，通過專項(xiàng)研究表明，手寫體文字渴求度極大且識(shí)別率高達(dá)80%，能夠?yàn)槿怂谩?/p>

而自計(jì)算機(jī)自然語言處理算法誕生以來，作業(yè)自動(dòng)批改系統(tǒng)的研究就一直處于熱門狀態(tài)。但目前已有的研究?jī)H是針對(duì)自然語言類與計(jì)算機(jī)文本處理的作業(yè)批改，因此本文針對(duì)算術(shù)型作業(yè)自動(dòng)批改，并首次將文字識(shí)別與作業(yè)批改相結(jié)合，研發(fā)了一套基于文字掃描識(shí)別技術(shù)的作業(yè)自動(dòng)批改系統(tǒng)。

1.4 論文安排

第一部分，緒論。介紹了本文的研究對(duì)象、背景意義以及文字識(shí)別技術(shù)的現(xiàn)狀和發(fā)展前景。

第二部分，相關(guān)技術(shù)。介紹了文字識(shí)別技術(shù)和核心技術(shù)，即文本特征提取和python 語言的應(yīng)用和優(yōu)勢(shì)。

第三部分，核心算法。介紹了核心算法的應(yīng)用與優(yōu)勢(shì)，主要包括三大算法：表達(dá)式轉(zhuǎn)二叉樹、匹配與二叉樹的遍歷算法以及規(guī)范化處理算法。

圖1：表達(dá)式轉(zhuǎn)二叉樹

第四部分，系統(tǒng)設(shè)計(jì)。

2 相關(guān)技術(shù)

2.1 技術(shù)基礎(chǔ)：文字掃描識(shí)別技術(shù)簡(jiǎn)介

文字識(shí)別技術(shù)為算術(shù)型作業(yè)書寫與批改在計(jì)算機(jī)上的可操作性提供了支持。因此本系統(tǒng)的設(shè)計(jì)與開發(fā)建立在文字掃描識(shí)別技術(shù)的發(fā)展上。下面對(duì)文字掃描識(shí)別技術(shù)做簡(jiǎn)要介紹。

2.1.1 印刷體文字識(shí)別技術(shù)簡(jiǎn)介

光學(xué)字符識(shí)別（Optical Character Recognition），是指電子設(shè)備（如掃描儀）通過檢測(cè)紙張上字符的明暗圖案來確定其形狀，然后通過字符識(shí)別將其翻譯成計(jì)算機(jī)語言的過程。即將打印的字符光學(xué)轉(zhuǎn)換成黑白點(diǎn)陣圖像文件，并通過相應(yīng)的識(shí)別技術(shù)將圖像中的文本轉(zhuǎn)換為計(jì)算機(jī)文本格式，以供文字處理軟件進(jìn)一步的處理與加工。

2.1.2 手寫體文字識(shí)別技術(shù)簡(jiǎn)介

（1）在線手寫體文字識(shí)別。在線手寫體文字識(shí)別（on linehandwritten character recognition）指人在線書寫，而計(jì)算機(jī)通過識(shí)別人書寫文字時(shí)的筆劃特征來確定相應(yīng)字符并轉(zhuǎn)換為對(duì)應(yīng)文本格式。

（2）離線手寫體文字識(shí)別。離線手寫體文字識(shí)別（off linehandwritten character recognition）指掃描儀通過掃描由書寫者預(yù)先寫在紙上的文字并將其轉(zhuǎn)成圖像，再由計(jì)算機(jī)識(shí)別成相應(yīng)文字并轉(zhuǎn)換為文本格式。

2.2 核心技術(shù)

2.2.1 文本特征提取

本系統(tǒng)是基于文字識(shí)別技術(shù)的作業(yè)自動(dòng)批改系統(tǒng)，而進(jìn)行了文字識(shí)別后的計(jì)算機(jī)可讀文本一般都含有大量冗余信息，若直接對(duì)其文本進(jìn)行自動(dòng)批改，將極大地減緩系統(tǒng)的運(yùn)行速度，同時(shí)冗余信息也將使批改的錯(cuò)誤率大為升高。因此，本系統(tǒng)在作業(yè)批改前對(duì)識(shí)別后的文本進(jìn)行了文本預(yù)處理，文本預(yù)處理的方法主要是特征提取。下面簡(jiǎn)要介紹文本特征提取。

在算術(shù)型作業(yè)（以大學(xué)物理為例）的文本特征提取中，該團(tuán)隊(duì)更關(guān)心的是文本中出現(xiàn)的一個(gè)隨機(jī)變量t 與大學(xué)物理的專業(yè)用詞集c 是否相關(guān)以及相關(guān)度的大小。因此，在文本特征提取階段選擇開方檢驗(yàn)方法進(jìn)行特征選擇與提取，其基本思想是通過檢測(cè)實(shí)際值與理論值之間的偏差來確定該學(xué)生答案文本詞與實(shí)際答案文本值關(guān)聯(lián)與否。

使用隨機(jī)變量t 與專業(yè)用詞集c 不相關(guān)為原假設(shè)，根據(jù)式（1）對(duì)兩個(gè)隨機(jī)變量進(jìn)行假設(shè)檢驗(yàn)：

表1：運(yùn)算符的統(tǒng)一化處理

表2：微分及導(dǎo)數(shù)的統(tǒng)一化處理

表3：符號(hào)類運(yùn)算符優(yōu)先級(jí)標(biāo)準(zhǔn)規(guī)范

表4：變量類運(yùn)算符優(yōu)先級(jí)標(biāo)準(zhǔn)規(guī)范

式中：A——文本中出現(xiàn)隨機(jī)變量t 且類別為c 的詞匯數(shù)目；

B——文本中出現(xiàn)隨機(jī)變量t 但不屬于c 的詞匯數(shù)目；

C——文本中不出現(xiàn)隨機(jī)變量t 但屬于c 類的詞匯數(shù)目；

D——文本中不出現(xiàn)隨機(jī)變量t 且不屬于c 類的詞匯數(shù)目。

由式（1）計(jì)算出的開方值越大，隨機(jī)變量t 與專業(yè)用詞集c 的相關(guān)性越大，t 越能表征c。

將文本中每個(gè)詞匯（隨機(jī)變量）t 與專業(yè)用詞集c 的開方檢驗(yàn)值按從大到小詞序排列，取該文本詞匯總數(shù)的90%作為文本特征提取。

2.2.2 Python

基于文字識(shí)別技術(shù)作業(yè)自動(dòng)批改系統(tǒng)的實(shí)現(xiàn)需要具有簡(jiǎn)易性、安全性且自定義性高、可拓展性強(qiáng)的編程語言與編程框架，因此，本系統(tǒng)開發(fā)選擇python 作為編程語言。下面對(duì)Python 作簡(jiǎn)要介紹。

Python 是一種跨平臺(tái)的計(jì)算機(jī)程序設(shè)計(jì)語言，集解釋性、編譯性、互動(dòng)性和面向?qū)ο笥谝惑w，在計(jì)算機(jī)科學(xué)、web 開發(fā)、人工智能等領(lǐng)域應(yīng)用廣泛。與C++、java 等語言對(duì)比，Python 具有下述優(yōu)點(diǎn)：

（1）開發(fā)效率高。Python 具有其它編譯語言所不具有的強(qiáng)大的第三方庫，包含了數(shù)據(jù)庫、網(wǎng)頁、文件、文本、GUI 等大量?jī)?nèi)容，因此利用Python進(jìn)行系統(tǒng)開發(fā)將大大降低開發(fā)難度，節(jié)約開發(fā)成本，提高開發(fā)周期。同時(shí)，系統(tǒng)開發(fā)者間通過代碼封裝可實(shí)現(xiàn)代碼作為第三方庫使用，提升了合作效率。

（2）可擴(kuò)展性高。Python 的模塊具有高可擴(kuò)展性，它的類庫涵蓋了文件 I/O、GUI、網(wǎng)絡(luò)編程、數(shù)據(jù)庫訪問、文本操作等絕大部分應(yīng)用場(chǎng)景，是腳本語言中最豐富和強(qiáng)大的。Python 的高可擴(kuò)展性更好地體現(xiàn)在：當(dāng)系統(tǒng)中的一段關(guān)鍵部分代碼實(shí)現(xiàn)需要快速運(yùn)行時(shí)，可以通過 C 或 C++ 等高級(jí)語言編寫，然后在 Python 程序設(shè)計(jì)中使用它們。

（3）可移植性強(qiáng)。由于Python 的開源特性，因此其具有較強(qiáng)的可移植性，即如果能夠有效避免工作的核心程序?qū)ο到y(tǒng)的依賴性，那就意味著系統(tǒng)所有的Python 程序都無需修改就可以在諸多平臺(tái)上運(yùn)行。

3 核心算法

3.1 表達(dá)式轉(zhuǎn)二叉樹

樹型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，其中以樹和二叉樹最為常用。而二叉樹每個(gè)結(jié)點(diǎn)至多只有兩棵子樹且子樹有左右之分，其次序不能任意顛倒[1]，十分廣泛地應(yīng)用于表達(dá)式處理。

例：如圖1，將(4-3)*(2+5)轉(zhuǎn)為二叉樹：

其所有葉子節(jié)點(diǎn)均為操作數(shù)，所有非葉子節(jié)點(diǎn)均為操作符。

3.2 規(guī)范化處理算法

3.2.1 數(shù)學(xué)運(yùn)算符與變量的統(tǒng)一化處理

數(shù)學(xué)運(yùn)算符與變量的統(tǒng)一化處理是指將答案所得文本與答案庫中的數(shù)學(xué)運(yùn)算符與變量作統(tǒng)一化處理，以方便機(jī)器識(shí)別與匹配，部分統(tǒng)一方法如表1、表2。

3.2.2 表達(dá)式的規(guī)范化處理

結(jié)合考慮算術(shù)型作業(yè)含有的表達(dá)式中的優(yōu)先級(jí)問題與二叉樹的轉(zhuǎn)化問題，此處規(guī)定表達(dá)式的范式為具有優(yōu)先級(jí)次序的后綴表達(dá)式，下面給出優(yōu)先級(jí)次序的規(guī)定與由表達(dá)式獲得相應(yīng)的后綴表達(dá)式的部分算法。

（1）運(yùn)算符優(yōu)先級(jí)的規(guī)定。對(duì)于同一個(gè)表達(dá)式的不同學(xué)生表示,進(jìn)行作業(yè)批改時(shí)需要考慮運(yùn)算符出現(xiàn)的次序問題與不同的運(yùn)算符的優(yōu)先級(jí)管理問題,因此對(duì)運(yùn)算符優(yōu)先級(jí)作如表3 的統(tǒng)一標(biāo)準(zhǔn)規(guī)范：

（2）相應(yīng)后綴表達(dá)式的獲得。由表達(dá)式獲得對(duì)應(yīng)后綴表達(dá)式的算法實(shí)現(xiàn)需要借助兩個(gè)輔助棧stack data 和stack symbol 進(jìn)行。其中，stack data 棧中存放變量名或后綴表達(dá)式，stack symbol 棧用來存放運(yùn)算符，函數(shù)名為TransFromExptoPtost，參數(shù)post 表示最終得到的后綴表達(dá)式存放的數(shù)組名稱，參數(shù)exp 表示最初的表達(dá)式。其主要思想是每次遇到運(yùn)算符時(shí)，需要將該運(yùn)算符與棧stack symbol 中棧頂?shù)倪\(yùn)算符進(jìn)行比較。如果該運(yùn)算符的優(yōu)先級(jí)比棧stack symbol 棧頂?shù)倪\(yùn)算符優(yōu)先級(jí)高，則將該運(yùn)算符壓入棧stack symbol；否則，當(dāng)棧stack symbol 中棧頂元素運(yùn)算符優(yōu)先級(jí)大于等于當(dāng)前遇到的運(yùn)算符時(shí)，需要進(jìn)行以下處理：從棧stack data 中出棧兩個(gè)數(shù)據(jù)對(duì)象，從棧stack symbol 中出棧一個(gè)運(yùn)算符，連接成一個(gè)后綴表達(dá)式壓入棧stack data，然后將當(dāng)前運(yùn)算符壓入棧stack symbol；每次遇到數(shù)據(jù)對(duì)象 （即變量名）,則將該數(shù)據(jù)對(duì)象壓入棧stack data。[2]

再將由學(xué)生答案獲得的后綴表達(dá)式進(jìn)行兩兩匹配，過濾重復(fù)性表達(dá)式后生出答案表達(dá)式集合t,t 中的元素具有唯一性。

3.2.3 二叉樹的規(guī)范化處理

為了實(shí)現(xiàn)作業(yè)自動(dòng)批改并提升批改的準(zhǔn)確率與速率，將上述后綴表達(dá)式（標(biāo)準(zhǔn)答案庫與學(xué)生作答的文本答案中的表達(dá)式）二叉樹轉(zhuǎn)為范式二叉樹，即將表達(dá)式二叉樹進(jìn)行規(guī)范化處理。規(guī)范化處理規(guī)則如下：

（1）若同深度的非葉子節(jié)點(diǎn)為數(shù)字/字母，則左右葉子節(jié)點(diǎn)將按阿拉伯?dāng)?shù)字/希臘字母的字典序排列，即字典序小的數(shù)字/字母位于左葉子節(jié)點(diǎn)，字典序大的數(shù)字/字母位于右葉子節(jié)點(diǎn)。同時(shí)對(duì)同深度的非葉子節(jié)點(diǎn)的數(shù)字與字母作優(yōu)先級(jí)劃分，優(yōu)先級(jí)高的位于左葉子節(jié)點(diǎn)。優(yōu)先級(jí)次序如表4。

（2）二叉樹與若出現(xiàn)加減父節(jié)點(diǎn)中含兩個(gè)除號(hào)子節(jié)點(diǎn)，則將子節(jié)點(diǎn)合并，以提高匹配準(zhǔn)確度。

3.3 匹配與二叉樹的遍歷算法

作業(yè)自動(dòng)批改的核心是匹配，通過匹配算術(shù)型作業(yè)的計(jì)算過程與答案是否相同，并根據(jù)匹配度的高低進(jìn)行打分，下面就匹配與二叉樹的遍歷算法作簡(jiǎn)要介紹。

兩個(gè)二叉樹的匹配算法如下：

其中二叉樹的遍歷采用后序遍歷法。

匹配與二叉樹遍歷算法在本系統(tǒng)的應(yīng)用如下：

設(shè)題目答案為S0，具有S1、S2……Sm個(gè)表達(dá)式二叉樹，作答者答案為t0，具有t1、t2……tn個(gè)表達(dá)式二叉樹，其中n ≥ m。

從t 的第一個(gè)二叉樹開始，將S 中的二叉樹依次和t 中二叉樹匹配，若t1=S1&&……&&tm=Sm，則證明匹配成功，返回下標(biāo)0，進(jìn)行t0、S0的匹配，當(dāng)所有匹配均成功后，返回值1。

若在某一步ti!=Si，為了作業(yè)批改分?jǐn)?shù)的準(zhǔn)確性，記下不匹配二叉樹位置i,并從Si+1二叉樹開始依次與ti匹配直至n==m 或ti與Si+1……Sm中某個(gè)二叉樹匹配成功，然后從ti+1個(gè)二叉樹開始與S 中第i 個(gè)二叉樹進(jìn)行比較，同理，至n==m 為止（當(dāng)n==m 時(shí)匹配依然不成功則記下匹配不成功的t 中二叉樹個(gè)數(shù)n，并以此作為作業(yè)成績(jī)的評(píng)判依據(jù)）。依此類推若知道以t中第n-m個(gè)開始二叉樹為止，還沒有匹配成功則證明t 中不存S，返回值-1。

4 系統(tǒng)設(shè)計(jì)

4.1 系統(tǒng)概述

該系統(tǒng)結(jié)合文字掃描技術(shù)，突破以往的遠(yuǎn)程教育的形式，實(shí)現(xiàn)師生間的課后互動(dòng)。該系統(tǒng)對(duì)比之前單一的人工作業(yè)評(píng)分或人工網(wǎng)上評(píng)分模式，通過創(chuàng)建題庫，老師從題庫選擇作業(yè)題目，學(xué)生通過拍照等方式上傳答案，系統(tǒng)通過算法對(duì)作業(yè)評(píng)分，實(shí)現(xiàn)作業(yè)評(píng)分的自動(dòng)化。同時(shí)會(huì)將學(xué)生作答情況反饋給老師/學(xué)生并根據(jù)實(shí)際情況自動(dòng)更新題庫，老師還可以自己創(chuàng)建作業(yè)，保證系統(tǒng)數(shù)據(jù)庫的即時(shí)性與真實(shí)性，便于下次作業(yè)評(píng)分，從而從真正意義上實(shí)現(xiàn)作業(yè)評(píng)分的自動(dòng)化。

4.2 系統(tǒng)核心功能

4.2.1 作業(yè)發(fā)布

教師可通過登錄教職工賬號(hào)，從題庫中勾選作業(yè)題目，在平臺(tái)發(fā)布作業(yè)的內(nèi)容和具體要求，系統(tǒng)后臺(tái)自動(dòng)發(fā)送至學(xué)生端，學(xué)生登陸自己的賬號(hào)即可查詢作業(yè)詳情。

4.2.2 作業(yè)自動(dòng)批改

通過文字掃描識(shí)別技術(shù)，將學(xué)生上傳的圖片轉(zhuǎn)化為文字形式后上傳至系統(tǒng)，若掃描失敗，則通知學(xué)生重新上傳；逾期則直接將掃描失敗的圖片上傳至教師端，進(jìn)行人工批改。然后通過作業(yè)評(píng)分算法，以標(biāo)準(zhǔn)答案為參考，將學(xué)生作業(yè)與之進(jìn)行匹配：若匹配度很高且答案正確，則根據(jù)算法進(jìn)行評(píng)分；若答案不正確，則根據(jù)算法適當(dāng)扣分；若匹配度較高且答案正確，則根據(jù)算法演算中間過程，根據(jù)過程得分標(biāo)準(zhǔn)適當(dāng)?shù)梅只蚩鄯郑黄溆嗲闆r悉數(shù)上傳至教師端，進(jìn)行人工批改。

4.2.3 成績(jī)管理

系統(tǒng)對(duì)數(shù)據(jù)進(jìn)行匯總和分析，將成績(jī)、錯(cuò)題、排名等結(jié)果反饋給學(xué)生，平均分、易錯(cuò)題、查重率等反饋給老師。

4.2.4 作業(yè)復(fù)審

學(xué)生對(duì)不滿意的評(píng)分結(jié)果進(jìn)行申訴，系統(tǒng)上傳至教師端。教師對(duì)上傳的題目進(jìn)行在線評(píng)分并反饋結(jié)果，將誤判的答案用來完善答案庫。

5 結(jié)語

本文針對(duì)國(guó)內(nèi)作業(yè)批改以及相關(guān)技術(shù)的發(fā)展現(xiàn)狀展開了討論，重點(diǎn)論述了基于文字掃描識(shí)別技術(shù)的作業(yè)自動(dòng)批改系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)。在文字掃描識(shí)別技術(shù)快速發(fā)展的今天，本團(tuán)隊(duì)嘗試將其與作業(yè)批改相結(jié)合，通過Python 語言結(jié)合表達(dá)式轉(zhuǎn)二叉樹算法完成程序的編寫，實(shí)現(xiàn)作業(yè)的自動(dòng)化批改，成為本項(xiàng)目的一大亮點(diǎn)。該項(xiàng)目從學(xué)科代表性強(qiáng)的大學(xué)物理入手進(jìn)行研究和實(shí)踐，后續(xù)可推廣至其他科目作業(yè)的自動(dòng)批改，有很大的發(fā)展前景。