基于多特征權(quán)重分配的源代碼搜索優(yōu)化

李 陣，鈕 俊，王 奎，辛園園

(寧波大學(xué) 信息科學(xué)與工程學(xué)院 浙江 寧波 315211)

0 引言

在軟件開(kāi)發(fā)過(guò)程中，代碼復(fù)用是提高軟件開(kāi)發(fā)效率的重要手段。目前，互聯(lián)網(wǎng)中積累了大量的開(kāi)源代碼，如知名開(kāi)源庫(kù)GitHub[1]、OSChina[2]、CodePlex[3]等。在編制程序時(shí)，程序員可以對(duì)這些開(kāi)源代碼進(jìn)行復(fù)用，從而降低開(kāi)發(fā)成本。代碼搜索是對(duì)其復(fù)用的前提。如何從開(kāi)源軟件中準(zhǔn)確地提取高質(zhì)量的代碼資源并復(fù)用到軟件產(chǎn)品中，是提高軟件開(kāi)發(fā)效率需要解決的重要問(wèn)題。

針對(duì)代碼搜索算法輸入的不同形式，當(dāng)前已經(jīng)出現(xiàn)了基于關(guān)鍵字、接口、輸入輸出等形式的開(kāi)源代碼搜索引擎。不同于其他輸入形式的搜索方法，由于方法簽名是開(kāi)發(fā)者通過(guò)一些能表達(dá)方法功能的詞語(yǔ)根據(jù)駝峰命名法則命名的，所以基于關(guān)鍵字的搜索在匹配方法簽名時(shí)往往更能體現(xiàn)方法功能的匹配；但針對(duì)面向?qū)ο笳Z(yǔ)言開(kāi)發(fā)的開(kāi)源軟件，當(dāng)前基于關(guān)鍵字的搜索沒(méi)有考慮其源代碼具有多種代碼特征[2]，或者只考慮了用戶查詢(xún)語(yǔ)句與方法簽名的單一匹配而忽視了源代碼的其他重要特征如注釋、類(lèi)名等。比如源代碼注釋是對(duì)代碼功能的描述，其中含有能體現(xiàn)方法功能的大量信息，這些信息對(duì)搜索特定功能的源代碼是有幫助的。同理，類(lèi)名中也含有少量體現(xiàn)代碼功能的信息，而且源代碼中各特征之間會(huì)有一定的聯(lián)系。匹配時(shí)不能僅僅匹配單一方法名或者將多個(gè)代碼特征轉(zhuǎn)化成純文本進(jìn)行搜索而不考慮各代碼特征的重要度，因此，將方法簽名、源代碼注釋、方法體等代碼特征結(jié)合起來(lái)應(yīng)用于代碼搜索中。

源代碼的注釋有描述代碼功能的作用，根據(jù)描述的對(duì)象不同分為類(lèi)注釋與方法注釋。在代碼搜索中，對(duì)于代碼功能模塊來(lái)說(shuō)，當(dāng)搜索定位到方法為功能模塊的最小單位時(shí)，則與方法相關(guān)的代碼特征的重要程度會(huì)比較大。不同類(lèi)型的注釋對(duì)代碼搜索的準(zhǔn)確度都有貢獻(xiàn)，且貢獻(xiàn)度不一樣。方法注釋的貢獻(xiàn)度要大于類(lèi)注釋。文獻(xiàn)[5]雖然也是基于關(guān)鍵字搜索并考慮了多個(gè)代碼特征，但是沒(méi)有對(duì)注釋進(jìn)行分類(lèi)，且未區(qū)分不同類(lèi)型注釋的重要性程度。另外對(duì)于方法簽名來(lái)說(shuō)，開(kāi)發(fā)者在命名需要實(shí)現(xiàn)的功能模塊時(shí)，通常使用具有代表性的可以概括這些模塊功能的有意義的名稱(chēng)，但考慮名稱(chēng)的簡(jiǎn)潔性，方法簽名往往只是由若干個(gè)單詞組合而成，所以一個(gè)完整的方法簽名往往不能完全描述出方法實(shí)現(xiàn)的功能?？紤]到代碼注釋通常有描述方法功能的作用，注釋中往往含有方法簽名中未包含的關(guān)鍵詞。針對(duì)結(jié)合注釋的搜索在一定程度上滿足了基于語(yǔ)義的匹配。

搜索代碼時(shí)，將注釋與方法簽名和方法體等代碼特征分別與查詢(xún)語(yǔ)句進(jìn)行匹配。根據(jù)不同代碼特征的重要程度對(duì)匹配結(jié)果進(jìn)行加權(quán)組合，制定評(píng)分機(jī)制，得到代碼方法與查詢(xún)語(yǔ)句的相似度評(píng)分。根據(jù)結(jié)果評(píng)分對(duì)代碼方法進(jìn)行排序，得到結(jié)果列表。

1 相關(guān)工作

