基于向量表示的代碼搜索方法

慕江林，劉克劍*，林 晗

(1.西華大學(xué)計算機(jī)與軟件工程學(xué)院， 四川 成都 610039；2.成都理工大學(xué)管理科學(xué)學(xué)院， 四川 成都 610059)

軟件開發(fā)者基于Github、SourceForge等開源代碼倉庫上的可復(fù)用的基礎(chǔ)軟件包再次開發(fā)，可降低開發(fā)的時間和成本。開發(fā)者如果使用某些未在接口的使用方法中聲明的方法，需要在代碼搜索引擎搜索相關(guān)代碼片段。如何有效地幫助開發(fā)者從代碼庫中搜索與任務(wù)相關(guān)的代碼，成為代碼搜索[1-3]的研究方向之一。

用戶將少量關(guān)鍵詞輸入到代碼搜索引擎中，搜索引擎搜索相關(guān)代碼片段按照與關(guān)鍵詞的匹配度返回給用戶?；陂_發(fā)者的開發(fā)經(jīng)驗，搜索的關(guān)鍵詞為 “iterate a java hashmap”，搜索引擎應(yīng)該返回java有關(guān)于hashmap迭代的示例，如圖1所示。

已有的代碼搜索引擎，如Ohlh Code[4]、 Krugle[5]等，將用戶輸入關(guān)鍵詞當(dāng)作純文本，通過關(guān)鍵詞檢索類似的代碼片段。使用該方法搜索到的結(jié)果中只包含單一的關(guān)鍵詞，搜索結(jié)果與用戶期望相差較大。

近期的一些代碼搜索方法開始對代碼結(jié)構(gòu)和代碼語義分析。PARSEWeb將代碼抽象為方法調(diào)用序列，對方法調(diào)用序列聚類排序，查找相似使用模式的代碼片段[6]，是一種基于結(jié)構(gòu)的代碼搜索，準(zhǔn)確率不高。PRIME將代碼片段作為輸入，從結(jié)構(gòu)上對代碼片段進(jìn)行分析，尋找代碼片段的相似之處[7]，它忽略了代碼語義，在搜索結(jié)果上表現(xiàn)不佳。SWIM算法通過詞袋模型將自然語言查詢語句翻譯成API，再通過API生成代碼片段[8]。雖然該方法有效地利用了查詢的語義，但是基于詞袋模型的語義匹配結(jié)果不太理想，基于API生成的代碼片段，考慮了代碼結(jié)構(gòu)特性，忽略了代碼之間的語言特性。QECK 算法是一種利用群體知識來擴(kuò)充查詢的方法，其中群體知識是指Stack Overflow的問答信息[9]，該方法雖然擴(kuò)展了查詢文本，豐富了查詢的語義，但是忽略了代碼之間的語義，在代碼相似度比較上不足。本文提出了一種基于向量表示的代碼搜索方法——VRCS算法 (vector representation based code search)，它充分利用了代碼搜索關(guān)鍵詞—代碼之間語義和代碼—代碼之間的語義，在一定程度上提升了搜索的準(zhǔn)確率。

1 基于向量表示的代碼搜索方法

基于向量表示的代碼搜索方法能夠有效地利用搜索關(guān)鍵詞的語義實現(xiàn)相關(guān)代碼搜索。具體流程是：1)抽取代碼片段庫的代碼，形成以單個方法為單位的代碼片段，分割代碼片段為單個代碼詞和代碼符號，使用one-hot編碼分解得到的代碼詞和代碼符號，將編碼后的向量輸入到skip-gram模型中，得到向量組表示的代碼庫和一個訓(xùn)練好的skip-gram模型，其中，代碼庫的每段代碼片段都是由代碼詞向量組成的向量組；2)對搜索文本進(jìn)行預(yù)處理，去掉搜索文本中的修飾詞匯，如介詞、冠詞等，將預(yù)處理后的搜索文本關(guān)鍵詞作為代碼關(guān)鍵詞，利用第1步訓(xùn)練完成的skip-gram模型生成搜索關(guān)鍵詞上下文代碼片段向量組，其中向量組的每一個向量是搜索關(guān)鍵詞上下文代碼片段中的代碼詞的向量表示；3)將搜索關(guān)鍵詞上下文代碼片段向量組和待匹配代碼片段向量組分別輸入到編碼器中編碼，生成搜索關(guān)鍵詞上下文代碼片段隱向量和待匹配代碼片段的隱向量；4)利用余弦相似度計算搜索關(guān)鍵詞上下文代碼片段隱向量和待匹配代碼片段的隱向量的相似度，排序生成搜索結(jié)果，如圖2所示。

