国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

基于文字識別技術(shù)的作業(yè)自動批改系統(tǒng)

2020-02-03 02:37:42劉淇李瑞陽李雨盈劉佳文
電子技術(shù)與軟件工程 2020年19期
關(guān)鍵詞:運算符二叉樹表達式

劉淇 李瑞陽 李雨盈 劉佳文

(1.華北電力大學控制與計算機工程學院 北京市 102209 2.華北電力大學電氣與電子工程學院 北京市 102209)

1 緒論

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

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

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

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

1.2 背景意義

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

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

1.3 研究現(xiàn)狀

作為信息錄入的方法之一,文字識別的速度遠遠高于人工錄入,而在科學技術(shù)飛速發(fā)展和進步的今天,文字識別的應(yīng)用領(lǐng)域也得到相應(yīng)的擴展,其中文字識別和數(shù)字識別的應(yīng)用最為廣泛。在這之中,文字識別成為一大主流,通過專項研究表明,手寫體文字渴求度極大且識別率高達80%,能夠為人所用。

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

1.4 論文安排

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

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

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

圖1:表達式轉(zhuǎn)二叉樹

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

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

2.1 技術(shù)基礎(chǔ):文字掃描識別技術(shù)簡介

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

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

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

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

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

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

2.2 核心技術(shù)

2.2.1 文本特征提取

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

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

使用隨機變量t 與專業(yè)用詞集c 不相關(guān)為原假設(shè),根據(jù)式(1)對兩個隨機變量進行假設(shè)檢驗:

表1:運算符的統(tǒng)一化處理

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

表3:符號類運算符優(yōu)先級標準規(guī)范

表4:變量類運算符優(yōu)先級標準規(guī)范

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

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

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

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

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

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

2.2.2 Python

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

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

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

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

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

3 核心算法

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

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

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

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

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

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

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

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

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

(1)運算符優(yōu)先級的規(guī)定。對于同一個表達式的不同學生表示,進行作業(yè)批改時需要考慮運算符出現(xiàn)的次序問題與不同的運算符的優(yōu)先級管理問題,因此對運算符優(yōu)先級作如表3 的統(tǒng)一標準規(guī)范:

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

再將由學生答案獲得的后綴表達式進行兩兩匹配,過濾重復性表達式后生出答案表達式集合t,t 中的元素具有唯一性。

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

為了實現(xiàn)作業(yè)自動批改并提升批改的準確率與速率,將上述后綴表達式(標準答案庫與學生作答的文本答案中的表達式)二叉樹轉(zhuǎn)為范式二叉樹,即將表達式二叉樹進行規(guī)范化處理。規(guī)范化處理規(guī)則如下:

(1)若同深度的非葉子節(jié)點為數(shù)字/字母,則左右葉子節(jié)點將按阿拉伯數(shù)字/希臘字母的字典序排列,即字典序小的數(shù)字/字母位于左葉子節(jié)點,字典序大的數(shù)字/字母位于右葉子節(jié)點。同時對同深度的非葉子節(jié)點的數(shù)字與字母作優(yōu)先級劃分,優(yōu)先級高的位于左葉子節(jié)點。優(yōu)先級次序如表4。

(2)二叉樹與若出現(xiàn)加減父節(jié)點中含兩個除號子節(jié)點,則將子節(jié)點合并,以提高匹配準確度。

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

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

兩個二叉樹的匹配算法如下:

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

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

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

從t 的第一個二叉樹開始,將S 中的二叉樹依次和t 中二叉樹匹配,若t1=S1&&……&&tm=Sm,則證明匹配成功,返回下標0,進行t0、S0的匹配,當所有匹配均成功后,返回值1。

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

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

4.1 系統(tǒng)概述

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

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

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

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

4.2.2 作業(yè)自動批改

通過文字掃描識別技術(shù),將學生上傳的圖片轉(zhuǎn)化為文字形式后上傳至系統(tǒng),若掃描失敗,則通知學生重新上傳;逾期則直接將掃描失敗的圖片上傳至教師端,進行人工批改。然后通過作業(yè)評分算法,以標準答案為參考,將學生作業(yè)與之進行匹配:若匹配度很高且答案正確,則根據(jù)算法進行評分;若答案不正確,則根據(jù)算法適當扣分;若匹配度較高且答案正確,則根據(jù)算法演算中間過程,根據(jù)過程得分標準適當?shù)梅只蚩鄯?;其余情況悉數(shù)上傳至教師端,進行人工批改。

4.2.3 成績管理

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

4.2.4 作業(yè)復審

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

5 結(jié)語

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

猜你喜歡
運算符二叉樹表達式
CSP真題——二叉樹
電腦報(2022年37期)2022-09-28 05:31:07
老祖?zhèn)魇诨具\算符
科學24小時(2021年10期)2021-10-09 23:09:37
二叉樹創(chuàng)建方法
一個混合核Hilbert型積分不等式及其算子范數(shù)表達式
表達式轉(zhuǎn)換及求值探析
淺析C語言運算符及表達式的教學誤區(qū)
一種由層次遍歷和其它遍歷構(gòu)造二叉樹的新算法
C++運算符重載剖析
價值工程(2014年17期)2014-04-16 03:29:20
論復雜二叉樹的初始化算法
河南科技(2014年24期)2014-02-27 14:20:01
表達式求值及符號推導
宜城市| 公主岭市| 沁阳市| 潜山县| 湟中县| 海口市| 白沙| 柘荣县| 镶黄旗| 肥东县| 安阳市| 临洮县| 奇台县| 洛南县| 临夏县| 甘泉县| 谷城县| 抚远县| 郎溪县| 新巴尔虎右旗| 桂东县| 黑河市| 原平市| 牟定县| 建湖县| 彰化县| 郸城县| 民和| 凤台县| 广元市| 万荣县| 长汀县| 航空| 集安市| 高青县| 札达县| 漾濞| 鄂伦春自治旗| 云和县| 偏关县| 师宗县|