傳統(tǒng)源代碼搜索主要是識(shí)別用戶查詢(xún)語(yǔ)句與方法簽名之間的相關(guān)度而將相關(guān)度最大的方法返還給用戶，這在一定程度上忽視了源代碼的其他代碼特征。文獻(xiàn)[4]通過(guò)識(shí)別查詢(xún)語(yǔ)句與應(yīng)用程序編程接口(Application Programming Interface,API)的關(guān)系來(lái)提高搜索準(zhǔn)確度。文獻(xiàn)[5]通過(guò)分析查詢(xún)?cè)~在方法簽名中扮演的角色來(lái)確定相關(guān)的源代碼，并整合四個(gè)部分內(nèi)容：查詢(xún)?cè)~在剩余代碼中的使用率、查詢(xún)?cè)~在方法簽名中的語(yǔ)義角色、查詢(xún)?cè)~在方法簽名中的頭部距離以及分析源代碼的哪個(gè)位置比較有利于相關(guān)性最大化。文獻(xiàn)[6]通過(guò)對(duì)Google經(jīng)典算法PageRank的修改并應(yīng)用在代碼函數(shù)之間的調(diào)用上，從而找出“流行度”最大的函數(shù)，然后結(jié)合對(duì)源代碼內(nèi)容的匹配，返給用戶最相關(guān)的源代碼。文獻(xiàn)[7]通過(guò)代碼克隆技術(shù)，識(shí)別克隆代碼并根據(jù)函數(shù)調(diào)用關(guān)系找出被調(diào)用最多的克隆代碼。但這些研究都忽視了源代碼中一個(gè)比較重要的代碼特征：代碼注釋。

2 代碼搜索引擎結(jié)構(gòu)

源代碼搜索是將從開(kāi)源平臺(tái)上獲取的源代碼資源收集起來(lái)構(gòu)成本地代碼倉(cāng)庫(kù)；對(duì)倉(cāng)庫(kù)中的源代碼進(jìn)行預(yù)處理，建立源代碼對(duì)應(yīng)的抽象語(yǔ)法樹(shù)(Abstract Syntax Tree, AST)[8]并從中識(shí)別出對(duì)搜索有用的代碼特征并建立索引；用處理過(guò)的用戶查詢(xún)語(yǔ)句在索引文件中搜索出相關(guān)的代碼文件并計(jì)算相似度；根據(jù)相似度評(píng)分對(duì)結(jié)果進(jìn)行排序。具體流程如圖1所示。

圖1 代碼搜索引擎流程 Fig. 1 Flow chart of code search engine

2.1 源代碼處理

2.1.1 源代碼獲取

現(xiàn)在一些開(kāi)源搜索引擎如GitHub、CodePlex等積累了大量的開(kāi)源項(xiàng)目，這為源代碼搜索的研究提供了“原材料”。本文從GitHub中獲取源代碼。

2.1.2 代碼特征識(shí)別

本文從三個(gè)代碼特征：注釋、方法簽名、方法體入手，對(duì)獲取的源代碼進(jìn)行處理。通過(guò)建立并遍歷源代碼文件的AST，提取出源代碼中的這三種代碼特征。其中，方法模塊的功能往往需要包名、類(lèi)名和方法名的結(jié)合才能完整地描述出來(lái)。比如用戶希望搜索到連接MySQL數(shù)據(jù)庫(kù)的方法實(shí)現(xiàn)，識(shí)別出來(lái)的描述性的名稱(chēng)有包名:org.com.Mysql、類(lèi)名：Connection、方法簽名：getConnection()，此時(shí)識(shí)別完整路徑上的名稱(chēng)才能滿足精確的查找。重構(gòu)后的方法簽名為：org.com.Mysql.Connection.getConnection()。本文針對(duì)傳統(tǒng)的方法簽名進(jìn)行重構(gòu)，在原有的方法簽名前加上方法所屬類(lèi)的類(lèi)名及包名。

2.1.3 代碼特征索引的建立

對(duì)所有代碼特征進(jìn)行文本標(biāo)準(zhǔn)化，然后對(duì)代碼特征建立索引。在面向?qū)ο蟮恼Z(yǔ)言中，所有方法都隸屬于一個(gè)具體的類(lèi)，則針對(duì)每個(gè)方法可能存在對(duì)應(yīng)的方法注釋和屬于該類(lèi)的類(lèi)注釋。每一個(gè)代碼方法為一個(gè)搜索單位，建立索引時(shí)其對(duì)應(yīng)一個(gè)Document，而Document是Lucene框架中存放在索引中的對(duì)象，每個(gè)Document根據(jù)不同代碼特征分成多個(gè)域(Field)。因?yàn)獒槍?duì)注釋這一代碼特征來(lái)說(shuō)分為類(lèi)注釋與方法注釋?zhuān)栽谧⑨寣哟螌⒎譃閮蓚€(gè)域，最終針對(duì)索引中的Document會(huì)有4個(gè)域。這4個(gè)域隸屬于一個(gè)Document，也就是針對(duì)每個(gè)方法將4種代碼特征規(guī)約在一起。在建立索引的同時(shí)可以指定每個(gè)域所占有的權(quán)重。

2.2 搜索與排序

2.2.1 查詢(xún)語(yǔ)句預(yù)處理

本文假定用戶輸入的查詢(xún)語(yǔ)句為自然語(yǔ)言，這樣可以使具有不同開(kāi)發(fā)經(jīng)驗(yàn)的開(kāi)發(fā)者都可以使用代碼搜索引擎。軟件開(kāi)發(fā)初學(xué)者不必糾結(jié)于以何種格式的輸入才能準(zhǔn)確地找到結(jié)果，但是必須要對(duì)查詢(xún)語(yǔ)句作一定的處理，使之可以用來(lái)匹配我們識(shí)別出來(lái)的代碼特征。

2.2.2 搜索索引

