基于代碼結構知識的軟件文檔語義搜索方法?

林澤琦 , 鄒艷珍,3 , 趙俊峰,3 , 曹英魁 , 謝 冰

1(高可信軟件技術教育部重點實驗室(北京大學),北京 100871)

2(北京大學 信息科學技術學院,北京 100871)

3(北京大學(天津濱海)新一代信息技術研究院,天津 300450)

軟件復用是在軟件開發(fā)中避免重復勞動的解決方案,可以提高軟件開發(fā)的效率與質(zhì)量[1].近年來,隨著開源軟件的快速發(fā)展,互聯(lián)網(wǎng)上匯聚了大量可復用的軟件項目,例如Apache Lucene、Apache POI、JFreeChart等.這些軟件項目除了有源代碼之外,往往還包含數(shù)量龐大、類型各異的自然語言文本形式的文檔資源,例如用戶手冊、郵件歸檔、缺陷報告、用戶論壇討論等.這些文檔中蘊含著豐富的知識,能夠幫助軟件開發(fā)者學習與理解該軟件項目,從而更有效地對其進行復用.當軟件開發(fā)人員在復用一個軟件項目的過程中遇到問題,例如不知道一個功能的實現(xiàn)原理,或者是不知道一個需求應該被如何實現(xiàn)時,往往會在這些軟件文檔中進行搜索,以期找到一些相關的文本段落,其中包含可以用來回答該問題的信息.近年來,為項目內(nèi)的文檔資源提供搜索服務已經(jīng)成為開源軟件項目中最基本的輔助服務之一.如何提高軟件文檔搜索的準確率,已經(jīng)成為軟件復用領域的重要研究話題[2].

最基本也是最常見的軟件文檔搜索方法是基于關鍵詞匹配的,這種方法將軟件開發(fā)者輸入的自然語言形式的問題與各個文檔進行關鍵詞匹配,并將關鍵詞匹配程度最高的文檔作為搜索結果.這種方法沒有考慮到不同的詞之間是具有語義關聯(lián)的,因此搜索效果往往不夠理想.在信息檢索領域中,為了解決這一問題,相關研究工作主要分為兩類:其一是基于統(tǒng)計分析的方法,如潛在語義分析(latent semantic analysis,簡稱LSA)[3]、潛在狄利克雷分析(latent Dirichlet allocation)[4]、基于神經(jīng)語言模型的詞表示學習技術[5]等,此類方法依賴于訓練所用的語料庫,受數(shù)據(jù)稀疏和實際噪聲的干擾較大;其二是基于概念知識的方法[6?12],使用概念實體來表示自然語言文本的語義,并以概念實體之間的結構關聯(lián)關系來度量文本之間的語義相關度,此類方法直觀、有效,但需要用到互聯(lián)網(wǎng)上大型的通用概念知識庫(如WordNet、DBpedia、Freebase、Yago等).然而,這些通用概念知識庫中又往往不包含軟件項目中領域特定的概念知識.總的來看,軟件文檔中的數(shù)據(jù)稀疏現(xiàn)象較為明顯,這導致了基于統(tǒng)計分析的方法對搜索效果的改進是有限的.我們希望通過基于概念知識的方法來提升搜索效果,但其中亟待解決的問題是如何獲取軟件項目中領域特定的概念知識.

我們在研究中發(fā)現(xiàn),軟件項目中涉及的領域特定的概念實體大多都在這個軟件的開發(fā)過程中被定義成了諸如類、接口等的代碼元素,因此軟件項目的代碼結構圖在一定程度上表達了領域特定的概念知識,可以用來幫助機器理解自然語言文本的語義.基于這種思路,本文提出了一種基于代碼結構知識的軟件文檔語義搜索方法.更具體地:(1) 我們將這些代碼元素抽取出來用于表示領域特定的概念實體;(2) 抽取這些代碼元素之間的結構依賴關系(例如繼承關系、調(diào)用關系)可以體現(xiàn)出相應的概念實體之間的語義關聯(lián)關系,并利用它們來推理出文本之間的語義相關度.

與現(xiàn)有工作相比,本文的主要貢獻是:

(1) 提出一種基于代碼結構知識的文本語義表示方法,將文本的語義表示為代碼結構圖上的一個帶權子圖,從而實現(xiàn)了利用軟件項目源代碼中蘊含的概念知識來“解釋”文本的語義;

(2) 提出一種基于代碼結構知識的軟件文檔語義搜索方法,基于多關聯(lián)數(shù)據(jù)的表示學習技術,利用代碼元素間的結構依賴關系推理出文本間的語義相關度,從而解決了信息檢索技術未能考慮不同的詞之間的語義關聯(lián)的問題;

(3) 在StackOverflow數(shù)據(jù)集上對該方法進行了驗證,與其他多種信息檢索方法(包括向量空間模型、潛在主題建模、神經(jīng)語言模型等) 相比,本方法在平均準確率(mean average precision,簡稱MAP)指標上可以取得至少13.77%的效果提升.

本文第1節(jié)概述文本的研究目標與方法框架.第2節(jié)具體描述基于代碼結構知識的軟件文檔語義搜索方法的實現(xiàn)細節(jié),包括代碼結構圖提取、文檔語義表示、文檔語義相關度度量3個步驟.第3節(jié)介紹本文的實證研究,包括實驗設計、采用的評測數(shù)據(jù)集及評價指標以及實驗結果分析等.第4節(jié)與相關工作進行比較.第5節(jié)總結全文并對未來研究工作進行展望.

1 方法概覽

