相似度算法在源程序比較中的應(yīng)用

朱利龍

摘要：在計(jì)算機(jī)程序課的教學(xué)過(guò)程中，時(shí)常需要對(duì)學(xué)生所提交的源程序進(jìn)行檢查，特別是源程序的重復(fù)率檢查。純?nèi)斯?duì)比不但花費(fèi)時(shí)間長(zhǎng)，而且效率低下。因此，本文提出利用文本相似度算法解決源程序?qū)Ρ鹊姆椒?，并設(shè)計(jì)出相應(yīng)的源程序比較系統(tǒng)，來(lái)幫助老師從繁重的工作中解脫出來(lái)。

關(guān)鍵詞： 相似度；距離編輯算法；源程序?qū)Ρ?/p>

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

源程序?qū)Ρ确治鍪且粋€(gè)復(fù)雜的過(guò)程，不僅需要考慮實(shí)用性和考慮準(zhǔn)確性，而且還要兼顧運(yùn)行效率等問(wèn)題。在程序上機(jī)課的過(guò)程性考核中，很多同學(xué)提交的程序源代碼之間重復(fù)率很高。本文借助計(jì)算機(jī)實(shí)現(xiàn)源程序的自動(dòng)對(duì)比，不但可以降低勞動(dòng)強(qiáng)度，提高工作效率，而且可以減少誤判的可能性，進(jìn)一步保證源程序?qū)Ρ冉Y(jié)果的正確性。

1 特征提取

要獲取源程序重復(fù)率，判斷是否抄襲程度，可以通過(guò)計(jì)算源程序的相似率來(lái)代替。相似率越高說(shuō)明源程序重復(fù)部分越多，學(xué)生抄襲的可能性越高。要計(jì)算代碼的相似率，就得提取源代碼的有關(guān)特征參數(shù)。

根據(jù)源程序塊粒度大小不同，可以利用源程序中諸如換行符之類的分割符來(lái)分解成程序語(yǔ)句，分解得到的每一部分稱為一個(gè)程序塊。源程序塊的選擇將在很大程度上影響程序的效率，要比較源程序部分復(fù)制，就必須減少源程序塊的長(zhǎng)度。本文將每一個(gè)語(yǔ)句看成一個(gè)源程序塊，即粒度大小為一條語(yǔ)句。于是，源程序就被分解為語(yǔ)句集合，源程序的相似程度便可以由語(yǔ)句的相似率來(lái)計(jì)算。因此，對(duì)于源程序的對(duì)比，選擇程序語(yǔ)句作為源程序的對(duì)比粒度塊是具有可行性的。

本文系統(tǒng)采用的是距離編輯算法，利用字符串的模式匹配實(shí)現(xiàn)對(duì)源程序相似度進(jìn)行判斷。把兩篇源程序進(jìn)行全文對(duì)比得出相似度；得出相似度后，根據(jù)源程序分隔符把兩源程序分割成逐條語(yǔ)句的，然后對(duì)這些語(yǔ)句進(jìn)行一一對(duì)比，得出語(yǔ)句的相似度；比較出來(lái)的超過(guò)語(yǔ)句的相似度的語(yǔ)句稱為相似句，把相似句對(duì)應(yīng)的原句進(jìn)行紅色標(biāo)記；統(tǒng)計(jì)出相似句對(duì)應(yīng)原句占原源程序的比例，在比較中可以通過(guò)紅色顯示相同。

2 距離編輯算法

距離編輯算法，簡(jiǎn)稱為L(zhǎng)D算法。該方法主要從源程序中選取一些源程序塊，利用LD算法比較兩源程序塊字符串的相似性，由此得出比較子串相似度（即子串間的距離）。兩個(gè)字符串距離就是一個(gè)字符串轉(zhuǎn)換成另一個(gè)字符串過(guò)程中，進(jìn)行添加、刪除、修改等基本操作的次數(shù)，將源程序的語(yǔ)句作為字符串，借助LD算法對(duì)比代碼間的距離，然后計(jì)算取其占代碼長(zhǎng)度的比例作為判斷代碼重復(fù)率，從而即可得到學(xué)生源程序的抄襲程度。如果兩個(gè)源程序字符串的距離越大，就說(shuō)明他們?cè)讲煌?/p>

該算法對(duì)兩個(gè)字符串（句子或整篇源程序）進(jìn)行對(duì)比，得出兩個(gè)字符串之間的“距離”，然后根據(jù)相似度計(jì)算公式計(jì)算出兩個(gè)字符串之間的相似度。下面給出了在Visual Basic編程環(huán)境下，利用遞歸法實(shí)現(xiàn)的算法代碼。

