陳秀芳 岳江寧 渠艷琪 蔡旺 王旭

摘要：代碼相似度檢測(cè)研究是軟件工程領(lǐng)域許多很重要的任務(wù)的基礎(chǔ)操作，而現(xiàn)有的代碼相似度檢測(cè)方法普遍存在著緯度高、計(jì)算復(fù)雜和執(zhí)行成本高的問(wèn)題。為了解決這些問(wèn)題，本文提出了局部敏感哈希（Locality Sensitive Hash，LSH）算法：它能夠?qū)Υ罅繑?shù)據(jù)進(jìn)行最近鄰快速查找，挖掘出相似的數(shù)據(jù)，從而實(shí)現(xiàn)代碼相似度的檢測(cè)研究。實(shí)驗(yàn)結(jié)果表明：LSH算法可以對(duì)海量數(shù)據(jù)進(jìn)行處理，對(duì)與代碼相似度的檢測(cè)檢測(cè)有很大的好處，本文還將LSH算法與其他檢測(cè)方法進(jìn)行了比較，實(shí)驗(yàn)結(jié)果表明LSH算法優(yōu)于Word2vec檢測(cè)方法。

關(guān)鍵詞：代碼相似度;局部敏感哈希;代碼分類(lèi);代碼檢測(cè)

1簡(jiǎn)介

代碼相似性檢測(cè)是用來(lái)衡量?jī)蓚€(gè)代碼片段之間的相似程度。度量代碼相似性是許多軟件工程任務(wù)的前端基礎(chǔ)。研究代碼相似性能夠提升代碼質(zhì)量，這對(duì)許多軟件工程的開(kāi)發(fā)有很大的研究?jī)r(jià)值。

現(xiàn)存的代碼相似性檢測(cè)方法可以分成三類(lèi)：屬性計(jì)數(shù)方法、結(jié)構(gòu)度量技術(shù)和深度學(xué)習(xí)技術(shù)。屬性計(jì)數(shù)方法的基本原理是統(tǒng)計(jì)源程序中的某些屬性計(jì)數(shù)作為相似性判斷的依據(jù)。如：Grier[1]等人分別使用了20和24種統(tǒng)計(jì)特征來(lái)檢測(cè)代碼的相似性。結(jié)構(gòu)度量技術(shù)主要是對(duì)源程序進(jìn)行結(jié)構(gòu)分析以及執(zhí)行程序流程。具有代表性的研究有：北京郵電大學(xué)[2]采用了基于XML方法對(duì)結(jié)構(gòu)度量技術(shù)進(jìn)行相似度計(jì)算。深度學(xué)習(xí)技術(shù)是學(xué)習(xí)樣本數(shù)據(jù)的內(nèi)在規(guī)律和表示層次。如：White[3]等人提出的基于深度學(xué)習(xí)技術(shù)的代碼相似性檢測(cè)方法。這三種技術(shù)既有優(yōu)點(diǎn)也有缺點(diǎn)：屬性技術(shù)方法語(yǔ)法結(jié)構(gòu)容易被人所理解，實(shí)現(xiàn)簡(jiǎn)單，但是精確率比較差;結(jié)構(gòu)度量技術(shù)對(duì)于語(yǔ)法相似性檢測(cè)有較好效果但是忽略了語(yǔ)義層面的信息;深度學(xué)習(xí)技術(shù)方法性能很好但是需要很大的數(shù)據(jù)集，并且受數(shù)據(jù)集、參數(shù)的好壞影響，具有不穩(wěn)定性和不可解釋性。

針對(duì)上面提出的問(wèn)題以及現(xiàn)有的方法，我們提出使用LSH算法去更好的解決問(wèn)題，LSH能夠?qū)⒑Ａ繑?shù)據(jù)進(jìn)行清洗與降維用于解決海量數(shù)據(jù)與高維空間的困難，將K最近鄰（K-NearestNeighbor，KNN）分類(lèi)算法的時(shí)間復(fù)雜度縮減到亞線性。實(shí)驗(yàn)結(jié)果表明：LSH算法通過(guò)降維和過(guò)濾操作極大地縮短了查詢計(jì)算時(shí)間，提高了效率。

2相關(guān)工作

2.1代碼相似度檢測(cè)方法

