陳星+李郴

摘要：在一套試卷中，重復(fù)題問(wèn)題是影響考試質(zhì)量的一個(gè)重要因素。該文針對(duì)C語(yǔ)言試卷中選擇題間易出現(xiàn)重復(fù)題問(wèn)題進(jìn)行深入研究.通過(guò)對(duì)代碼相似性檢測(cè)以及文本相似性檢測(cè)綜合研究應(yīng)用，希望能找到較好地處理C語(yǔ)言試卷中選擇題的重復(fù)題問(wèn)題的方法，進(jìn)一步提高C語(yǔ)言組卷模塊的組卷質(zhì)量，減輕教師的工作量。

關(guān)鍵詞：重復(fù)題；代碼相似性檢測(cè)；文本相似性檢測(cè)

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）01-0214-03

Abstract：In a set of test papers， repetition problem is an important factor affecting the quality of the examination. Aiming at the problem easily appears between the in-depth study of repeated questions C language test. Based on the code similarity detection and text similarity detection method of comprehensive research， hope to repeat questions can find better choice C language in the test， to further improve the quality of the C language test paper module， reduce the teacher the workload.

Key words： Repetition problem；Code similarity detection；Text similarity detection

隨著計(jì)算機(jī)技術(shù)的高速發(fā)展，越來(lái)越多的教學(xué)環(huán)節(jié)向電子化和網(wǎng)絡(luò)化轉(zhuǎn)變，目前很多高校開(kāi)始創(chuàng)建自己的C語(yǔ)言試題庫(kù)平臺(tái)，大部分的C語(yǔ)言試題庫(kù)都可以進(jìn)行試卷的自動(dòng)生成，這不僅省去了教師編題時(shí)苦惱于自身偏向的煩惱，更能體現(xiàn)考試的公平性與公正性，同時(shí)減輕了教師的工作壓力與負(fù)擔(dān)。計(jì)算機(jī)自動(dòng)組卷保證了試卷的客觀性、科學(xué)性和公平性，使得試題和試卷的管理變得高效便捷，對(duì)提高教師工作效率，實(shí)現(xiàn)課程管理現(xiàn)代化具有十分重要的意義。但是在C語(yǔ)言自動(dòng)組卷過(guò)程中，有可能會(huì)發(fā)生重復(fù)題問(wèn)題，導(dǎo)致組卷質(zhì)量下降，進(jìn)而影響考試質(zhì)量。

由于在C語(yǔ)言試卷中選擇題形式有其特殊性，主要表現(xiàn)于在一道選擇題中文本和代碼同時(shí)存在，情況相對(duì)復(fù)雜，因此本文針對(duì)C語(yǔ)言試卷中的選擇題進(jìn)行研究。對(duì)重復(fù)題的檢測(cè)，本文應(yīng)用相似性檢測(cè)原理，并針對(duì)選擇題的特殊性，采用合理方案，而不能僅僅使用文本相似度檢測(cè)或者代碼相似度檢測(cè)來(lái)對(duì)C語(yǔ)言試卷中的選擇題進(jìn)行相似性比對(duì)，需要綜合應(yīng)用兩種算法進(jìn)行比對(duì)。

1 相關(guān)技術(shù)分析

本文研究如何解決C語(yǔ)言試卷中選擇題易出現(xiàn)的重復(fù)題問(wèn)題，故本文研究的重點(diǎn)是如何尋找選擇題中出現(xiàn)的重復(fù)題，由于選擇題形式的特殊性，本文將引入空間向量模型的概念，綜合使用文本相似度比對(duì)方法以及代碼相似度比對(duì)方法來(lái)進(jìn)行C語(yǔ)言選擇題中是否出現(xiàn)重復(fù)的檢測(cè)。

1.1 空間向量模型概念

空間向量模型的思想是：每篇文本中都包含一些用特征項(xiàng)表達(dá)的揭示其內(nèi)容的獨(dú)立屬性，而每個(gè)屬性都可以看成是向量空間的一個(gè)維數(shù)，那么文本就可以表示為這些屬性的集合，從而忽略了文本的結(jié)構(gòu)中段落，句子及詞語(yǔ)之間的復(fù)雜關(guān)系。這樣，文本就可以用空間的一個(gè)向量來(lái)表示，文本之間的相似度可以用向量間的距離來(lái)衡量。

