基于XML的標記串提取算法

鐘美

（成都東軟學院，成都611844）

基于XML的標記串提取算法

鐘美

（成都東軟學院，成都611844）

研究一種基于XML的標記串提取算法。從C語言全集中挑選出部分能代表程序結構的關鍵結構，總結出常見抄襲方式；根據不同的關鍵結構設計不同的標記串提取算法，將關鍵結構的結構信息存儲于XML文本中；對此算法進行相關測試，測試結果驗證算法的有效性。

XML；C程序；標記串提取算法

0　引言

隨著互聯網的迅速發展，信息資源的獲取變得更加方便和快捷，同時抄襲也變更得加容易。就計算機專業而言，因其工程實踐性的特征幾乎完全采用計算機進行教學與考核，從而導致作業中程序代碼抄襲、克隆等現象越來越普遍［1-4］。日益嚴重的抄襲現象既破壞正常的教學秩序，同時也影響到教學質量和學生素質的提高。程序代碼的相似度研究既能高效地發現存在抄襲嫌疑的程序代碼，也有助于確保檢測的準確性與評判的客觀性。高效的標記串提取算法能提高檢測的有效性。

本文針對C程序提出一種生成標記字符串的方法，即用XML（Extensible Markup Language）文本來表示C程序。XML是可擴展標記語言［5-6］，加上C語言的強結構性，用XML文本來存儲提取的標記串并反映程序的結構是可行的。此方法提取的標記串可以任意提取C程序代碼中容易發生抄襲的信息，可以細化到某個變量的初始化、函數名、結構體名、for語句的3個條件表達式、while和do…while語句的判斷條件等，從而提高相似度計算的準確率，為程序代碼的抄襲判定提供更準確的度量依據。

1　基于XML的標記串提取算法設計

為了能更好地檢測學生程序代碼的抄襲和減輕教師的工作量，在研究和設計以XML為基礎的標記串提取算法時針對不同的關鍵結構設計出了不同的標記串提取算法。C程序的關鍵結構主要分為以下幾類：變量定義，指針，結構體，宏定義，函數，循環結構（do…while；while；for）和條件結構（if；else if；else；switch；case；default）。由于篇幅限制，在這主要介紹結構體和for循環的標記串提取算法。

1.1常見抄襲方式

通過近五年講授《程序設計基礎》課程的經驗和對五百多份學生編程作業的仔細研究和總結，把結構體和for循環的常見抄襲方式分別總結如下：

①結構體：重命名結構體名和結構體變量名；結構體變量的直接定義與間接定義互換；改變結構體成員的數據類型；結構體成員的標識符重命名；拆分結構體變量定義和初始化賦值；重排序結構體成員列表；調整結構體定義語句或結構體變量定義語句的位置；改變結構體定義語句的書寫格式。與結構體相關的部分抄襲方式如圖1所示。

圖1　結構體抄襲方式實例

②for循環：for、while、do…while之間相互替換；將for語句中的第一個表達式放到for語句的前面；將for語句中的第三個表達式放到for語句循環體的最后面；重命名條件判斷語句中的標識符；增加冗余的條件判斷語句；循環體內部語句的重排序；語句的等價替換，如把i++變為i=i+1或者把sum=sum+i變為sum+=i；增加冗余語句；調整循環結構的位置。與for循環相關的部分抄襲方式如圖2所示。

圖2　for循環抄襲方式實例

1.2結構體轉化為XML文本的算法

在前文中，我們已經詳細給出結構體常見的抄襲方式，在這些信息的基礎上設計結構體轉化為對應的XML文本的算法。對于結構體而言，我們主要提出它的結構體名和具體的屬性項，屬性項的提取調用的是變量定義的提取方法。還需要注意的是當結構體變量采用直接定義法時，應提取出結構體變量定義語句，并使用變量定義的轉化方法把它轉化為對應的XML文本。當識別到程序代碼中的某行是結構體定義的開始行我們就調用名為structs的函數來實現轉換。structs函數中調用了一個名為CToXml的函數，它的主要功能是實現遞歸調用將不同關鍵結構轉化為對應的XML文本，此函數的實現只是簡單使用字符串的匹配，在這就不給予詳細的介紹。structs函數的偽代碼如圖3所示。

圖3　structs函數的偽代碼

get_struct_name函數是結構體轉化為XML文本的具體信息提取函數。針對提取行，從左到右按標識符提取，當提取的標識符是struct時緊跟著提取結構體名，接著提取結構體的body屬性并獲得結構體定義語句的結束行行號，最后判斷是否存在結構體變量的直接定義語句，如果存在則記錄下來。get_struct_name的偽代碼如圖4所示。

圖4　get_struct_name函數的偽代碼

1.3for循環轉化為XML文本的算法