在不同的域中，對(duì)建立的倒排索引進(jìn)行搜索，找出與查詢(xún)語(yǔ)句相關(guān)的Document。Document中的任何域?qū)?yīng)的代碼特征與查詢(xún)語(yǔ)句相關(guān)，則定義Document與之相關(guān)。將各種相關(guān)的代碼特征按照不同權(quán)重組合，給出多特征下的代碼特征總的相關(guān)度，這里的相關(guān)度是處理過(guò)的查詢(xún)語(yǔ)句與每個(gè)Document中4個(gè)域表示的代碼特征轉(zhuǎn)化為等維向量后的余弦相似度分?jǐn)?shù)。查詢(xún)語(yǔ)句與每種代碼特征的相關(guān)度分?jǐn)?shù)在沒(méi)有權(quán)重影響下取值區(qū)間為[0,1]，0表示查詢(xún)語(yǔ)句與該代碼特征不相關(guān)。其中任何一種代碼特征與查詢(xún)語(yǔ)句的相關(guān)度分?jǐn)?shù)不為零，則表明包含該代碼特征的Document是與查詢(xún)語(yǔ)句相關(guān)的，而Document對(duì)應(yīng)的代碼方法能被檢索到并返回。

2.2.3 排序

根據(jù)返回結(jié)果相似度分?jǐn)?shù)的高低，對(duì)返回結(jié)果進(jìn)行排序并將排好序的結(jié)果列表返回給用戶。

3 代碼注釋的提取與索引

源代碼的不同類(lèi)型注釋在相關(guān)度匹配中的重要程度不同。在以源代碼中的方法為搜索單位時(shí)，類(lèi)注釋的重要程度要小于方法注釋。根據(jù)重要程度對(duì)各類(lèi)型注釋賦予不同的權(quán)重。圖2 是識(shí)別并處理不同類(lèi)型注釋的流程。

3.1 注釋的提取

將源代碼轉(zhuǎn)換為對(duì)應(yīng)的抽象語(yǔ)法樹(shù)。抽象語(yǔ)法樹(shù)作為源代碼的語(yǔ)法結(jié)構(gòu)表示，在源代碼分析和代碼復(fù)用中起著重要作用。在抽象語(yǔ)法樹(shù)中每個(gè)節(jié)點(diǎn)都有相應(yīng)的節(jié)點(diǎn)類(lèi)型，根據(jù)不同節(jié)點(diǎn)類(lèi)型來(lái)訪問(wèn)節(jié)點(diǎn)的值。圖3所示為一般抽象語(yǔ)法樹(shù)的部分節(jié)點(diǎn)類(lèi)型樹(shù)。在EclipseJDT[9]中，抽象語(yǔ)法樹(shù)的根節(jié)點(diǎn)表示為CompilationUnit；在PackageDeclaration中獲取包名；在TypeDeclaration中包含類(lèi)注釋和類(lèi)名。BodyDeclaration節(jié)點(diǎn)下還有MethodDeclaration類(lèi)型的節(jié)點(diǎn)，可以從中獲取方法注釋、方法名和方法體。

圖2 不同類(lèi)型注釋處理流程 Fig. 2 Flow chart of processing different types of comments

圖3 抽象語(yǔ)法樹(shù)節(jié)點(diǎn)類(lèi)型樹(shù) Fig. 3 Node type tree of AST

本文使用EclipseJDT中的ASTParser與ASTNode對(duì)源代碼抽象語(yǔ)法樹(shù)進(jìn)行創(chuàng)建與訪問(wèn)。根據(jù)Java設(shè)計(jì)模式中的訪問(wèn)者模式編寫(xiě)訪問(wèn)類(lèi)，提取出不同類(lèi)型的注釋與相應(yīng)的方法簽名、類(lèi)名、包名以及方法體等代碼特征。

3.2 注釋及查詢(xún)預(yù)處理

對(duì)查詢(xún)語(yǔ)句及不同類(lèi)型的注釋進(jìn)行處理，包括文本標(biāo)準(zhǔn)化、去除停詞、詞干提取等操作。對(duì)其他種類(lèi)的代碼特征作同樣的預(yù)處理。

3.2.1 文本標(biāo)準(zhǔn)化

文本標(biāo)準(zhǔn)化主要包括去除代碼注釋與查詢(xún)語(yǔ)句中的標(biāo)點(diǎn)符號(hào)以及對(duì)其分詞。由于源代碼中的方法名基本上是由很多單詞組合在一起，通常是從第二個(gè)單詞開(kāi)始首字母大寫(xiě)，而注釋有對(duì)方法功能的語(yǔ)義描述功能，其中可能也存在組合的單詞。因此，本文采用大小寫(xiě)分詞算法[4]。Lucene檢索包中已經(jīng)封裝好了基本的分詞模塊。針對(duì)普通的英文語(yǔ)句，Lucene能進(jìn)行分詞并去除其中的停詞[10]以及詞干的提取，但是針對(duì)源代碼，開(kāi)發(fā)者往往在命名方法簽名時(shí)，通常使用駝峰命名法則，所以Lucene自帶的分詞模塊不能滿足針對(duì)源代碼的分詞。本文在Lucene分詞模塊的基礎(chǔ)上設(shè)計(jì)了針對(duì)駝峰命名的詞語(yǔ)的分詞模塊。

3.2.2 去除停詞

為了比較完整地描述方法的功能，開(kāi)發(fā)者往往會(huì)使用一些詞語(yǔ)修飾關(guān)鍵詞，這就會(huì)導(dǎo)致注釋中包含了一些對(duì)搜索沒(méi)有幫助的詞語(yǔ)，在搜索引擎領(lǐng)域中這樣的詞語(yǔ)稱(chēng)為停詞。本階段去除這些停詞，比如冠詞a、the，系動(dòng)詞 is、are和副詞how等。