在現(xiàn)有技術(shù)中，SourcererCC[4]是基于token的代碼克隆檢測(cè)器， 它可以在不同的粒度級(jí)別和不同語(yǔ)言上進(jìn)行檢測(cè)。但它只考慮代碼片段在詞匯層次上的相似性，忽略了語(yǔ)法信息。Word2vec[5]是一個(gè)將單詞轉(zhuǎn)換成詞向量的工具，它的模型以大規(guī)模語(yǔ)料庫(kù)作為輸入，通過(guò)模型的訓(xùn)練后映射到一個(gè)幾百維度的向量空間中。這些都是現(xiàn)存的在代碼相似性方面做的較好的方法，其余不再介紹。在代碼相似度研究領(lǐng)域，LSH算法一開(kāi)始是用來(lái)做引擎的，現(xiàn)在我們將它用做代碼相似度的檢測(cè)。在使用LSH算法之前，首先要對(duì)源程序進(jìn)行代碼表征，現(xiàn)有的代碼表征的方法主要有：基于文本、基于Token、基于AST樹(shù)和基于圖的表征代碼發(fā)方法。具體方法可自行查詢。

3基于LSH的代碼相似度檢測(cè)模型

為了能夠?qū)^大數(shù)據(jù)集進(jìn)行代碼相似度的檢測(cè)，本文提出了基于LSH算法的模型。如圖3-1所示，該模型主要由數(shù)據(jù)預(yù)處理、數(shù)據(jù)特征向量化和LSH算法三部分組成。

在此過(guò)程中需要將讀取的數(shù)據(jù)進(jìn)行初步處理，具體步驟如下：第一步數(shù)據(jù)抽?。簩?duì)指定文件中的代碼進(jìn)行讀取，從中提取出數(shù)據(jù)的實(shí)體和關(guān)系，經(jīng)過(guò)關(guān)聯(lián)和聚合之后采用統(tǒng)一定義的結(jié)構(gòu)來(lái)存儲(chǔ)這些數(shù)據(jù)。第二步數(shù)據(jù)清理：通過(guò)填寫(xiě)缺失值，光滑噪聲數(shù)據(jù)，識(shí)別或刪除離群點(diǎn)，并解決不一致性“清理”數(shù)據(jù)。本文采用了nltk（Natural Language Toolkit）自然語(yǔ)言處理工具庫(kù)中的word_tokenize進(jìn)行分詞。

本文為了進(jìn)行詞集的向量化表現(xiàn)采用了one-hot的詞袋模型，將進(jìn)行分詞之后獲取到的詞典數(shù)據(jù)集進(jìn)行特征詞提取，生成一個(gè)詞典。用該詞在代碼中出現(xiàn)的次數(shù)去表示所出現(xiàn)的頻率，分別為1或0。如上過(guò)程在數(shù)據(jù)特征向量化模型中得到每篇代碼的詞向量之后，就可以送入到LSH模型中進(jìn)行下一步計(jì)算。

3.1 LSH算法

將提取出的特征向量進(jìn)行局部敏感哈希處理，使得在一個(gè)大的原始數(shù)據(jù)集合內(nèi)查找相似特征向量的問(wèn)題轉(zhuǎn)化為在一個(gè)小集合內(nèi)查找相似特征向量的問(wèn)題，極大降低了時(shí)間復(fù)雜度。

定義1 局部敏感哈希。給定一族哈希函數(shù)H，H是一個(gè)從歐式空間S到哈希編碼空間U的映射。對(duì)于H中的函數(shù)h，若都滿足以下條件，則稱此哈希函數(shù)是敏感的，其中為敏感散列函數(shù)。

（1）如果，那么

（2）如果，那么

其中，表示兩個(gè)具有多維屬性的數(shù)據(jù)對(duì)象，為2個(gè)對(duì)象的相異程度。

代碼相似度檢測(cè)過(guò)程中的LSH算法偽代碼如下所示。

算法1?LSH算法：其功能是將原始高維空間中的點(diǎn)映射到一個(gè)或多個(gè)哈希表中的不同位置，該術(shù)語(yǔ)位置稱為桶。它的映射原理是：在高維空間中非常接近的點(diǎn)將以高概率映射到同一哈希桶上。

1： function LSH（V ： vectors， r ： distance， p1 ： prob）： rcANs

2：N←?; LSH（V，r ， p1）

3：repeatpick a ν ∈ V

4：rcAN ←queryLSH（ν）

5：if rcAN > 1 then

6：N ←N ∪ {rcAN＼Un∈Nn}

