增強並構造用戶查詢以支持有效的自由格式代碼搜索

引用

Raphael Sirres and Tegawendé F. Bissyandé and Dongsun Kim and David Lo and Jacques Klein and Kisub Kim and Yves Le Traon. Augmenting and structuring user queries to support efficient free-form code search. Empirical Software Engineering, 2018, 23(5): 2622-2654

摘要

源代碼術語（例如方法名稱和變量類型）通常與搜索查詢中提到的概念詞不同。這個詞彙不匹配的問題會使代碼搜索效率低下。在本文中，我們介紹了 COdevoCABUlary（CoCaBu），這是一種解決自由格式代碼搜索查詢時出現的詞彙不匹配問題的方法。我們的方法利用了常見的開發者問題和相關的專家答案，以使用相關但缺省的結構化代碼實體來擴展用戶查詢，以提高在大型代碼存儲庫中匹配相關代碼示例的性能。為了實例化這種方法，我們在 GitHub 和 Stack Overflow 問答數據之上構建了代碼搜索引擎 GitSearch。我們在多個方面對 GitSearch 進行評估，以證明（1）對於用戶可接受的答案，其代碼搜索結果是正確的；（2）結果在質量上要優於現有的 Internet 級代碼搜索引擎；（3）我們的引擎在幫助用戶完成解決編程任務方面與 Google 等網絡搜索引擎相比具有競爭力；（4）GitSearch 提供了社區可以接受或感興趣的代碼示例，作為 Stack Overflow 問題的答案。

2 動機

在代碼搜索中，與查詢詞匹配的索引中關鍵字可能不包含 API 名稱，因為可通過幾種不同的類和方法來翻譯和實現單個編程概念。這種不匹配可能會降低代碼搜索結果的質量。

我們的目標是解決詞彙不匹配問題，使代碼搜索引擎為用戶自由格式查詢返回高度相關的代碼段。如果我們可將搜索查詢中使用的單詞適當地轉換為在源代碼中找到的關鍵字，則搜索結果將更加準確，如圖 2。這是我們在下一節中描述的方法的實際搜索結果。從真實世界代碼中提取生成的代碼片段實際上與“問答”帖子中問題所接受的人工回答答案相同。

由於詞彙不匹配問題，當前最新的代碼搜索方法無法完全支持自由格式和複雜查詢，例如開發者在問答網站上向其他有經驗開發者提出的查詢。

我們利用問答網站的開發者問題和相關代碼段記錄概念映射，即人類概念到程序元素的映射。大量此類可用映射將緩解詞彙失配問題。任何以自然語言編寫的開發者查詢都可轉換為明確引用特定程序元素的程序查詢。然後可將此新查詢與任何源代碼文件直接匹配。

3 方法

CoCaBu 旨在檢索最相關的代碼片段以回答用戶的自由格式查詢。圖 3 概述了我們的方法。

搜索過程從用戶的自由格式查詢開始，即以自然語言寫成的句子：

(a)-對於給定查詢，CoCaBu 首先在“問答”論壇中搜索相關帖子。搜索代理將開發者自由格式的查詢轉發到 Web 搜索引擎來收集和排列問答中與查詢最相關的文檔中的條目。

(b)-然後 CoCaBu 主要根據先前確定的帖子中的代碼段生成增強查詢。這些代碼段已被開發者批准為發佈問題中可接受的代碼示例，因此 CoCaBu 將其視為人類概念到程序元素的翻譯。CoCaBu 的代碼查詢生成器會創建另一個查詢，包含最初的用戶查詢字詞和提取的摘錄中的程序元素。CoCaBu 預先為問答帖子建立了摘要索引來加快這一步。

(c)-構造擴展查詢後，CoCaBu 會在源代碼文件中搜索與查詢詞匹配的代碼位置。它通過爬取大量公共代碼庫，為源代碼中程序元素預先構建代碼索引，進而生成給定的增強查詢的搜索結果。可以以相關的源代碼文件或代碼片段等不同粒度向用戶呈現該搜索結果。

