摘　要：

摘　要：利用計算機科學并結(jié)合數(shù)學算法對英語語法規(guī)則進行分析，對于英語語法中的謂語動詞部分的自動評改做出了相應的研究，并實現(xiàn)了英語作文自動評改平臺。此系統(tǒng)主要包含兩個方面：一是對作文中的單詞的拼寫的自動評改及反饋；二是對英語作文的謂語部分的自動檢測。經(jīng)測試，該系統(tǒng)可完成上述兩大功能，實現(xiàn)作文的自動評改并反饋出錯誤信息，對于其它語法現(xiàn)象的自動評改和自動檢錯還有待完善。對于以英語作為第二語言學習的教學工作，該系統(tǒng)的研究和實現(xiàn)將在寫作方面起到重要作用。

關鍵詞：

關鍵詞：計算機輔助學習　自動評改　自然語言處理　語法錯誤

1　研究背景

     英語自動作文評分領域的開拓者是Page，他在1966年開發(fā)了Project Essay Grader(PEG)系統(tǒng)，目的就是為了使大規(guī)模作文評分更加實際而高效。但該系統(tǒng)是通過文章的淺層語言學形式特征的分析對作文進行評分，沒有觸及文章結(jié)構(gòu)或者內(nèi)容，這使得該領域的研究在上世紀90年代之前基本處于停滯狀態(tài)。

     1990年，美國教育考試中心(Educational Testing Service簡寫為ETS)開始研發(fā)Educational Testing Service I(ETS I)。雖然這個系統(tǒng)還沒有考慮內(nèi)容方面，且只能用來評測20個詞以下的短句子，但它已更多地依靠對文章質(zhì)量的直接測量進行評分。

     另一條研究路線是由Larkey & Croft在1998年開辟的。她們所研發(fā)的系統(tǒng)是基于文本分類技術(Text Categorization Techniques簡稱為TCT)、文本復雜性特征、以及線性回歸方法。類似的還有Rudner and Liang建立的基于統(tǒng)計分析的Bayesian Essay Test Scoring System(BETSY)系統(tǒng)。

    國外目前較為完善的自動評分系統(tǒng)為E-rater（ Eleclectic Essay Rater)，是由美國教育測試服務中心(Educational Testing Centre)的Burstein博士及其研究小組利用自然語言處理(NLP)與信息擷取技術(IR，Information Retrieval)研究開發(fā)的一種英文在線測評英語寫作能力的計算機程序。自1999年起，用該技術測評GMAT應試者的作文總量已逾60萬篇，經(jīng)與常規(guī)人工批閱作文的結(jié)果比較，評分的準確率超過97％�，F(xiàn)在，美國研究生管理專業(yè)委員會(GMAC)已經(jīng)認為E—Rater電子軟件判分相對于傳統(tǒng)的由教師閱讀判分更有效。

　　國內(nèi)自動作文評分研究尚處于起步階段,梁茂成首先從自動作文評分領域進行初步的探索。他以提取淺層文本特征為主，結(jié)合針對內(nèi)容的潛在語義分析，進行線性回歸，得到了與人工評分較高的相關度。但由于其分析均以淺層特征的統(tǒng)計分析為主，以及樣本數(shù)量、范圍的局限性，其評分模型與實用系統(tǒng)尚存在一定的距離。目前，在國內(nèi)從事作文自動評分研究的主要還有文秋芳教授主持的基于學習者語料庫的英語作文訓練評估系統(tǒng)項目和荀恩東博士主持的非母語寫作水平計算機自動評測技術研究項目。由于非母語寫作的特殊性，采用深層次的文本特征分析難度很大。其中較成熟的產(chǎn)品有冰果英語智能作文評閱系統(tǒng)，它是浙江大學團隊攜手中外人工智能專家隊伍，經(jīng)過多年自主研發(fā)，推出的個性化智能化互動網(wǎng)絡英語學習系統(tǒng)。此外，南京大學高思丹等對主觀試題的計算機自動批改技術做了綜述；湘潭大學李輝陽等提出了帶權(quán)匹配技術進行簡單論述的正誤判定。

