凌春陽(yáng),鄒艷珍,3,林澤琦,謝 冰,趙俊峰,3

1(高可信軟件技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室(北京大學(xué)),北京 100871)

2(北京大學(xué) 信息科學(xué)技術(shù)學(xué)院,北京 100871)

3(北京大學(xué)(天津?yàn)I海)新一代信息技術(shù)研究院,天津 300450)

在軟件開(kāi)發(fā)過(guò)程中,開(kāi)發(fā)者最常用的復(fù)用方式就是通過(guò)檢索、調(diào)用軟件項(xiàng)目提供的 API(application programming interface,應(yīng)用程序接口)來(lái)實(shí)現(xiàn)所需的功能.然而隨著軟件項(xiàng)目源代碼的規(guī)模變得越來(lái)越大,源代碼之間的依賴(lài)關(guān)系越來(lái)越復(fù)雜,API檢索也變得越來(lái)越困難[1].比如,開(kāi)源項(xiàng)目Lucene包含了超過(guò)5 377個(gè)類(lèi)以及 34 042種方法.而研究人員在研究搜索引擎查詢(xún)?nèi)罩緯r(shí)發(fā)現(xiàn),開(kāi)發(fā)者往往花費(fèi)了大量的時(shí)間與精力來(lái)查找API[2],通用搜索引擎(如 Google)在檢索軟件代碼方面存在許多問(wèn)題且效率較低[3].由此也促生了在很多技術(shù)性問(wèn)答網(wǎng)站(如StackOverflow)上,可以發(fā)現(xiàn)大量關(guān)于如何使用API的提問(wèn).

受自然語(yǔ)言處理技術(shù)的影響,目前許多軟件源代碼檢索工具,比如 Krugle、Ohloh和 Sourcerer[4]等,都是將源代碼視為純文本進(jìn)行處理.其基本思路是:利用軟件源代碼中的自然語(yǔ)言特征,基于查詢(xún)問(wèn)題與代碼的文本相似度進(jìn)行匹配,返回相似度較高的檢索結(jié)果.典型的相似度匹配模型包括布爾模型(Boolean model)[5]、向量空間模型(vector space model)[5]、BM25模型[5]等.然而研究表明,這些工具的準(zhǔn)確率不能讓人滿(mǎn)意.在 Lü等人[6]于2015年進(jìn)行的一項(xiàng)研究中表明,Ohloh返回的排名前十的結(jié)果中,只有25.7%～38.4%是有用的.研究者們指出,導(dǎo)致現(xiàn)有軟件源代碼檢索工具效果不理想的一個(gè)主要原因是其缺乏對(duì)自然語(yǔ)言查詢(xún)問(wèn)題語(yǔ)義的理解.對(duì)此,研究者們從深化問(wèn)題理解的角度提出了許多新的方法,如擴(kuò)展語(yǔ)義相近的詞(semantic similar word)[7]、引入查詢(xún)重構(gòu)策略(query reformulation)[8]或利用其他在線(xiàn)文檔(如 MSDN)來(lái)優(yōu)化問(wèn)題理解和檢索過(guò)程[6]等.雖然這些技術(shù)很大程度上提高了API定位的準(zhǔn)確度,但其需要積累和利用大量的輔助信息,在上述信息缺乏的情況下,往往不能達(dá)到預(yù)期效果.本文則希望僅從軟件項(xiàng)目的源代碼出發(fā),幫助開(kāi)發(fā)者提高API檢索的效率,因?yàn)樵创a是復(fù)用過(guò)程中能夠直接獲得的資源,其他信息有時(shí)則難以獲得.

此外,現(xiàn)有這些檢索工具返回的結(jié)果往往只有相關(guān)的代碼片段信息,缺乏對(duì)關(guān)聯(lián)API的說(shuō)明與展示,不便于用戶(hù)理解目標(biāo)API調(diào)用背后的邏輯關(guān)聯(lián)和整體概念,在一定程度上影響了軟件復(fù)用的效率.為此,研究者們指出,不應(yīng)單純地將軟件代碼視為純文本.比如在McMillan等人和Chan等人[9,10]的工作中,將源代碼以有向圖的形式組織起來(lái),圖中的結(jié)點(diǎn)表示代碼元素,邊表示代碼元素之間的關(guān)聯(lián)關(guān)系.圖結(jié)構(gòu)是對(duì)源代碼知識(shí)的一種自然且有效的表示,被廣泛應(yīng)用于軟件文檔檢索、特征定位等問(wèn)題.借助代碼的結(jié)構(gòu)圖,對(duì)源代碼的檢索就轉(zhuǎn)化為圖上的搜索過(guò)程,這樣得到的結(jié)果既能包含需要被定位的代碼元素,又能充分體現(xiàn)代碼之間的關(guān)聯(lián)關(guān)系.舉例來(lái)說(shuō),假設(shè)在使用開(kāi)源軟件項(xiàng)目 ApacheLucene(http://Lucene.apache.org/)的過(guò)程中,開(kāi)發(fā)者當(dāng)前使用 StringField類(lèi)對(duì)一個(gè)字符串的字段進(jìn)行處理.當(dāng)需求發(fā)生變化,還要對(duì)含有浮點(diǎn)數(shù)的字段進(jìn)行處理時(shí),這個(gè)開(kāi)發(fā)者就需要使用FloatPoint類(lèi)并考慮如何重構(gòu)代碼.而我們可以從圖1所示的源代碼圖中發(fā)現(xiàn),這兩個(gè)類(lèi)都繼承自Field類(lèi),實(shí)現(xiàn)了IndexableField接口,同時(shí)具有tokenStream方法.因此對(duì)開(kāi)發(fā)者來(lái)說(shuō),一種更好的策略是使用該抽象的父Field作為變量類(lèi)型,并在處理不同查詢(xún)時(shí)賦值為不同的子類(lèi),從而能夠較好地滿(mǎn)足其上述需求.

Fig.1 Code graph of Lucene project (Part)圖1 Lucene項(xiàng)目的代碼圖示例(部分)

目前,在基于圖結(jié)構(gòu)的 API檢索方面,主要采用了最短路徑[10]、PageRank[9]等淺層語(yǔ)義分析技術(shù).考慮到在圖上進(jìn)行搜索是一個(gè)計(jì)算量很大的問(wèn)題,且要求延遲越短越好,算法的效率至關(guān)重要.如果使用在線(xiàn)查詢(xún)最短路徑的方式,則由于搜索過(guò)程中經(jīng)常需要計(jì)算圖上兩個(gè)結(jié)點(diǎn)之間的距離,將會(huì)導(dǎo)致較長(zhǎng)的延遲時(shí)間.Chan等人的工作[10]也提到了這個(gè)問(wèn)題,并利用了一些近似算法進(jìn)行優(yōu)化.

針對(duì)這些問(wèn)題,本文提出一種基于圖嵌入的軟件項(xiàng)目源代碼檢索方法.圖嵌入是一種表示學(xué)習(xí)技術(shù),能夠?qū)D上的結(jié)點(diǎn)映射為低維空間中的實(shí)值向量,通過(guò)向量之間的關(guān)系來(lái)表達(dá)圖上的結(jié)構(gòu)信息.對(duì)于本文的問(wèn)題而言,圖嵌入技術(shù)一方面能夠有效表達(dá)軟件代碼圖中的深層結(jié)構(gòu)信息,與最短路徑等方法相比,更充分地考慮了結(jié)點(diǎn)的上下文和關(guān)聯(lián)關(guān)系;另一方面,圖嵌入過(guò)程可以離線(xiàn)進(jìn)行,在用戶(hù)在線(xiàn)查詢(xún)階段可以立即參與計(jì)算,時(shí)間復(fù)雜度僅是常數(shù)級(jí)別,大大提高了算法效率.

對(duì)比現(xiàn)有工作,本文主要貢獻(xiàn)包括:

(1) 提出了一種將軟件源代碼進(jìn)行圖嵌入表示的方法,該方法能夠能夠基于軟件項(xiàng)目源代碼,自動(dòng)構(gòu)建其代碼圖結(jié)構(gòu),并通過(guò)圖嵌入對(duì)源代碼進(jìn)行信息表示.

(2) 提出了一種基于圖嵌入的軟件項(xiàng)目源代碼檢索方法,該方法能夠基于項(xiàng)目源代碼的圖嵌入技術(shù)表示,將自然語(yǔ)言查詢(xún)問(wèn)題語(yǔ)義匹配到代碼子圖,提高了檢索的準(zhǔn)確性,同時(shí)展示了API的關(guān)聯(lián)關(guān)系;

(3) 實(shí)現(xiàn)了一個(gè)基于圖嵌入的軟件項(xiàng)目API檢索工具原型,并通過(guò)2個(gè)具體軟件項(xiàng)目中關(guān)于源代碼檢索的實(shí)際問(wèn)題為例,驗(yàn)證了本文方法的有效性.與Chan等人提出的方法相比,本文方法在召回率、F1值上有了顯著提升,并有效減低了檢索響應(yīng)時(shí)間.