3.1 結構化代碼實體提取

為有效地在存儲庫中搜索源代碼以查找與來自“問答”帖子的信息相匹配的相關代碼位置，CoCaBu 會在代碼段和源代碼文件中創建結構化代碼實體的索引。表 1 列出了 CoCaBu 在解析來自“問答”帖子的摘錄和來自代碼庫的源代碼文件時收集的結構化代碼實體。

包裝代碼段：CoCaBu 通過使用自定義偽類和方法模板來刪除省略號幷包裝代碼段，以使其能夠由標準 Java 解析器進行解析。

使名稱合格：CoCaBu 使用 AST 遍歷期間收集的結構信息將不合格名稱轉換為部分合格名稱。圖 4 以方法限定之前和之後的代碼片段示例說明了此處理步驟。

文本處理：CoCaBu 將源代碼視為文本進行預處理，如標記化，停用詞移除和詞幹提取。

索引：利用收集的信息集，CoCaBu 可用 Lucene 構建文本術語索引及源代碼中找到的結構化代碼實體。Lucene 將數據存儲為索引，索引由一組代表本例中用於搜索的基本代碼元素的字段組成。字段中填充了上述過程產生的結構和文本信息及特定於索引的元數據。

3.2 搜索代理

搜索代理以自由格式查詢作為輸入，並返回從開發者問答網站收集的一組相關帖子作為輸出。該組件的目的是收集足夠的數據，以便搜索引擎以後可以發現如何將自然語言概念轉換為程序元素。問答環節中的代碼片段可提供潛在的翻譯規則，通過減輕用戶查詢和源代碼元素之間存在的詞彙不匹配問題，促進後續代碼搜索過程。

依靠 Google Web Search，Bing 和 Yahoo Search 等通用引擎，CoCaBu 可以搜索多個不同論壇，並根據它們與查詢的相關性對搜索結果進行排名。我們認為專用語文本搜索的通用引擎比“問答”論壇中其他內置搜索引擎要好。搜索代理會過濾 Web 搜索結果以消除與問答帖子無關的 URL。相關帖子排名根據通用引擎建議的排序順序保留。如果我們考慮 “用 Java 生成隨機詞？”問題，Google Web Search 支持的搜索代理返回表 2 中列出的相關帖子。

3.3 代碼查詢生成器

代碼查詢生成器創建一個代碼搜索查詢，該查詢搜索查詢可增強和構造由搜索代理採取的自由格式查詢。該增強查詢是程序元素的列表以及可用於匹配文檔的自然語言術語。

為生成增強查詢，CoCaBu 從搜索代理返回的相關帖子中問題答案嵌入的代碼片段中提取結構化代碼實體(圖 5(b))。代碼查詢生成器組件僅問答網站社區批准接受的答案。

圖 5(c)中基於 Lucene 搜索引擎查詢格式說明了由代碼查詢生成器生成的增強查詢。讀者可以從所示的示例查詢中觀察到以下內容，其字段語義先前已在表 1 中進行了描述：

-詞幹提取之後，用戶自由格式查詢(圖 5(a))中的術語(不含停用詞)將保留在增強查詢中。

-問答片段(圖 5(b))中收集的結構化代碼實體在增強型查詢中被提及其類型。

CoCaBu 通過建立帖子索引加快代碼查詢生成速度。通常問答論壇提供使用如 XML 的結構化語言格式化過的帖子存檔。如圖 6，CoCaBu 下載問答站點中的帖子，提取每個帖子的元數據(帖子 ID，問題標題)和代碼段，然後分析每個代碼段以檢索結構代碼實體。

如果已經為目標帖子建立了索引，則預先構建索引可以減少查詢生成時間。對於收集的新帖子，該組件按照圖 6 所示的過程將其插入索引中。

3.4 代碼搜索引擎

代碼搜索引擎從代碼查詢生成器獲取擴展查詢，並向發出原始查詢的用戶提供搜索結果列表。搜索結果具有兩個粒度級別：,