本節(jié)首先通過一個實際例子來更為直觀地說明本文的目標與基本方法,之后給出基于代碼結構知識的軟件文檔語義搜索方法的總體框架.

1.1 示例說明

文檔A和文檔B都是在線問答社區(qū)StackOverflow上的問題,它們都與開源軟件項目Apache Lucene有關.表1給出了這兩個問題的標題以及詳細描述.文檔A的答案中指出,文檔B所對應的問答對可以用于回答文檔A中所提出的問題.因此,我們認為文檔A和文檔B是高度語義相關的.然而文檔A和文檔B中所包含的詞匯的匹配程度并不高,因此在StackOverflow提供的基于詞匹配的信息檢索系統(tǒng)中,文檔B被排在了檢索結果中較為靠后的位置.

Table 1 Two sample documents selected from StackOverflow表1 從StackOverflow中選取的兩個示例文檔

為了解決這一問題,我們利用Apache Lucene項目源代碼中的概念知識作為橋梁來建立文檔A和文檔B間的語義關聯(lián)關系.這一想法主要分為兩個步驟:首先建立起文本中的詞匯與源代碼中的代碼元素之間的對應關系,從而能夠用源代碼中的概念知識來“解釋”文本的語義;之后,利用代碼元素在源代碼中的結構依賴關系,度量文本之間的語義相關度.以文檔A中的句子:“My problem is how to parse wildcard queries with Lucene that the query term is passed through a TokenFilter …”為例.該句中直接提及了Apache Lucene項目中的類TokenFilter.同時,該句中還包含關鍵詞:parse,wildcard,query和term.根據(jù)這些關鍵詞,我們可以合理地猜測出這個句子的語義與Apache Lucene項目中的類WildcardQuery、類QueryParser和類Term等代碼元素有關.基于這一思想,這個句子的語義可以用這些代碼元素的集合來表示.類似地,我們可以將文檔B的語義表示為由類Token、類TokenStream、方法TokenStream.incrementToken(?)、類AttributeSource等代碼元素構成的集合.我們基于TF-IDF技術[13]為這些代碼元素賦上權值,則每個文檔的語義就可以分別被表示為代碼結構圖上的一個帶權子圖.

圖1解釋了我們?nèi)绾卫迷创a中的概念知識作為橋梁來建立文檔A和文檔B之間的語義關聯(lián)關系.圖中展示了Apache Lucene項目的代碼結構圖的一小部分.在代碼結構圖中,每個結點代表一個代碼元素,而不同類型的有向邊則代表代碼元素間各種類型的結構依賴關系.與文檔A相關的代碼元素在圖中以網(wǎng)格線標記,而與文檔B相關的代碼元素則在圖中以淺灰色標記.由于在Apache Lucene項目的整個代碼結構圖中,兩類結點是很接近的,因此,即使文檔A和文檔B中所包含的詞匯的匹配程度并不高,我們也能根據(jù)代碼結構圖上的結構依賴關系來推理出文檔A和文檔B具有很高的語義相關度.

Fig.1 A brief illustration of how we can use conceptual knowledge in source code to capture the semantic relatedness between two documents圖1 如何利用軟件項目源代碼中的概念知識來度量文檔間的語義相似度的一個示例說明

綜上,為了實現(xiàn)基于代碼結構知識的軟件文檔語義搜索,需要解決兩個方面的關鍵問題:一是如何準確地將文本的語義表示為代碼結構圖上的一個帶權子圖;二是如何利用這些子圖在代碼結構圖上的結構依賴關系來計算文本的語義相關度.

1.2 方法框架

本文提出了一種基于代碼結構知識的軟件文檔語義搜索方法.圖2給出了該方法的整體流程.該方法主要由3部分構成.

(1) 代碼結構圖提取:這一部分用于從軟件項目的源代碼中提取出一個代碼結構圖.一個代碼結構圖由代碼元素(例如類、接口、方法等)以及這些代碼元素之間的結構依賴關聯(lián)(例如調(diào)用、繼承等)組成.在我們的方法中,代碼結構圖被作為軟件項目特定的概念知識庫來使用.

(2) 文檔語義表示:這一部分用于將文檔的語義表示為代碼結構圖上的一個帶權子圖.更具體地,我們基于詞匹配和文本上下文分析建立文檔中的詞匯與代碼結構圖中的代碼元素之間的關聯(lián)關系,并基于TF-IDF技術為這些代碼元素賦上權值.

(3) 文檔語義相關度度量:這一部分用于度量2個文檔之間的語義相關度.首先,我們基于多關聯(lián)數(shù)據(jù)的表示學習技術,利用代碼元素之間的結構依賴關聯(lián),計算不同的代碼元素在結構上的相似度;隨后,我們利用代碼元素在結構上的相似度來計算代碼結構圖上的2個帶權子圖在結構上的相似度,從而用這一相似度來度量2個文檔之間的語義相關度.在軟件文檔檢索系統(tǒng)中,我們使用得到的文檔語義相關度來對檢索結果進行重排序:如果一個文檔和查詢語句之間具有較高的語義相關度,則該文檔在檢索結果中應該被排在更加靠前的位置.

Fig.2 Workflow of the software text semantic search approach based on code structure knowledge圖2 基于代碼結構知識的軟件文檔語義搜索方法整體流程

2 方法實現(xiàn)

本節(jié)具體描述基于代碼結構知識的軟件文檔語義搜索方法的實現(xiàn)細節(jié),包括代碼結構圖提取、文檔語義表示、文檔語義相關度度量這3個步驟.

2.1 代碼結構圖提取

