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

鐘美

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

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

鐘美

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

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

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

0　引言

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

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

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

為了能更好地檢測(cè)學(xué)生程序代碼的抄襲和減輕教師的工作量，在研究和設(shè)計(jì)以XML為基礎(chǔ)的標(biāo)記串提取算法時(shí)針對(duì)不同的關(guān)鍵結(jié)構(gòu)設(shè)計(jì)出了不同的標(biāo)記串提取算法。C程序的關(guān)鍵結(jié)構(gòu)主要分為以下幾類(lèi)：變量定義，指針，結(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常見(jiàn)抄襲方式

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

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

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

②for循環(huán)：for、while、do…while之間相互替換；將for語(yǔ)句中的第一個(gè)表達(dá)式放到for語(yǔ)句的前面；將for語(yǔ)句中的第三個(gè)表達(dá)式放到for語(yǔ)句循環(huán)體的最后面；重命名條件判斷語(yǔ)句中的標(biāo)識(shí)符；增加冗余的條件判斷語(yǔ)句；循環(huán)體內(nèi)部語(yǔ)句的重排序；語(yǔ)句的等價(jià)替換，如把i++變?yōu)閕=i+1或者把sum=sum+i變?yōu)閟um+=i；增加冗余語(yǔ)句；調(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)體常見(jiàn)的抄襲方式，在這些信息的基礎(chǔ)上設(shè)計(jì)結(jié)構(gòu)體轉(zhuǎn)化為對(duì)應(yīng)的XML文本的算法。對(duì)于結(jié)構(gòu)體而言，我們主要提出它的結(jié)構(gòu)體名和具體的屬性項(xiàng)，屬性項(xiàng)的提取調(diào)用的是變量定義的提取方法。還需要注意的是當(dāng)結(jié)構(gòu)體變量采用直接定義法時(shí)，應(yīng)提取出結(jié)構(gòu)體變量定義語(yǔ)句，并使用變量定義的轉(zhuǎn)化方法把它轉(zhuǎn)化為對(duì)應(yīng)的XML文本。當(dāng)識(shí)別到程序代碼中的某行是結(jié)構(gòu)體定義的開(kāi)始行我們就調(diào)用名為structs的函數(shù)來(lái)實(shí)現(xiàn)轉(zhuǎn)換。structs函數(shù)中調(diào)用了一個(gè)名為CToXml的函數(shù)，它的主要功能是實(shí)現(xiàn)遞歸調(diào)用將不同關(guān)鍵結(jié)構(gòu)轉(zhuǎn)化為對(duì)應(yīng)的XML文本，此函數(shù)的實(shí)現(xiàn)只是簡(jiǎn)單使用字符串的匹配，在這就不給予詳細(xì)的介紹。structs函數(shù)的偽代碼如圖3所示。

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

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

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

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

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

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

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

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

2　算法測(cè)試

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

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

表1　測(cè)試用例表

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

圖7　測(cè)試實(shí)例

3　結(jié)語(yǔ)

上述測(cè)試結(jié)果表明，本文提出的基于XML的標(biāo)記串提取算法較好地實(shí)現(xiàn)了從C程序到XML文本的轉(zhuǎn)換，經(jīng)過(guò)30個(gè)程序的測(cè)試，轉(zhuǎn)換工作正常。但由于前期算法設(shè)計(jì)需要準(zhǔn)備的知識(shí)較多，花費(fèi)時(shí)間較長(zhǎng)，實(shí)現(xiàn)后的測(cè)試工作還不夠充分。今后我們將選擇更多的學(xué)生程序，來(lái)對(duì)算法進(jìn)行更全面的測(cè)試，完善存在的不足。基于XML的標(biāo)記串提取算法現(xiàn)在只適用于C程序，如需要還可以擴(kuò)展到C++、Java程序。基于XML的標(biāo)記串提取算法的實(shí)現(xiàn)不僅為檢測(cè)學(xué)生程序設(shè)計(jì)類(lèi)課程中的抄襲奠定了基礎(chǔ)，而且保證了抄襲檢測(cè)的準(zhǔn)確性和評(píng)價(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］侯敏，劉東升.程序代碼抄襲檢測(cè)技術(shù)研究［J］.內(nèi)蒙古師范大學(xué)學(xué)報(bào)（自然科學(xué)漢文版），2007，36（6）：24-26.

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

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

［6］朱江.基于XML的程序設(shè)計(jì)自動(dòng)批改的研究［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