-如果查詢被擴大，則由於結構代碼實體在源文件中匹配，並且搜索結果可以集中於僅顯示發生匹配的代碼行的摘錄，因此可以進一步控制粒度。

-如果查詢沒有得到擴展(即搜索代理未在前十個網絡搜索結果集中找到任何問答鏈接)，則搜索引擎會針對每個結果返回一個完整的文件。

為有效提供增強查詢的答案，代碼搜索引擎構建了在存儲庫中找到的源代碼文件索引(圖 7)。隨著增強查詢中的結構化實體以及 NLP 術語使用將列出最相關文件的索引直接進行搜索，匹配變得非常簡單。

由於代碼段索引和代碼索引(分別如圖 6 和 7 所示)以相同格式存儲索引，因此全文搜索可以有效獲得搜索結果。源代碼文件就是文檔，而結構代碼實體則代表搜索詞。

由於顯示源代碼文件的全部內容通常使用戶無法理解代碼示例，代碼搜索引擎會在彙總內容並突出顯示與給定查詢相關的代碼行後顯示文件。為總結和突出顯示搜索結果，CoCaBu 使用一種依賴於查詢的方法，根據源文件中出現的查詢詞來顯示一組包含匹配查詢關鍵字的相鄰代碼行。最後，我們突出顯示了摘要文件中出現的查詢詞以方便識別。

3.5 GitSearch 代碼搜索引擎

為構建 GitSearch 代碼搜索引擎，我們選擇 Stack Overflow 作為問答站點來檢索開發者認可的相關代碼段。我們直接利用 Google 網絡搜索實現搜索代理。用戶查詢將發送到 Google 搜索以檢索所有相關問答環節(即文本相似度匹配)。其他實現可能使用其他 Web 搜索引擎，包括問答網站內置搜索服務。

我們使用 2008 年 7 月至 2015 年 3 月之間的 Stack Overflow 帖子轉儲，其中包含 1363002 個 Java 和 Android 標記的問題來構建代碼段索引。我們使用具有實際帖子(即問題和答案對)以及其他相關元數據(例如標籤，創建日期，問題 ID，帖子的查看數量和答案得分)的 posts.xml 文檔。此外，我們從已接受且答案為正的答案中摘錄片段以確保代碼示例的高質量。為說明帖子中的更新，我們利用 StackExchange REST API9 提取元數據和摘要。 CoCaBu 的用戶可從其他多個問答論壇收集和使用帖子，以擴展搜索更多代碼段的機會。

對於代碼索引，我們考慮了至少被 fork 一次的非玩具、活躍的、主要語言是 Java 的 GitHub 項目(我們專注於 Java 和 Android)，然後在構建代碼索引時從項目中刪除所有非 Java 文件。表 3 顯示了這項工作中收集的 GitHub 項目統計信息。

表 4 總結了根據 Stack Overflow 帖子和 GitHub 開源代碼存儲庫構建的結果索引(即圖 6 和 7 中所示的代碼片段和代碼索引)。

4 評估

評估包括：手動驗證，在線調查，受控用戶研究和實時研究，分別專注於回答以下研究問題：

4.1 RQ1：針對社區基本事實的驗證

首先，我們調查 GitSearch 產生的結果的相關性。

研究設計：我們基於兩個要求從 Stack Overflow 帖子中收集著名開發者問題：(i)帖子中問題必須與“ Java”相關，並且(ii)其答案必須包含代碼段。我們選擇“觀看次數”值最高的前 10 個帖子，以確保研究重點放在有代表性的開發者任務上。表 5 列出了研究中使用的查詢。

結果：圖 8 顯示 GitSearch 結果很大程度上與用戶查詢相關，間接證明該方法的準確性。

4.2 RQ2: 與其他代碼搜索引擎的比較

我們進行了一項用戶研究，要求開發者檢查不同代碼搜索引擎的有效性，並從從業者的角度評估 GitSearch 的有用性。

