C語言組卷系統中重復題問題研究

陳星+李郴

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

關鍵詞：重復題；代碼相似性檢測；文本相似性檢測

中圖分類號：TP311 文獻標識碼：A 文章編號：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

隨著計算機技術的高速發展，越來越多的教學環節向電子化和網絡化轉變，目前很多高校開始創建自己的C語言試題庫平臺，大部分的C語言試題庫都可以進行試卷的自動生成，這不僅省去了教師編題時苦惱于自身偏向的煩惱，更能體現考試的公平性與公正性，同時減輕了教師的工作壓力與負擔。計算機自動組卷保證了試卷的客觀性、科學性和公平性，使得試題和試卷的管理變得高效便捷，對提高教師工作效率，實現課程管理現代化具有十分重要的意義。但是在C語言自動組卷過程中，有可能會發生重復題問題，導致組卷質量下降，進而影響考試質量。

由于在C語言試卷中選擇題形式有其特殊性，主要表現于在一道選擇題中文本和代碼同時存在，情況相對復雜，因此本文針對C語言試卷中的選擇題進行研究。對重復題的檢測，本文應用相似性檢測原理，并針對選擇題的特殊性，采用合理方案，而不能僅僅使用文本相似度檢測或者代碼相似度檢測來對C語言試卷中的選擇題進行相似性比對，需要綜合應用兩種算法進行比對。

1 相關技術分析

本文研究如何解決C語言試卷中選擇題易出現的重復題問題，故本文研究的重點是如何尋找選擇題中出現的重復題，由于選擇題形式的特殊性，本文將引入空間向量模型的概念，綜合使用文本相似度比對方法以及代碼相似度比對方法來進行C語言選擇題中是否出現重復的檢測。

1.1 空間向量模型概念

空間向量模型的思想是：每篇文本中都包含一些用特征項表達的揭示其內容的獨立屬性，而每個屬性都可以看成是向量空間的一個維數，那么文本就可以表示為這些屬性的集合，從而忽略了文本的結構中段落，句子及詞語之間的復雜關系。這樣，文本就可以用空間的一個向量來表示，文本之間的相似度可以用向量間的距離來衡量。

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

通過上述的向量空間模型，文本數據就轉換成了計算機可以處理的結構化數據，兩個文檔之間的相似性問題轉變成了兩個向量之間的相似性問題。

1.2 分詞方法

對于選擇題中出現的文本，需要通過分詞方法選取出其中的文本關鍵詞，目前常用的分詞方法主要有以下兩種：

1.2.1 基于統計的分詞方法

基于統計的分詞方法就是把字與字相鄰共現的頻率作為成詞的可信度評價標準。可以對語料中相鄰共現的各個字的組合的頻度進行統計，計算它們的互現信息。互現信息體現了漢字之間結合關系的緊密程度。當緊密程度高于某一個閾值時，便可認為此字組可能構成了一個詞，否則，認為它們不能組合。基于統計的分詞方法的原理是根據相鄰字出現的頻率來確定是否屬于一個詞，該方法不需要建立詞典，有詞的歧義判斷能力，適用于大規模的文本分詞處理。

在本文研究的文本部分中，內容少，相同詞匯出現的頻率低，因此不適合使用基于統計的分詞方法。

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

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

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

1.3 代碼相似度計算方法

目前使用比較多的代碼相似度計算方法主要有，基于屬性計數的相似度計算方法，基于結構的相似度計算方法，以及基于語法樹的相似度計算方法。基于屬性計數計算方法主要是針對于程序代碼中的定義的關鍵詞，循環數等，不考慮程序的結構。基于結構的相似度計算方法主要是通過程序的結構特征，分析程序的結構信息及執行流程，通過對程序的內部結構進行分析比較其相似性。基于語法樹的代碼相似度檢測方法對源程序進行語法分析而得到其語法樹，對待處理的源程序的語法樹結點進行分類統計，采用矢量和計算方法計算結點屬性向量，最終通過向量相似度與預設閾值的比較判定是否相似。endprint

該文研究的程序代碼的特點是，不一定具有明顯的結構，有可能僅僅是幾個簡單的語句，因此無法僅使用基于屬性計數或者基于結構的相似度計算方法進行比較，而基于語法樹的相似度計算方法結合了程序代碼的結構特征以及屬性特征，滿足了該文程序代碼的特點。因此該文擬采用基于語法樹的相似度計算方法處理代碼。

1.4 余弦相似度

余弦相似度是用向量空間中兩個向量夾角的余弦值作為衡量兩個個體間差異的大小的度量。n維余弦公式（公式1）為：

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

2 重復題檢測方案

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

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

所謂的規范化是指：將試題中出現的一些用文本表達的代碼表達式，使用代碼表示；將題目中相同語義的詞語使用同一個詞替換。比如在試題中出現這樣一句話，“定義一個整型變量a”，轉換成“int a”這樣的代碼表達式表示； “下列屬于合法的標識符的是”和“下列標識符正確的是”，兩句話中“合法”和“正確”屬于同義詞，都替換成“正確”一詞。

2.1 文本特征向量的提取

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

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

2.2 代碼特征屬性的提取

對于代碼，主要通過對待比較的代碼程序進行語法分析，得到語法樹，對待處理源程序的語法樹結點進行分類統計，采用矢量和計算方法計算結點屬性向量。

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

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

在生成程序的語法樹之后，可以針對相應的文件來抽取里面的特征向量（結構信息）及其個數。這里從該語法樹中抽取其相應的結點作為特征向量，其結點可以表示為[標識符，常量，賦值語句，函數或過程，數組和結構體，條件結構，表達式語句，聲明變量個數，循環結構]，每個結點出現的個數作為其頻度信息。

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

2.3 向量對齊

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

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

2.4 題目相似度計算

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

將求得的余弦值與預定閾值進行比較，判斷兩道題目是否相似。

3 結束語

本文在C語言試題庫的研究基礎上，對自動組卷后的試題進行重復題查找研究，通過對試卷中出現的重復題特點進行歸納總結，對文本和代碼相似度進行深入研究，給出合理算法，以查找自動組卷后試卷中產生的重復題，使C語言試題庫系統的智能組卷功能更加合理有效。

參考文獻：

[1] Jacob G，Debar H，Fillol 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] 全上克，楊新鋒.程序代碼相似度檢測方法的設計與實現[J].微型電腦與應用，2013（6）.

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

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

[6] 尚文倩.文本分類及其相關技術的研究[D].北京：北京交通大學，2015.endprint