錢 程，謝春麗，王夢琦，權(quán) 雷

（1.江蘇師范大學(xué)智慧教育學(xué)院；2.江蘇師范大學(xué)計算機科學(xué)與技術(shù)學(xué)院，江蘇徐州 221116）

0 引言

隨著Github、StackOverflow 等開源代碼平臺的開放，這些開源代碼的直接獲取不可避免地引發(fā)了代碼剽竊，無形中增加了程序漏洞的傳播。高校各種在線判題系統(tǒng)（On?line Judge，OJ）使用過程中，學(xué)生作業(yè)以源代碼形式提交到OJ 平臺，平臺在線自動完成評測，這種方式使得學(xué)生抄襲他人代碼現(xiàn)象泛濫［1］。事實上，商用軟件領(lǐng)域抄襲的現(xiàn)象也愈演愈烈［1］，造成了維護程序編寫者知識產(chǎn)權(quán)日漸困難的局面。因此，研究代碼克隆并評測代碼剽竊這一問題很有必要。文本相似度度量是解決該類問題的基礎(chǔ)手段，它也適用于其他領(lǐng)域，如文本分類［2］、信息檢索、自動代碼補充［3］等。相關(guān)文本相似度計算方法不斷被設(shè)計研究出來，比較常見的有N-gram、TF-IDF、LSA 等。

N-gram 模型注重詞數(shù)量特征，缺乏對語義的檢測［4］。武永亮等［5］提出的TF-IDF 模型通過計算詞頻權(quán)重來比較詞的重要性，但這種方法僅僅只針對文本統(tǒng)計信息，缺乏對詞義、結(jié)構(gòu)的計算。一些其他基于關(guān)鍵詞典的方法受詞典大小限制，需要大量詞匯；而基于編輯距離的方法由于應(yīng)用場景受限制，對長句的檢測、計算存在較大誤差［6］。

針對上述問題，本文選擇基于向量空間的模型，通過TF-IDF 和Word2vec 構(gòu)建模型。將該模型與基于N-Gram的模型進(jìn)行對比，以期盡可能考慮到文本相似度的語義因素，并對其計算結(jié)果進(jìn)行比較和分析。實驗結(jié)果表明，基于向量空間的模型在檢測C++源碼相似情況的效果要優(yōu)于基于詞的N-gram 模型。

1 相關(guān)工作

1.1 關(guān)鍵詞匹配方法

N-gram 是一種語言模型思想，廣泛應(yīng)用于語音識別、手寫體識別、拼寫糾錯等領(lǐng)域。這種思想基于一個假設(shè)：在一個句子中下一個詞的出現(xiàn)僅依賴于前面的一個或幾個詞，而與其他任何詞不相關(guān)（即隱含馬爾可夫模型中的假設(shè)）［7］。以“好好學(xué)習(xí)，天天”為例，當(dāng)出現(xiàn)該句子后，大部分人很容易就會接出之后的“向上”一詞，而不是其他的詞，這表明“向上”一詞的出現(xiàn)依賴于“好好學(xué)習(xí)，天天”的出現(xiàn)。

在N-gram 模型中，N 表示分解的句子中詞的數(shù)量，其中第N 個詞的出現(xiàn)只與前N-1 個詞有關(guān)，而與其他詞無關(guān)［8］。常用的N-gram模型有Bi-gram模型和Tri-gram模型。

（1）Bi-gram。即N=2 時的N-gram 模型（二元模型），指一個詞的出現(xiàn)只依賴于它前面出現(xiàn)的那一個詞，使用該模型對“我愛學(xué)習(xí)”這句話進(jìn)行分解可得：｛我，愛｝、｛愛，學(xué)｝、｛學(xué)，習(xí)｝。

（2）Tri-gram。即N=3 時的N-gram 模型（三元模型），指一個詞的出現(xiàn)只依賴于它前面出現(xiàn)的那兩個詞，使用該模型對“我愛學(xué)習(xí)”這句話進(jìn)行分解可得：｛我，愛，學(xué)｝、｛愛，學(xué)，習(xí)｝。