研究設計：我們通過在軟件開發者社區(750 個 GitHub，Mozilla 和 Eclipse 開發者及一家韓國公司的開發者)中發佈在線調查邀請來招募參與者。所有調查邀請中，我們明確指出僅邀請具有 Java 經驗的開發者/學生。為促進研究，我們構建了一個基於 Web 的調查工具，它在三個匿名列中顯示來自 OpenHub，Codota 和 GitSearch 的代碼搜索結果。為避免人們對使用該工具的偏見，我們僅考慮使用表 5 中的查詢完整完成研究的參與者的條目。

結果：研究結束時，我們有 47 位參與者嘗試了該工具(至少一項答覆)。他們中有些人沒有完成研究。其中，有 14 位參與者完成了這項研究。

圖 9(a)顯示了每個代碼搜索引擎的選定搜索結果數。與所有其他查詢相比，參與者選擇了更多 GitSearch 返回的代碼示例。除查詢 Q3 外，所選結果數量是其他結果的兩倍多。

此外，我們計算了所選搜索結果排名分佈。若用戶選擇一個引擎的多個搜索結果，則我們只會計算排名最高的結果。如圖 9(b)，GitSearch 的中值等於 1，而其他引擎為 2。

討論：儘管我們無法與最新的 CodeHow 工具進行比較，但其作者報告說，它產生的相關結果比 OpenHub 多 20％，而圖 9(a)表明，GitSearch 比 OpenHub 多 50％。

4.3 RQ3: 與傳統搜索引擎的比較

我們對 GitSearch 和一般網絡搜索引擎(谷歌和百度)進行比較研究。由於許多開發者依靠通用搜索引擎查找編程任務解決方案，我們評估了 GitSearch 與此類引擎相比的競爭力。

研究設計：我們從三所大學(法國皮埃爾和瑪麗·居里大學，盧森堡大學和中國浙江大學)招募了 20 名研究生。要求每個學生找到解決以下兩個編程任務的代碼示例：

結果：研究參與者輸入了 77 種不同形式自由格式查詢(任務 1 為 37，任務 2 為 40)。

表 7 顯示了參與者為不同搜索引擎標記的相關搜索結果的百分比。這表明 GitSearch 與 Web 搜索引擎相比具有競爭力。我們沒考慮在 Web 搜索中遵循鏈接重定向和解析網頁以查找不完整的代碼段所需的努力。另外 GitSearch 提供了現實中的工作代碼示例。

討論：我們從參與者輸入的 77 個查詢中發現，網絡搜索引擎上輸入的查詢更加“完整”，且在參與者之間更具冗餘性。參與者承認自己遵循了網絡搜索引擎的自動完成建議。

我們通過對參與者在網絡搜索引擎上輸入的 10 個查詢進行隨機抽樣並在 GitSearch 上使用它們來執行交叉驗證實驗。我們對參與者在 GitSearch 上輸入的 10 個查詢進行隨機抽樣，並在 Google 搜索引擎上使用它們。對 GitSearch，任務 1 和 2 的 MRR 值分別為 0.94 和 0.90。對 Web 搜索引擎，任務 1 和 2 的 MRR 值分別降低到 0.72 和 0.65。

這些結果表明了 GitSearch 的未來工作方向，我們必須使用日誌記錄和反饋機制來記錄成功的查詢，並建議它們自動完成對未來請求者的查詢。

4.4 RQ4: Live study into the wild

我們發佈代碼搜索結果作為 Stack Overflow 問題的答案來評估代碼搜索引擎的有用性。這項研究調查了開發者遇到編程問題時如何解釋有效的代碼示例。儘管 GitSearch 並非旨在直接回答開發者的問題，但可幫助他們找到編程任務的起點。由於 Stack Overflow 中有許多未回答問題，因此 GitSearch 在 Stack Overflow 方面可以是一個很好的第一回答者。

研究設計：我們使用 Java 標籤監視問題，並根據以下標準從其中選擇了 25 個：