針對for循環，我們主要提取它的三個條件表達式和for語句包含的所有內部語句。由于for循環三個條件表達式書寫的靈活性，導致出現了越來越多因改變條件表達式的位置而產生的抄襲現象。在設計提取算法時，我們就設法統一for、while和do…while三種循環語句轉化為XML文本的形式，將for語句中的條件表達式1和條件表達式3抽取出來分別處理并轉化為對應的XML文本。在for語句的提取過程中，我們主要涉及到的是get_for函數和get_for_condition函數。get_for函數主要用于條件表達式3的提取和實現for循環體語句的遞歸提取。get_for函數的偽代碼如圖5所示。

圖5　get_for函數的偽代碼

get_for_condition函數中主要實現for語句中條件表達式1、條件表達式2和body屬性的提取。其中涉及到一個名為begin_end的函數，它的主要功能是得到for循環體內部語句的開始行號、結束行號和循環體的所有內部語句即body屬性的存儲內容，此函數的實現簡單，在這就不給予詳細的介紹。get_for_condition函數的偽代碼如圖6所示。

圖6　get_for_condition函數的偽代碼

2　算法測試

為了證明本文設計的基于XML的標記串提取算法的有效性，我們將以C程序的關鍵結構為分類原則對標記串提取算法進行測試。

基于XML的標記串提取算法的設計目的就是為了更有效地檢測學生程序設計類課程中存在的抄襲現象，所以在選擇測試數據時，我們就隨機抽取學生的程序作業作為測試數據。首先選擇具有代表性的程序題目，所選擇的程序題目必須包括能代表C程序的10種關鍵結構，再從學生提交成功的程序作業中隨機抽取30個程序作為測試數據。把這30個測試用例放在一個test文件夾下，直接把test存放的地址作為輸入，輸出相應的XML文本。以C程序的10種關鍵結構為分類原則整理測試數據和測試結果，整理結果如表1所示。經人工仔細判定生成的30個XML文本，全部轉化為正確的XML文本。

表1　測試用例表

接著我們來看一個實例，如圖7所示，左邊的程序代碼是上述測試數據中的一個學生作業的源程序，右邊為此程序轉化為的XML文本。測試程序中的普通變量定義、數組定義、while語句、for語句、if語句和函數都轉化為正確的XML文本。

圖7　測試實例

3　結語

上述測試結果表明，本文提出的基于XML的標記串提取算法較好地實現了從C程序到XML文本的轉換，經過30個程序的測試，轉換工作正常。但由于前期算法設計需要準備的知識較多，花費時間較長，實現后的測試工作還不夠充分。今后我們將選擇更多的學生程序，來對算法進行更全面的測試，完善存在的不足?；赬ML的標記串提取算法現在只適用于C程序，如需要還可以擴展到C++、Java程序?；赬ML的標記串提取算法的實現不僅為檢測學生程序設計類課程中的抄襲奠定了基礎，而且保證了抄襲檢測的準確性和評價的客觀性。

［1］Georgina C，Mike J.Source-Code Plagiarism：A UK Academic Perspective［R］.Research Report RR-422，Department of Computer Science，University of Warwick，2006.

［2］Sheard J，Dick M，Markham S，et al.Cheating and Plagiarism：Perceptions and Practices of First Year IT Students［A］.In Proc.of the 7th Annual SIGCSE Conference on Innovation and Technology in Computer Science Education.New York：Association for Computing Machinery，2002：183-187.

［3］侯敏，劉東升.程序代碼抄襲檢測技術研究［J］.內蒙古師范大學學報（自然科學漢文版），2007，36（6）：24-26.

［4］程金宏，劉東升.程序代碼相似度自動度量技術研究綜述［J］.內蒙古師范大學學報（自然科學漢文版），2006，35（4）：457-461.

［5］王繼遠.一種用于軟件作業評判系統的程序結構分析算法的設計與實現［D］.北京郵電大學，2007.

［6］朱江.基于XML的程序設計自動批改的研究［D］.湘潭：湘潭大學，2004.

Algorithm of Token String Extraction Based on XML

ZHONG Mei
（Chengdu Neusoft University，Chengdu 611844）

Studies an extraction algorithm for token string based on XML.The key structure that can represent the procedural structure from C language is picked out，summarizes the means of plagiarism of possible existence of key structure；according to the different key structure，designs the different extraction algorithm for token string，the structure information of key structure is extracted and stored in XML text. Test result verifies the efficiency of the algorithm.

XML；C Program；Extraction Algorithm for Token String

1007-1423（2016）23-0046-04DOI：10.3969/j.issn.1007-1423.2016.23.012

鐘美（1985-），女，四川都江堰，碩士研究生，研究方向為計算機輔助教學、算法設計與分析

2016-05-26

2016-07-20