3.2.3 詞干提取

由于自然語(yǔ)言中的英文單詞在句子中會(huì)根據(jù)不同語(yǔ)態(tài)使用相應(yīng)形式的單詞，針對(duì)不同形式存在的單詞，必須保證能夠匹配到。比如用戶輸入關(guān)鍵詞find時(shí)，像finding、finds等詞語(yǔ)都要被識(shí)別出，反之亦然。處理過(guò)程即把所有關(guān)鍵詞的詞干提取出來(lái)作為關(guān)鍵詞進(jìn)行匹配，本文使用PorterStem算法[11]進(jìn)行詞干提取。

3.3 相似度評(píng)分

在相似度評(píng)分的過(guò)程中，需要對(duì)注釋建立索引。本文用傳統(tǒng)搜索引擎中的倒排索引算法。

3.3.1 倒排索引

通常在某篇文章中找某個(gè)關(guān)鍵詞的時(shí)候，需要建立文章號(hào)與關(guān)鍵詞的對(duì)應(yīng)關(guān)系，然后通過(guò)文章號(hào)找到文章中的關(guān)鍵詞。所謂倒排索引，就是將這種關(guān)系逆轉(zhuǎn)過(guò)來(lái)，通過(guò)關(guān)鍵詞來(lái)找到包含該關(guān)鍵詞的文章號(hào)。如表1和表2表示的關(guān)系。

表1 文章中包含的關(guān)鍵詞Tab. 1 Keywords in the articles

表2 關(guān)鍵詞對(duì)應(yīng)的文章號(hào)Tab. 2 Article numbers correspond to keywords

對(duì)于索引中的關(guān)鍵詞按照字典順序排序，通過(guò)二元搜索算法找到查詢(xún)語(yǔ)句中的關(guān)鍵詞在注釋中的文章號(hào)，之后將注釋和查詢(xún)語(yǔ)句通過(guò)向量空間模型轉(zhuǎn)化為一定維度的向量，進(jìn)而求兩者之間的相關(guān)度評(píng)分。

3.3.2 向量空間模型

本文使用向量空間模型[12]來(lái)實(shí)現(xiàn)查詢(xún)語(yǔ)句與注釋的匹配。將提取出來(lái)的注釋轉(zhuǎn)化為以關(guān)鍵詞權(quán)重為元素的n維向量，其中n為關(guān)鍵詞的個(gè)數(shù)。每個(gè)元素的權(quán)重使用全文檢索技術(shù)中比較流行的TF-IDF(Term Frequency-Inverse Document Frequency)方法。

定義1 詞頻(Term Frequency, TF)，即關(guān)鍵詞在注釋中出現(xiàn)的頻率，計(jì)算公式如下：

(1)

定義2 逆文檔頻率(Inverse Document Frequency, IDF)表示關(guān)鍵詞的普遍重要性，計(jì)算公式如下:

(2)

其中：D表示注釋總數(shù)，|{d|ti∈d}|表示包含關(guān)鍵詞ti的注釋數(shù)目。關(guān)鍵詞i的權(quán)重記為Wi，計(jì)算公式如下:

Wi=TFi, j×IDFi

(3)

3.3.3 注釋余弦相似度計(jì)算

將不同類(lèi)型的注釋轉(zhuǎn)化為以關(guān)鍵詞權(quán)重為元素的向量后，將用經(jīng)過(guò)處理后的用戶查詢(xún)語(yǔ)句轉(zhuǎn)化為與注釋相同維度的向量。通常查詢(xún)語(yǔ)句中的關(guān)鍵詞的數(shù)量比較少，對(duì)于在注釋中出現(xiàn)而在查詢(xún)語(yǔ)句中沒(méi)有出現(xiàn)的關(guān)鍵詞，將查詢(xún)語(yǔ)句向量相對(duì)應(yīng)的權(quán)重設(shè)為零以保證未在查詢(xún)語(yǔ)句中出現(xiàn)的關(guān)鍵詞在計(jì)算相似度時(shí)貢獻(xiàn)度為零。注釋向量設(shè)為V(a)={W1,a,W2,a,…,Wn,a}，查詢(xún)語(yǔ)句向量為V(q)={W1,q,W2,q,…,Wn,q}，計(jì)算兩個(gè)向量的余弦相似度依據(jù)如下公式:

(4)

其中:分子是查詢(xún)語(yǔ)句向量與注釋向量的點(diǎn)積，分母是2個(gè)向量的歐幾里得距離的乘積。

4 搜索與排序

在建立索引的過(guò)程中，以每個(gè)Java文件中方法為單位建立一個(gè)索引Document，在Document中添加4個(gè)Field:類(lèi)注釋(Class Comment, CC)、方法注釋(Function Comment, FC)、方法簽名(Function Signature, FS)、方法體(Function Body, FB)。將處理后的查詢(xún)語(yǔ)句在每個(gè)域中進(jìn)行匹配，得到查詢(xún)語(yǔ)句與各代碼特征的相關(guān)度評(píng)分。任何一個(gè)域所代表的代碼特征與查詢(xún)語(yǔ)句的相關(guān)度評(píng)分不為0，則表明該Document是與查詢(xún)語(yǔ)句相關(guān)的。其中在建立索引的過(guò)程中，為每個(gè)Field設(shè)置一定的權(quán)重，以計(jì)算每個(gè)查詢(xún)語(yǔ)句與搜索結(jié)果總的相關(guān)度評(píng)分。