對每個問題，我們提取其標題並將其放入 GitSearch 中，並將最好的搜索結果發佈為答案。答案包括 1) GitSearch 選擇的最相關代碼片段，及 2) GitSearch 從中找到片段的原始源代碼超鏈接。我們對 OpenHub 重複相同過程，以將其有效性與我們的技術進行比較。

結果：如表 8 所示，GitSearch 比 OpenHub 回答了更多問題並獲得了更多的贊成和反對意見，而人類回答則接受了更多的贊成票和更少的反對票。表 8 展示了我們在 GitSearch，OpenHub 和人類間進行的實時研究結果。“#Ans”中的“Resp”是每種技術回答的問題數量，而“Acc”是發問者接受的答案數量。“Upvotes”和“Downvotes”票數是 Stack Overflow 用戶給出的票數。“Pos. Comm.”和“Neg. Comm.”評論是用戶對每個答案的正面和負面評論。“Most voted？”代表獲得最多投票的答案數量。|x|表示具有至少一個 Upvotes/Downvotes 投票和正面/負面評論的答案數量。Σ 是出現次數的總和，而括號中的數字是平均值(即 Σ/|x|)。

Stack Overflow 的投票表明那些用戶鼓勵(或勸阻)答案。儘管它的優缺點幾乎與人工結果相關，但顯而易見的是，與 OpenHub 相比，GitSearch 對用戶的興趣更大。GitSearch 更頻繁地引起用戶討論。GitSearch 並未明顯勝過人類回答，但人類用戶尚未回答 17 個。對這 17 個問題，GitSearch 回答並獲得 1 票贊成和 3 票反對，3 條正面和 2 條負面評論。

討論：這項研究的結果表明，與 OpenHub 相比，GitSearch 可以是更好的第一回答者。如表 8 所示，Stack Overflow 中的許多問題幾天都沒有得到回答。我們的技術可以提供問題的起點，即使它們不是完整的答案，因為許多用戶會通過投票和添加評論來跟進答案。一旦用戶對一個問題感興趣，討論該問題的解決方案的可能性就會更大。

另外，Stack Overflow 用戶將 GitSearch 的代碼搜索結果選擇為可接受的答案，意味著結果與問題高度相關且適當。請注意，提問者只能選擇一個答案作為接受的答案。這可能表明發問者將利用代碼搜索結果來處理問題中顯示的問題。此外，這可能意味著如果代碼搜索引擎的準確性得到提高，它們將成為 Stack Overflow 中某些問題的自動答案生成器。

4.5 對有效性的威脅

CoCaBu 的設計和 GitSearch 的實施帶來了許多我們試圖緩解的有效性威脅：

內部有效性：與其他 API 示例搜索引擎的用戶研究相比，我們的研究參與者較少，僅為 34 名。但在自由格式代碼搜索作品的用戶研究中參與者少於我們或沒有用戶研究。我們試圖通過邀請專業開發者和研究生來達到代表性。而在 4.4 節中，我們嘗試在問題解決循環中從 Stack Overflow 用戶那裡獲取反饋。這意味著我們的評估涉及更多的參與者。

外部有效性：我們僅使用英語作為查詢語言，重點關注與 Java 有關的問題，且在實現中僅探討了 Stack Overflow 和 GitHub。這種威脅應受到以下事實的限制：(1)英語是編程社區中的一種流行語言，(2)Java 是最受歡迎的編程語言之一，(3)GitHub 和 Stack Overflow 是最大的代碼託管站點和問答論壇。

構造有效性：我們只關注沒有確切 API 名稱的查詢。但這種威脅是有限的，因為對於新任務，開發者通常不知道相關 API 的名稱。

致謝

感謝國家重點研發計劃課題：基於協同編程現場的智能實時質量提升方法與技術（2018YFB1003901）和國家自然科學基金項目：基於可理解信息融合的人機協同移動應用測試研究（61802171）支持！

本文由南京大學軟件學院 2019 級碩士生朱晨乾翻譯轉述。