如何使用N-gram 模型對代碼進(jìn)行相似度計算就要引入N-gram 距離概念。N-gram 距離通過衡量兩個句子之間的差異來實現(xiàn)相似度計算。按長度N 對原句進(jìn)行分詞處理，得到所有長度為N（單詞數(shù)量為N）的字符串。對于兩個句子S 和T，通過計算他們公共子串的數(shù)量得到兩者的相似度。N-gram 距離計算公式如下：

1.2 向量空間方法

本文的向量空間指將源碼文本向量化，一般通過對文本分詞、去停用詞、編碼、向量化這幾個步驟完成對文本中詞的向量化，再通過權(quán)重疊加法或模型法獲取文本（句子、段落、文章）的向量，這實際上是一種將源碼文本表示成低維、稠密、實數(shù)向量的方法。

1.2.1 TF-IDF 方法

TF-IDF 是一種統(tǒng)計方法，用以評估某個字詞對于一個文件集或一個文件的重要程度，其思想是：在一篇文章中，某個詞的重要性與該詞在這篇文章中出現(xiàn)的次數(shù)正相關(guān)，與語料庫中出現(xiàn)該詞的文章數(shù)負(fù)相關(guān)。

TF（Term Frequency）：詞頻，指一個詞在文章中出現(xiàn)的頻率，表示這個詞與該文章的相關(guān)性。這個數(shù)字是對詞數(shù)的歸一化，以防止它偏向長文件。TF 值計算公式如下：

IDF（Inverse Document Frequency）：逆向文件詞頻，表示一個詞語出現(xiàn)的普遍程度。一個詞的IDF 值可以通過文章總數(shù)除以包含該詞的文章數(shù)，再將得到的商取以10 為底的對數(shù)。但是可能存在沒有任何一篇文章包含這個詞的情況，這會導(dǎo)致分母為0，為了防止該情況發(fā)生，分母通常會加上1。最終的IDF 值計算公式如下：

一篇文章中某個詞的重要程度，可以標(biāo)記為詞頻和逆向文件詞頻的乘積，某個詞對文章的重要性越高，它的TFIDF 值也就越大，就認(rèn)為其具有很好的類別區(qū)分能力。TFIDF 值計算公式如下：

余弦相似度通過測量兩個向量夾角的余弦值確定兩個向量大致指向是否相同從而來度量它們之間的相似性，該結(jié)果與向量的長度無關(guān)，與向量的指向相關(guān)。余弦相似度常用于高維正空間，例如在信息檢索中，每個詞項被賦予不同的維度，而一個維度由一個向量表示，其各個維度上的值對應(yīng)于該詞項在文檔中出現(xiàn)的頻率。余弦相似度因此可以給出兩篇文檔在其主題方面的相似度，計算公式如下：

1.2.2 基于Word2vec 的代碼相似性

Word2vec 是2013 年Google 研發(fā)的一款用于訓(xùn)練詞向量的工具，它將詞語用向量表示，然后映射到向量空間進(jìn)行處理，其核心架構(gòu)主要有CBOW 模型和Skip-gram 模型［9-10］。本文采用CBOW 模型，該模型特點是可以通過上下文來預(yù)測當(dāng)前單詞，如圖1 所示。

2 模型構(gòu)建

2.1 基于TF-IDF 的模型

本文結(jié)合TF-IDF 模型構(gòu)建基于詞向量的模型。模型通過數(shù)據(jù)預(yù)處理器，將送入的源碼集處理成一個文本矩陣，矩陣每一行代表一篇源碼，一行中任一元素代表一個詞。隨后將文本矩陣送入TF-IDF 生成器，輸出一個TFIDF 矩陣，其中每一行同樣代表一篇源碼，一行中的每一個元素為詞的TF-IDF 值。最后送入相似度矩陣生成器得到一個相似度矩陣，每一行即為一篇源碼的文本向量。模型結(jié)構(gòu)如圖2 所示。

Fig.1 CBOW model圖1 CBOW 模型

Fig.2 TF-IDF model圖2 TF-IDF 模型

2.2 基于Word2vec 的模型