4.1 搜索算法

由于第3章中在建立倒排索引的過(guò)程中，詞典中的關(guān)鍵詞都是按照字典順序排序的，所以本文使用高效的二元搜索算法來(lái)實(shí)現(xiàn)對(duì)索引的搜索，只要關(guān)鍵詞同時(shí)出現(xiàn)在查詢(xún)語(yǔ)句與代碼特征中，則該代碼特征所對(duì)應(yīng)的Document便能被檢索到，從而得到有相關(guān)性的源代碼文件Document，然后根據(jù)不同的權(quán)重分別計(jì)算查詢(xún)語(yǔ)句與源代碼文件中各代碼特征的相關(guān)度評(píng)分。

4.2 權(quán)重分配

對(duì)不同類(lèi)型的注釋在建立索引時(shí)賦予不同的權(quán)重，然后計(jì)算注釋與查詢(xún)語(yǔ)句的相似度并結(jié)合不同權(quán)重的影響直接對(duì)搜索結(jié)果進(jìn)行優(yōu)化。針對(duì)注釋階段的匹配，給出計(jì)算注釋方面的匹配分?jǐn)?shù)Sc(Scoring Comments)，計(jì)算公式如下：

Sc(c,q)=αSim(q,CC)+(1-α)Sim(q,FC)

(5)

其中:Sim(q,CC)表示查詢(xún)語(yǔ)句與類(lèi)注釋的余弦相似度。Sim(q,FC)表示查詢(xún)語(yǔ)句與方法注釋的余弦相似度。α表示類(lèi)注釋在注釋方面中占有的權(quán)重，(1-α)表示方法注釋占有的權(quán)重。由于方法注釋在注釋方面的重要性大于類(lèi)注釋?zhuān)?-α大于0.5,在此固定α的值為0.2。

針對(duì)方法對(duì)象Sf(Scoring Function)的匹配包括查詢(xún)語(yǔ)句與方法簽名匹配以及查詢(xún)語(yǔ)句與方法體的匹配，其相關(guān)度得分依據(jù)如下公式計(jì)算:

Sf(F,q)=Sim(q,FS)+βSim(q,FB)

(6)

其中：Sim(q,FS)表示查詢(xún)語(yǔ)句與方法簽名的余弦相似度，Sim(q,FB) 表示查詢(xún)語(yǔ)句與方法體的余弦相似度。β表示相對(duì)于方法簽名，方法體在計(jì)算相關(guān)度的重要性。根據(jù)已有的研究[6]，β的值一般取0.1。

針對(duì)用戶搜索的結(jié)果(即代碼方法)，本文對(duì)方法對(duì)象與注釋對(duì)象的相關(guān)評(píng)分進(jìn)行權(quán)重分配并計(jì)算最終的相關(guān)度分?jǐn)?shù)，其計(jì)算公式如下：

S(F,q)=Sf(F,q)+λSc(c,q)

(7)

其中：Sf(F,q)是由式(6)計(jì)算出的查詢(xún)語(yǔ)句與方法對(duì)象的相關(guān)度評(píng)分，Sc(c,q)是由式(5)計(jì)算出的查詢(xún)語(yǔ)句與不同類(lèi)型注釋的綜合相關(guān)度評(píng)分，λ表示在方法對(duì)象和注釋對(duì)象在計(jì)算相關(guān)度評(píng)分過(guò)程中的貢獻(xiàn)度。由于注釋是對(duì)方法對(duì)象的補(bǔ)充說(shuō)明與描述，在計(jì)算相關(guān)度評(píng)分的過(guò)程中的貢獻(xiàn)度遠(yuǎn)遠(yuǎn)大于方法對(duì)象中的方法體，故本文在此定義λ的取值區(qū)間為[0.2,0.8]。

4.3 結(jié)果排序

根據(jù)式(7)查詢(xún)語(yǔ)句與代碼特征的相關(guān)度評(píng)分對(duì)代碼特征代表的結(jié)果排序，返還給用戶。本文選取所有相關(guān)結(jié)果中的前30個(gè)結(jié)果，因?yàn)橛脩敉魂P(guān)心排在前面的結(jié)果，排序相對(duì)靠后的結(jié)果對(duì)用戶的幫助不大。

4.4 結(jié)果去重

由于在軟件的開(kāi)發(fā)過(guò)程中，針對(duì)一個(gè)規(guī)模比較大的軟件來(lái)說(shuō)，難免會(huì)出現(xiàn)功能相似的模塊。這種情況下，用戶往往傾向于復(fù)用已實(shí)現(xiàn)相應(yīng)功能的代碼以實(shí)現(xiàn)另一種功能。這種情況會(huì)導(dǎo)致在這個(gè)軟件中有大量的代碼是重復(fù)的，如果用戶在搜索代碼時(shí)返回大量功能相似的代碼，則會(huì)增加用戶查找結(jié)果的工作量。本文通過(guò)采用SimHash算法[13]對(duì)相似代碼進(jìn)行去重。

5 實(shí)驗(yàn)評(píng)估

5.1 實(shí)驗(yàn)環(huán)境

5.1.1 源代碼選取