我們使用抽象語法樹解析器org.eclipse.jdt.core.ASTParser,從Java軟件項目的源代碼中提取代碼結構圖.在一個代碼結構圖中,結點代表源代碼中的代碼元素,結點間不同類型的有向邊代表這些代碼元素之間不同類型的結構依賴關系.在本方法中,我們考慮了4種類型的代碼元素:類、接口、方法和域.我們考慮了這些類型的代碼元素之間的11種類型的結構依賴關系,見表2.

Table 2 Eleven different edge types in code structure graphs表2 代碼結構圖中的11種結構依賴關系類型

2.2 文檔語義表示

文檔語義表示用于將文檔的自然語言文本表示為代碼結構圖上的一個帶權子圖.在這里,“文檔”并不限于軟件文檔中的一個文本段落,還包括軟件開發(fā)者輸入的文本形式的查詢語句.文檔語義表示的實現(xiàn)分為2個步驟:代碼元素識別與代碼元素權重度量.

2.2.1 代碼元素識別

文檔語義表示中,最關鍵的部分是識別出該文檔的語義該由該軟件項目中的哪些代碼元素來表示:首先,我們使用開源工具Recodoc[14]來識別出文檔中直接提及的代碼元素;其次,我們基于詞匹配對代碼元素進行擴充.

Recodoc是一個基于文本上下文分析的用于識別出文檔中直接提及的代碼元素的工具.例如,對于句子“My problem is how to parse wildcard queries with Lucene that the query term is passed through a TokenFilter …”,Recodoc能夠從中識別出類TokenFilter.然而,僅靠類TokenFilter是不足以表達這個例句的語義的.例如,由于句子中出現(xiàn)了 wildcard和 query這兩個關鍵詞,因此我們可以合理地猜測,這個句子和類WildcardQuery也是相關的.類似地,根據(jù)句子中的query,parser,term等關鍵詞,我們還可以識別出類QueryParser和類Term等代碼元素.盡管這些代碼元素并未在句子中被顯式地提及,但它們能夠體現(xiàn)出潛藏在句子的關鍵詞中的語義信息,因此它們也應該被加入到這個句子的語義表示中去.基于這一思想,我們采用了基于詞匹配的方法對代碼元素進行擴充.

首先,我們對每個文檔進行詞法預處理.我們使用空白字符與標點符號將文檔切分為詞袋,并使用停用詞表將其中的停用詞過濾掉.我們使用Porter詞根化算法(https://tartarus.org/martin/PorterStemmer/)對剩下的詞進行詞根化處理,最終得到了每個文檔的關鍵詞集合.

對于一個文檔中的每一個關鍵詞,我們從軟件項目的源代碼中找到所有標識符中包含這個關鍵詞的代碼元素,并將這些代碼元素的集合稱為這個關鍵詞的候選代碼元素集合.一個候選代碼元素集合可能會包含大量的候選代碼元素.例如,對于關鍵詞english,其候選代碼元素集合包含55個代碼元素,包括類EnglishStemmer、類EnglishAnalyzer、類EnglishPossessiveFilterFactory,等等.如果我們直接將這樣一個候選代碼元素集合用于文檔的語義表示,則計算代價巨大,且其中包含的大量噪音也會極大地影響計算效果.因此,基于對候選代碼元素集合的觀察,我們提出了3條啟發(fā)式規(guī)則,以對集合中的候選代碼元素進行過濾.

(1) 基于關鍵詞對候選代碼元素進行過濾.提出這一啟發(fā)式規(guī)則所基于的假設是:若一個代碼元素能夠匹配上更多的關鍵詞,則說明這個代碼元素更可能與這個文檔是語義相關的.例如,filter是一個文檔中的一個關鍵詞,類TokenFilter和類StopFilter是這個關鍵詞的2個候選代碼元素.該文檔還包含關鍵詞token,但不包含關鍵詞stop.類TokenFilter的標識符中的關鍵詞比率高于類StopFiler,這說明文檔中的關鍵詞 filter更有可能是指類TokenFilter,而不是類 StopFiler.因此在這種情況下,我們過濾掉類StopFilter,而留下類TokenFilter.

(2) 基于代碼元素類型對候選代碼元素進行過濾.我們認為,在軟件的源代碼中,軟件項目特定的概念知識主要是以類/接口的形式定義在項目的源代碼中的,而方法/域則主要用于描述這些概念中的具體細節(jié)與動作.因此,如果一個關鍵詞的候選代碼元素集合中既包含類/接口,也包含方法/域,則我們會過濾掉所有方法/域,留下所有類/接口.

(3) 基于代碼元素標識符長度對候選代碼元素進行過濾.提出這一啟發(fā)式規(guī)則所基于的假設是:若一個代碼元素的標識符中包含的無法與文檔中的關鍵詞相匹配的信息越多,則可以認為該代碼元素與這個文檔的語義相似度越低.例如,english是一個文檔中的一個關鍵詞,類 EnglishAnalyzer和類EnglishMinimalStemFilterFactory是這個關鍵詞的兩個候選代碼元素.在這種情況下,由于類EnglishMinimalStemFilterFactory的標識符的長度遠大于類 EnglishAnalyzer,我們會過濾掉類EnglishMinimalStemFilterFactory而留下類EnglishAnalyzer.在本方法中,我們將“長度遠大于”定義為超過5個字母或是超過1倍.

對于每個文檔,我們對其中的每個關鍵詞的候選代碼元素集合應用上述3條啟發(fā)式規(guī)則進行過濾,所得到的代碼元素集合即是用于表示該文檔的語義的子圖.

2.2.2 代碼元素權重度量我們基于TF-IDF技術為從文檔中識別出的代碼元素進行權重度量,從而將文檔的語義表示為代碼結構圖上的一個帶權子圖.首先,我們使用TF-IDF技術度量出文檔中的各個關鍵詞的權重;隨后,我們將該權重重新分配給這些關鍵詞所對應的代碼元素,如公式(1)與公式(2)所示.

在公式(1)和公式(2)中,wc表示代碼元素c的權重,C表示在文檔中識別到的所有代碼元素的集合,Tc表示與代碼元素c對應的所有關鍵詞的集合,Ct表示與關鍵詞t對應的所有代碼元素的集合.

經(jīng)過代碼元素識別與代碼元素權重度量,我們?yōu)槊總€文檔生成了代碼結構圖上的一個帶權子圖.我們使用這個帶權子圖來表示文檔的語義.

