基于Levenshtein距離的Word操作題自動(dòng)評分算法

羅泉，劉芝

（1.廣西大學(xué)行健文理學(xué)院，南寧 530005；2.南寧師范大學(xué)，南寧 530001）

0 引言

《大學(xué)計(jì)算機(jī)基礎(chǔ)》是大多數(shù)高校的通識必修課程，學(xué)生們通過學(xué)習(xí)后能熟練掌握Word、Excel、Power?Point等軟件的常用操作，這就需要任課教師能督促學(xué)生完成課堂、課后練習(xí)并及時(shí)修改。但由于班級眾多，任課教師需要大量時(shí)間進(jìn)行批閱修改。為了減輕教師負(fù)擔(dān)，眾多學(xué)者對Office操作題的自動(dòng)評分進(jìn)行了研究，采用的方法主要有幾種。

方法1：使用Office內(nèi)嵌的VBA技術(shù)或Office提供的COM接口，讀取考生文檔每個(gè)元素的屬性信息，依次與標(biāo)準(zhǔn)答案的屬性信息進(jìn)行比較，根據(jù)得分點(diǎn)自動(dòng)計(jì)算出分?jǐn)?shù)[1-3]。

方法2：通過計(jì)算考生文檔與標(biāo)準(zhǔn)答案之間的文本距離，獲得兩者之間的相似度，實(shí)現(xiàn)操作題的自動(dòng)評分[4]。

方法1依賴于Office軟件，不適用于多線程、高并發(fā)情景；方法2適用于考生從空白文件創(chuàng)建答卷文檔的情景，而不適用于從給定素材創(chuàng)建答卷文檔的情景。例如，素材文件有文字“Hello”，題目要求在素材基礎(chǔ)上添加信息，并得到最終文字“Hello World”。若考生將素材文件作為答卷提交，按方法2會得到50分，但實(shí)際應(yīng)為0分。

依據(jù)上述分析，本文針對學(xué)生基于素材完成操作練習(xí)的場景，基于編輯距離實(shí)現(xiàn)了一種Word操作題自動(dòng)評分算法，并對算法進(jìn)行了測試驗(yàn)證。

1 Word OpenXML文件格式介紹

微軟從Office 2007開始使用OpenXML[5]格式來存儲信息，一個(gè)Office文檔由多個(gè)XML文件構(gòu)成，每個(gè)XML文件被稱為部件，用于存儲不同含義的信息。將Word文檔后綴名改為zip并解壓，可以得到如圖1所示的目錄結(jié)構(gòu)。

圖1 Word的OpenXML目錄結(jié)構(gòu)

圖1中，styles.xml包含Word樣式信息，分別存儲在、、節(jié)點(diǎn)中；drawing1.xml包含Word中插入的形狀、SmartArt圖形等信息，存儲在多個(gè)及其子節(jié)點(diǎn)中；document.xml包含Word正文的段落文本、段落屬性、文本屬性、頁面等信息，其中段落文本及相關(guān)屬性按順序存儲在以及子節(jié)點(diǎn)中，字體顏色存儲在節(jié)點(diǎn)中，頁面信息如頁邊距、頁面尺寸等存儲在節(jié)點(diǎn)中[6]。在本文中，將上述存儲了XML核心內(nèi)容的節(jié)點(diǎn)稱為特征節(jié)點(diǎn)。

2 Levenshtein距離

Levenshtein距離即文本編輯距離，提出于1965年，是字符串A通過編輯（添加、刪除、修改）單個(gè)字符，最終修改為字符串B所用的最少步驟次數(shù)，主要用于度量兩個(gè)字符串間的距離[7]。其公式如下：

在本文中，Levenshtein距離主要用于度量兩個(gè)XML片段間的距離，如片段 A：與片段 B：的距離為6，其中代表的是字體顏色。由于在Word中改變字體顏色只需要操作一步，直接計(jì)算XML片段的文本編輯距離并不合理，因此需要將XML片段進(jìn)行轉(zhuǎn)換再計(jì)算距離。以片段為例，對轉(zhuǎn)換的流程說明如下：

（1）定義innerNode類型，innerNode.label用于存儲文本

（2）創(chuàng)建innerNode類型數(shù)組NodeArray

（3）依據(jù)片段的開始標(biāo)簽，構(gòu)造innerNode對象，使 innerNode.label=”A”，添加到 NodeArray數(shù)組尾部