從當(dāng)前最為流行的開(kāi)源網(wǎng)站平臺(tái)Github上下載51個(gè)Java開(kāi)源項(xiàng)目，總大小為1.04 GB，這些項(xiàng)目中共有42 709個(gè)類(lèi)，357 912個(gè)方法。選取的標(biāo)準(zhǔn)是比較開(kāi)源項(xiàng)目在Github上的Star與Fork值，值大的優(yōu)先考慮。往往這些開(kāi)源項(xiàng)目較為穩(wěn)定，在大量開(kāi)發(fā)人員的共同開(kāi)發(fā)下，這些項(xiàng)目的源代碼在代碼質(zhì)量上優(yōu)于一些剛成型的開(kāi)源軟件，并且這些開(kāi)源代碼中會(huì)存在大量的描述代碼功能的各類(lèi)注釋。

5.1.2 開(kāi)發(fā)工具包

本文通過(guò)遍歷源代碼的抽象語(yǔ)法樹(shù)來(lái)識(shí)別各類(lèi)代碼特征，其中在遍歷抽象語(yǔ)法樹(shù)的過(guò)程中使用了EclipseJDT中的ASTParser和ASTNode工具包；在為代碼特征建立索引并分配權(quán)重和搜索的過(guò)程中通過(guò)修改Lucene6.2.1全文檢索開(kāi)發(fā)工具包源碼達(dá)到自己的搜索目的。

5.1.3 查詢(xún)語(yǔ)句的搜集

根據(jù)以往研究[14]和一些軟件開(kāi)發(fā)者的查詢(xún)?nèi)罩?，本文搜集?5條查詢(xún)語(yǔ)句，如表3所示。

表3 查詢(xún)語(yǔ)句列表Tab. 3 List of query statements

5.2 度量評(píng)估標(biāo)準(zhǔn)

在信息檢索與統(tǒng)計(jì)學(xué)分類(lèi)領(lǐng)域中最常用的度量標(biāo)準(zhǔn)為準(zhǔn)確率與召回率。準(zhǔn)確率(precision)表示檢索出的相關(guān)結(jié)果占所有檢索出的結(jié)果的比例。召回率(Recall)表示檢索出的相關(guān)結(jié)果占所有相關(guān)結(jié)果的比例。由于本文的相關(guān)性取決于主觀判斷，所以無(wú)法在大量的源代碼中確定具體數(shù)目的相關(guān)代碼，而且當(dāng)前也沒(méi)有評(píng)測(cè)查詢(xún)語(yǔ)句與代碼是否相關(guān)的自動(dòng)化判定方法，所以也無(wú)法計(jì)算出基于準(zhǔn)確率與召回率的F-measure的評(píng)價(jià)指標(biāo)，故本文放棄使用基于準(zhǔn)確率-召回率的評(píng)價(jià)標(biāo)準(zhǔn)。

由于源代碼的數(shù)量巨大，經(jīng)過(guò)查詢(xún)后返回的結(jié)果數(shù)量也是非常多的，但是用戶往往只關(guān)注排在最前面的結(jié)果，所以本文選擇基于排序的評(píng)價(jià)指標(biāo)Precision@K。Precision@K表示設(shè)定一個(gè)閾值K，在檢索結(jié)果到第K個(gè)結(jié)果是正確召回為止，排序結(jié)果的相關(guān)度。Precision@K(簡(jiǎn)寫(xiě)為P@K)的計(jì)算公式如下：

P@K=n/MK

(8)

其中:n表示在第K個(gè)結(jié)果是正確召回的前提下相關(guān)結(jié)果的數(shù)目，MK表示到第K個(gè)結(jié)果正確召回時(shí)總的返回結(jié)果個(gè)數(shù)。

因?yàn)镻@K只能表示單點(diǎn)的策略效果，故引入Average_Precision@K評(píng)價(jià)標(biāo)準(zhǔn)，Average_Precision@K表示設(shè)定一個(gè)閾值K，在檢索結(jié)果到第K個(gè)正確召回為止，排序結(jié)果的相關(guān)度。Average_Precision@K(簡(jiǎn)寫(xiě)為AP@K)的計(jì)算公式如下:

(9)

其中j表示不大于K的閾值。

因?yàn)樯婕暗揭粋€(gè)策略在滿足所有查詢(xún)語(yǔ)句查詢(xún)的結(jié)果，所以需引入Mean_Average_Precision@K(簡(jiǎn)寫(xiě)為MAP@K)，MAP表示的是搜索查詢(xún)結(jié)果Average_Precision@K值的均值，其計(jì)算公式如下：

(10)

其中:Q表示查詢(xún)語(yǔ)句集合，i表示第i個(gè)查詢(xún)語(yǔ)句，本實(shí)驗(yàn)總共搜集到15個(gè)查詢(xún)語(yǔ)句。Mij表示在第i個(gè)查詢(xún)語(yǔ)句查詢(xún)時(shí)第j個(gè)結(jié)果正確召回時(shí)的返回結(jié)果總數(shù)。

在返回的結(jié)果序列中，第一個(gè)相關(guān)結(jié)果在序列中的位置可以反映出搜索算法的好壞。MRR(Mean Reciprocal Rank)是國(guó)際上對(duì)搜索算法進(jìn)行評(píng)價(jià)的通用機(jī)制，即第一個(gè)相關(guān)結(jié)果在結(jié)果序列中位置的度量指標(biāo)，其計(jì)算公式如下：

(11)