2 代碼詞嵌入表示

2.1 代碼片段詞嵌入表示

自然語言的詞嵌入表示有2大優(yōu)勢：能夠獲取單詞的上下文語境；有助于句子的編碼表示。由于程序語言具有與自然語言相似的語義特性[10]，以詞嵌入方式表示程序代碼，以便代碼關(guān)鍵詞的語義擴(kuò)充和從語義上對代碼相似程度的計算。

圖2 基于向量表示的代碼搜索方法概述

自然語言中符號常常被視為無用信息，代碼數(shù)據(jù)集中的代碼片段包含很多有助于代碼理解的符號信息，如圖1代碼片段，其中“+”表示拼接字符串，“?”表示方法調(diào)用，“：”表示對集合的遍歷等。為保存代碼中的符號對代碼片段語義的影響，將代碼中的符號按照詞進(jìn)行編碼。

為獲取skip-gram模型的輸入向量，抽取代碼片段庫的代碼，形成以單個方法為單位的代碼片段，分割代碼片段為單個代碼詞和代碼符號，使用one-hot編碼分解得到的代碼詞和代碼符號，將編碼后的向量輸入到skip-gram模型中。

通過訓(xùn)練skip-gram模型[11]，可以得到代碼詞的唯一編碼，skip-gram模型的結(jié)構(gòu)如圖3所示。

圖3 skip-gram模型

w(t)是一個向量，表示代碼詞或代碼符號的one-hot編碼，w(t-1)和w(t+1)分別表示代碼詞或代碼符號w(t)的上一個代碼詞或代碼符號的one-hot編碼和w(t)的下一個代碼詞或代碼符號的one-hot編碼。 采用無監(jiān)督學(xué)習(xí)訓(xùn)練skip-gram模型，目標(biāo)函數(shù)是最大化式(1)之和。

(1)

式中：c是滑動窗口的大?。籘是單詞序列的長度；p(wt+j|wt)用softmax函數(shù)定義條件概率，為

(2)

Vc={v1，v2，…，vkc}=

2.2 關(guān)鍵詞語義擴(kuò)展

用戶輸入的搜索文本中包含部分介詞等修飾詞匯，對代碼的匹配不具有重要意義，將此類詞匯去掉，得到純凈的語義相關(guān)的搜索關(guān)鍵詞。為了對關(guān)鍵詞的語義更好地補(bǔ)充，將上述清理后的關(guān)鍵詞視為代碼關(guān)鍵詞，使用上述訓(xùn)練的skip-gram模型生成搜索關(guān)鍵詞上下文代碼片段向量組，其中每一個向量是代碼關(guān)鍵詞的向量表示。例如，搜索的關(guān)鍵詞為 “iterate a java hashmap”，將其中的“a”去掉，留下“iterate java hashmap”，通過skip-gram模型擴(kuò)充得到的代碼片段，如圖4所示。

搜索關(guān)鍵詞上下文代碼片段向量組為Vs，ks為代碼詞的個數(shù)，Vs表示為

3 基于代碼片段的隱向量相似度計算

深度語義結(jié)構(gòu)模型[12](deep sematic structured model， DSSM)是文檔匹配[13]中的常用模型。深度語義模型將單詞向量映射為句子隱表示，以便計算句子之間的相似度。為了計算搜索關(guān)鍵詞上下文代碼片段向量組和待匹配代碼片段向量組的語義相似度，使用改進(jìn)的DSSM模型進(jìn)行相似度計算，如圖5所示。

在圖5中，Q對應(yīng)搜索關(guān)鍵詞上下文代碼片段向量組，Ci對應(yīng)代碼片段詞向量組。