7：end if

8：V ←V＼rcAN

9：until v =?

10：return PostProcessing（N）

11： end function

4實(shí)驗(yàn)

在本節(jié)中，我們?cè)谡鎸?shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)并報(bào)告結(jié)果。實(shí)驗(yàn)旨在檢測(cè)LSH模型在中小型數(shù)據(jù)集上的效果。Word2vec根據(jù)上下文進(jìn)行訓(xùn)練后的詞向量可以使用上下文信息來(lái)判斷并找到具有類(lèi)似含義的詞語(yǔ)，用該結(jié)果對(duì)文本語(yǔ)義上的相似度進(jìn)行一定的度量，且采用與LSH詞向量化方法原理相同的數(shù)據(jù)處理方法。本文是將基于LSH算法的代碼相似度實(shí)驗(yàn)和基于Word2Vec算法的代碼相似度實(shí)驗(yàn)進(jìn)行比較。我們所有的LSH實(shí)驗(yàn)都是在I5CPU服務(wù)器上完成的。

4.1實(shí)驗(yàn)設(shè)置

4.1.1數(shù)據(jù)準(zhǔn)備

我們?cè)趦蓚€(gè)真實(shí)數(shù)據(jù)集下進(jìn)行實(shí)驗(yàn)：OJ系統(tǒng)的OJClone（C++_DATA）和網(wǎng)絡(luò)上搜集整合的數(shù)據(jù)集（C_DATA）。

在數(shù)據(jù)預(yù)處理的過(guò)程中，我們先對(duì)代碼中容易引起歧義的字符進(jìn)行清除，去除空白、停用詞等，保證代碼內(nèi)容不引起歧義;并將代碼中出現(xiàn)的特征詞訓(xùn)練為對(duì)應(yīng)的詞向量，以便用于LSH模型的函數(shù)輸入和查詢;接著通過(guò)計(jì)算歐式距離得到各個(gè)相似度，歐式距離越小則越相似。表4-1列出了數(shù)據(jù)集的總體信息。

4.2性能評(píng)價(jià)指標(biāo)

代碼相似度計(jì)算屬于二分類(lèi)問(wèn)題，兩個(gè)代碼文件若被判斷為相似則分類(lèi)為1，不相似則被分類(lèi)為0。對(duì)于這樣的問(wèn)題，本文使用了sklearn庫(kù)中的metrics進(jìn)行計(jì)算，通過(guò)精確率、召回率、準(zhǔn)確率和F1值等參數(shù)來(lái)評(píng)價(jià)我們所使用的LSH模型的好壞。

4.3實(shí)驗(yàn)結(jié)果及分析

針對(duì)本文提出的模型，實(shí)施了兩個(gè)實(shí)驗(yàn)進(jìn)行驗(yàn)證：

（1）對(duì)LSH模型使用不同編程語(yǔ)言數(shù)據(jù)集來(lái)判斷模型的優(yōu)劣;

（2）將本文提出的LSH模型和其他的基準(zhǔn)模型Word2Vec模型進(jìn)行對(duì)比。

4.3.1 LSH模型的相似度計(jì)算實(shí)驗(yàn)

（1）模型的搭建

LSH算法的模型搭建主要利用了Lshash函數(shù)以及nltk語(yǔ)料庫(kù)進(jìn)行英文分詞實(shí)現(xiàn)。并采用了sklearn庫(kù)中model_selection來(lái)同時(shí)進(jìn)行訓(xùn)練集和測(cè)試集的劃分來(lái)進(jìn)行相似度計(jì)算。對(duì)于輸入的數(shù)據(jù)集數(shù)據(jù)采用隨機(jī)打亂的方式，訓(xùn)練集和測(cè)試集的比值為7：3。主要調(diào)節(jié)的參數(shù)為L(zhǎng)SH主函數(shù)初始化時(shí)的二進(jìn)制散列的長(zhǎng)度，程序中名稱為hash_size（最終選定值為64）。通過(guò)不斷調(diào)整hash_size參數(shù)和訓(xùn)練，直到模型的精確度最高、語(yǔ)義相似度的F1值最大為止。

為了研究hash_size對(duì)于該模型的Precision和Recall值的影響，本文選擇了不同的hash_size對(duì)C++_DATA數(shù)據(jù)集進(jìn)行了重復(fù)計(jì)算，得到的結(jié)果如下圖4-2所示：