2　英語寫作自動評改平臺研究

　　目前國內(nèi)外的英語寫作自動“評改”系統(tǒng)均是以英語作文自動評分為目的進行研究及開發(fā)的，其主要方法是利用了計算機的高速計算能力，根據(jù)文章之間的相似程度給出分數(shù)。這種方法對于以母語為英語的學習者來說，類似E-rater的軟件系統(tǒng)能夠客觀的給出一個分數(shù)，并反映出寫作者的實際寫作水平。然而對于母語為非英語的學習者來說，需要系統(tǒng)提供反饋及建議，能夠幫助非英語為母語的國家的學生來更好的學習英語。

2.1　設計思路

　　本研究首先針對實現(xiàn)以下兩個功能：單詞的自動評改和基本英語語法的自動檢測。對于單詞的自動評改部分，其技術已比較成熟。但由于這些英語單詞軟件作為商業(yè)軟件，其源代碼嚴格保密，本研究決定采用“基于多重索引模型的詞典近似匹配算法”進行實現(xiàn)。

　　對于基本英語語法自動檢測與分析部分，目前國內(nèi)外還沒有相應的系統(tǒng)出現(xiàn)，其設計也屬于空白，而現(xiàn)有的此類系統(tǒng)只是給出分數(shù)，并不能給出錯誤所在。為了能實現(xiàn)語法錯誤的反饋，本文采用BF算法對其進行實現(xiàn)。

2.2　近似詞典匹配算法

　　最簡單的計算模式P的近似匹配的方法就是對背景詞典的每一個單詞w，計算P與w的編輯距離ed(P，w)，從而確定P的所有近似匹配結(jié)果。有研究者對Wagner和Fischer提出的動態(tài)規(guī)劃算法進行了改進，但由于背景詞典一般都比較大，即便采用目前最好的計算編輯距離的算法，計算背景詞典中每一個單詞Ⅳ與P的編輯距離，從而確定P的近似匹配結(jié)果集也是不現(xiàn)實的。為了解決這個問題，研究者采用了兩階段匹配策略，將詞典近似匹配過程分為兩個階段：粗匹配階段和細匹配階段。在粗匹配階段通過一定策略過濾掉大部分不可能成為匹配結(jié)果的詞典單詞，使背景詞典中只有少部分單詞成為候選匹配結(jié)果；細匹配階段對第一階段產(chǎn)生的候選匹配結(jié)果集中的每一個單詞W，計算w與用戶輸入模式P的編輯距離，從而確定最終的詞典近似匹配結(jié)果集合R。由于細匹配階段中速度較慢，因此兩階段匹配策略的速度很大程度上取決于粗匹配階段產(chǎn)生的候選匹配結(jié)果數(shù)量。

　　N-gram索引是一個倒排索引，索引項為詞典單詞中所有連續(xù)N個字符的集合，索引項g的倒排鏈是詞典中所有包含g的單詞的ID集合。對于輸入模式P，只有P中出現(xiàn)的N-gram對應倒排鏈中的單詞才有可能成為最終匹配結(jié)果，因此細匹配階段只需要對這些單詞分別計算與P的編輯距離，即可得到最終的近似匹配結(jié)果集合。一般來說，采用N-gram索引后粗匹配階段產(chǎn)生的候選匹配結(jié)果數(shù)量遠遠小于詞典單詞的總數(shù)，因此N—gram索引可以提高詞典近似匹配的速度。自動機理論也逐步應用到詞典的近似匹配領域，Oflazer提出的確定性有窮狀態(tài)識別器(deterministic finite-state recognizer，F(xiàn)SR)就是其中一種基于自動機的詞典近似匹配算法。Oflazer將背景詞典D視為字母表三上的正則語言，F(xiàn)SR就是識別D中所有單詞的有窮狀態(tài)自動機。