圖5 代碼片段的編碼和相似度計算

i∈{Q，C1，C2，…，Cn}

(3)

(4)

(5)

hi(3)為第3層第i個節(jié)點的隱向量表示，當(dāng)i=Q時，是代碼片段Q經(jīng)過網(wǎng)絡(luò)的編碼計算得到代碼的隱向量表示，當(dāng)i=Ci時，是代碼片段Ci經(jīng)過網(wǎng)絡(luò)的編碼計算得到代碼的隱向量表示。Wj為神經(jīng)網(wǎng)絡(luò)的權(quán)重參數(shù)；bj為偏置向量；式(4)中的激活函數(shù)f(·)表示為

(6)

R(Q，Ci)表示搜索關(guān)鍵詞上下文代碼片段隱向量hQ和待匹配代碼片段的隱向量hCi的余弦相似度，計算式為

(7)

通過計算hQ和hCi的相似度，可得出搜索文本和待匹配代碼片段的相似度，將相似度排序，得出的搜索列表作為最終的搜索列表。例如，與搜索的關(guān)鍵詞 “iterate a java hashmap”匹配的代碼片段，如圖6所示。

代碼片段匹配度Map map=new HashMap();Iterator it=mp.entrySet().iterator();while (it.hasNext()) { Map.Entry pair=(Map.Entry)it.next(); System.out.println(pair.getKey()+"="+pair.getValue());}0.7230for (Map.Entry e: map.entrySet()){ T key=e.getKey(); U value=e.getValue();}0.3580map.replaceAll((k, v)-> { int newValue=v+1; System.out.println("key="+k+" value="+v+" new value="+newValue); return newValue;});0.1242Map testMap=new HashMap();testMap.put(10, "a");testMap.put(20, "b");for (Entry entry: testMap.entry-Set()) { Integer key=entry.getKey(); String value=entry.getValue();}0.6501

圖6 關(guān)鍵詞為“iterate a java hashmap”的相關(guān)代碼匹配度

4 代碼相似度計算模型訓(xùn)練

代碼相似度計算模型訓(xùn)練的目標(biāo)是使搜索文本與目標(biāo)代碼片段在語義上盡可能的相似，等價于搜索關(guān)鍵詞上下文代碼片段隱向量和待匹配代碼片段的隱向量相似。為訓(xùn)練本模型，采用類似于深度語義模型DSSM的訓(xùn)練方式訓(xùn)練[12]，對于實踐中很難收集到的用戶搜索文本和期望代碼對，使用Stack Overflow開發(fā)者問答數(shù)據(jù)集和收集的Github數(shù)據(jù)集作為訓(xùn)練數(shù)據(jù)，從中抽取搜索文本和匹配代碼片段作為正例，選擇其他代碼片段作為負(fù)例。其目標(biāo)函數(shù)為

(8)

其中

(9)

Map map=new HashMap();Iterator it=mp.entrySet().iterator();while (it.hasNext()) { Map.Entry pair=(Map.Entry)it.next(); System.out.println(pair.getKey()+"="+pair.getValue());}

圖7 回答被贊同數(shù)最多的答案(正例)

圖8 無關(guān)回答(負(fù)例)

5 實驗分析

5.1 數(shù)據(jù)收集

為了緩解小量數(shù)據(jù)導(dǎo)致的實驗結(jié)果偏差，收集Github[14]上stars最高的500個項目中的代碼和Stack Overflow開源數(shù)據(jù)[15]的Posts表作為訓(xùn)練數(shù)據(jù)集，這2份數(shù)據(jù)集的代碼行數(shù)規(guī)模都超過了數(shù)10億。Stack Overflow數(shù)據(jù)集中Posts表中的問題貼和回答貼總數(shù)量超過4 300萬條。問題貼中包含用戶提出問題。與問題貼對應(yīng)的回答貼中包含其他用戶對該問題的回答代碼和提問者的滿意回答貼。Github上收集項目包含大量類和類方法代碼片段。

5.2 代碼庫的獲取