本文第1節(jié)介紹圖嵌入技術(shù).第2節(jié)詳細(xì)描述本文提出的基于圖嵌入的軟件項(xiàng)目源代碼檢索方法.第3節(jié)通過(guò)實(shí)驗(yàn)驗(yàn)證本文方法的有效性.第4節(jié)介紹相關(guān)工作.第5節(jié)對(duì)本文工作進(jìn)行總結(jié)并展望未來(lái)研究工作.

1 圖嵌入

圖嵌入(graph embedding)的主要目的是將一張圖上的結(jié)點(diǎn)映射到低維空間的向量,通過(guò)這些向量來(lái)體現(xiàn)原本圖上的結(jié)構(gòu)信息.這里的結(jié)構(gòu)信息可以是一階、二階甚至更高階的結(jié)構(gòu),一階結(jié)構(gòu)信息即保持原本相鄰的結(jié)點(diǎn)在嵌入空間中的距離仍然很近,而更高階的結(jié)構(gòu)信息則可以保持原本具有相似上下文的結(jié)點(diǎn)在嵌入空間中的距離仍然很近.目前,圖嵌入技術(shù)在知識(shí)表示領(lǐng)域頗受關(guān)注,被廣泛應(yīng)用于可視化、頂點(diǎn)分類(lèi)、關(guān)聯(lián)預(yù)測(cè)、推薦等任務(wù).現(xiàn)有的圖嵌入技術(shù)主要可以分為以下幾類(lèi)[11].

· 基于因子分解的圖嵌入方法.該類(lèi)方法將圖上結(jié)點(diǎn)之間的關(guān)系表示成矩陣,對(duì)該矩陣進(jìn)行因子分解從而得到嵌入的向量.矩陣的類(lèi)型包括鄰接矩陣、拉普拉斯矩陣(Laplacian matrix)、卡茲相似矩陣(Katz similarity matrix)等,根據(jù)不同的矩陣類(lèi)型有不同的分解方法,其中,Belkin等人[12]提出的 Laplacian Eigenmaps就是對(duì)拉普拉斯矩陣做特征值分解得到的;Ahmed等人[13]提出的GF算法則是基于對(duì)鄰接矩陣做因子分解.這種方法的時(shí)間復(fù)雜度是結(jié)點(diǎn)數(shù)的平方量級(jí),可擴(kuò)展性較差,對(duì)于規(guī)模龐大的代碼圖而言并不適用.

· 基于隨機(jī)游走的圖嵌入方法.該類(lèi)方法算法能夠近似表示圖的許多屬性,比如結(jié)點(diǎn)的中心度和相似度.Perozzi等人提出的 DeepWalk[14]就是該方法的典型代表,該算法利用了神經(jīng)語(yǔ)言模型 SkipGram的思想,根據(jù)周?chē)泥従咏Y(jié)點(diǎn)來(lái)預(yù)測(cè)當(dāng)前結(jié)點(diǎn)的嵌入向量.該類(lèi)方法通常從某一結(jié)點(diǎn)為中心出發(fā)進(jìn)行多次隨機(jī)游走,最大化觀(guān)測(cè)到的前k個(gè)結(jié)點(diǎn)以及后k個(gè)結(jié)點(diǎn)的概率,能夠保持高階的相似性.當(dāng)只需要觀(guān)測(cè)圖的部分結(jié)構(gòu)或者圖太大而無(wú)法全部測(cè)量時(shí),該類(lèi)方法是一個(gè)不錯(cuò)的選擇.但是該類(lèi)方法通常只能捕捉到一條路徑上的局部結(jié)構(gòu)信息,并且難以找到最佳的采樣方法,調(diào)優(yōu)困難.

· 基于深度學(xué)習(xí)的圖嵌入方法.該類(lèi)方法有的利用深度自編碼器(deep autoencoder)來(lái)實(shí)現(xiàn)降維,因?yàn)樽跃幋a器擁有學(xué)習(xí)數(shù)據(jù)中非線(xiàn)性結(jié)構(gòu)的能力.典型地,Wang等人[15]提出的SDNE包括無(wú)監(jiān)督和有監(jiān)督兩部分:前一部分由自編碼器學(xué)習(xí)能夠重新構(gòu)鄰居的結(jié)點(diǎn)嵌入,后一部分則基于 Laplacian Eigenmaps對(duì)那些本來(lái)相鄰而映射到嵌入空間后卻相距很遠(yuǎn)的結(jié)點(diǎn)進(jìn)行懲罰.還有一些算法利用卷積神經(jīng)網(wǎng)絡(luò)來(lái)得到嵌入向量,如Kipf等人[16]提出的一種半監(jiān)督學(xué)習(xí)的方法,這些算法的計(jì)算開(kāi)銷(xiāo)更小,更適用于相對(duì)稀疏的圖.這一類(lèi)方法雖然能更好地捕捉非線(xiàn)性的結(jié)構(gòu),然而復(fù)雜度還是較高,需要大量的計(jì)算開(kāi)銷(xiāo).

本文采用的是Tang等人[17]提出的LINE(large-scale information network embedding)方法,該方法的可擴(kuò)展性很好,能夠快速地對(duì)大規(guī)模網(wǎng)絡(luò)進(jìn)行嵌入,并且能夠同時(shí)保留局部和全局的結(jié)構(gòu)信息.該方法嚴(yán)格意義上不屬于上述的 3種類(lèi)型,而是在模型中顯式地定義了一階和二階的近似函數(shù)以及任意 2個(gè)結(jié)點(diǎn)之間的聯(lián)合概率分布,通過(guò)最小化嵌入矩陣與鄰接矩陣所代表的兩個(gè)概率分布之間的 KL(Kullback-Leibler)散度得到圖嵌入的向量.定義好目標(biāo)函數(shù)之后,LINE并沒(méi)有采用傳統(tǒng)的隨機(jī)梯度下降算法進(jìn)行優(yōu)化,而是提出了一種新的邊采樣的方法(edge-sampling),根據(jù)邊的權(quán)值成比例的概率進(jìn)行采樣,這樣能夠防止隨機(jī)梯度下降中由于邊的權(quán)值過(guò)大導(dǎo)致的梯度爆炸問(wèn)題.為了進(jìn)一步形象地闡明一階近似和二階近似的意義,我們以圖2為例進(jìn)行說(shuō)明.一階近似能夠?qū)⒅苯佑羞呄噙B的結(jié)點(diǎn)映射到更近的距離,比如圖2中的結(jié)點(diǎn)6和結(jié)點(diǎn)7,它們之間有一條權(quán)重很大的邊連接.而二階近似則能夠?qū)⒕哂邢嗤従拥慕Y(jié)點(diǎn)映射到更近的距離,比如圖2中的結(jié)點(diǎn) 5和結(jié)點(diǎn) 6,它們都具有很多相同的鄰居結(jié)點(diǎn).因此,一階近似能夠保留更多局部的結(jié)構(gòu)信息,而二階近似能夠保留更多全局的結(jié)構(gòu)信息.同時(shí)考慮2種近似的結(jié)果,就是將結(jié)點(diǎn)5～結(jié)點(diǎn)7都映射到嵌入空間中更近的距離.

Fig.2 Graph embedding maps nodes with similar structure to closer distance in the embedding space[17]圖2 圖嵌入將結(jié)構(gòu)相似的結(jié)點(diǎn)映射到嵌入空間中更近的距離[17]

2 本文工作

本文提出了一種基于圖嵌入的軟件項(xiàng)目源代碼檢索方法,其基本思想是:利用圖嵌入技術(shù)有效表達(dá)軟件代碼圖中的深層結(jié)構(gòu)信息,在檢索過(guò)程中充分地考慮了結(jié)點(diǎn)的上下文和關(guān)聯(lián)關(guān)系.如圖3所示.

Fig.3 Framework of searching software project’s source code based on graph embedding圖3 基于圖嵌入的軟件項(xiàng)目源代碼檢索方法框架

該方法主要包括4個(gè)部分.

1)代碼圖的構(gòu)建:獲取項(xiàng)目的源代碼并做相應(yīng)解析,自動(dòng)構(gòu)建其代碼圖.

2)代碼圖的嵌入:使用圖嵌入技術(shù)將代碼圖中的結(jié)點(diǎn)表示為向量,以備后續(xù)階段使用.

3)問(wèn)題與代碼圖結(jié)點(diǎn)的匹配:對(duì)用戶(hù)輸入的自然語(yǔ)言問(wèn)題進(jìn)行預(yù)處理,然后匹配到代碼圖中結(jié)點(diǎn)作為候選結(jié)點(diǎn),并對(duì)候選結(jié)點(diǎn)進(jìn)行度量.

4)代碼子圖的生成與推薦:從第 2階段得到的候選結(jié)點(diǎn)中挑選合適的結(jié)點(diǎn)構(gòu)成子圖,并擴(kuò)展為連通的子圖,將排名最佳的結(jié)果返回給用戶(hù).

2.1 代碼圖的構(gòu)建