其中:Q表示查詢(xún)語(yǔ)句集合，i表示第i個(gè)查詢(xún)語(yǔ)句，ranki表示第i個(gè)查詢(xún)語(yǔ)句搜索返回的第一個(gè)相關(guān)結(jié)果在結(jié)果序列中的位置。選擇這個(gè)度量指標(biāo)的原因是開(kāi)發(fā)者往往找到第一個(gè)相關(guān)結(jié)果時(shí)便能滿足搜索要求。第一個(gè)結(jié)果越靠前表明搜索算法越好。

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

在基于關(guān)鍵詞的搜索當(dāng)中，Krugle可以命中包含查詢(xún)關(guān)鍵字的源代碼文件，同本文的搜索方式大致相同，所以為了驗(yàn)證本文提出的加入注釋與重構(gòu)方法簽名的方法，在基于權(quán)重分配的條件下是否有效，選擇與Krugle進(jìn)行對(duì)比實(shí)驗(yàn)。在對(duì)返回的實(shí)驗(yàn)結(jié)果是否相關(guān)的問(wèn)題上，由于相關(guān)性的判斷是由人為判斷的，所以為了盡可能地減少由于人為主觀性帶來(lái)的誤差，本文選擇編程經(jīng)驗(yàn)近似的3名開(kāi)發(fā)人員對(duì)實(shí)驗(yàn)結(jié)果相關(guān)性進(jìn)行判斷，并且將3名開(kāi)發(fā)人員各自分開(kāi)進(jìn)行獨(dú)立的判斷，在3名開(kāi)發(fā)人員同時(shí)將結(jié)果定為相關(guān)的時(shí)候，才將結(jié)果記錄為相關(guān)。

上述實(shí)驗(yàn)結(jié)果是在默認(rèn)權(quán)重下的實(shí)驗(yàn)結(jié)果，其中注釋權(quán)重默認(rèn)設(shè)為0.4。針對(duì)查詢(xún)語(yǔ)句集中的append string to file的實(shí)驗(yàn)結(jié)果如表4所示。可以看出，準(zhǔn)確率提升最少有8%，平均提升12%左右。一個(gè)查詢(xún)語(yǔ)句對(duì)比結(jié)果的參考價(jià)值往往不高。

表4 單一查詢(xún)語(yǔ)句AP@K實(shí)驗(yàn)結(jié)果 %Tab. 4 AP@K experiment results of single query statement %

下面對(duì)所有查詢(xún)語(yǔ)句進(jìn)行實(shí)驗(yàn)對(duì)比后得到MAP@K參數(shù)如表5所示。

表5 復(fù)合查詢(xún)語(yǔ)句MAP@K實(shí)驗(yàn)結(jié)果 %Tab. 5 MAP@K experiment results of multiple query statements %

由表5可以看出，在15條查詢(xún)語(yǔ)句的實(shí)驗(yàn)對(duì)比下，本文的方法在相關(guān)結(jié)果排序上總體提升將近10%，這說(shuō)明本文方法在提升搜索準(zhǔn)確率上是有效的。為了使搜索優(yōu)化度最大化，通過(guò)調(diào)整注釋的權(quán)重，找出使MAP@K參數(shù)最大的權(quán)重系數(shù)。通過(guò)調(diào)整權(quán)重,得到實(shí)驗(yàn)曲線如圖6所示，其中KMAP@7為Krugle搜索的MAP@7值。

在調(diào)整權(quán)重的實(shí)驗(yàn)中得出本文方法在不同權(quán)重下的MRR值與使用Krugle搜索的MRR值，由于Krugle沒(méi)有考慮權(quán)重影響，所以Krugle針對(duì)本文的查詢(xún)語(yǔ)句集合Q的MRR值是不變的。實(shí)驗(yàn)結(jié)果數(shù)據(jù)如表6所示。

圖6 不同權(quán)重系數(shù)結(jié)果對(duì)比 Fig. 6 Comparison of the results of different weight coefficients 表6 MRR實(shí)驗(yàn)結(jié)果 Tab. 6 Experiment results of MRR

權(quán)重本文方法Krugle權(quán)重本文方法Krugle0.20.750.600.60.6900.600.40.720.600.80.6730.60

通過(guò)圖6可以看出不是注釋權(quán)重越大，搜索效率提升越明顯。當(dāng)權(quán)重系數(shù)為0.8時(shí)，本文方法的搜索效率與Krugle就相差不多了(圖中MAP@7與KMAP@7的趨勢(shì))。這說(shuō)明，注釋這一代碼特征確實(shí)可以幫助提升搜索效率，但是，過(guò)大的權(quán)重也會(huì)增加查詢(xún)語(yǔ)句中對(duì)查詢(xún)不起主要作用的關(guān)鍵詞的搜索得分，從而會(huì)在一定程度上限制搜索準(zhǔn)確度的提升。所以本文在默認(rèn)權(quán)重為0.4情況下得到效率提升將近10%，在0.2權(quán)重下提升大于10%。而表6的實(shí)驗(yàn)數(shù)據(jù)表明本文搜索方法在MRR的度量上是優(yōu)于Krugle的，即在使用本文方法搜索的返回結(jié)果序列中，針對(duì)15條查詢(xún)語(yǔ)句的第一個(gè)相關(guān)結(jié)果的綜合位置比Krugle得到的結(jié)果靠前，說(shuō)明在搜索中加入注釋這一代碼特征并考慮權(quán)重可以提升代碼搜索準(zhǔn)確度。在MAP@K與MRR度量標(biāo)準(zhǔn)下的實(shí)驗(yàn)對(duì)比結(jié)果說(shuō)明本文方法是有效的。