為訓(xùn)練代碼片段的隱向量相似度計算模型，將從Github數(shù)據(jù)集[14]和Stack Overflow數(shù)據(jù)集[15]中構(gòu)建2個向量表示的代碼庫，Github代碼庫和Stack Overflow代碼庫，作為訓(xùn)練的訓(xùn)練集和測試集。

構(gòu)建方式：第1步，分別抽取數(shù)據(jù)集中的代碼片段和代碼片段文本描述，將代碼片段切割成以方法為基礎(chǔ)的代碼片段，并分割基礎(chǔ)代碼片段為代碼詞輸入到skip-gram模型中，并采用負(fù)采樣[12]優(yōu)化概率值，獲得skip-gram模型中的參數(shù)，同時，將代碼片段中的基礎(chǔ)代碼片段表示成向量組的形式，將得到的代碼文本描述和對應(yīng)的代碼片段向量表示放入數(shù)據(jù)庫中；第2步，將第1步抽取的代碼片段文本描述預(yù)處理，即當(dāng)從Stack Overflow數(shù)據(jù)集中抽取代碼片段文本描述時，抽取提問貼中的語義關(guān)鍵詞，如 “iterate a java hashmap”，抽取的語義關(guān)鍵代碼詞為 “iterate java hashmap”作為代碼片段文本描述關(guān)鍵詞，當(dāng)從Github數(shù)據(jù)集中抽取代碼片段文本描述時，按照駝峰、下劃線或其他類名命名方式分割類名和方法名，如，ThreadDumpEndpoint AutoConfiguration類中的方法dumpEndpoint，抽取成語義關(guān)鍵詞“Thread Dump Endpoint Auto Configuration dump Endpoint” 作為代碼片段文本描述關(guān)鍵詞，利用第1步訓(xùn)練的skip-gram模型進(jìn)行擴(kuò)充，形成代碼描述關(guān)鍵詞上下文的向量表示；第3步，將第2步得到的代碼描述關(guān)鍵詞上下文向量表示，替換第1步代碼文本描述——代碼片段向量表示庫中的代碼文本描述，即可得到代碼描述關(guān)鍵詞上下文—代碼片段庫，如圖9所示。

圖9 代碼庫的獲取

5.3 代碼相似度計算實驗流程

對于代碼相似度匹配模型的訓(xùn)練，選取5.2節(jié)構(gòu)建的代碼庫中一份數(shù)據(jù)作為訓(xùn)練集，另一份數(shù)據(jù)作為測試集。隨機(jī)選取代碼描述關(guān)鍵詞上下文—代碼片段庫中的1組數(shù)據(jù)，將其中的代碼描述關(guān)鍵詞上下文向量組作為搜索輸入，將其中的代碼片段作為訓(xùn)練的正例，隨機(jī)選擇其他的代碼片段作為訓(xùn)練的負(fù)例。

采用mini-batch SGD算法訓(xùn)練模型，首先將模型中的l1，l2層元素取為300，參數(shù)隨機(jī)初始化，每一次mini-batch取1 024個訓(xùn)練數(shù)據(jù)，在整個數(shù)據(jù)集上迭代20次后，神經(jīng)網(wǎng)絡(luò)收斂。

5.4 評估方法

為了評估代碼搜索方法的有效性，將從準(zhǔn)確率、召回率、F值3方面對搜索結(jié)果進(jìn)行評價。在Q個搜索中，使用符號NQK表示搜索結(jié)果為正確結(jié)果的數(shù)量，NQS表示搜索結(jié)果中總搜索次數(shù)，NQW表示搜索結(jié)果中的非最佳匹配結(jié)果被視為最佳匹配結(jié)果的數(shù)量。搜索結(jié)果準(zhǔn)確率Pk是滿意搜索結(jié)果所占總的搜索結(jié)果的比例，定義為

(10)

搜索結(jié)果的召回率Precall是所有搜索結(jié)果中的正確結(jié)果數(shù)占正確搜索結(jié)果數(shù)和被錯誤識別的正確結(jié)果數(shù)的比例，定義為

(11)

搜索結(jié)果的F值 (F-Measure) 表示準(zhǔn)確率Pk和召回率Precall的加權(quán)調(diào)和平均， 用于評價模型的好壞，定義為