在一個(gè)軟件項(xiàng)目(對(duì)于面向?qū)ο蟮暮瘮?shù)庫(kù)而言)的源代碼中,主要有兩種組成成分:一種是類(lèi)或接口,另一種是方法.而類(lèi)與方法之間的關(guān)聯(lián)關(guān)系的類(lèi)型大體上所有面向?qū)ο笳Z(yǔ)言都共有,當(dāng)然,部分關(guān)聯(lián)關(guān)系與具體編程語(yǔ)言有關(guān).本文以Java語(yǔ)言作為實(shí)驗(yàn)對(duì)象,考慮了Java語(yǔ)言中的如下6種關(guān)聯(lián)關(guān)系,分別為繼承(Inh)、實(shí)現(xiàn)(Imp)、成員(Mem)、參數(shù)(Par)、返回值(Ret)和調(diào)用(Call),用集合Rel={Inh,Imp,Mem,Par,Ret}表示(見(jiàn)表1).在此基礎(chǔ)上,我們可以利用現(xiàn)有工具對(duì)一個(gè)開(kāi)源軟件項(xiàng)目的源碼進(jìn)行解析,構(gòu)建代碼圖并存儲(chǔ)于圖數(shù)據(jù)庫(kù)中.

Table 1 Relationship types in code graph表1 代碼圖中的關(guān)系類(lèi)型

代碼圖(code graph).代碼圖G=(VG,EG)是一個(gè)有向無(wú)權(quán)圖,頂點(diǎn)集VG是所有的類(lèi)和方法的結(jié)點(diǎn),邊集EG中任一條邊e(u,v),?R∈Rel,使得uRv.其中,uRv表示u,v之間存在R類(lèi)型的關(guān)聯(lián)關(guān)系.

現(xiàn)在主流的Java源碼解析工具有很多,例如CheckStyle,JAVAssist,Yasca,JDT等.這些工具都現(xiàn)成可用,可以解析Java項(xiàng)目并提取出代碼元素以及它們之間的關(guān)系.本文使用的是Eclipse的JDT,作為一個(gè)輕量級(jí)的代碼解析工具,它可以迅速將Java代碼構(gòu)建成一個(gè)DOM結(jié)構(gòu)的抽象語(yǔ)法樹(shù)(AST).代碼中的每個(gè)元素都對(duì)應(yīng)AST上的一個(gè)結(jié)點(diǎn),通過(guò)遍歷AST就可以得到所有代碼元素和它們之間的關(guān)系,用來(lái)構(gòu)建軟件代碼結(jié)構(gòu)圖.