Word2Vec 將每一個詞都映射成向量，同時不斷訓(xùn)練向量，從而提取出詞與詞之間的語義特征［11］，最后根據(jù)某些規(guī)則計算出詞向量的文本向量。本文將數(shù)據(jù)集送入gensim庫中的Word2vec 模型，獲取所有詞的詞向量。通過對每一篇源碼進(jìn)行分詞、去停用詞處理后對所有詞的詞向量求和取平均，從而獲得每一篇代碼的向量，最后通過計算向量間的余弦值獲得源碼與源碼之間的相似度（即余弦相似度）。模型結(jié)構(gòu)如圖3 所示。

Fig.3 Word2vec model圖3 Word2vec 模型

3 實驗結(jié)果與分析

3.1 數(shù)據(jù)集

本文將江蘇師范大學(xué)教學(xué)科研輔助平臺（http：//cstlab.jsnu.edu.cn）學(xué)生提交的課程作業(yè)作為數(shù)據(jù)集，包括35 個種類共905 篇C++源碼，每個種類都代表一種功能實現(xiàn)（包含但不止于計算最大公約數(shù)、歐幾里得算法、冒泡排序），每個種類的文件夾內(nèi)包含數(shù)量不等的源代碼文件。

3.2 實驗過程

3.2.1 TF-IDF 實驗過程

圖4 為該實驗的實驗過程，第一個步驟是數(shù)據(jù)預(yù)處理，首先對所有C++源碼使用jieba 庫進(jìn)行分詞處理，然后保留需要的詞，本文使用兩種方法選擇需要保留的詞。實際上，這兩種方法正好是相反的：

Fig.4 Experiment process of TF-IDF圖4 TF-IDF 實驗過程

（1）去停用詞，去除如‘return’、‘define’、‘include’、‘main’、‘int’、‘bool’、‘｛’、‘｝’、‘；’等這類詞，保留以外的詞。

（2）在閉區(qū)間內(nèi)選擇需要保留下來的詞，僅保留以下詞，而去除其他詞：

步驟（2）生成的文本向量，將每一篇源碼TF-IDF 值相應(yīng)設(shè)置為特征值，其余位置設(shè)置為0，這樣形成一種類似于one-hot 編碼的編碼方式，為每一篇源碼生成專屬向量。

（3）將已生成的文本向量利用余弦相似度計算出任何兩篇源碼的相似度。

該實驗的向量矩陣生成的部分偽代碼如下：

3.2.2 Word2vec 實驗過程

該實驗步驟分為：數(shù)據(jù)準(zhǔn)備、模型構(gòu)建和模型評估三大步驟，如圖5 所示。

Fig.5 Experiment process of Word2vec圖5 Word2vec 實驗過程

讀取數(shù)據(jù)集中所有的數(shù)據(jù)，然后將其存入一個列表，隨后將這個列表送入第二個過程中——模型構(gòu)建，首先設(shè)置好模型訓(xùn)練的參數(shù)，然后開始構(gòu)建模型。在第三個過程中，讀取測試數(shù)據(jù)的源碼內(nèi)容進(jìn)行分詞處理，并通過模型獲取分詞后詞的向量，將這些向量求和取平均處理后得到源碼的特征向量，最后計算源碼向量間的相似度并計算模型的F1-score。完成一次上述操作后，返回第二個過程，對模型構(gòu)建的參數(shù)進(jìn)行修改，重新構(gòu)建模型，計算F1-score值。

計算兩篇源碼之間相似度的部分偽代碼，輸入值的前5 項皆為模型參數(shù)，最后兩項為需要計算相似度的兩篇源碼，輸出內(nèi)容即為兩者的相似度。

3.3 模型評判

閾值是一個分界線，用于判斷兩篇源碼是否可以判定為相似：

（1）在N-gram 方法下，源碼間的相似程度與N-gram 距離反相關(guān)，所以當(dāng)相似度小于或等于閾值時，兩篇源碼相似；反之則兩者不相似。

（2）在TF-IDF 和Word2vec 方法下，源碼間的相似程度與余弦相似度正相關(guān)，因此當(dāng)相似度大于或等于閾值時，認(rèn)為兩篇源碼相似；反之則認(rèn)為兩者不相似。

