基于詞嵌入的源碼相似度研究

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

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

0 引言

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

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

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

1 相關(guān)工作

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

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

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

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

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

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

1.2 向量空間方法

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

1.2.1 TF-IDF 方法

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

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

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

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

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

1.2.2 基于Word2vec 的代碼相似性

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

2 模型構(gòu)建

2.1 基于TF-IDF 的模型

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

Fig.1 CBOW model圖1 CBOW 模型

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

2.2 基于Word2vec 的模型

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

Fig.3 Word2vec model圖3 Word2vec 模型

3 實(shí)驗(yàn)結(jié)果與分析

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

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

3.2 實(shí)驗(yàn)過(guò)程

3.2.1 TF-IDF 實(shí)驗(yàn)過(guò)程

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

Fig.4 Experiment process of TF-IDF圖4 TF-IDF 實(shí)驗(yàn)過(guò)程

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

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

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

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

該實(shí)驗(yàn)的向量矩陣生成的部分偽代碼如下：

3.2.2 Word2vec 實(shí)驗(yàn)過(guò)程

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

Fig.5 Experiment process of Word2vec圖5 Word2vec 實(shí)驗(yàn)過(guò)程

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

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

3.3 模型評(píng)判

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

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

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

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

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

F1-score 計(jì)算公式如下：

3.4 實(shí)驗(yàn)結(jié)果

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

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

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

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

圖6 展示了Word2vec 模型不同參數(shù)下的實(shí)驗(yàn)結(jié)果，其參數(shù)數(shù)值從左往右分別是workers、size、sample 參數(shù)。在實(shí)驗(yàn)中，將參數(shù)min_count 和參數(shù)window 分別設(shè)置為1 和10除需要測(cè)試的參數(shù)和指定的參數(shù)之外，其他參數(shù)均為默認(rèn)值，實(shí)驗(yà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三個(gè)模型的最大F1-score 分別為0.621 2、0.775 9、0.658 8。

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

4 結(jié)語(yǔ)

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

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