本文使用圖數(shù)據(jù)庫(kù)Neo4j(https://neo4j.com/)來(lái)存儲(chǔ)代碼圖.Neo4j是一個(gè)用Java實(shí)現(xiàn),完全兼容ACID的圖數(shù)據(jù)庫(kù),其本身數(shù)據(jù)組織的結(jié)構(gòu)和我們需求的代碼結(jié)構(gòu)圖非常相似,也是通過(guò)結(jié)點(diǎn)與結(jié)點(diǎn)之間的關(guān)系構(gòu)成整張圖.除此之外,Neo4j還提供了諸如索引(index)、遍歷(traversal)等機(jī)制以及一種類(lèi)SQL的查詢(xún)語(yǔ)言Cypher,以方便在圖上進(jìn)行更高級(jí)的操作.

2.2 代碼圖的嵌入

本文使用圖嵌入的原因是在第 3階段,即代碼子圖的生成與推薦時(shí),需要計(jì)算圖上任意兩個(gè)頂點(diǎn)之間的距離.圖嵌入技術(shù)可以使得這一步驟變得十分方便與快速.如果采用在線(xiàn)查詢(xún)兩個(gè)頂點(diǎn)的最短路徑的方式則將非常耗時(shí),而圖嵌入過(guò)程卻是離線(xiàn)的,在構(gòu)建完代碼圖后即可完成.

本文使用了Tang等人[17]提出的名為L(zhǎng)INE的方法,該方法的可擴(kuò)展性很好,時(shí)間復(fù)雜度較低,能夠快速地對(duì)大規(guī)模網(wǎng)絡(luò)進(jìn)行嵌入,并且同時(shí)保留局部和全局的結(jié)構(gòu)信息,能夠適用于有向圖、無(wú)向圖、帶權(quán)圖等多種類(lèi)型.LINE的源代碼可以在Github上找到,本文用Java語(yǔ)言重新實(shí)現(xiàn)了該算法.

結(jié)點(diǎn)之間的距離.代碼圖嵌入以后,代碼圖中的任一頂點(diǎn)v∈VG,都映射到一個(gè)向量rv∈Rd,其中,d表示該向量的維度;任意2個(gè)頂點(diǎn)u,v之間的距離定義為相應(yīng)的向量之間的歐氏距離,即dist(u,v)=||ru-rv||2.

2.3 問(wèn)題與結(jié)點(diǎn)的匹配

從這一階段開(kāi)始,便進(jìn)入在線(xiàn)查詢(xún)的過(guò)程.當(dāng)用戶(hù)輸入一個(gè)自然語(yǔ)言的問(wèn)題后,我們先對(duì)問(wèn)題進(jìn)行預(yù)處理,然后匹配到代碼圖中一些候選結(jié)點(diǎn).

2.3.1 問(wèn)題與結(jié)點(diǎn)的預(yù)處理

本文采用簡(jiǎn)單的詞袋模型(bag of words),將問(wèn)題視為一些無(wú)序的詞組成的集合,忽略其句式和位置等信息.由于自然語(yǔ)言文本還存在單詞之外的一些符號(hào),如標(biāo)點(diǎn)符號(hào)等,本文將去除非數(shù)字和非字母的其他符號(hào),并以此作為分隔符進(jìn)行切詞.切詞以后,進(jìn)行停用詞處理.自然語(yǔ)言包含許多無(wú)實(shí)際意義的功能詞,比如冠詞和介詞等.這些詞存在十分普遍而包含信息的卻極少,人們一般稱(chēng)之為停用詞(stop words).本文去除的停用詞包括常見(jiàn)的英文停用詞、Java保留字以及項(xiàng)目領(lǐng)域特有的功能詞(比如Lucene),等.

代碼圖中結(jié)點(diǎn)(類(lèi)或方法)的預(yù)處理是將該類(lèi)或方法的名字通過(guò)切詞得到一個(gè)詞袋,用來(lái)描述該結(jié)點(diǎn)的語(yǔ)義信息.本文使用駝峰切詞法進(jìn)行處理,比如QueryParser這個(gè)類(lèi)名,切詞后的結(jié)果就是{query,parser}.

問(wèn)題(query).問(wèn)題Q是由一些去除停用詞之后的單詞的集合組成,將該單詞集合記為BOWQ={q1,…,qn}.

結(jié)點(diǎn)單詞集合.代碼圖G中的任一結(jié)點(diǎn)v,都有一個(gè)與之關(guān)聯(lián)的單詞集合,記為BOWv={s1,…,sm}.

2.3.2 產(chǎn)生候選結(jié)點(diǎn)

候選結(jié)點(diǎn)集合.問(wèn)題Q所匹配到的候選結(jié)點(diǎn)集合是一個(gè)集族,記為CandidateQ={C1,…,Cn},其中,Ci(1≤i≤n)是單詞qi匹配到的代碼圖中結(jié)點(diǎn)的集合,其大小記為|Ci|.

對(duì)于 Query詞袋中的每個(gè)詞,我們都為之在圖上找到一系列的候選結(jié)點(diǎn),這樣做是為了充分保留原問(wèn)題中的語(yǔ)義信息.接下來(lái)需要明確對(duì)于每個(gè)單詞q,如何匹配到它所對(duì)應(yīng)的候選結(jié)點(diǎn).本文使用文本匹配的方法,主要考慮了如下5種匹配情形.

(1) 全名匹配.單詞q本身就是就是一個(gè)類(lèi)或方法的全名,比如q=QueryParser.

(2) 部分匹配.單詞q被結(jié)點(diǎn)v所對(duì)應(yīng)的詞袋所包含,即q∈BOWv,比如q=query.

(3) 詞根化匹配.單詞q與結(jié)點(diǎn)v所對(duì)應(yīng)的詞袋中的詞經(jīng)詞根化后相同.詞根化(stemming)能夠?qū)⒄Z(yǔ)義上相同而由于語(yǔ)法等原因?qū)е略~形不同的詞抽取出同樣的詞根,本文采用 Snowball(http://snowball.tartarus.org/)作為詞根化工具.比如q=parse,由于 parse和 parser詞根化后都是 pars,因此q會(huì)匹配到QueryParser這個(gè)結(jié)點(diǎn).

(4) 縮略規(guī)則匹配.單詞q經(jīng)過(guò)手工構(gòu)造的一些規(guī)則轉(zhuǎn)換后,被結(jié)點(diǎn)v所對(duì)應(yīng)的詞袋包含.這是為了解決自然語(yǔ)言的詞匯與代碼元素中的命名不一致的問(wèn)題,代碼元素的命名為了方便,很可能只采取了自然語(yǔ)言單詞的縮寫(xiě),比如Document在代碼中的命名可能是Doc,Number在代碼中的命名可能是Num,等.

(5) 同義詞匹配.單詞q與結(jié)點(diǎn)v所對(duì)應(yīng)的詞袋中的詞,經(jīng)過(guò)相似度計(jì)算被判定為同義詞.同近義詞是自然語(yǔ)言處理領(lǐng)域的一個(gè)重要研究問(wèn)題,在自然語(yǔ)言與代碼元素匹配的過(guò)程中也存在這個(gè)問(wèn)題,比如問(wèn)題中的詞是delete,但代碼中某個(gè)方法的名字可能是remove,這種情況也應(yīng)該被考慮.為了解決這個(gè)問(wèn)題,本文使用了在Wikipedia上預(yù)訓(xùn)練的glove(https://nlp.stanford.edu/projects/glove/)詞向量.通過(guò)計(jì)算兩個(gè)詞向量的余弦相似度來(lái)表示語(yǔ)義的相近性,當(dāng)大于特定閾值時(shí),就認(rèn)為這兩個(gè)詞是同義詞.

2.3.3 候選結(jié)點(diǎn)的度量

上一步驟為了保證對(duì)原問(wèn)題中詞匯的覆蓋程度,產(chǎn)生了大量的候選結(jié)點(diǎn).但這些結(jié)點(diǎn)不應(yīng)該都是同等地位的,有的候選結(jié)點(diǎn)與問(wèn)題語(yǔ)義更貼近,有的卻徒增了許多噪音,因此需要對(duì)結(jié)點(diǎn)與問(wèn)題的文本相似程度進(jìn)行度量.本文考慮兩種評(píng)價(jià)指標(biāo):一是該結(jié)點(diǎn)詞袋與問(wèn)題中相關(guān)的詞越多越好;二是該結(jié)點(diǎn)引入的不相關(guān)的詞越少越好,即當(dāng)結(jié)點(diǎn)與問(wèn)題相關(guān)的詞數(shù)量相同時(shí),BOWv越小的結(jié)點(diǎn)質(zhì)量越好.可類(lèi)比于信息檢索中的準(zhǔn)確率與召回率,具體定義如下.

為了考慮同義詞的影響,在計(jì)算兩個(gè)詞袋的交集時(shí),需要進(jìn)行特殊處理.如果結(jié)點(diǎn)詞袋中的某個(gè)單詞不在Query詞袋中出現(xiàn)過(guò),那么利用詞向量計(jì)算該單詞與Query中所有單詞的余弦相似度,取其中的最大值作為該單詞對(duì)交集的貢獻(xiàn).因此,該交集的值不一定是整數(shù).

結(jié)點(diǎn)權(quán)重.以scorerelevant和scoreirrelevant的F1值作為該結(jié)點(diǎn)與問(wèn)題的相關(guān)度的度量,稱(chēng)為該結(jié)點(diǎn)的權(quán)重,記為w(v),其計(jì)算公式如下所示.

2.4 子圖的生成與推薦

得到候選結(jié)點(diǎn)集合之后,需要從中挑選合適的結(jié)點(diǎn)來(lái)構(gòu)成能夠反映問(wèn)題語(yǔ)義的子圖.從大量的候選結(jié)點(diǎn)中構(gòu)成子圖的搜索空間非常巨大,如何高效地生成子圖并度量其優(yōu)質(zhì)程度是問(wèn)題的重中之重.最后,將生成的子圖擴(kuò)展成為連通的子圖返回給用戶(hù).因此,本階段可分為兩個(gè)部分:子圖的生成與度量,子圖的擴(kuò)展與推薦.

2.4.1 子圖的生成與度量

本文從兩個(gè)方面來(lái)評(píng)價(jià)子圖的質(zhì)量:一是子圖中的結(jié)點(diǎn)與問(wèn)題之間的文本相似程度盡可能地高,每個(gè)結(jié)點(diǎn)的文本相似程度即結(jié)點(diǎn)的權(quán)重w(v);二是子圖中結(jié)點(diǎn)之間的距離越近越好,這將起到消除歧義的作用.比如子圖中的一個(gè)結(jié)點(diǎn)是Document類(lèi),現(xiàn)在有兩種同名的方法add,它們的文本相似程度是相同的,那么距離Document類(lèi)更近的那個(gè)方法更可能是相關(guān)的,而距離遠(yuǎn)的結(jié)點(diǎn)可能是一個(gè)屬于其他類(lèi)的方法,與本問(wèn)題無(wú)關(guān).

首先,我們定義如何從候選結(jié)點(diǎn)的集合中選擇子圖的頂點(diǎn)集.

頂點(diǎn)集.CandidateQ={C1,…,Cn}構(gòu)成的子圖G′的頂點(diǎn)集V′={Ci,j|xi,j=1},其中,xi,j是二元變量,表示Ci中的第j個(gè)結(jié)點(diǎn)是否被選中,滿(mǎn)足約束條件.

這里的第1個(gè)約束條件是為了使問(wèn)題中的每個(gè)詞所對(duì)應(yīng)的候選結(jié)點(diǎn)集合中至少有1個(gè)結(jié)點(diǎn)被選中,以此保證對(duì)原問(wèn)題語(yǔ)義的覆蓋度.另外,同一個(gè)結(jié)點(diǎn)可能在不同的集合中重復(fù)出現(xiàn),因此只要該結(jié)點(diǎn)在某個(gè)集合中被選中,則其他集合中也必須選中它,這就由第2個(gè)約束條件保證.

接下來(lái),我們定義一個(gè)子圖G′的度量函數(shù):

其中的距離dist(u,v)即第 2.2節(jié)中所述的使用圖嵌入向量計(jì)算的歐氏距離.子圖的生成過(guò)程即求解這個(gè)優(yōu)化問(wèn)題 minscore(G′),這可以看成一個(gè)二次優(yōu)化問(wèn)題.為了方便求解,本文提出一種基于柱狀搜索(beam search)的方法.柱狀搜索可以看作對(duì)貪心法的一種優(yōu)化,每次將保留前k個(gè)最佳的候選結(jié)果.具體如算法1所示.

算法1.柱狀搜索子圖.

輸入:候選結(jié)點(diǎn)集合CandidateQ={C1,…,Cn}.

輸出:排名最高的一個(gè)子圖.

對(duì)于輸入的候選結(jié)點(diǎn)集合,按權(quán)值排序后取最高的k個(gè)結(jié)點(diǎn)作為起始結(jié)點(diǎn),其中,參數(shù)k就代表著柱狀的大小(beam size).第7行～第10行是先根據(jù)公式(5)中的度量函數(shù)計(jì)算加入當(dāng)前結(jié)點(diǎn)后增加的代價(jià),然后生成一個(gè)新的子圖加入候選集合中,并計(jì)算累積的代價(jià).第13行、第14行仍是只保留列表中排序靠前的k個(gè)結(jié)果.最后,我們返回排名最高的一個(gè)子圖.

2.4.2 子圖的擴(kuò)展與推薦

利用圖嵌入的向量來(lái)計(jì)算距離,帶來(lái)了計(jì)算的便利和速度的提升,但由于在選擇結(jié)點(diǎn)的過(guò)程中我們并沒(méi)有考慮實(shí)際存在的邊,因此到目前為止,我們只得到了子圖的頂點(diǎn)集.為了給用戶(hù)提供更形象地理解,我們應(yīng)該將這些結(jié)點(diǎn)是如何連接起來(lái)的一同展示給用戶(hù),即從頂點(diǎn)集擴(kuò)展成一個(gè)連通的子圖.

本文利用將這個(gè)問(wèn)題定義成給頂點(diǎn)集V′構(gòu)造一棵最小生成樹(shù)(minimum spanning tree,簡(jiǎn)稱(chēng)MST),將V′中任意兩個(gè)頂點(diǎn)之間的最小跳數(shù)定義為它們之間的邊的權(quán)重,這樣做就意味著用盡可能少的邊將所有頂點(diǎn)連接起來(lái).具體算法如下表的算法2所示,其中,第5行的FindShortestPath函數(shù)即尋找結(jié)點(diǎn)集合X和Y之間最短路徑,而每?jī)蓚€(gè)結(jié)點(diǎn)之間的最短路徑可以通過(guò)Cypher語(yǔ)句在代碼圖中進(jìn)行查詢(xún);第8行、第9行是將這條路徑上所經(jīng)過(guò)的結(jié)點(diǎn)和邊都加入到擴(kuò)展后的子圖中.直到所有結(jié)點(diǎn)都被包含進(jìn)來(lái),該算法便得到了一個(gè)連通的子圖.

算法2.擴(kuò)展為連通子圖.

輸入:頂點(diǎn)集V′.

輸出:擴(kuò)展后的子圖Ge.

3 實(shí)驗(yàn)與實(shí)例

基于上述方法,本文設(shè)計(jì)并實(shí)現(xiàn)了基于圖嵌入的軟件 API檢索工具原型.下面我們通過(guò)一些實(shí)驗(yàn)來(lái)驗(yàn)證本文所提出方法和工具的有效性.這些實(shí)驗(yàn)主要用于回答下列研究問(wèn)題.

· 研究問(wèn)題1:本文所提出的方法是否能夠有效地定位用戶(hù)所需要的API?

本文方法將源代碼組織成代碼結(jié)構(gòu)圖的形式而非僅視為純文本來(lái)處理,其中利用了圖嵌入技術(shù),定義了子圖的度量函數(shù),并使用基于柱狀搜索的算法進(jìn)行代碼子圖的檢索.我們希望本文所提出的方法在回答開(kāi)發(fā)者提出的實(shí)際自然語(yǔ)言問(wèn)題時(shí),能夠有效提升軟件項(xiàng)目API檢索的效果.為了驗(yàn)證這一點(diǎn),我們選擇了兩個(gè)著名的開(kāi)源項(xiàng)目以及與它們相關(guān)的自然語(yǔ)言問(wèn)題進(jìn)行了驗(yàn)證,并與傳統(tǒng)基于文本匹配的方法進(jìn)行了對(duì)比.

· 研究問(wèn)題2:本文中所提出的圖嵌入方法與現(xiàn)有其他檢索方法相比效果如何?

在本文所提出的方法中,我們使用了圖嵌入方法來(lái)挖掘代碼圖的結(jié)構(gòu)信息,在度量結(jié)點(diǎn)之間的距離時(shí),使用圖嵌入向量之間的距離,并由此定義了子圖的度量函數(shù).我們關(guān)心圖嵌入方法是否能夠有效地表達(dá)代碼結(jié)構(gòu)圖中蘊(yùn)含的語(yǔ)義信息,從而改進(jìn)代碼檢索的效果.因此,我們?cè)O(shè)計(jì)了相應(yīng)的實(shí)驗(yàn),將本文所使用的圖嵌入方法與現(xiàn)有的基于最短路徑的方法進(jìn)行了對(duì)比,以驗(yàn)證圖嵌入方法的有效性.