本文中把C語(yǔ)言試卷選擇題中的文本部分和代碼部分的內(nèi)容當(dāng)做是一篇文本，那么我們就可以將向量空間模型的概念引入到本文研究的選擇題中。兩道選擇題之間的相似度就可以用向量間的距離來(lái)衡量，向量之間的距離通常采用余弦系數(shù)法進(jìn)行判定，即用兩個(gè)向量之間的夾角余弦來(lái)表示兩道選擇題之間的相似度。夾角越小，說(shuō)明兩道選擇題的相似度越大。

通過(guò)上述的向量空間模型，文本數(shù)據(jù)就轉(zhuǎn)換成了計(jì)算機(jī)可以處理的結(jié)構(gòu)化數(shù)據(jù)，兩個(gè)文檔之間的相似性問(wèn)題轉(zhuǎn)變成了兩個(gè)向量之間的相似性問(wèn)題。

1.2 分詞方法

對(duì)于選擇題中出現(xiàn)的文本，需要通過(guò)分詞方法選取出其中的文本關(guān)鍵詞，目前常用的分詞方法主要有以下兩種：

1.2.1 基于統(tǒng)計(jì)的分詞方法

基于統(tǒng)計(jì)的分詞方法就是把字與字相鄰共現(xiàn)的頻率作為成詞的可信度評(píng)價(jià)標(biāo)準(zhǔn)?？梢詫?duì)語(yǔ)料中相鄰共現(xiàn)的各個(gè)字的組合的頻度進(jìn)行統(tǒng)計(jì)，計(jì)算它們的互現(xiàn)信息?；ガF(xiàn)信息體現(xiàn)了漢字之間結(jié)合關(guān)系的緊密程度。當(dāng)緊密程度高于某一個(gè)閾值時(shí)，便可認(rèn)為此字組可能構(gòu)成了一個(gè)詞，否則，認(rèn)為它們不能組合。基于統(tǒng)計(jì)的分詞方法的原理是根據(jù)相鄰字出現(xiàn)的頻率來(lái)確定是否屬于一個(gè)詞，該方法不需要建立詞典，有詞的歧義判斷能力，適用于大規(guī)模的文本分詞處理。

在本文研究的文本部分中，內(nèi)容少，相同詞匯出現(xiàn)的頻率低，因此不適合使用基于統(tǒng)計(jì)的分詞方法。

1.2.2 基于詞典匹配的分詞方法

基于詞典匹配的分詞方法是按照一定的策略將待分析的字符串與詞典中的詞條進(jìn)行匹配，若在詞典中找到某個(gè)字符串，則匹配成功[2]。該方法分詞效率高，但是完全依賴于詞典，無(wú)法判斷詞的歧義性，而且由于漢語(yǔ)環(huán)境復(fù)雜，詞典不太完備，規(guī)則不一致等問(wèn)題的存在，使得這種分詞方法無(wú)法應(yīng)用與大規(guī)模的文本分詞處理。

本文研究的文本，規(guī)模小，詞匯量少，詞匯之間的歧義性低。因此適合于這種分詞方法，能夠降低重復(fù)題檢測(cè)模塊的時(shí)間復(fù)雜度。

1.3 代碼相似度計(jì)算方法

目前使用比較多的代碼相似度計(jì)算方法主要有，基于屬性計(jì)數(shù)的相似度計(jì)算方法，基于結(jié)構(gòu)的相似度計(jì)算方法，以及基于語(yǔ)法樹(shù)的相似度計(jì)算方法?；趯傩杂?jì)數(shù)計(jì)算方法主要是針對(duì)于程序代碼中的定義的關(guān)鍵詞，循環(huán)數(shù)等，不考慮程序的結(jié)構(gòu)?；诮Y(jié)構(gòu)的相似度計(jì)算方法主要是通過(guò)程序的結(jié)構(gòu)特征，分析程序的結(jié)構(gòu)信息及執(zhí)行流程，通過(guò)對(duì)程序的內(nèi)部結(jié)構(gòu)進(jìn)行分析比較其相似性?；谡Z(yǔ)法樹(shù)的代碼相似度檢測(cè)方法對(duì)源程序進(jìn)行語(yǔ)法分析而得到其語(yǔ)法樹(shù)，對(duì)待處理的源程序的語(yǔ)法樹(shù)結(jié)點(diǎn)進(jìn)行分類統(tǒng)計(jì)，采用矢量和計(jì)算方法計(jì)算結(jié)點(diǎn)屬性向量，最終通過(guò)向量相似度與預(yù)設(shè)閾值的比較判定是否相似。endprint