確定任意兩篇源碼是否為相似的標(biāo)記，選擇實現(xiàn)同一功能（即在同一文件夾下的）源碼標(biāo)記為相似，標(biāo)記為1；實現(xiàn)不同功能（即在不同文件夾下的）源碼標(biāo)記為不相似，標(biāo)記為0。

每一篇源碼與數(shù)據(jù)集中所有源碼一一進(jìn)行相似度計算，得到一個由相似度構(gòu)成的二維矩陣。通過計算不同閾值下的F1-score 值并獲取其中最大的F1-score 值然后根據(jù)該值來衡量一個模型相似度計算效果的優(yōu)劣。F1-score 值取值范圍為0 到1，數(shù)值越大認(rèn)為模型的計算效果越佳。

F1-score 計算公式如下：

3.4 實驗結(jié)果

表1 為N-gram 模型不同N 值的情況，它顯示了模型在何閾值下能得到最大F1-score 值以及最大F1-score 值的具體數(shù)值。結(jié)果顯示當(dāng)N=2 時，該模型可以得到最大的準(zhǔn)確值、召回值以及F1-score 值，具體數(shù)值分別為56.06%、69.67%和62.12%。

Tabel 1 Experimental result of N-gram model表1 N-gram 模型試驗結(jié)果

表2 為選擇保留詞的兩種不同方式下TF-IDF 模型的實驗結(jié)果，結(jié)果表明在閉區(qū)間內(nèi)選擇保留詞能夠得到更高的F1-score 值和更高的準(zhǔn)確度、召回值。從原理上分析可知，選擇閉區(qū)間保留了源碼的結(jié)構(gòu)信息，而開區(qū)間僅保留語義、單詞，并沒有保留結(jié)構(gòu)信息。

Table 2 Experimental result of TF-IDF model表2 TF-IDF 模型試驗結(jié)果

圖6 展示了Word2vec 模型不同參數(shù)下的實驗結(jié)果，其參數(shù)數(shù)值從左往右分別是workers、size、sample 參數(shù)。在實驗中，將參數(shù)min_count 和參數(shù)window 分別設(shè)置為1 和10除需要測試的參數(shù)和指定的參數(shù)之外，其他參數(shù)均為默認(rèn)值，實驗得到最高的F1-score 值為0.658 8。

Fig.6 Results of Word2vec models with different parameters圖6 Word2vec 模型參數(shù)下的數(shù)據(jù)值

根據(jù)以上數(shù)據(jù)，可以得到N-gram、TF-IDF、Word2vec三個模型的最大F1-score 分別為0.621 2、0.775 9、0.658 8。

從方法原理上看，N-gram 方法只考慮到了詞數(shù)量上的關(guān)系，而Word2vec 和TF-IDF 在考慮詞數(shù)量的基礎(chǔ)上還考慮到了結(jié)構(gòu)、語義。因此基于空間向量的方法能夠考慮的范圍更廣，對于C++代碼相似檢測更有效。實驗結(jié)果表明，基于空間向量的方法在檢測相似度方面效果確實比基于關(guān)鍵詞的方法好。

4 結(jié)語

本文采用基于關(guān)鍵詞的N-gram 方法、基于向量空間并通過結(jié)合TF-IDF 和Word2vec 的方法完成對C++源碼的相似度計算。反復(fù)實驗后的結(jié)果表明，基于空間向量的方法可以更加全面、準(zhǔn)確反映代碼之間的結(jié)構(gòu)關(guān)系、語義關(guān)系。但實驗還存在以下缺陷：①模型準(zhǔn)確度不是很高；②各模型整體結(jié)構(gòu)單一；③在識別粒度更小的結(jié)構(gòu)上存在不足。

對于相似度計算，后續(xù)將在關(guān)鍵詞、語義、語法、結(jié)構(gòu)等方面設(shè)計更全面的檢測方法。同時，使用基于CNN 的方法對C++源碼進(jìn)行相似度計算，以期解決相應(yīng)不足并取得更好的效果。