2.3 文檔語義相關度度量

文檔語義相關度度量部分通過計算文檔所對應的帶權子圖在代碼結構圖上的結構相關度來度量文檔之間的語義相關度,從而能夠對文本檢索的結果進行重排序.具體分兩步:代碼元素表示學習和子圖相關度度量.

2.3.1 代碼元素表示學習

代碼元素表示學習用于計算不同的代碼元素之間的相似度,這一步驟是在線下完成的.

在本方法中,我們將代碼元素間的相似度定義為:在代碼結構圖上,兩個代碼元素的上下文的相似度.這里的“上下文”是指代碼元素以何種類型的結構依賴關系關聯(lián)到哪個其他的代碼元素.例如,如果類A和類B都是類C的子類,則我們認為類A和類B比較相似;如果類A和類B還共同作為方法m的輸入?yún)?shù),則我們認為類A和類B應該具有更高的相似度.此外,我們認為代碼元素間的相似度是具有傳遞性的.例如,假設類A和類B具有很高的相似度,方法x和方法y分別用到了類A和類B,則我們認為方法x和方法y也具有較高的相似度.

我們使用多關聯(lián)數(shù)據(jù)表示學習算法TransR[15]來計算不同的代碼元素之間的相似性,其基本思想是:通過機器學習的方法,將代碼結構圖中的每個代碼元素表示為一個低維、實值的向量,兩個向量之間的距離越近,則說明這兩個向量所對應的代碼元素的相似度越高.TransR的基本假設是:存在一個K0維的向量空間,使得代碼結構圖中的每一個結點都可以表示為該空間中的一個向量.兩個向量之間的距離越近,則說明這兩個向量所對應的代碼元素的相似度越高.我們稱這個向量空間為主向量空間.同時,對于每種類型的結構依賴關系r,都存在一個與之對應的K1維的向量空間,我們稱其為面向關系類型r的向量空間.對于代碼結構圖中的任意一個結點e,我們將它在主向量空間中對應的向量記為e.我們使用3元組〈h,r,t〉來表示一條始于結點h、指向結點t、類型為r的邊.對于這樣一條邊,TransR算法首先將其首尾兩個結點通過一個與r有關的線性變換Mr映射到面向關系類型r的向量空間中去.

隨后,TransR算法在面向關系類型r的向量空間中對結點h與結點t所對應的向量進行線性約束,即

其中,r是一個與r有關的平移變換.fr(h,t)是用于進行學習的似然函數(shù),即如果3元組〈h,r,t〉存在于代碼結構圖中,則fr(h,t)應該盡可能地小;否則,fr(h,t)應該盡可能地大.綜合考慮所有可能的3元組的fr(h,t),就得到了總體的最小似然優(yōu)化函數(shù):

我們使用隨機批量梯度下降法,以L為目標進行最小似然優(yōu)化,從而訓練出模型參數(shù).這些參數(shù)包括每個結點對應的一個K0維的向量以及每種類型的結構依賴關系r所對應的一個K0×K1的線性變換Mr和一個K1維的平移變換r.在訓練過程中,我們限制所有向量的長度不超過1.

圖3對TransR的基本思想進行了簡單解釋.在圖3中,我們考慮方法m1以及被方法m1所調(diào)用的3種方法m2,m3和m4.如圖所示:對于這種情況,在面向關系類型methodInvocation的向量空間中,TransR傾向于將方法m2,m3和m4所對應的向量約束在一個以m1Mr+r為中心的小鄰域內(nèi),即m2Mr≈m3Mr≈m4Mr≈m1Mr+r.相應地,在主向量空間中,方法m2,m3和m4所對應的向量就被約束在同一個流型附近.因此,兩個結點在代碼結構圖中的上下文越相似,則用來約束它們的流型越多,它們的位置也就會越傾向于靠近.通過以L為最小似然函數(shù)的整體優(yōu)化,即可生成每一個結點在主向量空間中所對應的向量.兩個向量之間的距離越近,說明這兩個向量所對應的代碼元素的相似度越高.我們將兩個代碼元素a和b之間的相似度定義為1?|a?b|.

Fig.3 A brief illustration of TransR圖3 對TransR的簡單解釋

2.3.2 子圖相關度度量

在之前的文檔語義表示步驟中,我們將每個文檔的語義表示成為了代碼結構圖上的一個帶權子圖.在子圖相關度度量步驟中,我們將在代碼結構圖上計算兩個不同帶權子圖的相關度,以此來度量兩個文檔間的語義相關度.

首先,我們將代碼元素c到一個帶權子圖C的相似度定義為代碼元素c到C中的各個代碼元素的相似度的最大值,如公式(7)所示.

記Cq為查詢語句所對應的帶權子圖,Cd為一個候選文檔所對應的帶權子圖,我們定義Cq相對于Cd的相似度為