該文研究的程序代碼的特點(diǎn)是，不一定具有明顯的結(jié)構(gòu)，有可能僅僅是幾個(gè)簡(jiǎn)單的語(yǔ)句，因此無(wú)法僅使用基于屬性計(jì)數(shù)或者基于結(jié)構(gòu)的相似度計(jì)算方法進(jìn)行比較，而基于語(yǔ)法樹(shù)的相似度計(jì)算方法結(jié)合了程序代碼的結(jié)構(gòu)特征以及屬性特征，滿足了該文程序代碼的特點(diǎn)。因此該文擬采用基于語(yǔ)法樹(shù)的相似度計(jì)算方法處理代碼。

1.4 余弦相似度

余弦相似度是用向量空間中兩個(gè)向量夾角的余弦值作為衡量?jī)蓚€(gè)個(gè)體間差異的大小的度量。n維余弦公式（公式1）為：

余弦值越接近1，就表明夾角越接近0度，也就是兩個(gè)向量越相近，夾角等于0，即兩個(gè)向量相等，這就叫“余弦相似性”。

2 重復(fù)題檢測(cè)方案

本文的思想是將C語(yǔ)言中的選擇題看成是由文本特征向量，代碼特征向量以及知識(shí)點(diǎn)組成的n維向量空間模型，而從對(duì)C語(yǔ)言選擇題的特點(diǎn)上可以大致將選擇題分為以下幾種情況，以文字來(lái)表述的選擇題，以代碼形式表述的選擇題，以及文本和部分C語(yǔ)言語(yǔ)句混合表述的選擇題。對(duì)于單純的以文本形式表述的選擇題，其中的代碼特征向量全部用0表示，對(duì)于單純以代碼形式表述的選擇題，其文本特征向量全部用0表示。

在重復(fù)題查找的過(guò)程中，首先是對(duì)待比較的選擇題進(jìn)行格式規(guī)范化，然后將選擇題中的文本和代碼進(jìn)行分離，提取特征向量，并建立文本和代碼的空間向量模型，將文本和代碼向量進(jìn)行融合，得到題目的空間向量模型，之后求取兩個(gè)向量的余弦值，最終通過(guò)余弦值與預(yù)設(shè)閾值的比較判定是否相似。預(yù)設(shè)閾值的獲取是通過(guò)對(duì)大量相似題進(jìn)行比對(duì)，計(jì)算相似值，根據(jù)對(duì)大量相似值分析，確定預(yù)設(shè)閾值的大小，如果兩個(gè)向量的余弦值大于預(yù)設(shè)閥值時(shí)，就認(rèn)為這兩道選擇題是重復(fù)題。

所謂的規(guī)范化是指：將試題中出現(xiàn)的一些用文本表達(dá)的代碼表達(dá)式，使用代碼表示；將題目中相同語(yǔ)義的詞語(yǔ)使用同一個(gè)詞替換。比如在試題中出現(xiàn)這樣一句話，“定義一個(gè)整型變量a”，轉(zhuǎn)換成“int a”這樣的代碼表達(dá)式表示； “下列屬于合法的標(biāo)識(shí)符的是”和“下列標(biāo)識(shí)符正確的是”，兩句話中“合法”和“正確”屬于同義詞，都替換成“正確”一詞。

2.1 文本特征向量的提取

