李瑩　楊春哲

摘要：在教育部大力倡導(dǎo)教育信息化發(fā)展的今天，自動(dòng)閱卷技術(shù)的研究逐漸成為熱點(diǎn)，其已經(jīng)成為教育信息化平臺(tái)搭建中不可或缺的一部分。文章針對(duì)簡(jiǎn)答題自動(dòng)閱卷過程中涉及的分句與分詞算法、關(guān)鍵詞提取算法、相似度計(jì)算算法進(jìn)行了分析。

關(guān)鍵詞：自動(dòng)閱卷系統(tǒng)；簡(jiǎn)答題；分句算法；分詞算法；關(guān)鍵詞提取算法；VBA 文獻(xiàn)標(biāo)識(shí)碼：A

中圖分類號(hào)：TP316 文章編號(hào)：1009-2374（2015）35-0020-02 DOI：10.13535/j.cnki.11-4406/n.2015.35.010

1 分句與分詞的算法分析

分句算法與分詞算法是本系統(tǒng)針對(duì)簡(jiǎn)答題進(jìn)行自動(dòng)閱卷采用的兩種基本算法，對(duì)簡(jiǎn)答題進(jìn)行自動(dòng)閱卷的基本流程是：首先對(duì)學(xué)生答案按照標(biāo)點(diǎn)符號(hào)進(jìn)行分句（標(biāo)點(diǎn)主要為逗號(hào)、句號(hào)、分號(hào)、感嘆號(hào)等），接著對(duì)分得的子句進(jìn)行分詞，然后將分得的詞存儲(chǔ)為序列，最后對(duì)詞序列進(jìn)行關(guān)鍵詞抽取與標(biāo)準(zhǔn)答案進(jìn)行比較。如果將學(xué)生答案僅僅進(jìn)行關(guān)鍵詞比較就給出分?jǐn)?shù)，很容易產(chǎn)生誤判。所以本系統(tǒng)采用相似度計(jì)算算法，盡量將計(jì)算機(jī)自動(dòng)閱卷結(jié)果接近教師人工閱卷結(jié)果，使考試結(jié)果更加公平。

1.1 分句算法分析

所謂的分句是指將學(xué)生答案的一整段話以中文中特定的句末標(biāo)點(diǎn)符號(hào)（如逗號(hào)、句號(hào)、分號(hào)、感嘆號(hào)等）為分割將其分成若干個(gè)子句，為了便于分析、提高閱卷速度，我們以學(xué)生答案中的任意標(biāo)點(diǎn)符號(hào)為標(biāo)志，將學(xué)生答案分割成若干子句。本閱卷系統(tǒng)對(duì)答案進(jìn)行分句處理的過程是：首先刪除答案前后的回車換行符，然后對(duì)答案進(jìn)行掃描，按照分句符號(hào)將答案分割成若干子句，把分割后的子句保存到子句數(shù)組中，經(jīng)過這一次掃描操作，將答案中的回車換行符去掉了。前面分析了分句處理的過程，下面就其算法進(jìn)行研究。

1.1.1 刪除學(xué)生答案中的回車換行符。自動(dòng)閱卷系統(tǒng)所批閱的卷子基本上都是采用上機(jī)考試形式，這就不可避免地使學(xué)生在答題過程中不經(jīng)意地輸入回車換行符，而它對(duì)評(píng)分沒有任何意義。但是在計(jì)算機(jī)的存儲(chǔ)器中它是以字符的形式存儲(chǔ)的，在答案中分別占有一個(gè)字符的位置，如果不將其刪除，勢(shì)必會(huì)影響分詞處理。所以在考慮分句算法時(shí)，首先要去除學(xué)生答案中的回車換行符。算法如下：（1）取原始答案字符串key最左端的一個(gè)字符保存到str中，轉(zhuǎn)（2）；（2）判定str是否為換行符或者回車符，如果是，則把key中最左端一個(gè)字符去掉，轉(zhuǎn)（1）；如果不是，則說明答案前面已經(jīng)沒有回車換行符了，轉(zhuǎn)（3）；（3）取原始答案字符串key最右端一個(gè)字符保存到str中，判定str是否為回車符或換行符，如果是，則把key中最右端一個(gè)字符去掉，轉(zhuǎn)（3），若不是，則說明答案后面已經(jīng)沒有回車換行符，將key作為返回值，掃描結(jié)束。答案存放在key字符串中。