（4）依據(jù)片段的屬性名attr1，構(gòu)造innerNode對象，使 innerNode.label=”attr1”，添加到 NodeArray 數(shù)組尾部

（5）依據(jù)片段的屬性值val1，構(gòu)造innerNode對象，使innerNode.label=”val1”，添加到NodeArray數(shù)組尾部

（6）依據(jù)片段的文本abc，構(gòu)造3個(gè)innerNode對象，使每個(gè)對象的 label分別為”a”、”b”、”c”，并依次添加到NodeArray數(shù)組尾部

（7）依據(jù)片段的結(jié)束標(biāo)簽，構(gòu)造innerNode對象，使 innerNode.label=”/A”，添加到 NodeArray 數(shù)組尾部

當(dāng)比較兩個(gè)innerNode類型對象是否相等時(shí)，等價(jià)于比較對象的label值是否相等。經(jīng)過轉(zhuǎn)換，本節(jié)例子中片段A與片段B之前的編輯距離轉(zhuǎn)成了計(jì)算Node?Array數(shù)組A和NodeArray數(shù)組B之間的編輯距離，計(jì)算過程與公式（1）一致，最終結(jié)果為1。

3 自動(dòng)評分算法實(shí)現(xiàn)

課堂上，在Word操作練習(xí)時(shí)，教師為學(xué)生提供素材文檔，學(xué)生基于素材，按照標(biāo)準(zhǔn)答案效果進(jìn)行操作。因此，評分算法基于素材和答案文檔進(jìn)行度量更為合理。

（1）XML文件的特征節(jié)點(diǎn)向量

一個(gè)XML文件可以看成有序特征節(jié)點(diǎn)t[i]的集合，可表示為：

其中，t[i]擁有 name、NodeArray屬性，name 表示當(dāng)前特征節(jié)點(diǎn)名稱，NodeArray表示該節(jié)點(diǎn)XML片段轉(zhuǎn)換而成的innerNode類型數(shù)組。

設(shè)xmlfilename是xmlfile中所有name屬性值相等的元素的集合，則有：

（2）XML 文件編輯距離 xdist(xmla，xmlb)

設(shè)A、B分別為文件xmla、xmlb的特征節(jié)點(diǎn)向量，Aname、Bname分別是A、B中所有name屬性值相等的元素的集合。分別向A、B中添加NodeArray長度為0的元素，使|A|=|B|并且|Aname(i)|=|Bname(i)|，則兩個(gè) XML 文件的編輯距離計(jì)算方式如下：

其中，A[i]屬于 A，B[j]屬于 B，A[i]、B[j]必須且只能參與一次LevD運(yùn)算，A中的元素按順序與B中name屬性相同的元素進(jìn)行LevD運(yùn)算。

（3）Word文件距離向量

一個(gè)Word文件由多個(gè)XML文件構(gòu)成，為此可表示為 docx={f[1]，f[2]，…，f[n]}，其中，f[n]為一個(gè) XML 文件，按短文件名順序排列。

定義兩個(gè)Word文件docxA和docxB之間的距離向量為兩文件之間同名XML文件的編輯距離的有序集合 wVector(docxA，docxB)，計(jì)算方式如下：

商務(wù)筆譯，顧名思義，是針對商務(wù)文本的翻譯。對于商務(wù)筆譯的研究涉及兩個(gè)關(guān)鍵詞：一個(gè)是商務(wù)文本，另一個(gè)是翻譯。關(guān)于商務(wù)文本，需要梳理清四個(gè)問題：1）什么是商務(wù)文本？即商務(wù)文本的涵蓋范圍和種類。2）商務(wù)文本的分類方式如何？3）商務(wù)文本的功能是什么？4）商務(wù)文本的文體風(fēng)格是什么？關(guān)于翻譯，需要梳理清三個(gè)“誰”的問題：1）作者是誰？2）譯者是誰？3）讀者是誰？只有理清了以上的問題，才能進(jìn)入到下一步討論，即什么樣的翻譯理論對商務(wù)筆譯有切實(shí)的指導(dǎo)作用？本文將主要討論文本類型理論視角下的商務(wù)筆譯。

