朱利龍

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

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

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

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

1 特征提取

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

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

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

2 距離編輯算法

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

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

Dim mA（） As Byte，mB（） As Byte 模塊級變量，存放語句單元

計算編輯距離函數(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

計算最小值函數(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 源程序比較過程

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

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

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

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

4 總結(jié)

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

參考文獻：

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

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

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

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