3.1 實(shí)驗(yàn)設(shè)計(jì)

我們選取了兩個(gè)著名的開(kāi)源軟件項(xiàng)目——Apache Lucene和Apache POI作為實(shí)驗(yàn)對(duì)象,自動(dòng)構(gòu)造了這兩個(gè)項(xiàng)目的代碼圖,并分別對(duì)其進(jìn)行了基于自然語(yǔ)言的代碼檢索實(shí)驗(yàn).實(shí)驗(yàn)設(shè)計(jì)的細(xì)節(jié)列舉如下.

3.1.1 代碼圖構(gòu)造

對(duì)于每個(gè)軟件項(xiàng)目,我們基于它的源代碼中構(gòu)建一個(gè)代碼結(jié)構(gòu)圖.Lucene和POI項(xiàng)目的源代碼都可以通過(guò)其官網(wǎng)的連接或 Github直接下載.一個(gè)軟件項(xiàng)目往往會(huì)有很多個(gè)不同的版本,我們選取了這兩個(gè)項(xiàng)目其中被廣泛使用版本進(jìn)行代碼結(jié)構(gòu)圖的提取.與代碼結(jié)構(gòu)圖相關(guān)的統(tǒng)計(jì)信息在表2中進(jìn)行了展示,包括源代碼版本、類(lèi)或接口的結(jié)點(diǎn)數(shù)量、方法的結(jié)點(diǎn)數(shù)量、關(guān)聯(lián)關(guān)系的數(shù)量以及構(gòu)造時(shí)間.我們?cè)谝慌_(tái)3.40GHz雙核處理器、8GB內(nèi)存的服務(wù)器上,解析生成兩個(gè)項(xiàng)目的代碼結(jié)構(gòu)圖的時(shí)間開(kāi)銷(xiāo)分別為39min和31min.

Table 2 Information of code graphs for experimental projects表2 實(shí)驗(yàn)所用項(xiàng)目的代碼圖信息

在Chan等人的工作中,他們實(shí)驗(yàn)所使用的源代碼數(shù)據(jù)是JSE,它是一個(gè)非常通用的底層函數(shù)庫(kù).本文所關(guān)注的問(wèn)題是在軟件項(xiàng)目復(fù)用時(shí)如何有效進(jìn)行 API檢索,我們實(shí)驗(yàn)中使用的 Lucene和 POI是領(lǐng)域特定的函數(shù)庫(kù)/軟件項(xiàng)目.基于功能實(shí)現(xiàn)的需要,其API之間的關(guān)聯(lián)往往非常緊密,使得這類(lèi)領(lǐng)域特定的軟件項(xiàng)目在實(shí)際中的進(jìn)行代碼檢索和復(fù)用的難度更大.從表2中可以看出,Lucene項(xiàng)目代碼圖中,結(jié)點(diǎn)(類(lèi)和方法等)數(shù)量是39 000左右,但它們之間的關(guān)聯(lián)關(guān)系數(shù)量達(dá)到了255 000.同時(shí),在POI項(xiàng)目的代碼圖中結(jié)點(diǎn)數(shù)和關(guān)聯(lián)關(guān)系的數(shù)量關(guān)系也與此類(lèi)似.

3.1.2 API檢索問(wèn)題

進(jìn)行 API檢索的自然語(yǔ)言提問(wèn)多種多樣,為了保證問(wèn)題的真實(shí)有效性,本文使用了2種客觀(guān)的方式來(lái)獲得實(shí)驗(yàn)所需的問(wèn)題.

· 對(duì)于 POI項(xiàng)目,我們通過(guò)其官方網(wǎng)站上提供的用戶(hù)指南(https://poi.apache.org/spreadsheet/quick-guide.html),抽取了20個(gè)問(wèn)題作為第1組Query.每一個(gè)問(wèn)題在用戶(hù)指南中都有對(duì)應(yīng)的示例代碼,我們將這些示例代碼中涉及的API標(biāo)注為該問(wèn)題的groundtruth.

· 對(duì)于Lucene項(xiàng)目,由于其官方網(wǎng)站上沒(méi)有相關(guān)教程和示例代碼,我們使用StackOverflow上關(guān)于Lucene項(xiàng)目的問(wèn)答帖子作為來(lái)源,采取隨機(jī)抽樣的方法,直到挑選出 20個(gè)與源代碼檢索相關(guān)的問(wèn)題作為第 2組Query.具體抽取方法是:首先,從StackOverflow上2008年～2016年的數(shù)據(jù)中找出帶有Lucene標(biāo)簽的問(wèn)題,并按照問(wèn)題的投票為正,問(wèn)題有被接受的答案,答案中含有代碼片段的條件進(jìn)行篩選,得到了923個(gè)問(wèn)題,再?gòu)倪@些候選問(wèn)題中進(jìn)行無(wú)放回的隨機(jī)抽取,人工閱讀是否屬于源代碼檢索相關(guān)的問(wèn)題,直到挑選出20個(gè)相關(guān)問(wèn)題;其次,由于這些問(wèn)題在StackOverflow上分為標(biāo)題和內(nèi)容兩部分,且標(biāo)題基本上都可以作為其內(nèi)容概括,本文就以問(wèn)題的標(biāo)題作為代碼檢索工具的查詢(xún)輸入,即 Query.針對(duì)這 20個(gè)Query,我們還需要確定其對(duì)應(yīng)的目標(biāo)API.為此,我們組織了3名熟悉Lucene項(xiàng)目的研究生,分別閱讀了這些Query在StackOverflow上的問(wèn)題和答案,結(jié)合帖子的答案和源代碼的相關(guān)知識(shí),在代碼圖上進(jìn)行標(biāo)注.具體的標(biāo)注過(guò)程是:開(kāi)發(fā)人員以該問(wèn)題答案中出現(xiàn)的代碼片段為基準(zhǔn),并結(jié)合源代碼的相關(guān)文檔,利用代碼圖數(shù)據(jù)庫(kù)的查詢(xún)結(jié)果,最終確定該Query對(duì)應(yīng)的API集合.

本文實(shí)驗(yàn)所使用的問(wèn)題是開(kāi)發(fā)者在實(shí)際開(kāi)發(fā)過(guò)程中遇到的、真實(shí)存在的、用自然語(yǔ)言表述的問(wèn)題,其中部分問(wèn)題及其標(biāo)注見(jiàn)表3,問(wèn)題之中可能含有代碼元素的名稱(chēng),比如lengthNorm,也可能沒(méi)有.因此我們認(rèn)為,對(duì)這些問(wèn)題的解答,可以很好地反映各種方法的實(shí)際效果.

Table 3 Examples of query and annotated API表3 問(wèn)題與標(biāo)注API示例

3.1.3 比較對(duì)象

為了考察本文工作的實(shí)際效果,我們首先分析比較了本文方法在檢索過(guò)程中選擇第1個(gè)結(jié)果和選擇前3個(gè)結(jié)果的情況;其次,我們將這兩種情形與其他兩種典型的代碼檢索方法進(jìn)行了對(duì)比.實(shí)驗(yàn)方法包括以下幾種.