1.1.2 分句算法。刪除學(xué)生答案中的回車換行符后，依據(jù)學(xué)生答案段中的分句標(biāo)點(diǎn)符號(hào)進(jìn)行分句處理，遇到句號(hào)、分號(hào)、逗號(hào)等標(biāo)點(diǎn)符號(hào)將其分為一句，保存在答案的子句數(shù)組中。算法如下：（1）判斷key是否為空，如果是，結(jié)束，否則轉(zhuǎn)（2）；（2）從key左側(cè)取一個(gè)字符放入str中，判定str是否是分句標(biāo)點(diǎn)符號(hào)或者回車符，如果是，轉(zhuǎn)（3），如果不是，轉(zhuǎn)（5）；（3）如果str是分句標(biāo)點(diǎn)符號(hào)，則子句數(shù)組下標(biāo)加1，去除key左側(cè)的一個(gè)字符，轉(zhuǎn)（1），如果str是回車符，轉(zhuǎn)（4）；（4）判定str下一個(gè)字符是否為回車符或者換行符，如果是，去除key左側(cè)一個(gè)字符，取key下一字符放入str中，轉(zhuǎn)（4），否則答案子句數(shù)組下標(biāo)加1，去除str左側(cè)一個(gè)字符，轉(zhuǎn)（1）；（5）將str并入到子句數(shù)組當(dāng)前位置，去除key左側(cè)一字符，轉(zhuǎn)（1）。

上述算法中，key為待處理的字符串，str為字符類型變量。

1.2 分詞算法分析

中文分詞較英文分詞要復(fù)雜很多，因?yàn)橛⑽氖且栽~為單位組成一句話，詞與詞之間用空格分割，例如：I am a girl.很容易能夠憑借空格就提取出詞。漢語則不然，漢語是由字構(gòu)成詞，句子中所有的字連起來才能描述一個(gè)意思，但是計(jì)算機(jī)無法明白什么是詞，把中文的漢字序列切分成有意義的詞，就是中文分詞。漢語的詞與詞之間沒有標(biāo)記，對(duì)于詞的界定往往不清楚，人是憑借對(duì)自然語言知識(shí)的理解來劃分詞，而計(jì)算機(jī)的分詞依據(jù)有三大類：基于字詞匹配的分詞方法、基于人工智能的分詞方法和基于串頻統(tǒng)計(jì)的分詞方法。本文主要采用基于字詞匹配的分詞方法。算法描述：（1）以詞匯表中最長(zhǎng)詞中所含有的字?jǐn)?shù)個(gè)數(shù)作為最大詞長(zhǎng)（將最大詞長(zhǎng)定義為L(zhǎng)）；（2）將待分詞的句子從第一個(gè)字起向后取L個(gè)字；（3）在詞匯表中遍歷是否有上一步提取的L個(gè)字夠成的詞，若有，保留分解出獨(dú)立的詞，轉(zhuǎn)（5），若沒有，轉(zhuǎn)（4）；（4）將最大詞長(zhǎng)L=L-1，從L中減掉最右邊一個(gè)字，轉(zhuǎn)（3）（直至L=1）；（5）從句子中刪除該詞，判定句子中是否有字，若有，轉(zhuǎn)（2），否則結(jié)束。

2 關(guān)鍵詞提取算法分析

經(jīng)過分詞階段，將學(xué)生答案和標(biāo)準(zhǔn)答案分成各個(gè)語句塊，接下來就應(yīng)用關(guān)鍵詞提取算法，將學(xué)生答案中的關(guān)鍵詞提取出來，這里指的關(guān)鍵詞是詞庫(kù)中的實(shí)詞，諸如“的、地、得、把、可能、好像”等一些對(duì)句子表達(dá)沒有實(shí)際意義的詞，我們不把它們作為得分點(diǎn)?？梢院雎缘暨@些詞匯，只提取出對(duì)句子意思表述至關(guān)重要的詞匯。具體提取時(shí)，需要判定它是否是有實(shí)際意義的詞，方法是分別比對(duì)學(xué)生答案和標(biāo)準(zhǔn)答案各語句塊中的各個(gè)單詞，如果是，則提取出來，如果不是，則不提取。算法設(shè)計(jì)：

對(duì)學(xué)生答案進(jìn)行分詞后得到一個(gè)由學(xué)生答案組成的詞的序列，對(duì)其進(jìn)行關(guān)鍵詞提取，關(guān)鍵詞提取時(shí)只提取對(duì)句子意思表述至關(guān)重要的實(shí)詞。

具體算法如下：（1）順序搜索語句序列中的各詞，如果到末尾，則結(jié)束，否則轉(zhuǎn)（2）；（2）判定該詞是否為實(shí)詞，如果是，轉(zhuǎn)（3），否則轉(zhuǎn)（1）；（3）將關(guān)鍵詞提取出來，轉(zhuǎn)（1）。

3 相似度計(jì)算算法分析

3.1 單向貼近度算法

在簡(jiǎn)答題的自動(dòng)閱卷過程中，通常把學(xué)生答案和標(biāo)準(zhǔn)答案表示成若干個(gè)詞的形式來表示學(xué)生答案和標(biāo)準(zhǔn)答案的貼近度問題。

把學(xué)生答案和標(biāo)準(zhǔn)答案切分成若干個(gè)有意義的詞，并把這些詞構(gòu)成的有序集合稱為一個(gè)模糊集，U={Ul，U2，U3，…，Un}稱為論域，F(xiàn)（U）代表模糊冪集，是指論域U上的所有模糊子集構(gòu)成的集合。

這里用單向貼近度來衡量?jī)赡：慕咏潭取?/p>