　　詞典近似匹配算法的速度很大程度上取決于粗匹配階段產(chǎn)生的候選匹配結(jié)果數(shù)量，粗匹配階段過濾掉的與輸入模式P不可能相似的詞典單詞越多，在細匹配階段需要計算編輯距離的單詞數(shù)量就越少，近似匹配速度就越快。基于N—gram索引模型的近似匹配算法，N值的確定是關鍵．N值太大，可能會導致個別與輸入模式P近似匹配的詞典單詞不能輸出；N值太小會導致個別索引鏈特別長，從而導致匹配速度下降。傳統(tǒng)的N—gram索引模型很難在匹配速度和匹配效果中找到最佳折衷。另外，傳統(tǒng)N—gram索引模型對詞典所有單詞建立同一種索引，也是導致倒排鏈較長的主要原因。為了使粗匹配階段過濾掉盡可能多的詞典單詞，提高近似匹配速度，文本提出了一種基于詞典多重索引模型的近似匹配算法。        

2.3　BF算法

　　BF（Brute Force）算法核心思想是：首先S[1]和T[1]比較（S是主串，T是子串），若相等，則再比較S[2]和T[2]，一直到T[M]為止；若S[1]和T[1]不等，則T向 右移動一個字符的位置，再依次進行比較。如果存在k，1≤k≤N，且S[k+1…k+M]=T[1…M]，則匹配成功；否則失敗。該算法最壞情況下要進行 M*(N-M+1)次比較，時間復雜度為O(M*N)。 　　

3　具體設計與檢驗

3.1　單詞的自動評改

　　本文利用“BNC最常用15000詞匯排序 BNC(British National corpus)”作為英語單詞的準確單詞數(shù)據(jù)庫，對15000個單詞進行正確的匹配。因為單詞量較大，導致對一個單詞的模式匹配時間過長，影響用戶使用，對計算機要求計算速度很高。所以，本文用三重索引進行數(shù)據(jù)庫的優(yōu)化。步驟如下：

　　Step 1: 分割單詞庫

　　先用程序?qū)ⅰ癇NC最常用15000詞匯排序 BNC(British National corpus)”單詞格式進行修改，修改為純單詞形式。

　　Step2: 創(chuàng)建索引表

　　因為本文用三級索引來進行單詞的查找。索引建立了三級索引目錄表進行單詞查找。

　　Step3: 組建單詞數(shù)據(jù)庫

　　我們將一般單詞分為兩類。一是單詞字母數(shù)大于3。對這類單詞就進行一級查找，找到二級表目名；再進行二級查找，找到三級表目名；最后進行相應的數(shù)據(jù)庫查找。二是單詞字母數(shù)小于3。因為本文用三級索引來進行單詞處理，所以單詞字母數(shù)小于3的單詞添加到三級表目中會出現(xiàn)錯誤。所以，我們建立次三級表ThirdClass_A----ThirdClass_Z作為中間級別表。

　　Step 4: 查詢單詞

　　對每個單詞進行分割，先判斷組成單詞的字母個數(shù)。將單詞分為兩類，分別進行查找。

3.2　基本英語語法的自動評改

　　由于本系統(tǒng)面向的是中學生英語作文以及大學cet-4或者cet-6的水平的英語作文，又由于英語語法涉及內(nèi)容十分豐富與復雜，所以我們僅對進行英語語法中謂語動詞部分的相關自動檢測。但是，一旦謂語動詞部分的檢測能夠成功，那么其他部分（例如主語、賓語）等部分的檢測都能夠通過相類似的方法手段獲得成功。

　　由于英語語法涉及內(nèi)容很多，而且十分復雜。所以，本研究只是對英語中基本的語法進行自動評改。

　　英語謂語動詞涉及到動詞的時態(tài)問題，形式問題，搭配問題，以及搭配中的動詞這類問題。

　　以“He advises me to drink more water�！边@句話為例，其中出現(xiàn)動詞advises 、drink。

　　3.2.1　時態(tài)問題