(1) 本文方法(Top 1).這一檢索方法只采用了本文基于圖嵌入的代碼檢索方法的第1個(gè)結(jié)果.

(2) 本文方法(Top 3).這一檢索方法采用了本文基于圖嵌入的代碼檢索方法的前3個(gè)結(jié)果.

(3) 基于文本匹配的方法.這一檢索方法只考慮問(wèn)題與結(jié)點(diǎn)的文本相似度進(jìn)行匹配,而不考慮結(jié)點(diǎn)之間的距離因素,即第2.4.1節(jié)中子圖的度量函數(shù)公式(5)中只含權(quán)重部分而沒(méi)有距離部分.

(4) 基于最短路徑的方法.這一檢索方法來(lái)源于 Chan等人的工作,其采用最短路徑來(lái)計(jì)算兩個(gè)結(jié)點(diǎn)之間的距離,而非本文方法中使用的圖嵌入向量之間的距離.

3.1.4 評(píng)價(jià)指標(biāo)

為了評(píng)價(jià)檢索結(jié)果的好壞,本文使用了準(zhǔn)確率(precision)、召回率(recall)和F1-值(F1-score)作為評(píng)價(jià)指標(biāo).準(zhǔn)確率和召回率的計(jì)算與真陽(yáng)性(true positive)等概念有關(guān),其定義見(jiàn)表4.

Table 4 Metrics for search results表4 檢索結(jié)果的度量指標(biāo)

在本文的實(shí)驗(yàn)中,準(zhǔn)確率和召回率的定義如公式(6)、公式(7)所示.

其中,VH標(biāo)注結(jié)果的結(jié)點(diǎn)集合,VG本文工具返回結(jié)果的結(jié)點(diǎn)集合.這里的True positives即兩個(gè)集合的交集,F1值即準(zhǔn)確率和召回率的調(diào)和平均數(shù).

3.2 檢索實(shí)例

針對(duì)表3中的實(shí)驗(yàn)問(wèn)題1“how to set document boost attribute in Lucene?”,本文在Lucene軟件項(xiàng)目的代碼圖上進(jìn)行了檢索實(shí)驗(yàn).首先,這個(gè)問(wèn)題被預(yù)處理后的單詞集合為{set,document,boost,attribute},對(duì)于集合中每一個(gè)單詞,根據(jù)第 2.3.2節(jié)中提到的匹配方法,分別得到了{(lán)1623,1101,63,122}個(gè)對(duì)應(yīng)的候選結(jié)點(diǎn),可以看出,候選結(jié)點(diǎn)的規(guī)模相當(dāng)龐大.接著,我們針對(duì)每個(gè)候選結(jié)點(diǎn)計(jì)算與問(wèn)題相關(guān)程度作為該結(jié)點(diǎn)的權(quán)重,比如setBoost結(jié)點(diǎn)的權(quán)重為0.75,Attribute結(jié)點(diǎn)的權(quán)重為0.4,在這些候選結(jié)點(diǎn)的基礎(chǔ)上,按照第2.4節(jié)中的算法構(gòu)造問(wèn)題檢索對(duì)應(yīng)的子圖.這里分為兩個(gè)部分.

1)子圖的生成:基于離線(xiàn)完成的圖嵌入向量的結(jié)果可以計(jì)算兩個(gè)結(jié)點(diǎn)之間的距離,比如Document結(jié)點(diǎn)和setBoost結(jié)點(diǎn)之間距離為13.47,根據(jù)本文定義的目標(biāo)函數(shù),通過(guò)柱狀搜索算法可以得到子圖中應(yīng)該包含的候選結(jié)點(diǎn)為{Document,Attribute,setBoost}.

2)子圖的擴(kuò)展:采用基于最小生成樹(shù)的方法將子圖中的結(jié)點(diǎn)擴(kuò)展為連通的代碼子圖,得到的結(jié)果如圖4(a)所示,最終的連通子圖共包含了8個(gè)結(jié)點(diǎn).

Fig.4 Search result for query “how to set document boost attribute”圖4 問(wèn)題“how to set document boost attribute”的檢索結(jié)果

根據(jù)問(wèn)題的檢索結(jié)果,我們可以計(jì)算對(duì)應(yīng)的準(zhǔn)確率、召回率和F1值.在圖4中,用方框標(biāo)出的5個(gè)結(jié)點(diǎn)是該問(wèn)題被人工標(biāo)注的API,而其余3個(gè)結(jié)點(diǎn)則不屬于被標(biāo)注的.所以該檢索結(jié)果的準(zhǔn)確率為5/8.而由于方框的5個(gè)結(jié)點(diǎn)剛好覆蓋了全部標(biāo)注的API,因此該結(jié)果的召回率為1,最終得到的F1值為10/13.

本文的檢索結(jié)果是一個(gè)子圖,不僅展示了用戶(hù)需要的目標(biāo) API,還展示了其與相關(guān)代碼元素的關(guān)聯(lián).在此基礎(chǔ)上,用戶(hù)可以通過(guò)點(diǎn)擊圖中的 API結(jié)點(diǎn)顯示其對(duì)應(yīng)的代碼片段.如圖4(b)所示,就是在上述結(jié)果中點(diǎn)擊結(jié)點(diǎn)BoostAttributeImpl后,能夠看到對(duì)應(yīng)的代碼體.由此,該檢索結(jié)果能為用戶(hù)理解和復(fù)用API提供有效支持.

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

針對(duì)上述得到的兩組各20個(gè)問(wèn)題,本文對(duì)比了上述4種方法檢索結(jié)果的平均準(zhǔn)確率、召回率和F1值等評(píng)價(jià)指標(biāo),實(shí)驗(yàn)結(jié)果見(jiàn)表5.實(shí)驗(yàn)環(huán)境是在Windows 10系統(tǒng),2.30GHz的雙核處理器,8GB內(nèi)存,Java版本是1.8.實(shí)驗(yàn)中,圖嵌入向量的維度設(shè)置為200,柱狀搜索中的柱大小(beamsize)設(shè)置為8.

Table 5 Experimental results analysis表5 實(shí)驗(yàn)結(jié)果分析

3.3.1 方法效果對(duì)比

從表5中可以看出,在Lucene和POI這兩個(gè)項(xiàng)目中,本文方法的Top3都同時(shí)獲得了最高的平均準(zhǔn)確率、召回率和F1值.而本文方法Top 1與Top 3的結(jié)果相差很小,說(shuō)明對(duì)于大部分問(wèn)題本文方法的Top 1就是最佳的結(jié)果.

基于文本匹配的方法在兩個(gè)項(xiàng)目中都獲得了最低的平均準(zhǔn)確率、召回率和F1值,表明單純利用問(wèn)題與結(jié)點(diǎn)的文本相似度而忽視代碼結(jié)構(gòu)圖中的語(yǔ)義信息,難以取得很好的效果.而本文引入圖嵌入技術(shù)挖掘代碼圖結(jié)構(gòu)的方法之后,檢索結(jié)果得到了顯著的提升.

基于最短路徑的方法在檢索過(guò)程中也利用到了代碼結(jié)構(gòu)圖的信息,只是在計(jì)算結(jié)點(diǎn)之間的距離時(shí)使用的最短路徑,而非本文方法中使用的圖嵌入向量之間的距離.該方法的效果與純文本匹配方法相比有了較大提升,但仍然顯著低于本文方法的結(jié)果.本文方法檢索結(jié)果的F1值比基于最短路徑的方法提高了10%,表明了圖嵌入方法的有效性,能夠比最短路徑方法挖掘到更全面的圖結(jié)構(gòu)信息.

此外,我們還對(duì)比了不同方法的平均響應(yīng)時(shí)間和最長(zhǎng)響應(yīng)時(shí)間.從表5中可以看出,純文本匹配方法的效率最高,平均響應(yīng)時(shí)間和最長(zhǎng)響應(yīng)時(shí)間都非常短,因?yàn)槠溆?jì)算十分簡(jiǎn)單,然而其檢索效果也是最不令人滿(mǎn)意的.而最短路徑方法的平均響應(yīng)時(shí)間則非常長(zhǎng),超過(guò)了1min,這對(duì)于實(shí)際的用戶(hù)交互而言難以接受.這是因?yàn)樵摲椒看斡?jì)算距離都需要在線(xiàn)查詢(xún)兩個(gè)結(jié)點(diǎn)之間的最短路徑,使用廣度優(yōu)先搜索的算法最壞情況下也需要O(N)的復(fù)雜度,這里的N表示所有結(jié)點(diǎn)的數(shù)量.圖嵌入過(guò)程由于離線(xiàn)已經(jīng)完成在線(xiàn)計(jì)算兩個(gè)向量的距離時(shí)只需要常數(shù)時(shí)間,所以本文方法在改進(jìn)檢索效果的同時(shí)也大大提升了運(yùn)行的效率.