6 結(jié)語(yǔ)

在基于關(guān)鍵字的源代碼搜索研究中，本文在對(duì)單一代碼特征識(shí)別與匹配的基礎(chǔ)上，考慮其他代碼特征對(duì)搜索結(jié)果的影響，增加了對(duì)注釋的匹配和方法簽名的重構(gòu)，并且考慮了多個(gè)代碼特征的權(quán)重問(wèn)題。通過(guò)與已有代碼搜索引擎的實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比，多個(gè)代碼特征在不同權(quán)重影響下提升了代碼搜索準(zhǔn)確度。

本文在方法簽名的重構(gòu)中沒(méi)有考慮類(lèi)名、包名的權(quán)重問(wèn)題，在匹配重構(gòu)后的方法簽名時(shí)類(lèi)名、包名與方法名在搜索過(guò)程中的貢獻(xiàn)度是相同的，但是開(kāi)發(fā)人員在編碼過(guò)程中，往往在命名方法名與類(lèi)名時(shí)會(huì)加以區(qū)分，這就會(huì)導(dǎo)致重構(gòu)后的方法簽名中方法名與類(lèi)名、包名對(duì)搜索的貢獻(xiàn)度是不一樣的，所以在匹配方法簽名時(shí)會(huì)影響搜索結(jié)果的準(zhǔn)確度。后續(xù)可以對(duì)評(píng)分機(jī)制作出改進(jìn)，如考慮對(duì)類(lèi)名和包名賦予不同的權(quán)重，以期進(jìn)一步提高代碼搜索的準(zhǔn)確度。

參考文獻(xiàn)(References)

[1] Github. Github [DB/OL]. [2017- 01- 02]. https://github.com.

[2] Open Source China. OSChina [DB/OL]. [2017- 01- 02]. https://www.oschina.net.

[3] Microsoft. CodePlex [DB/OL]. [2017- 01- 02]. https://www.codeplex.com.

[4] 呂飛.基于搜索的代碼推薦技術(shù)研究[D].上海:上海交通大學(xué),2015.(LYU F. Research on search based code recommendation techniques [D]. Shanghai: Shanghai Jiao Tong University, 2015.)

[5] HILL E, POLLOCK L, VIJAY-SHANKER K. Improving source code search with natural language phrasal representations of method signatures [C] // Proceedings of the 2011 26th IEEE/ACM International Conference on Automated Software Engineering. Piscataway, NJ: IEEE, 2011: 524-527.

[7] ISHIHARA T, HOTTA K, HIGO Y, et al. Reusing reused code [C]// Proceedings of the 2013 20th Working Conference on Reverse Engineering. Washington, DC: IEEE Computer Society, 2013: 457-461.

[8] 林澤琦,趙俊峰,謝冰.一種基于圖數(shù)據(jù)庫(kù)的代碼結(jié)構(gòu)解析與搜索方法[J].計(jì)算機(jī)研究與發(fā)展,2016,53(3):531-540.(LIN Z Q, ZHAO J F, XIE B. A graph database based method for parsing and searching code structure [J]. Journal of Computer Research and Development, 2016, 53(3): 531-540.)

[9] 劉石,李合,王嘯吟,等.基于語(yǔ)法與語(yǔ)義分析的代碼搜索結(jié)果優(yōu)化[J].計(jì)算機(jī)科學(xué),2009,36(8):165-168.(LIU S, LI H, WANG X Y, et al. Enhancement of code search results using syntax and semantic analysis [J]. Computer Science, 2009, 36(8): 165-168.)

[10] HAIDUC S, ROSA G D, BAVOTA G, et al. Query quality prediction and reformulation for source code search: the Refoqus tool [C]// Proceedings of the 2013 35th International Conference on Software Engineering. Washington, DC: IEEE Computer Society, 2013: 1307-1310.

[11] PORTER M F. An algorithm for suffix stripping [J]. Program, 1980, 14(3): 130-137.

[12] ASWANI KUMAR C, RADVANSKY M, ANNAPURNA J. Analysis of a vector space model, latent semantic indexing and formal concept analysis for information retrieval [J]. Cybernetics and Information Technologies, 2016, 12(1): 34-48.

[13] 陳春玲,陳琳,熊晶,等.基于Simhash算法的重復(fù)數(shù)據(jù)刪除技術(shù)的研究與改進(jìn)[J].南京郵電大學(xué)學(xué)報(bào)(自然科學(xué)版),2016,36(3):85-91.(CHEN C L, CHEN L, XIONG J, et al. Research and improvement of data de-duplication based on Simhash algorithm [J]. Journal of Nanjing University of Posts and Telecommunications (Natural Science Edition), 2016, 36(3): 85-91.)

[14] BAJRACHARYA S K, OSSHER J, LOPES C V. Leveraging usage similarity for effective retrieval of examples in code repositories [C]// FSE ’10: Proceedings of the 18th ACM SIGSOFT International Symposium on Foundations of Software Engineering. New York: ACM, 2010: 157-166.

LIZhen, born in 1992, M. S. candidate. His research interests include open source search.

NIUJun, born in 1976, Ph. D., associate professor. His research interests include service computing, open source search.

WANGKui, born in 1988, M. S. candidate. His research interests include open source search.

XINYuanyuan, born in 1993, M. S. candidate. Her research interests include open source search.