wVector(docxA，docxB)={v[1]，v[2]，…，v[n]}，其中 v[i]=xdist(fa[i]，fb[i]），fa[i]∈docxA，fb[i]∈docxB，fa[i]和 fb[i]的短文件名相同。

（4）Word操作題自動(dòng)評分算法

有 Word 文件 d0、dx、d100，其中 d0 表示素材，dx表示學(xué)生答卷，d100表示答案。評分的基本思路為：以d0為基準(zhǔn)，分別計(jì)算dx到d0的距離向量vx、d100到d0的距離向量v100，然后依據(jù)vx在v100上的投影計(jì)算分值。

①計(jì)算vx=wVector(dx，d0)，vx為學(xué)生答卷與原始素材文件的文件距離向量。

②計(jì)算 v100=wVector(d100，d0)，v100 為答案文件與原始素材文件的文件距離向量。

③計(jì)算兩個(gè)向量vx、v100之間的余弦cosθ=vx·v100/(|vx|·|v100|)

⑤計(jì)算百分制成績score=100*projection/|v100|

⑥將百分制成績轉(zhuǎn)換成等級成績level，當(dāng)score<60時(shí)為一等級，否則每10分為一等級，等級劃分從高到低為 A、B、C、D、E。

4 實(shí)驗(yàn)驗(yàn)證

本文選用一套綜合練習(xí)題，由48位學(xué)生在課堂上完成，使用等級成績，以人工評分為基準(zhǔn)，對比本文算法與文獻(xiàn)[4]算法，驗(yàn)證評分效果。

該綜合練習(xí)題提供基本素材文件，由學(xué)生在此基礎(chǔ)上完成文字替換、字體顏色設(shè)置、段落格式設(shè)置、添加SmartArt圖形等操作，限時(shí)30分鐘完成。首先由教師課后人工評分，結(jié)果如表1所示，絕大部分學(xué)生能在限定時(shí)間內(nèi)完指定練習(xí)，有3位學(xué)生講所提供素材作為最終成果提交，人工評分應(yīng)為0分，等級為E。

表1 人工評分結(jié)果等級分布

在人工評分之后，分別使用本文算法、文獻(xiàn)[4]算法自動(dòng)給學(xué)生作品評分，并與人工評分結(jié)果比較，使用聚類中常用的Precision準(zhǔn)確度、Recall召回率、F1-Score等指標(biāo)來評價(jià)兩種算法哪一個(gè)更優(yōu)[8]；通過記錄兩種算法的運(yùn)行時(shí)間來評價(jià)其執(zhí)行效率。一般來說相關(guān)指標(biāo)數(shù)值越大表明越優(yōu)，實(shí)驗(yàn)結(jié)果如表2、表3所示。

表2 本文算法實(shí)驗(yàn)結(jié)果

表3 文獻(xiàn)[4]算法實(shí)驗(yàn)結(jié)果

從表2、表3中可以看出，在A等級中，Recall為1，說明人工評分中為A的所有成績，在兩種算法中均評定為A，表2的Precision指標(biāo)比表3的相應(yīng)指標(biāo)略高，說明本文算法比文獻(xiàn)[4]算法略優(yōu)；對于人工評分判定為E等級的3位學(xué)生，表2的Recall為1，說明本文算法判定其成績?yōu)镋等級，表3的Recall為0，說明文獻(xiàn)[4]算法判定為其他等級，因此本文算法更為準(zhǔn)確合理；在執(zhí)行效率上，本文算法所消耗時(shí)間263秒，比文獻(xiàn)[4]算法少。綜上所述，在所選測試樣本數(shù)據(jù)下，與文獻(xiàn)[4]算法相比，本文算法較優(yōu)，且能滿足日常練習(xí)的操作題評分要求。但由于本文算法忽略不同操作步驟的權(quán)重，因此無法根據(jù)作品所完成的步驟評分，尚未做到與人工評分完全一致。

5 結(jié)語

本文針對學(xué)生在素材基礎(chǔ)上完成操作練習(xí)的場景，設(shè)計(jì)了一種基于Levenshtein距離的Word自動(dòng)評分算法，通過計(jì)算學(xué)生作品文件與原始素材、答案文件之間的距離，通過一系列運(yùn)算自動(dòng)獲得該作品分?jǐn)?shù)等級。實(shí)驗(yàn)結(jié)果表明，該算法在為等級A、E的作品評分時(shí)有較高的精確率，日常的練習(xí)評分中有較好的應(yīng)用效果，可有效提高老師的工作效率，但不足之處在于不能調(diào)整步驟分值，不能為操作的每一個(gè)步驟設(shè)置得分權(quán)重，而且測試樣本容量較小，不能覆蓋所有的操作測試，有待進(jìn)一步完善。