Chan等人提出的方法是基于最短路徑方法,他們使用的子圖度量函數(shù)與本文有所差別,他們?cè)谡撐闹袌?bào)告的實(shí)驗(yàn)結(jié)果為準(zhǔn)確率0.53、召回率0.56、F1值0.54,與本文實(shí)驗(yàn)中最短路徑方法的結(jié)果十分接近.我們使用的數(shù)據(jù)集并不相同,他們的實(shí)驗(yàn)中所使用的問(wèn)題是從KodeJava網(wǎng)站上挑選的關(guān)于使用JSE編程的20個(gè)示例,并且將問(wèn)題抽取為多個(gè)詞組的形式作為輸入.而本文實(shí)驗(yàn)中使用的Lucene和POI則是領(lǐng)域特定的函數(shù)庫(kù),輸入也直接是自然語(yǔ)言的問(wèn)題.

3.3.2 準(zhǔn)確率與召回率分析

從實(shí)驗(yàn)結(jié)果來(lái)看,本文方法檢索的召回率比較高,但準(zhǔn)確率比較低.也就是說(shuō),代碼子圖中除了與Query相關(guān)的結(jié)點(diǎn)之外,還包含了較多無(wú)關(guān)的結(jié)點(diǎn).特別是對(duì)于 Lucene項(xiàng)目而言,準(zhǔn)確率和召回率的差別比較大,因此我們對(duì)Lucene項(xiàng)目的20個(gè)問(wèn)題做了進(jìn)一步的分析.

首先,我們對(duì)每個(gè)問(wèn)題的準(zhǔn)確率進(jìn)行了具體分析,結(jié)果如圖5所示.其中,斜線(xiàn)底色的柱形表示檢索結(jié)果中所有的結(jié)點(diǎn)(API)數(shù)量,純色柱形表示檢索結(jié)果中正確的結(jié)點(diǎn)數(shù)量.可以看到,在我們的檢索結(jié)果中,通常更多的API被返回和推薦出來(lái),大部分子圖的規(guī)模(結(jié)點(diǎn)數(shù))都在 5～8之間,只有兩個(gè)問(wèn)題的子圖大小達(dá)到了 10.經(jīng)分析發(fā)現(xiàn),導(dǎo)致這個(gè)問(wèn)題的主要原因是基于最小生成樹(shù)的子圖擴(kuò)展算法.由于很難斷定哪種類(lèi)型邊更加有益,我們將所有邊的權(quán)值都設(shè)為相同,從而產(chǎn)生了大量相同長(zhǎng)度的路徑,因而在擴(kuò)展路徑上很可能引入沒(méi)有被標(biāo)注的結(jié)點(diǎn).雖然我們不能確定這些更多的 API是必要的,但從召回率較高的事實(shí)出發(fā),也就是在保證能夠返回用戶(hù)所需API的情況下,我們相信,提供更多的信息對(duì)用戶(hù)理解和使用這些API仍然是有益的.而對(duì)子圖擴(kuò)展算法的優(yōu)化,可以作為本文的進(jìn)一步工作.

Fig.5 Precision of each question圖5 每個(gè)問(wèn)題的準(zhǔn)確率

我們對(duì)每個(gè)問(wèn)題的檢索召回率也進(jìn)行了具體分析,結(jié)果如圖6所示.其中,斜線(xiàn)底色的柱形表示人工標(biāo)注時(shí)的API結(jié)點(diǎn)數(shù)量,純色柱形表示檢索結(jié)果中正確的結(jié)點(diǎn)數(shù)量.從圖中可以看出,兩種柱形高度十分接近,表明整體的召回率很高.對(duì)于其中的10個(gè)實(shí)驗(yàn)示例而言,召回率都達(dá)到了100%,而召回率比較低的只有編號(hào)為13和15的兩個(gè)問(wèn)題,柱形高度之差為2.我們對(duì)這些召回率偏低的問(wèn)題進(jìn)行了分析,比如編號(hào)為15的問(wèn)題“How to query document have any term in a set?”,這里影響其實(shí)驗(yàn)效果的因素是自然語(yǔ)言的歧義性,問(wèn)題中的set是指集合的意思,而源代碼中則存在大量將 set作為動(dòng)詞使用的方法名.由于本文在解析問(wèn)題時(shí)只采用了簡(jiǎn)單的詞袋模型,目前尚無(wú)法很好地解決這類(lèi)歧義問(wèn)題.本文工具最終匹配到的是setTerm方法,因?yàn)樵摲椒ê袃蓚€(gè)與問(wèn)題相同的詞,結(jié)點(diǎn)的權(quán)重就很高.在未來(lái)工作中,我們將考慮利用代碼結(jié)構(gòu)圖和圖嵌入技術(shù)來(lái)盡可能地消除自然語(yǔ)言歧義,進(jìn)一步提升代碼檢索的效果.

Fig.6 Recall of each question圖6 每個(gè)問(wèn)題的召回率

3.4 有效性討論

· 實(shí)驗(yàn)評(píng)估的合理性.

本文工作的目標(biāo)是提高軟件項(xiàng)目 API檢索與復(fù)用的效率,檢索結(jié)果是一個(gè)代碼子圖.我們關(guān)注該子圖中的API及其關(guān)聯(lián)結(jié)點(diǎn)是否能夠解決開(kāi)發(fā)者的問(wèn)題.本文參考Chan等人的實(shí)驗(yàn)指標(biāo),使用準(zhǔn)確率、召回率和F值作為主要評(píng)價(jià),而非信息檢索中的 MRR等排名相關(guān)指標(biāo).而在進(jìn)行問(wèn)題答案的標(biāo)注過(guò)程中,我們從該問(wèn)題對(duì)應(yīng)的示例代碼中提取 API,并通過(guò)交叉驗(yàn)證等方式保證標(biāo)注結(jié)果的正確性和客觀(guān)性.由于實(shí)驗(yàn)的問(wèn)題都對(duì)應(yīng)有被接受的代碼片段,因此,如果檢索的子圖中包含了其中的 API,那么我們認(rèn)為它的確能夠幫助開(kāi)發(fā)者解決問(wèn)題.在未來(lái)工作中,我們也將考慮進(jìn)行用戶(hù)研究(UserStudy),以進(jìn)一步定量探討給開(kāi)發(fā)者帶來(lái)的提升效果.

· 影響實(shí)驗(yàn)結(jié)果的內(nèi)部因素.

關(guān)于檢索實(shí)例:本文針對(duì)Lucene和POI項(xiàng)目,分別通過(guò)兩組代碼檢索實(shí)例進(jìn)行了實(shí)驗(yàn),共40個(gè)問(wèn)題.盡管問(wèn)題數(shù)量有限,但我們相信這些問(wèn)題具有很好的代表性,不會(huì)影響實(shí)驗(yàn)結(jié)論:首先,我們選取的實(shí)驗(yàn)問(wèn)題源于實(shí)際,一組問(wèn)題來(lái)源于項(xiàng)目官網(wǎng)的用戶(hù)指南,另一組問(wèn)題來(lái)源于StackOverflow的帖子,這些問(wèn)題都是開(kāi)發(fā)過(guò)程中真實(shí)存在的,并且都有相應(yīng)的代碼片段,能夠保證問(wèn)題的較高質(zhì)量,而對(duì)于帖子的篩選和隨機(jī)抽取,也能夠保證其代表性;其次,問(wèn)題的數(shù)量對(duì)實(shí)驗(yàn)效果沒(méi)有明顯影響,在第 3.3.2節(jié)的實(shí)驗(yàn)中可以看到,單個(gè)檢索實(shí)例的評(píng)價(jià)指標(biāo)結(jié)果與所有實(shí)例的結(jié)果差異不大.在相關(guān)工作中,檢索實(shí)例的數(shù)量基本與本文相似.比如,CodeHow[6]使用了 34個(gè)問(wèn)題,Chan[10]使用了40個(gè)問(wèn)題.

· 影響實(shí)驗(yàn)結(jié)果的外部因素.

關(guān)于實(shí)驗(yàn)對(duì)比方法:由于本文不僅需要定位目標(biāo)API,還需要展示其與相關(guān)代碼元素的關(guān)聯(lián),為此,檢索結(jié)果是一個(gè)子圖.返回代碼片段或API列表的相關(guān)工作不適合與我們直接進(jìn)行比較.Chan等人的工作是目前與本文場(chǎng)景最接近的工作,其方法的本質(zhì)是基于最短路徑的.因此,本文實(shí)驗(yàn)中以最短路徑方法作為比較,能夠驗(yàn)證本文方法的有效性.

4 相關(guān)工作

本文的相關(guān)工作主要包括對(duì)源代碼API檢索和圖嵌入技術(shù)兩部分,圖嵌入技術(shù)已在第 1節(jié)進(jìn)行了介紹.本節(jié)主要介紹源代碼檢索與API推薦的相關(guān)技術(shù),重點(diǎn)關(guān)注的場(chǎng)景是針對(duì)源代碼的基于自然語(yǔ)言問(wèn)題檢索.