類似地,我們可以定義Cd相對于Cq的相似度sim(Cd→Cq):把公式(8)中的Cq和Cd進行交換即可.

之后,我們將Cq和Cd之間的相似度定義為

我們使用sim(Cq,Cd)來度量查詢語句q和候選文檔d之間的語義相關度,并使用它來對文本檢索系統(tǒng)的檢索結果進行重排序,從而實現(xiàn)語義搜索的效果,如公式(10)所示.

在公式(10)中,α是一個取值范圍在[0,1]區(qū)間上的實值超參數(shù);S0(d)表示文本檢索系統(tǒng)對文檔d的原始評分,一般而言,這一評分是基于該文檔與查詢語句的表層文本相似度的.通過正則化操作,我們將S0(d)的取值范圍限定在[0,1]區(qū)間上.sim(Cq,Cd)的取值范圍也是[0,1].之后,我們將S0(d)與sim(Cq,Cd)通過超參數(shù)α進行凸組合,從而實現(xiàn)對文本檢索系統(tǒng)的語義化重排序.

3 實驗與分析

為了驗證本文所提出的方法的有效性,我們基于StackOverflow數(shù)據(jù)集設計了一系列實驗.這些實驗用于回答下列研究問題.

· 研究問題1:本文所提出的方法是否能夠有效地改進軟件文檔檢索的效果?

我們關心本文所提出的方法在對文本檢索系統(tǒng)的檢索結果進行重排序后,是否能夠將有價值的文檔排在更靠前的位置.為了驗證這一點,首先,我們研究本方法中的超參數(shù)的選取;隨后,我們將本方法與多種已有的文本檢索方法進行對比.

· 研究問題2:本文中所使用的文本語義表示方法的有效性如何?

在本文所提出的方法中,我們將每個文檔的語義表示為代碼結構圖上的一個帶權子圖.我們關心這樣的一個帶權子圖是否能夠有效地表達文本內(nèi)容中蘊含的語義信息,從而改進軟件文檔檢索的效果.因此,我們設計了相應的實驗,將本文所使用的文本語義表示方法與若干變種方法進行對比,以驗證文中所述的方法的有效性.

· 研究問題3:本文中所使用的文本語義相關度度量方法的有效性如何?

在本文所提出的方法中,我們將代碼結構圖中的所有代碼元素映射到同一個低維、實值的向量表示空間中,再通過這些代碼元素的表示向量之間的距離作為橋梁來度量不同的文本之間的語義相關度.其中,我們將不同的代碼元素之間的相似度定義為在代碼結構圖上,兩個代碼元素的上下文的相似度.我們關心這樣的定義方式在文檔的語義搜索任務中是否有效.因此,我們設計了相應的實驗,將文本所使用的基于多關聯(lián)數(shù)據(jù)表示學習技術的代碼元素相似度計算方法與若干其他代碼元素相似度計算方法進行對比,以驗證本文中的文本語義相關度度量部分的有效性.

3.1 實驗設計

我們使用3個著名的Java開源軟件項目:Apache Lucene、Apache POI和JFreeChart作為我們的實驗對象.實驗任務為軟件文檔檢索,是在這3個項目上分別完成的.實驗設計的細節(jié)列舉如下.

3.1.1 文檔集

StackOverflow是一個著名的面向軟件開發(fā)者的在線問答社區(qū),其上積累了大量與軟件開發(fā)有關的問答形式的文檔.因此,我們從StackOverflow數(shù)據(jù)集中抽取出我們的實驗驗證所需的文檔集.對于上述的兩個用于實驗的開源軟件項目中的每一個項目,我們從StackOverflow上下載標簽中包含該項目名稱的所有相關的問答對,并將每個問題以及它所對應的被采納的答案定義為一個文檔.若一個問題沒有被采納的答案,則這個問題并不會被收錄到我們的文檔集中.這一做法是為了對文檔集中的文檔質(zhì)量進行保證.這樣,就分別為這3個軟件項目構造了一個文檔集.這3個文檔集的一些基本統(tǒng)計數(shù)據(jù),包括文檔數(shù)量、平均關鍵詞數(shù)量等,可在表3中找到.

Table 3 Various statistics from our dataset表3 實驗驗證數(shù)據(jù)集基本統(tǒng)計信息

3.1.2 代碼結構圖

對于每個軟件項目,我們的方法從它的源代碼中提取出了一個代碼結構子圖.一個軟件項目往往會有很多個不同的版本,我們選取其中最新的版本進行代碼結構圖的提取.與代碼結構圖相關的統(tǒng)計信息也在表3中進行了展示,包括源代碼版本、代碼元素數(shù)量、關聯(lián)關系數(shù)量.在一臺配置了3.40GHz雙核處理器的服務器上,解析生成3個項目的代碼結構圖的時間開銷分別為18min、31min和12min.

在我們的方法中,我們將每個文檔的語義表示為代碼結構圖上的一個帶權子圖.表3中的“文檔平均關聯(lián)到的代碼元素數(shù)量”這一列給出了這些帶權子圖中的平均結點數(shù)量.例如,“85.96(7.48)”是指,平均而言,每個文檔會被關聯(lián)到85.96個代碼元素,其中,有7.48個代碼元素是在文檔中被直接提及的.

3.1.3 測試集

為了驗證我們方法的有效性,對于每個軟件項目,我們從文檔集中隨機抽取出100個問題作為測試輸入.在被抽中后,這些問題所對應的文檔被我們從文檔集中刪去.我們的實驗任務是:對于每個問題,在文檔集中尋找可以用于回答該問題的文檔.