定義1：設(shè)U={Ul，U2，U3，…，Un}，A，B∈F（U）。若映射d：F（U）×F（U）→[0，1]；滿足條件：

（1）d（A，A）=1。

（2）d（B，B）=1。

（3）若A∈B∈C或C∈B∈A，則d（A，B）≥d（A，C），那么稱d（A，B）為A貼近于B的單向貼近度。

定義：設(shè)A、B是由詞構(gòu)成的詞串，A中包含n個(gè)詞，d（A，B）表示A貼近于B的單向貼近度，按照從左到右的順序，集合A中的每個(gè)詞在集合B中出現(xiàn)的有效次數(shù)之和記為m，則d（A，B）=m/n。

（1）

式中：S為該題的最終成績(jī)；S0為該題的分值；P代表單項(xiàng)貼近度所占的分值比例；（1-P）代表關(guān)鍵字匹配所占的分值比例；d（A，B）代表集合A貼近于B的單項(xiàng)貼近度；δ（A，B）代表關(guān)鍵詞匹配程度。

根據(jù)以上定義計(jì)算學(xué)生答案的最終得分，只依據(jù)詞的匹配程度，與詞知識(shí)庫(kù)和語義分析毫無關(guān)系，但是使用這種方法計(jì)算的學(xué)生最終得分精度不會(huì)很高。

3.2 基于詞語表層含義的相似度計(jì)算

所謂的詞語表層含義是指根據(jù)學(xué)生答案和標(biāo)準(zhǔn)答案中相同詞語個(gè)數(shù)而計(jì)算的相似度。假設(shè)有句子A和B，分別代表學(xué)生答案和標(biāo)準(zhǔn)答案，那么句子A和B的相似度用以下公式表示：

（2）

式中：WordSame（A，B）表示學(xué)生答案A和標(biāo)準(zhǔn)答案B的相似度；SameNum（A，B）表示學(xué)生答案A和標(biāo)準(zhǔn)答案B中相同詞語的數(shù)量；Num（A）表示學(xué)生答案A中包含詞的個(gè)數(shù)；Num（B）表示標(biāo)準(zhǔn)答案B中包含詞的個(gè)數(shù)。

這種算法也是基于匹配的方法，精度不高。

3.3 基于多層次結(jié)構(gòu)的句子相似度計(jì)算

通常一個(gè)完整的句子是由組成句子的詞、詞之間的結(jié)構(gòu)、語義、語態(tài)、語境等信息組成。漢語句子成分是非常復(fù)雜的，所以要想真正地實(shí)現(xiàn)計(jì)算機(jī)代替人工閱卷是非常復(fù)雜的。本文力求將構(gòu)成句子的各個(gè)成分完整地表達(dá)出來，分別分析了詞匯信息，綜合研究了單向貼近度、詞語表層含義的相似度算法，以便更加正確地進(jìn)行主觀題的自動(dòng)閱卷。

我們研究的目標(biāo)是將分詞技術(shù)、關(guān)鍵詞匹配技術(shù)、詞語結(jié)構(gòu)信息組合起來，取長(zhǎng)補(bǔ)短，互為補(bǔ)充，表述一個(gè)完整的句子，依據(jù)以上技術(shù)計(jì)算學(xué)生答案和標(biāo)準(zhǔn)答案之間的相似度，獲得較高的準(zhǔn)確率。

綜合以上分析將式（1）和式（2）合起來計(jì)算語句相似度?；谝陨戏治?，幾乎不能出現(xiàn)0分的情況，但是實(shí)際閱卷過程中是有0分的，所以我們?cè)O(shè)定一個(gè)閾值，當(dāng)句子的匹配結(jié)果小于設(shè)定的閾值，就將得分算為0分。

4 結(jié)語

要設(shè)計(jì)實(shí)現(xiàn)一個(gè)針對(duì)簡(jiǎn)答題的自動(dòng)閱卷系統(tǒng)，僅基于分句與分詞算法、關(guān)鍵詞提取算法、相似度計(jì)算算法進(jìn)行簡(jiǎn)答題的自動(dòng)閱卷還是遠(yuǎn)遠(yuǎn)不夠的，因?yàn)闈h語較英語而言擁有更加復(fù)雜的語法結(jié)構(gòu)，希望通過后續(xù)針對(duì)中文的語法和語義等方面的研究，不斷完善和改進(jìn)現(xiàn)有的自動(dòng)閱卷系統(tǒng)，促進(jìn)教育信息化平臺(tái)的建設(shè)。

參考文獻(xiàn)

[1] 金春霞.多層次結(jié)構(gòu)句子相似計(jì)算的應(yīng)用研究[J].計(jì)算機(jī)應(yīng)用與軟件，2009，（10）.

[2] 吳宏良.Office文檔對(duì)象分析與自動(dòng)閱卷系統(tǒng)研究

[D].華東師范大學(xué)，2009.

作者簡(jiǎn)介：李瑩（1982-），女，吉林吉林人，吉林醫(yī)藥學(xué)院計(jì)算機(jī)教研室講師，碩士，研究方向：軟件開發(fā)。

（責(zé)任編輯：周 瓊）