(12)

5.5 對比分析

為了評價本文所提出的算法的有效性，將VRCS方法與QECK和SWIM方法對比，并使用5.2節(jié)所構(gòu)建的Github代碼庫和Stack Overflow代碼庫作為訓(xùn)練集和測試集。當(dāng)Github代碼庫作為訓(xùn)練集，在Stack Overflow代碼庫做測試時，其準(zhǔn)確率、召回率和F值如表1—3所示。

表1 Stack Overflow數(shù)據(jù)集下的準(zhǔn)確率

表2 Stack Overflow數(shù)據(jù)集下的召回率

表3 Stack Overflow數(shù)據(jù)集下的F值

可以看出：VRCS 算法中58%的搜索能在第1個搜索結(jié)果找到正確答案，相對于QECK算法和SWIM算法，其準(zhǔn)確率、召回率和F值有1%～3%的提升；65%的搜索能在前5個答案中找到正確答案，相對于QECK算法和SWIM算法，其準(zhǔn)確率、召回率和F值有1%～7%的提升；72%的搜索能在前10個答案中找到正確答案，相對于QECK算法和SWIM算法，其準(zhǔn)確率、召回率和F值有1%～5%的提升。

當(dāng)Stack Overflow代碼庫作為訓(xùn)練集， Github代碼庫做測試時，其準(zhǔn)確率、召回率和F值如表4—6所示。

表4 Github數(shù)據(jù)集下的準(zhǔn)確率

表5 Github數(shù)據(jù)集下的召回率

表6 Github數(shù)據(jù)集下的F值

可以看出：VRCS算法中59%的搜索能在第1個搜索結(jié)果找到正確答案，相對于QECK算法和SWIM算法，準(zhǔn)確率、召回率和F值有2%～4%的提升；67%的搜索能在前5個答案中找到正確答案，相對于QECK算法和SWIM算法，準(zhǔn)確率、召回率和F值有3%～7%的提升；74%的搜索能在前10個答案中找到正確答案，相對于QECK算法和SWIM算法，準(zhǔn)確率、召回率和F值有2%～8%的提升。

通過將VRCS應(yīng)用于上述2份數(shù)據(jù)集的測試對比發(fā)現(xiàn)，VRCS方法在準(zhǔn)確率、召回率以及F值上有所提高。同時，VRCS算法在搜索結(jié)果的準(zhǔn)確率平均高于召回率的3%，這是因為在大量數(shù)據(jù)的測試下，搜索準(zhǔn)確率得到提高，導(dǎo)致了召回率變低。從數(shù)據(jù)集上看，使用Github數(shù)據(jù)集作為測試的搜索結(jié)果優(yōu)于Stack Overflow數(shù)據(jù)集的搜索結(jié)果，因為從Github數(shù)據(jù)集上抽取的關(guān)鍵詞更加具體，也更加能夠表示代碼片段。綜上所述，對于基于大量數(shù)據(jù)的代碼搜索，本文提出的VRCS算法充分利用了代碼搜索關(guān)鍵詞—代碼之間語義和代碼—代碼之間的語義，在一定程度上提升了搜索的準(zhǔn)確率。

6 總結(jié)

本文提出一種基于向量的代碼搜索方法，該方法通過Github和Stack Overflow數(shù)據(jù)集中的代碼片段訓(xùn)練一個skip-gram模型，并利用這個模型擴(kuò)充從搜索文本提取的關(guān)鍵詞，得到搜索關(guān)鍵詞上下文代碼片段向量組，最后計算搜索關(guān)鍵詞上下文向量組和待匹配向量組的語義相似度，排序完成搜索。該方法有效地降低了因關(guān)鍵詞語義模糊導(dǎo)致的搜索結(jié)果偏差。同時，應(yīng)用神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)代碼片段的隱表示，從語義上匹配有更高的精確度。實驗表明，本文提出的方法優(yōu)于已有的代碼搜索方法。在未來的研究中，可結(jié)合語義和代碼結(jié)構(gòu)，提高代碼搜索結(jié)果的精確度。