由于本文主要是針對(duì)于C語(yǔ)言選擇題進(jìn)行研究，對(duì)于C語(yǔ)言中存在的許多專業(yè)名詞，如數(shù)組，鏈表等，若單純采用普通文本詞匯庫(kù)進(jìn)行分詞，可能會(huì)造成較大誤差，并且會(huì)造成時(shí)間復(fù)雜度增加，所以我們需要建立專門(mén)的詞匯庫(kù)，通過(guò)基于字符串匹配的方法對(duì)試題中文本進(jìn)行特征向量提取。

對(duì)于短文本來(lái)說(shuō)特征向量越多，代表的文本信息越詳細(xì)。所以該文擬保留全部的文本詞匯，僅將其中的語(yǔ)句頓詞，例如“是”，“的”等詞匯去掉，剩余詞匯作為文本的特征向量，通過(guò)文本特征向量，將文本以空間向量模型（公式2）的形式表示出來(lái)：

2.2 代碼特征屬性的提取

對(duì)于代碼，主要通過(guò)對(duì)待比較的代碼程序進(jìn)行語(yǔ)法分析，得到語(yǔ)法樹(shù)，對(duì)待處理源程序的語(yǔ)法樹(shù)結(jié)點(diǎn)進(jìn)行分類統(tǒng)計(jì)，采用矢量和計(jì)算方法計(jì)算結(jié)點(diǎn)屬性向量。

首先，需要將源代碼進(jìn)行預(yù)處理，例如，將源代碼中的連續(xù)多個(gè)空格全部處理成一個(gè)，將代碼中注釋和多行空白行全部去掉，將在語(yǔ)義上相同的語(yǔ)句使用同一語(yǔ)句處理，比如將（a+=b）均使用（a=a+b）代替；（i++，++i）全部使用（i=i+1）代替，將聲明多個(gè)變量的語(yǔ)句（int a，b）使用單個(gè)聲明語(yǔ)句代替（int a；int b）等等。

語(yǔ)法樹(shù)中的結(jié)點(diǎn)也就是將源代碼進(jìn)行預(yù)處理之后程序的特征屬性，可以選擇以下結(jié)點(diǎn)[標(biāo)識(shí)符，常量，賦值語(yǔ)句，函數(shù)或過(guò)程，數(shù)組和結(jié)構(gòu)體，條件結(jié)構(gòu)，表達(dá)式語(yǔ)句，聲明變量個(gè)數(shù)，循環(huán)結(jié)構(gòu)等]表示語(yǔ)法樹(shù)的每個(gè)結(jié)點(diǎn)，父結(jié)點(diǎn)的屬性向量等于結(jié)點(diǎn)初始屬性向量及其所有子結(jié)點(diǎn)的屬性向量的矢量和。在生成語(yǔ)法樹(shù)的時(shí)候，可以采用UCC的方法或ANTLR語(yǔ)法分析工具，將程序生成相應(yīng)的語(yǔ)法結(jié)構(gòu)和抽像語(yǔ)法樹(shù)，本文將語(yǔ)法結(jié)構(gòu)存到一個(gè)*.txt文件中，之后利用著名的詞法分析工具Lex從這個(gè)文件中抽取邏輯結(jié)構(gòu)，另外將語(yǔ)法樹(shù)存放在*.asm文件中[6]。

在生成程序的語(yǔ)法樹(shù)之后，可以針對(duì)相應(yīng)的文件來(lái)抽取里面的特征向量（結(jié)構(gòu)信息）及其個(gè)數(shù)。這里從該語(yǔ)法樹(shù)中抽取其相應(yīng)的結(jié)點(diǎn)作為特征向量，其結(jié)點(diǎn)可以表示為[標(biāo)識(shí)符，常量，賦值語(yǔ)句，函數(shù)或過(guò)程，數(shù)組和結(jié)構(gòu)體，條件結(jié)構(gòu)，表達(dá)式語(yǔ)句，聲明變量個(gè)數(shù)，循環(huán)結(jié)構(gòu)]，每個(gè)結(jié)點(diǎn)出現(xiàn)的個(gè)數(shù)作為其頻度信息。

最后將提取的代碼特征向量，使用n維空間向量模型（公式3）表示出來(lái)：

2.3 向量對(duì)齊