早期的源代碼檢索工作主要是將源代碼視為純文本,考慮查詢(xún)問(wèn)題與代碼之間的文本相似度進(jìn)行匹配,利用了TF-IDF,BM25等信息檢索技術(shù).Krugle,Ohloh和Sourcerer[4]就是其中的典型代表.Sourcerer將解析后的源代碼存儲(chǔ)在本地的關(guān)系型數(shù)據(jù)庫(kù)中,并利用Lucene進(jìn)行索引.這些方法的查詢(xún)方式通常是基于關(guān)鍵詞,返回結(jié)果是包含查詢(xún)中關(guān)鍵詞或正則表達(dá)式的代碼片段.然而,由于其缺乏對(duì)問(wèn)題語(yǔ)義的理解,這些工具的實(shí)際效果往往不夠令人滿(mǎn)意.

針對(duì)上述問(wèn)題,近來(lái)有許多研究工作結(jié)合了自然語(yǔ)言處理技術(shù),從深化問(wèn)題語(yǔ)義理解的角度提出了一系列的查詢(xún)精煉(query refinement)技術(shù)應(yīng)用于代碼檢索,包括查詢(xún)擴(kuò)展(query expansion)、查詢(xún)重構(gòu)(query reformulation)等.典型地,COCAB[18]從 StackOverflow 帖子含有的代碼片段中提取結(jié)構(gòu)化信息來(lái)增強(qiáng)用戶(hù)的查詢(xún),以此解決自然語(yǔ)言與代碼元素的詞匯不匹配問(wèn)題.SNIFF[19]先為代碼片段中的 API尋找到相應(yīng)文檔作為其注解,繼而在這些被注解過(guò)的代碼上進(jìn)行自然語(yǔ)言的查詢(xún).CodeHow[6]則是通過(guò)搜索在線(xiàn)文檔識(shí)別出一些與問(wèn)題相關(guān)的潛在A(yíng)PI,然后使用擴(kuò)展布爾模型將這些API的信息結(jié)合到代碼檢索的過(guò)程中去,從而提高準(zhǔn)確度.還有一些方法通過(guò)加入語(yǔ)義上相似的詞來(lái)擴(kuò)展用戶(hù)的自然語(yǔ)言查詢(xún),這些相似的詞可以來(lái)源于對(duì)網(wǎng)頁(yè)[20]或者軟件項(xiàng)目[9,21]的挖掘.DERECS[22]就預(yù)先構(gòu)造了一個(gè)包含大量代碼-描述對(duì)的語(yǔ)料庫(kù),利用它對(duì)缺少注釋的代碼進(jìn)行描述增強(qiáng).然而有研究表明:如果在擴(kuò)展查詢(xún)時(shí)引入了一些不合適的詞,將會(huì)導(dǎo)致更為糟糕的結(jié)果[23].另一些方法則擴(kuò)展了用戶(hù)的查詢(xún)方式,Gu等人[24]的工作中,用戶(hù)除了可以使用關(guān)鍵詞進(jìn)行查詢(xún),還可以加入代碼的語(yǔ)法和語(yǔ)義約束條件,從而實(shí)現(xiàn)更精確地檢索.Wang等人[25]提出了一種動(dòng)態(tài)的檢索方法,能夠結(jié)合用戶(hù)的反饋信息來(lái)優(yōu)化查詢(xún).Haiduc等人[26]提出了一個(gè)名為Refoqus的工具,能夠預(yù)測(cè)用戶(hù)查詢(xún)的質(zhì)量,并自動(dòng)推薦查詢(xún)重構(gòu)的策略.BIKER[27]從StackOverflow上抽取了相似的問(wèn)題和 API,并利用詞嵌入(word embedding)來(lái)計(jì)算文本描述的相似度.基于機(jī)器學(xué)習(xí)的代碼檢索和 API推薦工作也是目前的一個(gè)研究熱點(diǎn),比如,ROSF[28]先通過(guò)信息檢索的方法生成候選集,再利用有監(jiān)督學(xué)習(xí)為候選結(jié)果進(jìn)行重排序.DEEPAPI[29]使用RNN Encoder-Decoder模型,將自然語(yǔ)言問(wèn)題翻譯到API調(diào)用序列.Function Assistant[30]則利用語(yǔ)義解析的技術(shù),從代碼-文本對(duì)中提取特征學(xué)習(xí)翻譯模型.APIRec[31]從細(xì)粒度的代碼修改庫(kù)中訓(xùn)練統(tǒng)計(jì)學(xué)習(xí)的模型,基于上下文上進(jìn)行 API推薦.RecRank[32]則引入路徑相關(guān)的特征對(duì)APIRec的結(jié)果進(jìn)行重排序,從而提升了Top 1推薦的準(zhǔn)確率.雖然這些技術(shù)很大程度上提高了API定位的準(zhǔn)確度,但其需要積累和利用大量的輔助信息,在上述信息缺乏的情況下,往往不能達(dá)到預(yù)期效果.在本文工作中,我們尤其關(guān)注了在沒(méi)有輔助文檔信息和大量查詢(xún)歷史的前提下,如何借助代碼自身蘊(yùn)含的語(yǔ)義信息來(lái)輔助提升代碼檢索的效果.

由于現(xiàn)有代碼檢索工具往往返回問(wèn)題相關(guān)的代碼片段,缺乏對(duì)關(guān)聯(lián) API的說(shuō)明與展示,不便于用戶(hù)理解目標(biāo)API調(diào)用背后的邏輯關(guān)聯(lián),如調(diào)用鏈、類(lèi)圖等,來(lái)理解整體的概念[33,34].為此,一些工作開(kāi)始關(guān)注如何在定位與問(wèn)題相關(guān)API的同時(shí),整合、利用和展示代碼元素之間的關(guān)聯(lián)信息.典型地,McMillan和Chan等人的工作就將代碼組織成有向圖的結(jié)構(gòu),將代碼檢索問(wèn)題轉(zhuǎn)化為圖上的搜索問(wèn)題.McMillan等人提出的工具 Portfolio[9],利用了PageRank和SAN(spreading activation network)算法,返回圖上與問(wèn)題相關(guān)的前k個(gè)結(jié)點(diǎn)作為答案.而Chan等人的工作[10]則更進(jìn)一步地保證了返回結(jié)果是一個(gè)連通的子圖,從而能夠清晰地展現(xiàn)出各個(gè)結(jié)點(diǎn)之間的連接關(guān)系.RACS[35]針對(duì) JavaScript框架,構(gòu)建方法之間的調(diào)用關(guān)系圖,并將自然語(yǔ)言問(wèn)題也抽取為圖形式,尋找與問(wèn)題的圖結(jié)構(gòu)相似的代碼片段.許多其他工作也將同樣地思想用于文檔檢索、特征定位等諸多場(chǎng)景[36,37].受這些工作的啟發(fā),本文也將源代碼組織為有向圖的結(jié)構(gòu),利用了圖嵌入技術(shù)來(lái)挖掘圖結(jié)構(gòu)的深層信息,能夠更充分地考慮代碼圖的上下文信息;同時(shí),由于圖嵌入可以離線(xiàn)完成,提高了在線(xiàn)查詢(xún)算法的效率.

5 總結(jié)與展望

為了幫助用戶(hù)更好地檢索和復(fù)用軟件項(xiàng)目 API,本文提出了一種基于圖嵌入的軟件項(xiàng)目源代碼檢索方法.圖結(jié)構(gòu)能夠很好地反映軟件項(xiàng)目源代碼中 API之間的關(guān)聯(lián),幫助用戶(hù)理解軟件項(xiàng)目;圖嵌入技術(shù)能夠更充分地挖掘圖結(jié)構(gòu)的深層信息,并且可以離線(xiàn)完成,有效地提高檢索過(guò)程中生成子圖的效率.基于上述方法,我們?cè)O(shè)計(jì)并實(shí)現(xiàn)了相應(yīng)的軟件項(xiàng)目API檢索工具,并以開(kāi)源項(xiàng)目ApacheLucene和POI為例,通過(guò)相關(guān)實(shí)驗(yàn)驗(yàn)證了本文方法的有效性.

在未來(lái)的的工作中,我們將在圖嵌入技術(shù)的基礎(chǔ)上進(jìn)一步改進(jìn)問(wèn)題與結(jié)點(diǎn)的匹配方法,利用詞性、句法等自然語(yǔ)言處理技術(shù)更好地挖掘問(wèn)題的語(yǔ)義;同時(shí),在匹配過(guò)程中增加對(duì)邊的類(lèi)型的分析,在擴(kuò)展子圖時(shí)考慮路徑上其余結(jié)點(diǎn)與問(wèn)題的相關(guān)度,以減少不相關(guān)結(jié)點(diǎn)的引入,從而提升檢索的準(zhǔn)確率.此外,我們將進(jìn)一步探討在實(shí)際過(guò)程中用戶(hù)與搜索結(jié)果之間的交互會(huì)面臨的問(wèn)題,增強(qiáng)搜索結(jié)果的可讀性.