我們使用基于TF-IDF的向量空間模型實現(xiàn)了一個經(jīng)典的文本檢索系統(tǒng).我們對每個測試用的問題進行關鍵詞提取,形成查詢語句輸入到該文本檢索系統(tǒng)中,從而得到與各個問題在表層文本上具有較高相似度的文檔.對于每個問題,我們選取檢索結果中的前20個文檔作為候選文檔.我們的目標是對這20個文檔進行重排序,使得有價值的文檔能夠被重排序到更靠前的位置.為了得到測試集,我們讓3位計算機專業(yè)的高年級本科生對這些候選文檔進行標注.這些標注人員都有1年以上的Java編程經(jīng)驗,且都有過復用這3個開源軟件項目的經(jīng)歷.對于每個測試問題,我們將該問題以及這個問題的被采納的答案顯示給標注者.隨后,對于20個候選文檔,標注者分別將它們與已有的被采納的答案進行對比,以判斷這些文檔是否對解決該問題有價值.對于一個問題-文檔對,標注者可以對其標注“是”或者“否”.若3個標注者都將一個文檔標注為“是”,則我們認為該問題-文檔對是一個正樣本;否則,我們認為這個問題-文檔對是一個負樣本.圖4給出了各個問題所擁有的正樣本的數(shù)量分布.平均而言,對于每個問題,會有2.76個文檔被認為是對解決該問題有幫助的.

Fig.4 Distribution of the number of ground truth related documents圖4 各個問題所擁有的正樣本的數(shù)量分布

3.1.4 比較對象

我們將我們的方法記為CK(conceptual knowledge).我們將該方法與如下4個文本檢索方法進行對比.

(1) TF-IDF.這一文本檢索方法首先將每個文檔表示為詞向量空間中的一個TF-IDF向量,之后使用兩個向量之間的余弦相似度來度量文檔之間的相似度[13].

(2) Okapi BM25.這一文本檢索方法是TF-IDF方法的概率化改進,在信息檢索領域有著廣泛的應用[16].我們使用Apache Lucene中提供的Okapi BM25模塊來實現(xiàn)這一方法.

(3) LDA.LDA是一種在文本處理領域被廣泛使用的潛在主題生成模型,這一方法將每個文檔表示為若干個潛在主題上的一個分布[4].我們使用開源軟件項目mallet中提供的LDA模塊來計算每個文檔的主題分布(經(jīng)過手工調(diào)優(yōu),我們將LDA模型中的各個超參數(shù)的取值設置如下:主題個數(shù)k=100,α=0.5,β=0.01).之后,我們將每個主題分布視為一個向量,并使用KL距離來度量兩個文檔之間的相似度.

(4) Word2vec.Word2vec是一種在文本處理領域被廣泛使用的神經(jīng)語言模型,這一方法能夠從文本語料庫中的上下文信息中對各個單詞的語義進行表示學習,從而將各個單詞映射為一個低維、實值的向量表示空間中的詞向量[17].不同詞向量之間的距離越近,意味著所對應的兩個單詞之間的語義相似度越高.我們采用Ye等人提出的方法[18],以word2vec詞向量作為基本單元來計算兩個文檔間的相似度.

3.1.5 評測指標

我們使用信息檢索領域中一個被廣泛使用的評測指標,即平均準確率(MAP)來驗證我們的方法的有效性.簡單來說,對于多個測試點,平均準確率是指方法在每個測試點上的準確率的平均值.更具體地,公式(11)和公式(12)給出了平均準確率的定義.

其中,

·k是指檢索結果列表中的名次.

·P(k)是指在檢索結果的前k名中,正樣本所占的比例.

·rel(k)的取值為0或1.當其取值為1時,說明排在第k位的文檔是一個正樣本;否則,其取值為0.

例如,考慮一個查詢語句,有兩個文檔與其相關,它們分別被排在檢索結果中的第2位和第5位.在這種情況下,平均準確率為

3.2 實驗結果

本節(jié)主要分析研究問題1:本文所提出的方法是否能夠有效地改進軟件文檔檢索的效果?

在我們的方法中,我們將文檔和代碼之間的表層文本相似度和代碼結構上的語義相關度進行了線性結合,從而對文本檢索的結果進行重排序.α是一個超參數(shù),代表表層文本相似度在其中的占比.若α=0,則說明我們只考慮代碼結構上的語義相關度,而不考慮表層文本相似度;若α=1,則我們的方法退化為原始的文本檢索方法(即TF-IDF方法).圖5對于我們所選取的3個實驗用的軟件項目分別給出了不同的α取值對平均準確率的影響.

從圖5中可以看出,我們方法的效果明顯好于TF-IDF方法.這一提升是顯著且普遍的,以Apache Lucene項目為例,當α=0.7時,我們的方法達到了最高的平均準確率,為0.314;而TF-IDF方法的平均準確率為0.245(α=1).

此外,圖5還說明了將文檔和代碼之間的表層文本相似度和代碼結構上的語義相關度進行線性結合是有必要的.如果我們只考慮代碼結構上的語義相關度,而不考慮表層文本相似度(α=0),平均準確率就會明顯降低.

Fig.5 Effect of varying α on the MAP of our approach圖5 調(diào)整本方法中的超參數(shù)α對平均準確率MAP的影響

對于3個軟件項目,α的最佳取值分別為0.7,0.5和0.6.在下文中,我們保持這樣的取值.

在我們的方法中,代碼元素表示學習的步驟上還有兩個超參數(shù):K0和K1,代表向量空間的維度.我們在實驗過程中對這兩個超參數(shù)在100～500的范圍內(nèi)進行調(diào)整,發(fā)現(xiàn)它們對實驗結果的影響是很有限的.因此,我們在實驗的全過程中統(tǒng)一將它們設置為200.

