慕江林，劉克劍*，林 晗

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

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

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

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

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

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

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

2 代碼詞嵌入表示

2.1 代碼片段詞嵌入表示

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

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

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

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

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

圖3 skip-gram模型

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

(1)

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

(2)

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

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

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

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

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

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

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

圖5 代碼片段的編碼和相似度計(jì)算

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

(3)

(4)

(5)

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

(6)

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

(7)

通過(guò)計(jì)算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 代碼相似度計(jì)算模型訓(xùn)練

代碼相似度計(jì)算模型訓(xùn)練的目標(biāo)是使搜索文本與目標(biāo)代碼片段在語(yǔ)義上盡可能的相似，等價(jià)于搜索關(guān)鍵詞上下文代碼片段隱向量和待匹配代碼片段的隱向量相似。為訓(xùn)練本模型，采用類(lèi)似于深度語(yǔ)義模型DSSM的訓(xùn)練方式訓(xùn)練[12]，對(duì)于實(shí)踐中很難收集到的用戶(hù)搜索文本和期望代碼對(duì)，使用Stack Overflow開(kāi)發(fā)者問(wèn)答數(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 無(wú)關(guān)回答(負(fù)例)

5 實(shí)驗(yàn)分析

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

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

5.2 代碼庫(kù)的獲取

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

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

圖9 代碼庫(kù)的獲取

5.3 代碼相似度計(jì)算實(shí)驗(yàn)流程

對(duì)于代碼相似度匹配模型的訓(xùn)練，選取5.2節(jié)構(gòu)建的代碼庫(kù)中一份數(shù)據(jù)作為訓(xùn)練集，另一份數(shù)據(jù)作為測(cè)試集。隨機(jī)選取代碼描述關(guān)鍵詞上下文—代碼片段庫(kù)中的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個(gè)訓(xùn)練數(shù)據(jù)，在整個(gè)數(shù)據(jù)集上迭代20次后，神經(jīng)網(wǎng)絡(luò)收斂。

5.4 評(píng)估方法

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

(10)

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

(11)

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

(12)

5.5 對(duì)比分析

為了評(píng)價(jià)本文所提出的算法的有效性，將VRCS方法與QECK和SWIM方法對(duì)比，并使用5.2節(jié)所構(gòu)建的Github代碼庫(kù)和Stack Overflow代碼庫(kù)作為訓(xùn)練集和測(cè)試集。當(dāng)Github代碼庫(kù)作為訓(xùn)練集，在Stack Overflow代碼庫(kù)做測(cè)試時(shí)，其準(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個(gè)搜索結(jié)果找到正確答案，相對(duì)于QECK算法和SWIM算法，其準(zhǔn)確率、召回率和F值有1%～3%的提升；65%的搜索能在前5個(gè)答案中找到正確答案，相對(duì)于QECK算法和SWIM算法，其準(zhǔn)確率、召回率和F值有1%～7%的提升；72%的搜索能在前10個(gè)答案中找到正確答案，相對(duì)于QECK算法和SWIM算法，其準(zhǔn)確率、召回率和F值有1%～5%的提升。

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

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

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

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

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

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

6 總結(jié)

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