基于XML的標(biāo)記串提取算法

鐘美

（成都東軟學(xué)院，成都611844）

基于XML的標(biāo)記串提取算法

鐘美

（成都東軟學(xué)院，成都611844）

研究一種基于XML的標(biāo)記串提取算法。從C語言全集中挑選出部分能代表程序結(jié)構(gòu)的關(guān)鍵結(jié)構(gòu)，總結(jié)出常見抄襲方式；根據(jù)不同的關(guān)鍵結(jié)構(gòu)設(shè)計(jì)不同的標(biāo)記串提取算法，將關(guān)鍵結(jié)構(gòu)的結(jié)構(gòu)信息存儲于XML文本中；對此算法進(jìn)行相關(guān)測試，測試結(jié)果驗(yàn)證算法的有效性。

XML；C程序；標(biāo)記串提取算法

0　引言

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

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

1　基于XML的標(biāo)記串提取算法設(shè)計(jì)

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

1.1常見抄襲方式

通過近五年講授《程序設(shè)計(jì)基礎(chǔ)》課程的經(jīng)驗(yàn)和對五百多份學(xué)生編程作業(yè)的仔細(xì)研究和總結(jié)，把結(jié)構(gòu)體和for循環(huán)的常見抄襲方式分別總結(jié)如下：

①結(jié)構(gòu)體：重命名結(jié)構(gòu)體名和結(jié)構(gòu)體變量名；結(jié)構(gòu)體變量的直接定義與間接定義互換；改變結(jié)構(gòu)體成員的數(shù)據(jù)類型；結(jié)構(gòu)體成員的標(biāo)識符重命名；拆分結(jié)構(gòu)體變量定義和初始化賦值；重排序結(jié)構(gòu)體成員列表；調(diào)整結(jié)構(gòu)體定義語句或結(jié)構(gòu)體變量定義語句的位置；改變結(jié)構(gòu)體定義語句的書寫格式。與結(jié)構(gòu)體相關(guān)的部分抄襲方式如圖1所示。

圖1　結(jié)構(gòu)體抄襲方式實(shí)例

②for循環(huán)：for、while、do…while之間相互替換；將for語句中的第一個(gè)表達(dá)式放到for語句的前面；將for語句中的第三個(gè)表達(dá)式放到for語句循環(huán)體的最后面；重命名條件判斷語句中的標(biāo)識符；增加冗余的條件判斷語句；循環(huán)體內(nèi)部語句的重排序；語句的等價(jià)替換，如把i++變?yōu)閕=i+1或者把sum=sum+i變?yōu)閟um+=i；增加冗余語句；調(diào)整循環(huán)結(jié)構(gòu)的位置。與for循環(huán)相關(guān)的部分抄襲方式如圖2所示。

圖2　for循環(huán)抄襲方式實(shí)例

1.2結(jié)構(gòu)體轉(zhuǎn)化為XML文本的算法

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

圖3　structs函數(shù)的偽代碼

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

圖4　get_struct_name函數(shù)的偽代碼

1.3for循環(huán)轉(zhuǎn)化為XML文本的算法

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

圖5　get_for函數(shù)的偽代碼

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

圖6　get_for_condition函數(shù)的偽代碼

2　算法測試

為了證明本文設(shè)計(jì)的基于XML的標(biāo)記串提取算法的有效性，我們將以C程序的關(guān)鍵結(jié)構(gòu)為分類原則對標(biāo)記串提取算法進(jìn)行測試。

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

表1　測試用例表

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

圖7　測試實(shí)例

3　結(jié)語

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

［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］侯敏，劉東升.程序代碼抄襲檢測技術(shù)研究［J］.內(nèi)蒙古師范大學(xué)學(xué)報(bào)（自然科學(xué)漢文版），2007，36（6）：24-26.

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

［5］王繼遠(yuǎn).一種用于軟件作業(yè)評判系統(tǒng)的程序結(jié)構(gòu)分析算法的設(shè)計(jì)與實(shí)現(xiàn)［D］.北京郵電大學(xué)，2007.

［6］朱江.基于XML的程序設(shè)計(jì)自動批改的研究［D］.湘潭：湘潭大學(xué)，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-），女，四川都江堰，碩士研究生，研究方向?yàn)橛?jì)算機(jī)輔助教學(xué)、算法設(shè)計(jì)與分析

2016-05-26

2016-07-20