基于眾包問答信息的API使用代碼搜索
2018-07-25 11:21:38李宇琨趙文耘
計(jì)算機(jī)應(yīng)用與軟件 2018年7期
關(guān)鍵詞：文本
李宇琨 彭 鑫 趙文耘
(復(fù)旦大學(xué)軟件學(xué)院 上海 201203) (上海市數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室(復(fù)旦大學(xué)) 上海 201203)
0 引 言
現(xiàn)代軟件開發(fā)大量依賴類庫以及第三方軟件框架和開發(fā)，為此軟件開發(fā)者經(jīng)常需要尋找能夠解決特定問題的API并通過示例代碼學(xué)習(xí)相關(guān)API的使用方式。另外，我們?cè)卺槍?duì)特定平臺(tái)編程時(shí)，比如安卓平臺(tái)、Windows平臺(tái)等，我們還需要利用到平臺(tái)提供的開發(fā)接口，以利用相應(yīng)的硬件資源或者系統(tǒng)資源。例如，獲取手機(jī)GPS定位、調(diào)用攝像頭等。程序員在面對(duì)一個(gè)與API密切相關(guān)的編碼任務(wù)時(shí)，他們需要知道哪個(gè)API能夠幫助他們實(shí)現(xiàn)這個(gè)功能，這個(gè)API應(yīng)該如何調(diào)用。目前，程序員主要依賴通用搜索引擎完成代碼搜索，例如：百度搜索、Bing搜索。通過這類網(wǎng)站，程序員可以看到其他有經(jīng)驗(yàn)程序員留下的文字以及樣例代碼，這些信息能幫助程序員理解相關(guān)API。但是，程序員很可能還不知道應(yīng)該如何調(diào)用這些API，他們需要看更多的真實(shí)的代碼。這時(shí)，他們會(huì)將相關(guān)API輸入到Github、Bitbucket等開源代碼托管網(wǎng)站，去搜索真實(shí)的示例代碼。由于開源代碼網(wǎng)站里面存在大量分支，分支與分支之間有大量克隆代碼，導(dǎo)致搜索結(jié)果重復(fù)度較高。程序員如果在首頁中無法獲得正確結(jié)果，需要往后翻好幾頁，或者根據(jù)結(jié)果重新組織搜索詞，極大地降低了工作效率，因此程序員需要代碼搜索工具來提升搜索效率?，F(xiàn)有的代碼搜索工具大多利用API文檔為數(shù)據(jù)源，通過匹配用戶查詢語句，返回相關(guān)API和與該API相關(guān)代碼。例如，SNIFF[1]通過VSM(Vector Space Model)計(jì)算API文檔與用戶查詢語句的匹配度查詢相關(guān)API，并返回相關(guān)代碼。CodeHow[2]通過使用擴(kuò)展布爾模型改進(jìn)匹配算法。但是，API經(jīng)常被組合使用以解決相關(guān)問題，同一個(gè)API也會(huì)被用到不同的場景發(fā)揮不一樣的作用。因此，通過匹配API文檔與查詢語句不能完全地理解用戶的意圖，也不能完全概括代碼所包含的信息。最近幾年，有許多研究者也在API的基礎(chǔ)上增加其他信息，以更確切地匹配用戶需求。例如，SWIM[3]通過對(duì)Bing的點(diǎn)擊記錄進(jìn)行搜索，獲取代碼API結(jié)構(gòu)序列，查詢代碼片段。DeepAPI[4]通過查詢深度學(xué)習(xí)技術(shù)，利用API序列與代碼注釋信息，訓(xùn)練映射模型，將自然語言映射到API序列。但標(biāo)準(zhǔn)的代碼注釋信息較少，深度學(xué)習(xí)技術(shù)受到詞表大小等因素限制，搜索范圍不能太大。因此，我們通過觀察程序員日常搜索代碼過程，提出一個(gè)新的代碼搜索方法。
本文首先接受用戶輸入的查詢語句，再利用Stack Overflow中包含的大量含有樣例代碼的帖子，匹配相關(guān)的樣例代碼，抽取樣例代碼中的代碼骨架信息，利用倒排索引技術(shù)，在代碼庫中搜索骨架相似的代碼片段，返回給用戶。然后利用Stack Overflow中包含的大量編碼信息，通過文本抽取技術(shù)與代碼骨架抽取技術(shù)，能更好地理解代碼的語義以及用戶的查詢語義。為了測試我們工具的有效性，我們通過Github和Stack Overflow提供的源數(shù)據(jù)，構(gòu)建了一個(gè)關(guān)于Java代碼的搜索工具原型。該原型目前包含有700多萬的Stack Overflow帖子，代碼庫中包含了3億多行Java代碼。用戶可以通過網(wǎng)頁使用該工具，從搜索框內(nèi)輸入問題描述，從結(jié)果頁中獲得代碼骨架以及相應(yīng)的代碼片段。我們從相關(guān)代碼搜索論文中選取了30個(gè)與API相關(guān)的問題進(jìn)行測試，其中有8個(gè)問題，正確答案排名第一，有20個(gè)問題能在前5個(gè)結(jié)果中找到答案，有29個(gè)問題都能在前十個(gè)問題中找到答案。在返回的十個(gè)結(jié)果中，有40%的結(jié)果符合要求，其中有15個(gè)問題能找到不同類型的答案。
本文主要有以下幾個(gè)貢獻(xiàn)：
(1) 我們提出了一個(gè)從自然語言到API集合的映射方法。
(2) 我們提出了一個(gè)從代碼庫中抽取API與代碼結(jié)構(gòu)特征的方法。
(3) 我們提出了一個(gè)利用代碼骨架(API與結(jié)構(gòu)信息)，搜索代碼的方法。
(4) 我們?yōu)樵摲椒▽?shí)現(xiàn)原型工具，并進(jìn)行實(shí)驗(yàn)，取得良好效果。
1 方法總覽
圖1展示了該方法的整體流程。該方法分成離線模塊與在線模塊。離線模塊對(duì)Stack Overflow中的信息和Github中的代碼進(jìn)行離線分析，并建立索引文件，用于提升線上搜索模塊搜索效率。離線模塊主要分成三個(gè)部分：Stack Overflow文字摘要模塊、Stack Overflow代碼骨架抽取模塊以及Github代碼庫代碼骨架抽取模塊。隨后，我們對(duì)抽取出來的三個(gè)數(shù)據(jù)分別建立索引，并將索引文件更新至線上模塊。線上模塊則是利用離線索引文件，模擬程序員利用Stack Overflow搜索問題的流程，搜索出相關(guān)代碼，并對(duì)代碼片段進(jìn)行評(píng)分與排名。線上模塊主要分成兩個(gè)模塊：第一個(gè)模塊為代碼骨架搜索模塊。該模塊獲取用戶的查詢語句，并通過離線建立的Stack Overflow的索引并獲取相關(guān)主題的帖子，以及帖子中的代碼骨架。然后，我們結(jié)合帖子中的文本信息分析判斷不同代碼骨架的評(píng)分，獲取候選代碼骨架，輸入第二模塊。第二模塊為代碼片段搜索模塊。該模塊主要接收代碼骨架搜索模塊的候選代碼骨架，然后通過離線建立的代碼庫搜索相關(guān)代碼，并根據(jù)代碼相似度、代碼骨架的評(píng)分等因素對(duì)代碼片段進(jìn)行排序，并將結(jié)果返回給用戶，完成搜索過程。
圖1 代碼搜索流程圖
我們通過一個(gè)搜索實(shí)例介紹工具的搜索流程。例如，輸入How to read text file line by line，工具會(huì)利用離線模塊建立的Stack Overflow索引，搜索與問題相關(guān)的帖子。圖2是一個(gè)排名第一的含有樣例代碼的帖子，里面含有一片關(guān)于如何一行一行地讀取文件的代碼。通過代碼骨架提取器，可以從中提取出如圖3所示的代碼骨架。同時(shí)，通過文本摘要模塊，從帖子中抽取出line、file、read、append等十個(gè)詞。同時(shí)工具還會(huì)搜索到其他一些關(guān)于文件操作的帖子以及相應(yīng)的代碼塊。隨后，將代碼骨架放入至代碼庫中搜索，能搜索到如圖4所示的代碼。這是搜索到的如何一行一行讀取文件的代碼，相比于匹配的代碼骨架，里面用Files.newBufferdReader()這個(gè)API代替了圖3中的前兩個(gè)API，同時(shí)多了Charset這個(gè)API。這片代碼更為完整地讀取了文件的代碼，更貼切實(shí)際需求。
圖2 Stack Overflow 樣例帖子
圖3 代碼骨架
圖4 文件讀取代碼
2 離線索引構(gòu)建
離線系統(tǒng)是離線構(gòu)建索引，并熱更新至線上系統(tǒng)的模塊。其中包括有代碼骨架索引構(gòu)建和文本索引構(gòu)建。代碼骨架索引構(gòu)建分為Stack Overflow中示例代碼骨架抽取和Github代碼庫骨架抽取。文本索引包括：文本摘要、文本向量抽取等部分。系統(tǒng)將索引文件熱更新至線上系統(tǒng)，以保證系統(tǒng)穩(wěn)定可擴(kuò)展。
2.1 代碼骨架抽取
API序列模式是由一系列經(jīng)常在一起使用的API語句組合而成的序列。程序員經(jīng)常會(huì)使用不同API序列模式在不同的環(huán)境中完成不同的編碼任務(wù)。API的使用組合會(huì)形成一種模式，并與其適用場景存在一種對(duì)應(yīng)關(guān)系[5]。Deep API[4]就是通過學(xué)習(xí)API序列與代碼注釋的對(duì)應(yīng)關(guān)系，提供代碼搜索的功能。但是傳統(tǒng)的API序列往往會(huì)忽略代碼中結(jié)構(gòu)信息，僅僅記錄代碼片段中存在的API，這樣會(huì)帶來歧義。圖2為關(guān)于逐行讀取文件的代碼。如果我們只提取API序列，BufferReader.readLine()后就不存在相關(guān)結(jié)構(gòu)信息。但同樣的序列模式，如果while語句改成if語句，那么就成了判斷第一行是否為空的代碼，語義完全不一樣。因此，工具將在API序列模式中增加代碼結(jié)構(gòu)信息，在每條語句結(jié)尾按照代碼層次結(jié)構(gòu)依次加上結(jié)構(gòu)信息，如圖3所示。這樣就能知道readLine這個(gè)API是在循環(huán)內(nèi)部調(diào)用，可以盡量減少API調(diào)用模式的歧義。本文中，我們將這樣含有代碼結(jié)構(gòu)信息的API序列模式稱為代碼骨架。代碼中的結(jié)構(gòu)種類較多，且包含的結(jié)構(gòu)信息的API序列需要被快速搜索，因此，我們針對(duì)Java的語法特點(diǎn)，統(tǒng)一代碼結(jié)構(gòu)的形式。具體規(guī)則如下：1) 所有的API語句有A.B(C)的形式表示，其中A為API的類型，B為A中的字段或者方法，如果為構(gòu)造函數(shù)則B與A同名，C為方法B的參數(shù)，如果B為字段則無括號(hào)。2) 每個(gè)API元素后面用中括號(hào)包裹，并從左往右依次帶有結(jié)構(gòu)信息。3) 所有的循環(huán)結(jié)構(gòu)用while表示，并將判斷條件放置在第一條。4) 所有的判斷結(jié)構(gòu)全部用if表示，包括else分支同樣用if表示，將判斷條件放置在第一條。5) Try-catch語句，將try后括號(hào)內(nèi)部的代碼放入try內(nèi)部第一句，catch語句的標(biāo)簽由括號(hào)內(nèi)部的異常類型的名字代替，finally語句后綴添加finally標(biāo)簽。6) 內(nèi)部方法、匿名方法等直接當(dāng)成新的代碼片段處理。經(jīng)過上述規(guī)則限定，我們能統(tǒng)一代碼骨架形式，下面是抽取代碼骨架的具體實(shí)現(xiàn)。
對(duì)Stack Overflow中樣例代碼進(jìn)行解析。Stack Overflow中含有大量無法解析的代碼片段，不能通過傳統(tǒng)的AST解析器解析其中代碼片段[6]。因此，工具利用字符串匹配以及正則表達(dá)式匹配的方式逐句匹配。首先，根據(jù)Java的語法規(guī)則，利用“;”、“{”、“}”三個(gè)符號(hào)對(duì)Java語句進(jìn)行分行，去除代碼注釋，并逐句匹配。然后通過Java關(guān)鍵字匹配結(jié)構(gòu)信息(while、if等)，如果匹配則將結(jié)構(gòu)信息存入棧中，如果不匹配，則通過正則表達(dá)式匹配去語句內(nèi)容。其中正則表達(dá)式主要使用以下3個(gè)公式[7]：
1) 類型聲明：typeVariable=/(w+(?:..w+)?)s([a-z]w{0,})/g
2) 方法調(diào)用：methodCall=/(w+)。(w+)(/g
3) 參數(shù)匹配：argsRegex = /((.*?))/
同時(shí)，使用鍵值對(duì)記錄變量類型與變量名的對(duì)應(yīng)關(guān)系，并用雙端隊(duì)列記錄已成功確認(rèn)的代碼序列信息，以上代碼主要針對(duì)Stack Overflow中的示例代碼。相比于Stack Overflow中的示例代碼，Github中工程代碼含有更多的上下文信息，比如有完整的類，類與類之間有方法調(diào)用等，但為了與Stack Overflow中提取的代碼骨架信息保持一致，我們依然使用正則表達(dá)式匹配的方式進(jìn)行解析。但是，額外增加了兩個(gè)要素：1) 由于Github中代碼骨架抽取以方法為單位，因此，這里增加全局變量類型匹配，建立全局變量名與變量類型的映射關(guān)系。2) 根據(jù)Java編碼規(guī)范[8]，包名應(yīng)該有域名、公司名、項(xiàng)目名以及包所屬模塊共同決定，因此可以通過分析包名與引入類路徑，判斷是否為引入外部第三方庫。具體方法為將包路徑和引入的類型路徑分詞，計(jì)算兩個(gè)路徑的詞向量夾角的余弦值，大于0.5的為內(nèi)部引入，小于0.5的為外部引用，并將外部引用更新API候選類型。
2.2 Stack Overflow信息索引構(gòu)建
Stack Overflow網(wǎng)站提供了一個(gè)通用的搜索接口，但是使用通用的搜索接口無法獲取每個(gè)帖子的評(píng)分。雖然有標(biāo)簽選擇，但是無法完全保證帖子的代碼語言，也無法保證搜索結(jié)果的質(zhì)量。因此，我們選擇通過Stack Exchange提供的Stack Overflow數(shù)據(jù)，離線建立索引。同時(shí)能對(duì)帖子進(jìn)行清洗，對(duì)內(nèi)容做預(yù)處理，保證線上搜索速度。
Stack Overflow作為程序員的問答網(wǎng)站，不但包含有大量有意義的回答與代碼，同時(shí)也存在許多缺陷，比如：問題語義重復(fù)，回答中沒有答案等。同時(shí)，有些冷門的問題雖然有正確答案，但是缺少其他人瀏覽和認(rèn)同，說明這是一個(gè)不普遍的問題。因此，我們首先要對(duì)Stack Overflow進(jìn)行清洗。清洗的規(guī)則如下：1) 含有Java或者Android標(biāo)簽，因?yàn)楣ぞ咧饕阉鱆ava代碼。2) 含有提問者認(rèn)同的標(biāo)準(zhǔn)答案。3) 問題或者標(biāo)準(zhǔn)答案的贊同數(shù)要為2或者2以上，以保證問題的普遍性。通過帖子清洗之后，將帖子的標(biāo)題、問題、標(biāo)簽以及最佳答案四個(gè)部分組合成最終數(shù)據(jù)，并刪除其余答案。然后，我們將剩余的帖子分成兩個(gè)部分：一部分包含樣例代碼，另一部分不包含樣例代碼為純文字。
對(duì)于含有樣例代碼的帖子，我們需要從含有代碼的帖子中抽取出樣例代碼。我們針對(duì)部分Stack Overflow帖子進(jìn)行統(tǒng)計(jì)分析，并調(diào)研了之前與Stack Overflow相關(guān)的文獻(xiàn)[9-10]，總結(jié)出以下三個(gè)特點(diǎn)：
1) 代碼格式特征。Stack Overflow會(huì)利用
的html標(biāo)簽塊，將大塊的代碼片段包裹起來，利用標(biāo)簽將小塊代碼元素包裹。這樣做一方面可以保持代碼的縮進(jìn)、換行等格式，方便讀者閱讀。另一方面，標(biāo)簽由于能保持輸入格式，因此也有非代碼元素出現(xiàn)在其中，例如：錯(cuò)誤信息、配置文件、腳本文件等。2) 代碼位置特征。Stack Overflow上代碼出現(xiàn)在帖子的位置隨不同作者的習(xí)慣會(huì)出現(xiàn)在不同的地方。有些樣例代碼會(huì)出現(xiàn)在文本末尾，有些樣例代碼會(huì)出現(xiàn)在帖子開頭，還有一些代碼會(huì)出現(xiàn)在文本中間。3) 代碼內(nèi)容特點(diǎn)。部分含有代碼的帖子中問題與答案中都存在代碼，但大多數(shù)情況問題中的變量名與答案中的變量名具有同樣的含義。針對(duì)Stack Overflow中代碼存在的特征，我們決定采用以下方式對(duì)帖子中代碼進(jìn)行提取：
1) 提取帖子中所有被
標(biāo)簽包裹的內(nèi)容，并通過啟發(fā)式規(guī)則檢驗(yàn)其是否為Java代碼。主要啟發(fā)式規(guī)則為：(1) 通過匹配以“at”開頭的語句的數(shù)量判斷是否為Exception輸出。(2) 通過匹配<>判斷是否為xml。(3) 至少有一個(gè)“.”符號(hào)出現(xiàn)，保證存在方法調(diào)用。(4) 通過查詢var的位置判定是否為JavaScript代碼，如果含有以var為類型的變量，則判定為JavaScript代碼。2) 將所有檢驗(yàn)為Java代碼的片段拼接并通過語句級(jí)別的去重，形成一片無重復(fù)代碼片段，并放置到代碼骨架抽取器中抽取代碼骨架。然后把代碼骨架抽取器中抽取出來的骨架與原帖子建立映射關(guān)系，并存入數(shù)據(jù)庫便于搜索。
針對(duì)純文本帖子，我們需要做的是對(duì)文本進(jìn)行過濾，排除一些常用的詞，或者一些感謝的詞。文本過濾的步驟如下：(1) 將標(biāo)題直接作為有意義的文本。(2) 將被標(biāo)簽標(biāo)記的代碼名詞直接算作特殊文本。(3) 將剩余的文本根據(jù)句子組成，形成一個(gè)網(wǎng)絡(luò)，然后通過PageRank算法[11]計(jì)算每個(gè)詞的結(jié)構(gòu)分，并且句子中所有詞的平均分作為該句子得分，去除掉得分為1以下的句子。(4) 將剩余的文本作為特殊文本。最后將特殊文本作為數(shù)據(jù)源，建立搜索索引。
2.3 代碼庫信息構(gòu)建
通過對(duì)Stack Overflow信息提取，我們可以將用戶輸入的查詢語句轉(zhuǎn)化成代碼骨架。得到骨架之后我們需要通過對(duì)代碼庫進(jìn)行處理，搜索實(shí)現(xiàn)該代碼骨架的相關(guān)代碼。為此，我們通過Boa[12]獲取大量Github上開源項(xiàng)目地址，選取其中Java相關(guān)的代碼工程進(jìn)行解析，抽取開源代碼骨架并建立索引。
Github是開源代碼托管網(wǎng)站，大量程序員在上面分享自己的代碼，并瀏覽他人代碼。還有大量程序員會(huì)在遵守開源協(xié)議的基礎(chǔ)上，克隆他人代碼進(jìn)行二次開發(fā)。因此，Github中存在大量克隆代碼。克隆代碼的存在會(huì)導(dǎo)致大量重復(fù)代碼骨架被抽取，建立重復(fù)索引，使最終搜索結(jié)果單一化。但是，由于代碼量較大(約16 GB)，通過代碼克隆檢測的方法難以在如此大量的代碼中高效地檢測出克隆代碼。為此，我們根據(jù)數(shù)據(jù)特點(diǎn)，設(shè)計(jì)了一個(gè)近似解決方案，從兩個(gè)維度對(duì)重復(fù)代碼進(jìn)行剔除：一是線下模塊，通過文件級(jí)別的檢測去除克隆文件；二是線上搜索排序模塊，在方法級(jí)別剔除克隆代碼塊，該模塊會(huì)在后文提到，此處暫時(shí)不談。線下模塊主要針對(duì)文件級(jí)別的克隆。由于Github中存在大量開源代碼的二次開發(fā)工程，因此在文件粒度上有許多文件的內(nèi)容是完全一致的。所以，我們決定通過文件級(jí)別檢測。但代碼文件數(shù)眾多，為了保證檢測運(yùn)行效率，我們通過文件大小對(duì)文件進(jìn)行分片。以1 KB為間隔，將代碼文件劃分到不同的區(qū)間，隨后通過MD5算法對(duì)文件進(jìn)行簽名，然后利用數(shù)據(jù)庫存儲(chǔ)與查重，同時(shí)對(duì)數(shù)據(jù)進(jìn)行持久化，方便后續(xù)擴(kuò)展新代碼文件時(shí)，能繼續(xù)查重。最后刪除重復(fù)文件，并放入代碼骨架抽取器中抽取代碼庫代碼骨架。最終將代碼骨架與代碼建立索引，方便搜索。
3 在線搜索
離線索引構(gòu)建完成后，在線搜索模塊會(huì)基于離線索引為用戶提供搜索服務(wù)。為了保證搜索的效率及可擴(kuò)展性，我們采用倒排索引技術(shù)[13]完成索引構(gòu)建以及搜索。倒排索引是通過對(duì)搜索數(shù)據(jù)進(jìn)行分詞，建立單詞到源數(shù)據(jù)間的聯(lián)系，同時(shí)通過對(duì)分出的單詞合并成前后綴字典樹，壓縮存儲(chǔ)空間，增加索引效率。通過倒排索引，可以將離線完成的索引文件熱更新至在線搜索系統(tǒng)，同時(shí)也能高效率地使用空間向量模型對(duì)文檔進(jìn)行評(píng)分與排序，方便后續(xù)排名。但是，僅僅依靠文本匹配搜索效果難以完全理解帖子的含義，因此，我們將根據(jù)不同帖子出現(xiàn)不同API出現(xiàn)的次數(shù)，以及帖子中代碼骨架與代碼庫中代碼骨架的匹配度進(jìn)行新的評(píng)分。接下來，我們?cè)诘古潘饕Y(jié)果基礎(chǔ)上進(jìn)行的二次評(píng)分與排序。
3.1 代碼骨架搜索
首先將用戶的查詢語句放入Stack Overflow搜索模塊中搜索其對(duì)應(yīng)的代碼骨架。在構(gòu)建Stack Overflow搜索模塊時(shí)，分成了兩個(gè)搜索模塊：1) 含有樣例代碼的帖子的搜索，選出代碼骨架候選集。2) 純文本帖子的搜索，提取關(guān)鍵詞，為代碼骨架進(jìn)行評(píng)分。具體步驟如下：(1) 利用搜索工具從含有代碼的帖子中搜索出排名前十的帖子，搜索匹配分即為代碼骨架基礎(chǔ)得分，另外從只含有文本的帖子中搜索出排名前十的帖子。(2) 代碼骨架之間兩兩對(duì)比，合并完全覆蓋的代碼骨架。(3) 對(duì)所有文本中出現(xiàn)的詞進(jìn)行合并與計(jì)數(shù)，并以次數(shù)最高的詞為1分，其余的得分為其出現(xiàn)次數(shù)與最高次數(shù)的比值，并與代碼骨架中出現(xiàn)的詞對(duì)比，如果代碼骨架中出現(xiàn)該詞則增加詞相應(yīng)的分?jǐn)?shù)。(4) 用戶輸入的查詢語句中的詞全部算作1分，與代碼骨架匹配，計(jì)算相應(yīng)得分。所有剩余代碼估計(jì)排名，選取前3個(gè)最終代碼骨架放入代碼庫中搜索代碼骨架實(shí)驗(yàn)代碼。
3.2 代碼片段搜索
代碼庫的搜索是基于代碼庫的搜索。同樣，我們通過倒排索引對(duì)3個(gè)候選代碼骨架進(jìn)行搜索，每個(gè)候選骨架得到排名前20的實(shí)現(xiàn)代碼片段。由于之前只在文件級(jí)別做過去重，還有大量的代碼塊克隆，或者開發(fā)者針對(duì)代碼文件有擴(kuò)展但遺留許多方法依然相同。因此，這一步搜索依然會(huì)得到許多克隆代碼。我們需要在線上搜索系統(tǒng)對(duì)結(jié)果進(jìn)行進(jìn)一步去重。這里代碼量相對(duì)較少，但是現(xiàn)有的代碼克隆檢測工具沒有提供API調(diào)用，我們需要重新建立新的進(jìn)程進(jìn)行克隆檢測，這樣加重了線上系統(tǒng)負(fù)擔(dān)。另一方面，我們也需要去除一些含有微小變化的代碼，是返回結(jié)果更加多樣。因此，我們采用空間向量模型，把代碼分成一組詞向量，計(jì)算代碼之間的夾角余弦值，將余弦值大于0.9的代碼結(jié)果合并，但是合并會(huì)為這個(gè)片代碼增加一個(gè)(1+n/10)的系數(shù)，其中n為合并代碼段的數(shù)量，說明這樣一片代碼會(huì)有更高的流傳度。最后將代碼得分與代碼骨架得分相乘作為代碼片的得分。系統(tǒng)最終會(huì)選出分值最高的10片代碼，為保證這10片代碼中含有不同類型的代碼骨架，系統(tǒng)將降低同一代碼骨架下排名靠后的代碼片段的權(quán)重。每個(gè)代碼片段權(quán)重將乘上一個(gè)(1-x/10)的系數(shù)，其中x表示代碼片段在其代碼骨架下的排名。這樣排名第一的代碼片段獲得所有分?jǐn)?shù)，排名最后的代碼片段不得分，其余代碼片段按照比例計(jì)算。最后對(duì)所有代碼片段的權(quán)重進(jìn)行排序，選出前10個(gè)代碼片段，并加上所使用的API，返回給用戶，完成整個(gè)搜索過程。
4 實(shí) 驗(yàn)
本節(jié)我們通過網(wǎng)頁對(duì)外代碼搜索服務(wù)，并以此為基通過實(shí)驗(yàn)檢驗(yàn)工具搜索結(jié)果的正確性，同時(shí)計(jì)算搜索時(shí)間保證工具實(shí)用性。
4.1 準(zhǔn) 備
我們通過Stack Exchange上面的提供的公共接口，下載了2014年至2016年的所有帖子數(shù)據(jù)，在利用Java和Andorid兩個(gè)標(biāo)簽過濾之后，一共得到700萬左右的帖子，其中含有樣例代碼的帖子總共137萬左右。我們利用Stack Overflow離線索引模塊對(duì)帖子進(jìn)行解析，并借助Java中的開源倒排索引庫Lucene[14]建立相關(guān)索引，最終得到1.1 GB索引文件。同時(shí)，我們利用Boa提供的開源軟件倉庫的地址，以及Github提供的公共接口，爬取了Github上面3億行Java代碼代碼，里面包含有2 786 631個(gè)代碼文件，占用磁盤空間為16 GB，經(jīng)過文件去重之后，文件數(shù)減少為2 132 218個(gè)，占用空間為12.8 GB。在這個(gè)基礎(chǔ)上，我們借助代碼索引模塊解析所有代碼文件，接入代碼骨架的分詞器，并用Lucene建立索引，最終得到2.1 GB索引文件。兩個(gè)索引庫都留有更新接口，方便我們可以將新的帖子數(shù)據(jù)或者代碼數(shù)據(jù)熱更新至線上系統(tǒng)，改進(jìn)搜索效果。
為了驗(yàn)證本方法的搜索準(zhǔn)確率與搜索效率，我們從近3年的4篇關(guān)于代碼搜索的論文中抽取出30個(gè)與API關(guān)系較為密切的問題，問題涵蓋了字符串處理、文件讀取、數(shù)據(jù)庫操作、網(wǎng)絡(luò)編程等多個(gè)應(yīng)用場景，答案中既含有單API問題，又包含有多API組合完成的問題。問題如表1所示。
表1 查詢列表
4.2 實(shí)驗(yàn)結(jié)果
我們請(qǐng)求了2位有5年Java編程經(jīng)驗(yàn)的碩士對(duì)所有問題返回的十個(gè)答案進(jìn)行驗(yàn)證，判斷每個(gè)答案是否能解決相關(guān)問題。兩位同學(xué)獨(dú)立驗(yàn)證所有答案，遇到有分歧的答案將交由第三位有5年Java編碼經(jīng)驗(yàn)的博士進(jìn)行驗(yàn)證，最終確定標(biāo)準(zhǔn)答案。
實(shí)驗(yàn)結(jié)果如表2所示。Id表示問題的序列號(hào)，與表1相對(duì)應(yīng)，F(xiàn)Rank表示前十個(gè)答案中第一個(gè)出現(xiàn)正確答案的選項(xiàng)排位，-1表示沒有搜到正確答案。從該欄結(jié)果表明，有40%的問題能直接在第一個(gè)結(jié)果中找到正確答案，只有一個(gè)問題無法找到答案，基本能滿足程序員搜索到問題的需求。%Top5指的是前5個(gè)答案中正確答案的比例，%Top10表示的前10個(gè)答案中正確答案的比例。兩者整體正確率偏低，可能是因?yàn)樗阉鞒绦虮旧黼y以理解一些細(xì)節(jié)化而選擇將更多的同類型關(guān)鍵字加入，從而匹配到同一類的問題。并且在最后選擇代碼片段的時(shí)候?yàn)楸ＷC解決方案的多樣性，系統(tǒng)降低同一代碼骨架下排名靠后代碼的權(quán)重有遞減，以保證多個(gè)代碼骨架的出現(xiàn)。這個(gè)設(shè)計(jì)導(dǎo)致準(zhǔn)確率偏低，但是大幅提高召回率，使得大多數(shù)問題能搜索到正確答案。另外，前十個(gè)正確答案個(gè)數(shù)不顯著高于前五個(gè)正確答案個(gè)數(shù)，這也說明了排序算法的正確性，能基本保證正確的答案整體靠前。Time表示的是搜索代碼所用時(shí)間，時(shí)間通過Web前端腳本計(jì)算，單位為s，結(jié)果取第二位小數(shù)。服務(wù)器部署在本地電腦，處理器為I5-5200U，2.2 GHz，內(nèi)存為8 GB。搜索時(shí)間的范圍在1.34～1.91 s之間，平均值為1.62 s。整個(gè)搜索的響應(yīng)時(shí)間較短，不會(huì)給用戶使用帶來不良體驗(yàn)。
表2 實(shí)驗(yàn)結(jié)果
4.3 實(shí)驗(yàn)案例
我們現(xiàn)在來看幾個(gè)搜索案例，根據(jù)搜索案例查看代碼搜索工具在處理不同類型問題的中間結(jié)果，以及針對(duì)不同問題的不同效率。首先查看一個(gè)正面樣例，generate md5 hash code。我們通過搜索這樣一個(gè)語句，找到問題13201180，標(biāo)題為Issue with MD5 hash generation。內(nèi)部有一段代碼使用MessageDIgest類對(duì)字符串進(jìn)行MD5加密。代碼骨架抽取器從樣例代碼中抽取到合法的代碼骨架，并且憑借代碼內(nèi)部變量名以及MD5文本出現(xiàn)次數(shù)得到較高評(píng)分。通過這片代碼骨架，系統(tǒng)可以搜索出相關(guān)代碼片段。另外，由于部分其他帖子的干擾，例如問題5992778，Computing the MD5 hash of a string in scala。這個(gè)問題打上了Java標(biāo)簽，但是問題卻與scala聯(lián)系更密切，所以搜索結(jié)果中混淆有錯(cuò)誤API骨架，例如MD5.asHex等。但是，由于大部分帖子與Java相關(guān)，且代碼庫中MD5這樣的API較少，因此，在排名上面正確的答案依然能占據(jù)主要地位。
其次，我們?cè)賮砜次覀儫o法找到正確答案的問題，how to save image in png format。首先，通過對(duì)Stack Overflow帖子的搜索，我們能獲取到一些含有代碼的帖子，標(biāo)題如下：1) java save jpg as png。2) How to get the format(ex:jpen,png,gif) of image file (BufferedImage) in java。3) How to save optimized png images with java’s ImageIO。4) Save a GIF with index transparency using ImageIO等。大部分帖子內(nèi)容關(guān)于ImageIO如何寫入圖片。我們也能從中找到關(guān)鍵API，例如：ImageIO.write(image, “png”, new File())。但是，這里有特別關(guān)鍵的字段png，是以字符串的形式傳入，而系統(tǒng)在提取相關(guān)形式的代碼骨架的時(shí)候，這個(gè)關(guān)鍵字已經(jīng)被模糊化成了String。因?yàn)榇蟛糠执a的字符串是表示特定項(xiàng)目背景的，無通用借鑒意義，因此我們無法搜索到特定情況下的API。我們只能搜索到圖片存儲(chǔ)的一般意義上的二代碼，沒有特定指明為“png”格式。我們嘗試將結(jié)果集擴(kuò)大，能找到一些以“png”為參數(shù)的代碼片段，但是這存在偶然性，我們方法確實(shí)缺乏處理有意義的字符串的能力。如果需要解決這類問題，未來可以考慮設(shè)立二級(jí)匹配模式，將我們認(rèn)為不重要的信息，例如字符串常亮等建立二級(jí)索引，在一類索引的基礎(chǔ)上對(duì)二類索引進(jìn)行搜索，以解決這樣的問題。
最后，我們查看一個(gè)排名靠后的問題，test file exists。這個(gè)問題答案出現(xiàn)靠后主要是因?yàn)閱栴}過于簡單，只需要file.exists單個(gè)API就能解決。但是file.exists這樣一個(gè)API常常與其他API連動(dòng)，比如：如果文件不存在就創(chuàng)建一個(gè)，如果沒有該文件就終止程序等。因此，在搜索帖子的時(shí)候會(huì)得到很多與其他文件操作相關(guān)的API。且其他相關(guān)的API出現(xiàn)次數(shù)又會(huì)比file.exists出現(xiàn)次數(shù)更多，因此權(quán)重反而在這個(gè)API上面。因此，這樣在實(shí)際代碼中單獨(dú)使用次數(shù)較少，也不便于我們進(jìn)行代碼搜索工作。當(dāng)然，這也是大多數(shù)依靠信息檢索實(shí)現(xiàn)搜索的一個(gè)問題，難以確切理解題目意義，只能靠文本匹配度以及關(guān)鍵詞出現(xiàn)次數(shù)，確定結(jié)果權(quán)重。不過，總的來說，我們的搜索方法能找到與問題相關(guān)的帖子，并能通過解析帖子中存在的代碼，匹配到代碼庫中，并最終返回給用戶正確的結(jié)果。
5 相關(guān)工作
代碼搜索一直是軟件工程領(lǐng)域的熱點(diǎn)話題，研究者先后提出了各種各樣的代碼搜索方法。這些方法分別支持不同類型查詢方式，例如輸入自然語言查詢，或者輸入代碼語言查詢，還有通過正則表達(dá)式查詢等。其中，通過自然語言搜索代碼與通用的搜索引擎相似，實(shí)現(xiàn)難度也相對(duì)較大，因此有更多的研究集中在通過自然語言搜索代碼上。
許多國內(nèi)外學(xué)者嘗試使用各種方法幫助程序員搜索相關(guān)代碼。早期，研究人員將代碼文本當(dāng)作普通文本對(duì)待，引用信息檢索領(lǐng)域中的相關(guān)技術(shù)，通過關(guān)鍵字或者正則表達(dá)式搜索相關(guān)代碼。此類搜索適用于程序員搜索內(nèi)部項(xiàng)目的代碼，需要程序員熟悉項(xiàng)目內(nèi)容，這其中的代表工具有Ohloh[15]、Krugle[16]、Sando[17]。
隨著傳統(tǒng)機(jī)器學(xué)習(xí)技術(shù)的發(fā)展，許多工作通過將軟件開發(fā)過程中的其他制品與代碼關(guān)聯(lián)，實(shí)現(xiàn)自然語言到代碼語言地轉(zhuǎn)換。在這其中，Strathcona[18]通過記錄項(xiàng)目的開發(fā)文檔，分別項(xiàng)目的開發(fā)層次，為用戶提供不同具有類似功能的工程以及代碼片段。Sourcerer[19]則是基于Lucene將更大范圍的代碼庫以及代碼間結(jié)構(gòu)信息存儲(chǔ)起來，用戶可以通過代碼關(guān)系結(jié)構(gòu)搜索代碼。隨后，代碼API文檔越來越完善，文本分析技術(shù)越來越強(qiáng)，有的研究開始利用API文檔作為搜索資料，以更好地理解使用了該API的代碼。其中，SNIFF[1]通過簡單的空間向量模型，對(duì)用戶的查詢與API文檔進(jìn)行匹配，獲取單一API的評(píng)分，選取最后結(jié)果。而CodeHow[2]則在此基礎(chǔ)上，利用擴(kuò)展布爾模型，結(jié)合條件概率改進(jìn)其在多API匹配的效果。但是，API文檔質(zhì)量不高，因此，后面有更多的學(xué)者將研究方向轉(zhuǎn)向眾智平臺(tái)，利用Stack Overflow、Bing等通用編程知識(shí)搜索入口，改善代碼搜索結(jié)果。QECK[20]利用Stack Overflow平臺(tái)中已有數(shù)據(jù)，通過半監(jiān)督訓(xùn)練擴(kuò)展用戶查詢語句，提高搜索效率。SWIM[3]則是利用Bing搜索引擎，搜集與程序相關(guān)帖子，通過抽取代碼結(jié)構(gòu)序列匹配代碼庫。本文與SWIM的主要不同點(diǎn)在與以下幾點(diǎn)：1) 本文合并同類型帖子并加重其綜合評(píng)分，同時(shí)區(qū)別不同的解決方案。2) 本文提取的代碼骨架相比于結(jié)構(gòu)序列更為精簡，同時(shí)適用于無法編譯的網(wǎng)頁中的代碼段。3) 本文為適配代碼骨架搜索，重新建立代碼庫。隨后，RACK[21]利用Stack Overflow與Github，并結(jié)合IDE(代碼編輯器)中的上下文環(huán)境，實(shí)現(xiàn)代碼搜索。但是相對(duì)于本文，RACK沒有利用代碼結(jié)構(gòu)特征，緊緊利用Stack Overflow將用戶的查詢語句轉(zhuǎn)化成相應(yīng)的API，并通過Github提供的接口進(jìn)行代碼搜索，沒有對(duì)代碼進(jìn)行預(yù)處理，建立相應(yīng)的代碼庫。
近年來，隨著深度學(xué)習(xí)的發(fā)展與在軟件學(xué)科的應(yīng)用，DeepAPI[4]利用循環(huán)神經(jīng)網(wǎng)絡(luò)，將API序列與相關(guān)注釋作為訓(xùn)練樣本，最后利用訓(xùn)練出來的循環(huán)神經(jīng)網(wǎng)絡(luò)，將自然語言映射到API序列，展現(xiàn)出相同API序列的代碼片段。深度學(xué)習(xí)能更好地理解用戶輸入的查詢語句，以及自然語言與代碼的對(duì)應(yīng)關(guān)系。但是深度學(xué)習(xí)技術(shù)詞表有限、搜索范圍不廣、可擴(kuò)展性不強(qiáng)。
在國內(nèi)，也有許多研究人員正在研究代碼搜索課題。DERECS[22]通過挖掘開源網(wǎng)頁中，收集代碼片段與解釋之間的對(duì)應(yīng)關(guān)系，擴(kuò)展搜索語句，最終搜索相關(guān)代碼。顧逸圣等[23]通過結(jié)合代碼結(jié)構(gòu)與查詢語句之間的關(guān)系，直接將查詢語句映射到代碼語句。
6 結(jié) 語
本文介紹了一種通過搜索眾包問答信息將自然語言轉(zhuǎn)化成代碼骨架，并通過自己建立代碼庫，將代碼骨架映射成代碼片段的代碼搜索方法。通過實(shí)現(xiàn)一個(gè)原型工具，來測試方法的準(zhǔn)確性與時(shí)效性。實(shí)驗(yàn)中有40%的問題的正確答案在排序的第一位，其余的問題大部分能在前5個(gè)找到正確答案。同時(shí)，工具的響應(yīng)時(shí)間較快，不給用戶帶來太多負(fù)擔(dān)。
本方法代碼搜索速度較快，但是在語義理解上有較多欠缺。未來可以通過深度學(xué)習(xí)等技術(shù)，深入理解用戶語義或者論壇中的文本語義，甚至是代碼語義，從而實(shí)現(xiàn)更精確的代碼搜索工具。
猜你喜歡
文本聯(lián)讀學(xué)概括 細(xì)致觀察促寫作云南教育·小學(xué)教師(2022年4期)2022-05-17 14:46:24 重點(diǎn)：論述類文本閱讀新世紀(jì)智能(語文備考)(2020年4期)2020-07-25 02:28:52 重點(diǎn)：實(shí)用類文本閱讀新世紀(jì)智能(語文備考)(2020年4期)2020-07-25 02:28:52 初中群文閱讀的文本選擇及組織甘肅教育(2020年8期)2020-06-11 06:10:02 作為“文本鏈”的元電影藝術(shù)評(píng)論(2020年3期)2020-02-06 06:29:22 在808DA上文本顯示的改善制造技術(shù)與機(jī)床(2019年10期)2019-10-26 02:48:08 “文化傳承與理解”離不開對(duì)具體文本的解讀與把握新世紀(jì)智能(語文備考)(2018年11期)2018-12-29 12:30:58 基于doc2vec和TF-IDF的相似文本識(shí)別電子制作(2018年18期)2018-11-14 01:48:06 文本之中·文本之外·文本之上——童話故事《坐井觀天》的教學(xué)隱喻小學(xué)教學(xué)參考(2015年20期)2016-01-15 08:44:38 從背景出發(fā)還是從文本出發(fā)語文知識(shí)(2015年11期)2015-02-28 22:01:59