將文本空間向量，代碼空間向量，以及從數(shù)據(jù)庫(kù)中提取的試題知識(shí)點(diǎn)屬性（本文采用每題最多3個(gè)知識(shí)點(diǎn)）融合到一起形成一個(gè)多維的試題空間向量模型S，如公式（4）。

由于不同試題中文本空間向量個(gè)數(shù)以及代碼空間向量個(gè)數(shù)不一致，因此需要將試題空間向量模型的維數(shù)統(tǒng)一成n維的，例如存在兩道試題，試題1的文本空間向量由（A，B，C）三個(gè)特征向量組成，代碼空間向量由（D，E，F(xiàn)）三個(gè)特征向量組成，知識(shí)點(diǎn)由（Z1，Z2，Z3）三個(gè)特征向量組成，試題1的空間向量模型可以表示為S1（A，B，C，D，E，F(xiàn)，Z1，Z2，Z3）；試題2的文本空間向量由（A，B，C，D）四個(gè)特征向量組成，代碼空間向量由（D，F(xiàn)，G，H）四個(gè)特征向量組成，知識(shí)點(diǎn)由（Z1，Z2，Z3）三個(gè)特征向量組成，試題2的空間向量模型組成可以表S2（A，B，C，D，D，F(xiàn)，G，H，Z1，Z2，Z3）。對(duì)于試題1和試題2的相似性比較，首先需要將文本，代碼維數(shù)進(jìn)行統(tǒng)一。對(duì)特征向量之間進(jìn)行比對(duì)，將兩道試題中不同的特征向量融合到一起作為試題的特征向量，若上面兩道試題中特征向量全都不一樣，則試題1的空間向量模型可以表示為：S1（A，B，C，A，B，C，D，D，E，F(xiàn)，D，F(xiàn)，G，H，Z1，Z2，Z3，Z1，Z2，Z3），對(duì)于試題1中的所有關(guān)于試題2的特征向量都不存在，因此需要用0來(lái)表示；同理，試題2的空間向量模型也可以用S2（A，B，C，A，B，C，D，D，E，F(xiàn)，D，F(xiàn)，G，H，Z1，Z2，Z3，Z1，Z2，Z3）來(lái)表示出來(lái)。這樣可以使得兩道待比較試題維數(shù)的統(tǒng)一。

2.4 題目相似度計(jì)算

通過(guò)上面對(duì)選擇題的處理，分別將兩道選擇題使用空間向量表示出來(lái)，然后通過(guò)多維余弦定理（公式5）進(jìn)行相似度計(jì)算：

將求得的余弦值與預(yù)定閾值進(jìn)行比較，判斷兩道題目是否相似。

3 結(jié)束語(yǔ)

本文在C語(yǔ)言試題庫(kù)的研究基礎(chǔ)上，對(duì)自動(dòng)組卷后的試題進(jìn)行重復(fù)題查找研究，通過(guò)對(duì)試卷中出現(xiàn)的重復(fù)題特點(diǎn)進(jìn)行歸納總結(jié)，對(duì)文本和代碼相似度進(jìn)行深入研究，給出合理算法，以查找自動(dòng)組卷后試卷中產(chǎn)生的重復(fù)題，使C語(yǔ)言試題庫(kù)系統(tǒng)的智能組卷功能更加合理有效。

參考文獻(xiàn)：

[1] Jacob G，Debar H，F(xiàn)illol E.Behavioral detection of malware： From a survey towards an established taxonomy.Journal in Computer Virology，2015.

[2] Li Y，Zuo ZH.An overview of object-code obfuscation technologies.Journal of Computer Technology and Development，2016（17）.

[3] 全上克，楊新鋒.程序代碼相似度檢測(cè)方法的設(shè)計(jì)與實(shí)現(xiàn)[J].微型電腦與應(yīng)用，2013（6）.

[4] 曹海英，元元等.程序代碼抄襲檢測(cè)中串匹配算法的研究[J].信息安全技術(shù)，2015（6）.

[5] 郭少友.自動(dòng)分類中的文檔表示及其改善方法研究[J].信息技術(shù)，2014，3（8）：23-25.

[6] 尚文倩.文本分類及其相關(guān)技術(shù)的研究[D].北京：北京交通大學(xué)，2015.endprint