圖6以平均準確率為指標,將我們的方法與TF-IDF方法、Okapi BM25方法、LDA方法和word2vec方法進行了對比.

Fig.6 Comparison of our approach and four other text retrieval approaches圖6 本方法與其他4種文本檢索方法的平均準確率效果對比

表4給出了各種方法在這3個項目上的平均MAP得分,以及它們相對TF-IDF方法的提升比率.

Table 4 Average MAP results across all the three software projects表4 各種方法在3個項目上平均MAP值

從圖6和表4中可以看出,我們的方法相對于TF-IDF方法能夠取得22.2%的效果提升,而表現(xiàn)第2好的word2vec方法的提升率僅為7.4%.因此,與其他文本檢索方法相比,我們提出的基于代碼結構知識的軟件文檔語義搜索方法的有效性是顯著的.

3.3 文本語義表示方法比較分析

本節(jié)主要分析研究問題2:本文中所使用的文本語義表示方法的有效性如何?

為了驗證本文所使用的文本語義表示方法的有效性,將我們的方法與如下兩種方法進行對比.

(1) CK-RecodocOnly.這一方法在我們方法的基礎上,對文本語義表示步驟進行了修改:用于表示文本語義的子圖中僅僅包含由Recodoc識別出的在文本中直接被提及的代碼元素,而不再包含基于詞匹配識別出的其他代碼元素.將我們的方法與這一方法進行比較分析的目的是驗證基于詞匹配對代碼元素進行擴充是有必要的.

(2) CK-UnWeighted.這一方法在我們方法的基礎上,對文本語義表示步驟進行了修改:不再為子圖中的代碼元素計算權重.將我們的方法與這一方法進行比較分析的目的是驗證代碼元素權重度量是有必要的.

圖7給出了我們的方法與這兩種方法的比較結果.可以看到,我們的方法達到的平均準確率顯著高于這兩種方法.例如,在 Apache Lucene項目中,我們的方法在α=0.7時達到了最高的平均準確率 0.314;對于CK-RecodocOnly方法,其最高準確率為0.257(α=0.9);對于CK-UnWeighted方法,其最高準確率為0.279(α=0.8).

Fig.7 Comparison between different conceptual document representation strategies圖7 文本語義表示方法比較分析結果

這一結果說明:

(1) 使用Recodoc識別出的文檔中直接被提及的代碼元素不足以用來表達文檔的語義.因此,基于詞匹配對代碼元素進行擴充是有必要的.

(2) 基于TF-IDF技術對子圖中的代碼元素進行權重度量能夠很好地提升文本語義表示的有效性.

3.4 文本語義相關度度量方法比較分析

本節(jié)主要分析研究問題3:本文中所使用的文本語義相關度度量方法的有效性如何?

為了驗證本文所使用的文本語義相關度度量方法的有效性,將我們的方法與如下兩種方法進行對比.

(1) CK-Coupling.這一方法在我們的方法的基礎上,對文本語義相關度度量步驟進行了修改:在計算兩個代碼元素之間的相似度時,使用由Briand等人提出的基于耦合度的算法[19],而不是我們的方法中提出的基于多關聯(lián)數(shù)據(jù)表示學習的算法.

(2) CK-ShortestPath.這一方法在我們的方法的基礎上,對文本語義相關度度量步驟進行了修改:在計算兩個代碼元素之間的相關度時,在代碼結構圖上使用基于Dijkstra最短路徑長度的算法,而不是我們的方法中提出的基于多關聯(lián)數(shù)據(jù)表示學習的算法.

圖8給出了我們的方法與這兩種方法的比較結果,可以看到,我們的方法達到的平均準確率顯著高于這兩種方法.例如,在Apache Lucene項目中,CK-ShortestPath方法在α=0.8時達到了最高的平均準確率0.248,而這一結果只是略微高于TF-IDF方法;而對于CK-Coupling方法,達到最高平均準確率的α值為1,這意味著其效果是低于TF-IDF方法的.這一實驗結果表明,我們將代碼元素之間的相似度定義為它們在代碼結構圖上的上下文相似度的做法是適合于文本語義相關度度量這一任務的.與我們的做法相比,其他代碼元素相似度的計算方法并不適合文本語義相關度度量任務.

Fig.8 Comparison between different code element pairwise similarity calculation strategies圖8 文本語義相關度度量方法比較分析結果

4 相關研究工作

本文的相關研究工作可分為兩類:(1) 軟件文檔檢索技術;(2) 基于概念知識的語義搜索技術.

4.1 軟件文檔檢索

在軟件工程領域中,信息檢索技術已被成功應用在各種類型的軟件文檔上,包括源代碼文件[20?25]、軟件文檔[26?29]、缺陷報告[30,31]、在線問答社區(qū)[32,33]等.

如何挖掘不同的詞之間的語義相關度,并用其來改進檢索效果,是信息檢索領域中的重要問題.在軟件工程中,從軟件文檔中挖掘不同的詞之間的語義相關度的代表性工作包括:Tian等人[34]基于點互信息PPMI對StackOverflow上的問答文檔進行挖掘,從而生成軟件項目特定的詞匯相似度數(shù)據(jù)庫;Ye等人[18]使用神經(jīng)語言模型對軟件項目的相關文檔進行分析,生成各個詞匯的低維實值詞向量,從而能夠度量不同的詞匯之間的相似度;Howard等人[35]和Yang等人[36]通過分析源代碼中的上下文來挖掘不同的詞匯之間的相似度;Wang等人[37]則通過分析FreeCode代碼庫中的標簽信息來挖掘不同的詞匯之間的相似度;Haiduc等人[2]提出了一種基于有監(jiān)督的機器學習的自動查詢重構方法Refoqus,以對查詢語句進行擴充;Panichella等人[38]提出了一種結合潛在主題建模技術和遺傳算法的軟件文檔檢索方法;等等.然而,上述方法都是基于對軟件文檔語料庫的統(tǒng)計分析的,其改進效果依賴于詞匯的特定模式在語料庫中的頻繁出現(xiàn).對于在語料庫中出現(xiàn)次數(shù)并不夠多的詞匯而言,這些方法難以挖掘出它們與其他詞匯的相似度.