Dim mA（） As Byte，mB（） As Byte 模塊級(jí)變量，存放語(yǔ)句單元

計(jì)算編輯距離函數(shù)LD

Public Function LD（ByVal A As String，ByVal B As String） As Integer

mA = StrConv（A，vbFromUnicode） ：mB = StrConv（B，vbFromUnicode）

ReDim L（Len（A），Len（B）） As Integer

For i = 1 To Len（A）

L（i， 0） = i

Next

For j = 1 To Len（B）

L（0， j） = j

Next

For I = 1 To Len（A）

For j = 1 To Len（B）

If mA（I - 1） = mB（j - 1） Then

L（I， j） = L（I - 1， j - 1）

Else

L（I， j） = Min（L（I - 1， j - 1）， L（I - 1， j）， L（I， j - 1）） + 1

End If

Next

Next

LD = L（Len（A）， Len（B））

End Function

計(jì)算最小值函數(shù)Min

Public Function Min（ByVal A As Integer，ByVal B As Integer，ByVal C As Integer） As Integer

Min = IIF（A > B，A，B） ：Min = IIF（Min < C，Min，C）

End Function

3 源程序比較過(guò)程

在上述算法的基礎(chǔ)上，本文所設(shè)計(jì)的源程序比較系統(tǒng)主要有三個(gè)步驟，該系統(tǒng)所對(duì)應(yīng)的流程圖見(jiàn)圖1。

1）從存放源程序的數(shù)據(jù)庫(kù)里取出程序代碼，構(gòu)成源程序集合。學(xué)生提交的程序代碼都會(huì)被提煉出主要部分匯總到程序數(shù)據(jù)庫(kù)中。在后期進(jìn)行代碼對(duì)比時(shí)，就可以直接從數(shù)據(jù)庫(kù)中讀取學(xué)生提交的源代碼，甚至可以用于年級(jí)之間學(xué)生編程能力的縱向比較。

2）分割源程序并從中提取特征參數(shù)。本文使用語(yǔ)句結(jié)束標(biāo)記或其他代碼間隔符（如“空格”“換行”等）作為語(yǔ)句的天然分割符，刨除源程序中影響對(duì)比操作的無(wú)用代碼，即程序通用框架部分，例如集成開(kāi)發(fā)工具產(chǎn)生的代碼，只保留學(xué)生自己編寫(xiě)的主要代碼，然后借助系統(tǒng)提取相關(guān)的特征參數(shù)。

3）計(jì)算源程序相似度。從上一步分割得到的語(yǔ)句集合，計(jì)算出語(yǔ)句之間的編輯距離，其占語(yǔ)句長(zhǎng)度的百分比即為語(yǔ)句相似度；將所有語(yǔ)句間的編輯距離累加作為源程序間的編輯距離，其占源程序代碼長(zhǎng)度的百分比就是源程序間的相似度；若相似度量值大于教師所給定的臨界值，說(shuō)明程序代碼間的重復(fù)率過(guò)高，學(xué)生存在復(fù)制抄襲的可能，并通過(guò)顏色標(biāo)示出重復(fù)部分，從而達(dá)到系統(tǒng)自動(dòng)對(duì)比源程序的目的，而且可以提高學(xué)生的自律性和積極性。

4 總結(jié)

本文所設(shè)計(jì)的源程序比較系統(tǒng)，在程序類課程的教學(xué)過(guò)程中，已經(jīng)作為該類課程過(guò)程考核手段之一，不僅幫助老師從繁重的工作中解脫出來(lái)，而且提高了學(xué)生的學(xué)習(xí)積極性。在今后將逐步引入數(shù)據(jù)挖掘的處理過(guò)程，以便可以實(shí)現(xiàn)程序類課程教學(xué)效果的縱向?qū)Ρ?，從而更好促進(jìn)程序類教學(xué)。

參考文獻(xiàn)：

[1] 李俊民，趙東. 零基礎(chǔ)學(xué)Visual Basic[M].北京：機(jī)械工業(yè)出版社，2010.

[2] 劉宏哲. 文本語(yǔ)義相似度計(jì)算[M]. 北京：電子工業(yè)出版，2014.

[3] 張憲超. 數(shù)據(jù)結(jié)構(gòu)、算法及應(yīng)用[M].北京：科學(xué)出版社，2012.

[4] 程海濤，王俏，盧亮，等.探索Visual Basic教學(xué)方法改革[J].科技信息，2011（12）：225.