（2）Word2Vec模型的相似度計(jì)算實(shí)驗(yàn)

本實(shí)驗(yàn)是針對(duì)本文提出的LSH模型實(shí)驗(yàn)所作的對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)過(guò)程中嚴(yán)格控制變量，最終通過(guò)LSH添加標(biāo)簽的LSH算法和直接進(jìn)行Word2Vec算法的相似度計(jì)算兩種方式在實(shí)驗(yàn)數(shù)據(jù)集上的優(yōu)劣來(lái)分析得出結(jié)論。

（3）實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)采用不同數(shù)據(jù)集重復(fù)進(jìn)行，通過(guò)四次實(shí)驗(yàn)的比對(duì)查看模型效率在數(shù)據(jù)量方面的變化以及在不同編程語(yǔ)言下的效果。LSH模型和Word2Vec模型在處理后的各個(gè)數(shù)據(jù)集上實(shí)驗(yàn)，評(píng)價(jià)指標(biāo)對(duì)比如下表4-2。

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

通過(guò)表4-2模型指標(biāo)數(shù)據(jù)，我們可以得出LSH模型在處理較大規(guī)模數(shù)據(jù)時(shí)效果比小規(guī)模數(shù)據(jù)效果要好;以及不論是數(shù)據(jù)量較大的C數(shù)據(jù)集還是數(shù)據(jù)量較小的C++數(shù)據(jù)集，LSH模型的準(zhǔn)確率和召回率都保持在0.9以上;此外，四組不同數(shù)據(jù)集下的數(shù)據(jù)可以看出，Word2Vec模型準(zhǔn)確率保持較為良好，但在召回率和F1值上顯示結(jié)果很差，這說(shuō)明Word2Vec模型對(duì)正樣本的識(shí)別能力弱以及模型不穩(wěn)健。

LSH模型在處理較大規(guī)模數(shù)據(jù)時(shí)效果優(yōu)于處理小規(guī)模數(shù)據(jù)，同時(shí)，LSH函數(shù)通過(guò)對(duì)詞向量再次降維處理，并且通過(guò)查詢的操作搜索相似對(duì)有利于代碼分類(lèi)結(jié)果的效率提升，在對(duì)于本實(shí)驗(yàn)給定的數(shù)據(jù)集下，LSH模型檢測(cè)代碼相似度明顯優(yōu)于Word2Vec模型，這充分體現(xiàn)了LSH本身的優(yōu)勢(shì)特點(diǎn)。

5結(jié)論

比較實(shí)驗(yàn)結(jié)果表明：LSH的模型在進(jìn)行較大規(guī)模的數(shù)據(jù)處理時(shí)依舊能夠保持一個(gè)不錯(cuò)的性能計(jì)算，與Word2Vec方法比較，多加一步局部敏感哈希算法的處理能使數(shù)據(jù)更加輕量化，更有利于進(jìn)行代碼相似度計(jì)算;與其他模型的比較，雖然LSH模型的表現(xiàn)更加突出，但缺乏對(duì)上下文語(yǔ)義的分析，得到結(jié)果為近似值，若想使LSH模型的代碼相似度檢測(cè)結(jié)果更加精準(zhǔn)，可以另外引入AST語(yǔ)法樹(shù)解析代碼語(yǔ)法。

參考文獻(xiàn)：

[1]Faidhi J A W，Robinson S K，An empirical approach for detecting program similarity and plagiarism within a university programming environment[J].Computer Education， 1987， 11（1）：11-19

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

[3]White M，Tufano M，Vendome C，et al.Deep Learning code fragments for code c-lone detection[C]//IEEE/ACM International Conference on Automated Software Engineerin-g.IEEE，2016.

[4]Hitesh Sajnani; VaibhavSaini; Jeffrey Svajlenko; Chanchal K. Roy; Lopes. SourcererCC.Software Enginee-ing.2016.PP 1157-1168

[5]陳丹華、王艷娜、周子力等人.《基于Word2Vec的WordNet詞語(yǔ)相似度計(jì)算研究》.計(jì)算機(jī)工程與應(yīng)用.CSCD.2021-03-16

基金項(xiàng)目：江蘇省高等學(xué)校大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計(jì)劃項(xiàng)目。

作者簡(jiǎn)介：陳秀芳（2000—），女，廣西玉林人，江蘇師范大學(xué)智慧教育學(xué)院本科在讀，研究方向：軟件工程。