此外,研究者們提出了多種基于非文本特征的軟件文檔檢索方法.例如,Ponzanelli等人[32]提出了一種面向StackOverflow問答文檔的檢索方法,在該方法中,問題評分、答案評分、用戶等級、問題標簽等非文本特征是檢索結果重排序的重要因素;Ye等人[25]提出了一種面向缺陷報告的源代碼文件檢索方法,該方法考慮了最近缺陷修復日期、缺陷修復頻率等非文本特征;Zou等人[39]提出了一種面向問題的軟件文檔檢索方法,該方法考慮了查詢語句中的疑問詞(例如“how”“why”,which”,等等)對檢索策略的影響.這些方法在特定的文本檢索任務中能夠有效地提升檢索效果,但這些特定的非文本特征不具有在各種類型的文檔中的可擴展性.例如,問題評分、答案評分、用戶等級、問題標簽等非文本特征能夠很好地改進針對StackOverflow問答文檔的檢索效果,但其他類型的文檔(如需求/設計文檔、缺陷報告、郵件歸檔等)并不具有這些特征,無法使用這些特征.

4.2 基于概念知識的語義搜索

近年來,隨著互聯(lián)網(wǎng)上大規(guī)模的通用概念知識庫(例如WordNet、DBpedia、Freebase、谷歌知識圖譜、Yago等)的飛速發(fā)展,研究者們提出了多種基于概念知識的語義搜索方法[6?12],以在信息檢索中發(fā)現(xiàn)并利用不同詞之間的語義相關度.在這里,概念知識是指現(xiàn)實世界中存在的各種實體以及這些實體之間的各種語義關聯(lián)關系.概念知識一般被表示為3元組,例如〈Michael_Jackson,publish_song,Billi_Jean〉,〈Barack_Obama,born_in,Honolulu〉等.基于概念知識的語義搜索的基本過程是:首先,識別出文檔中提及的實體;其次,利用實體之間的關聯(lián)關系來度量文檔之間的語義相關度;最后,利用得到的語義相關度對文本檢索的結果進行重排序.這些研究工作證明了引入額外的概念知識來幫助機器理解文本的語義能夠有效地解決詞匯間隙問題,改進文本檢索的效果.受到這些工作的啟發(fā),我們希望基于概念知識來實現(xiàn)軟件文檔的語義搜索.然而,軟件文檔中往往涉及到大量的軟件項目特定的概念知識,而互聯(lián)網(wǎng)上常用的大型通用知識庫中卻往往并不包含這些知識.因此,在軟件文檔上直接使用互聯(lián)網(wǎng)上常用的大型通用知識庫進行語義搜索所能達到的效果提升是非常有限的,我們需要尋找該軟件項目特定的概念知識來源.一些研究工作將專家構造的本體作為軟件項目特定的概念知識來源,以解決文本檢索中的詞匯間隙問題.然而,由專家構造本體的成本過高,這導致了此類方法的可用性不足.

本文提出,軟件項目特定的概念知識可以從該軟件項目的源代碼中抽取得到,并用于實現(xiàn)軟件文檔的語義搜索.在軟件工程的研究社區(qū)中,軟件源代碼中的結構依賴信息已經(jīng)被廣泛地應用在了多種自動軟件工程任務中[40?46],以幫助軟件開發(fā)人員在軟件的開發(fā)、維護和復用過程中對軟件項目進行學習與理解.McMillan等人[41]和Panichella等人[45]研究了如何將軟件源代碼中的結構依賴信息用作軟件項目特定的概念知識,從而在文本檢索任務中對查詢語句進行語義擴充.本文進一步研究如何利用從軟件項目源代碼中抽取出的軟件項目特定的概念知識來度量文檔之間的語義相關度,從而在語義層面上對文本檢索的結果進行重排序.

5 總結與展望

本文提出了一種基于代碼結構知識的軟件文檔語義搜索方法.在該方法中,我們的基本思想是:從軟件項目的源代碼中提取出代碼結構圖,以此作為先驗知識來幫助機器理解無結構的自然語言文本.更具體地,我們將每個文檔的語義表示為該代碼結構圖上的一個帶權子圖,并通過計算帶權子圖在代碼結構圖上的相似度來度量文檔之間的語義相關度.我們利用語義相關度對文本檢索系統(tǒng)返回的檢索結果進行重排序,從而實現(xiàn)了語義搜索.我們在StackOverflow數(shù)據(jù)集上對本方法的有效性進行了驗證.以平均準確率(MAP)作為評測指標,結果表明,本方法相對于其他文本檢索方法可以取得至少13.77%的效果提升.

我們下一步的工作計劃包括:研究如何改進本方法中的文本語義表示步驟,獲取能夠更準確地表示文本語義的帶權子圖;在更多類型的軟件文檔上驗證本方法的通用性和有效性,例如缺陷報告、需求文檔、設計文檔、郵件歸檔等等.