引用
Xi Ge and David C. Shepherd and Kostadin Damevski and Emerson R. Murphy-Hill. Design and evaluation of a multi-recommendation system for local code search. Journal of Visual Languages and Computing, 2017, 39:1--9.
摘要
在軟件維護過程中，通常會在本地代碼庫中搜索相關代碼。然而，研究表明 88％的手動搜索查詢均未檢索到任何相關結果。搜索失敗的原因之一是現有搜索工具對字符串匹配算法的依賴，該算法無法找到與語義相關的代碼。為了幫助開發人員編寫更好的查詢來解決此問題，研究人員提出了許多查詢推薦技術，這些技術依賴於各種字典和算法。但是，這些技術中很少有來自實際開發人員的使用數據進行評估的。為了填補這一空白，我們設計了一種基於多種查詢推薦技術協作的推薦系統。我們在 Sando 代碼搜索工具中實施並部署了此推薦系統，並進行了縱向調查。我們的研究表明，超過 34％的查詢結果採用來自推薦系統；拓建查詢檢索結果與手動查詢相比高出 11％。
1. 介紹
許多編程都是從搜索開始的。但搜索代碼其實困難：許多人被迫使用過時的工具（例如基於正則表達式的搜索工具）來搜索他們從未見過的數百萬行代碼。由於這些工具僅取決於開發人員編寫的查詢與陌生字符串的匹配程度，因此這些工具的查詢中有 88％沒有返回相關結果。而開發人員將 40％的時間用於搜索、導航、閱讀和理解源代碼，這些失敗的搜索會浪費大量開發人員的時間，進而增加軟件開發成本。
本地代碼搜索工具可幫助開發人員找到編程任務的起點。這類工具常作為主流集成開發環境（IDE）的一部分：如 InstaSearch 和 Sando 分別可用於 Eclipse 和 Visual Studio 。這些工具將開發人員的查詢作為輸入，並從 IDE 當前打開的項目中檢索代碼元素。研究表明，本地代碼搜索工具比正則表達式搜索工具更有效，並且已經觀察到許多開發人員每天都頻繁使用這種工具。本地代碼搜索工具與 grep 等正則表達式搜索工具不同在於：（1）檢索代碼元素（例如方法，類和字段），而不是文本行；（2）返回排名結果，使相關性越高的結果越易於訪問；（3）在開發人員搜索前對代碼庫進行索引，從而使搜索幾乎是即時的。
儘管有這些優點，本地代碼搜索工具仍存在某些與正則表達式搜索工具相同的問題。例如，假設開發人員想要搜索用戶名在身份驗證系統中的存儲方式。他們可以搜索“user file”或“user element”。但是，該實現可能將存儲稱為“user document”。如果不瞭解代碼庫中使用的確切術語，開發人員將不會考慮編寫此查詢語句。在這種情況下，正則表達式搜索工具和本地代碼搜索工具都不會對開發人員有所幫助。
為了解決這個問題，研究人員提出了多種查詢推薦技術。但是，在實際環境中，對這些技術的研究很少。如果不觀察開發人員與推薦技術的實際交互，則不清楚這些技術的可用性和實用性。為了填補這一空白，我們實施了 Coronado，這是 Sando 搜索工具的擴展，該工具集成了各種推薦技術，幫助開發人員撰寫新查詢並優化失敗的查詢。利用 Sando 的廣受歡迎，我們能夠通過收集現場數據來評估這些推薦技術。總體來說，本文的貢獻是：
- 多種查詢推薦技術的實現，作為對 Sando 的擴展。
- 調查了 Coronado 的可用性和實用性。我們收集了來自 591 位的 24 個月的 Sando 用戶使用情況數據。最終表明，在手動搜索之前或之後推薦查詢同樣有用，推薦代碼庫中的標識符是最為有效。
2. Sando 推薦
在介紹推薦技術之前，我們首先介紹一下名為 Sando 的本地代碼搜索工具，該工具可以實現和評估我們的技術。作為 Visual Studio 插件，Sando 允許開發人員通過發送與 Google 查詢類似的查詢，在本地代碼庫中搜索代碼片段。 Sando 支持對 C 和 C＃代碼的搜索。它將不同級別的軟件實體視為文檔，包括類，方法和字段。搜索結果是包含查詢術語的文檔列表。 Sando 根據“文檔頻率反比”得分對結果進行排序，這些得分反映了術語在文檔集中對文檔的重要性。圖 1 是 Sando 的屏幕截圖，其中搜索框在頂部（A），底部的列表視圖（B）呈現搜索結果。在搜索框附近，雲按鈕基於標籤雲調用推薦技術，“ [C]”按鈕清除搜索歷史，“ [？]”按鈕提供幫助。
當用戶單擊某一搜索結果時，Sando 將彈出一個窗口，以向其提供相應代碼元素的概述。彈出窗口的下半部分（C）包含整個代碼元素，而上半部分（D）包含查詢詞的確切行。雙擊結果可打開包含搜索結果的文件。
Sando 推薦系統將交互式查詢推薦技術與半自動查詢修改和擴展技術交織在一起，幫助用戶構建初始查詢，該技術旨在幫助用戶重新構造可能產生較差結果的初始查詢。在本文中，我們將第一組推薦稱為 pre-search，將第二組推薦（在初始查詢後出現）稱為 post-search。在這兩種情況下，Sando 都遵循典型推薦系統的精神，依靠用戶反饋來手動選擇、修改或擴展提交給系統的查詢詞。通常這種明確的用戶交互比完全自動化的查詢擴展系統能產生更準確的結果。
基於以下原因，我們將 Sando 用作實現和評估推薦技術的平臺：（1）Sando 代表了本地代碼搜索工具，因為它實現了與其他集成開發環境中的搜索工具類似的功能；（2）Sando 是具有可擴展 API 的開源項目，我們可以輕鬆地向其中添加功能；（3）Sando 的用戶下載超過一萬五千次，這為我們提供了大量可收集反饋的用戶。
2.1 組件
為了彌合本地代碼搜索用戶與正在搜索的代碼庫間的認知鴻溝，我們實現了名為 Coronado 的 Sando 擴展，該擴展基於五個組成部分：代碼庫術語，術語共現矩陣，Verb-Direct-Object 存儲庫，軟件工程同義詞庫和英語詞庫。在解釋 Coronado 如何使用這些組件推薦查詢之前，我們首先討論每個組件以及 Coronado 如何收集和維護這些內容。
2.1.1 代碼庫術語
Coronado 的第一個組件包含了代碼庫中正在被搜索的術語。當 Sando 的索引器遍歷開發者的項目時，Coronado 會收集這些術語。Sando 索引建立過程將源代碼元素拆分為一組術語，包括原始標識符和駝峰命名拆分後的術語。例如，Sando 將方法名稱“ parseFile”索引為三個術語：“ parse”，“ file”和“ parseFile”。C 和 C＃關鍵字不建索引。
Sando 分兩個階段對代碼庫進行索引：初始索引和增量索引。僅當開發人員打開未被 Sando 緩存的項目時，Sando 才執行初始索引。每當開發人員更改已緩存的項目時，Sando 會執行增量索引。最初為 10,000 行代碼的項目建立索引需要花費約 20 秒的時間，而為已更改的 C＃文件逐步建立索引只要花費約 20 毫秒的時間。通過重新使用索引期間收集的術語，Coronado 可以在代碼庫中構建和維護術語集。
2.1.2 術語共現矩陣
Coronado 的第二個組件是一個矩陣，該矩陣記錄兩個術語的共現次數。對於在源文檔中一起出現的每對術語[t1;t2]，矩陣生成器會將矩陣[t1; t2]處元素的當前值加 1。舉個例子，考慮下面的代碼片段：
PathManager CreatePathManager(string path) { if(Path.HasExtension(path)) return new PathManager(Path.GetDirectoryName(path)); else return new PathManager(path);}該方法包含以下十二個術語：path, manager, PathManager, create, CreatePathManager, has, extension, HasExtension, get, directory, name, 和 GetDirectoryName。因此，對於這種方法，同時出現的術語對是任意兩項的組合；總共是 144（12*12）。當開發人員將此方法添加到代碼庫中時，術語共現矩陣會將與每對對應的元素的當前值加一，例如，fcreate，pathg，fpath，managerg 等元素。
一個問題是將共現矩陣保存在內存中效率低下。例如，考慮一下 Sando 本身，這是一個包含約 10,000 行代碼和約 2000 個術語的項目。對於這樣的項目，矩陣中的元素數量約為 400 萬（2000*2000）。為了提高存儲效率，我們利用了共生矩陣通常稀疏這一事實。也就是說，根據我們的工具使用數據，矩陣中超過 90％的元素包含 0 值。因此，我們通過使用 Yale 格式表示共現矩陣，Yale 格式是一種有效存儲稀疏矩陣而幾乎不存儲數據的數據結構，且幾乎不影響查找和插入的速度。
Yale 格式通過使用三個數組表示一個稀疏矩陣：（1）矩陣中所有非零元素的值都以行形式存儲；（2）矩陣行的第一個非零元素的索引數組；（3）數組元素的列索引數組。圖 2 給出了 Yale 格式的例子，其中 A，IA 和 JA 分別對應於上述三個數組。矩陣中的零點越多，Yale 格式提高存儲效率的作用就越大。
2.1.3 Verb-Direct-Object 存儲庫
Coronado 技術中的另一個組件是 Verb-Direct-Object 存儲庫。基於源代碼通常涉及對對象執行操作，Fry 和同事提出了一種結合自然語言處理和源代碼分析的技術。他們的技術從代碼庫，例如“打開文件”或“關閉流”中提取動詞-對象對。通過採用此技術，Coronado 會定期分析代碼庫，提取動詞-對象對，並將其緩存以備將來使用。
2.1.4 軟件工程同義詞庫
Coronado 還使用軟件開發中經常使用的術語表。軟件工程已經發展出自己的術語、同義詞和縮寫集，而這些術語、同義詞和縮寫集在常規英語（例如“imap”）中不存在。一些軟件工程術語具有不同於其常規英語含義的特定含義，例如“class”。因此，簡單地重用通用同義詞庫將無助於解釋特定字段的信息，甚至可能有害於客戶端軟件工具。為了建立特定領域的詞庫，我們利用 Gupta 和同事們的工作，該工作在源代碼中挖掘不同術語之間的關係，並生成 1724 對語義相關的術語。在這些術語對中，有 91％是特定於軟件工程領域的同義詞。這些特定字段的同義詞的示例包括“execute”-“invoke”, “load”-“initialize”以及“instantiate”-“create”。此外，他們的工作還量化了同義詞對的共性。例如，已經發現“create”與幾個術語相關，包括“make”, “do”, 和“construct”。但是，“make”與“create”的關係要比與“construct”或“do”的關係更緊密。
2.1.5 英語同義詞庫
Coronado 的最後一部分是通用的英語詞庫。為了建立這個詞庫，我們重用了 Miller 的詞彙數據庫 WordNet。WordNet 將相關概念表示為圖，其中節點是單詞，邊將具有相似含義的單詞連接起來。由於 Coronado 只是在尋找給定單詞的鄰居，因此使用 WordNet 查找同義詞需要花費恆定的時間。儘管 WordNet 包含完整的英語單詞集，但是將整個數據集保存在內存中的成本很高。因此，我們減少了 WordNet 的大小隻包含英語中最常用的 10 萬個單詞。 我們推測 10 萬個單詞足以滿足大多數查詢的需求，儘管用戶查詢不尋常單詞的頻率仍然是一個懸而未決的問題，出於隱私原因，我們不收集有關 Sando 用戶正在搜索的術語數據。
2.2 搜索前推薦
接下來，我們描述 Coronado 如何使用這些組件。每當開發人員在 Sando 的搜索框中鍵入內容時，Coronado 都會在開發人員單擊搜索按鈕之前就推薦查詢，如圖 3 所示。我們稱這些為搜索前推薦。這些推薦來自三個來源：標識符，Verb-Direct-Object 對和共同出現的術語。
由於在搜索框中每按一次鍵，就會向用戶顯示搜索前的推薦，因此查詢的響應時間對其可用性至關重要。對於大型代碼庫（例如 Linux 內核），我們測試搜索前推薦生成響應時間約為秒級，這肯定會影響 Sando 的可用性。像許多其他搜索工具一樣，我們發現從推薦術語中預生成 trie 數據結構可以將響應時間縮短几個數量級，但所需的額外內存和 CPU 時間卻相對較少。
2.2.1 標識符
搜索前推薦的第一個來源是標識符。當程序員在搜索框中鍵入字符串時，Coronado 將遍歷代碼庫術語組件以確定該字符串是否為本地術語中任何標識符的前綴。然後推薦使用每個匹配的標識符來完成開發者的搜索查詢，並在搜索框下方的下拉菜單中顯示該標識符。 例如，圖 3a 顯示了當開發人員在 Family 上搜索時鍵入字符串“ update”時，向開發人員推薦的搜索詞。Showcodebase 是一個開放源代碼項目，允許用戶構建 Family Tree。
2.2.2 Verb-Direct-Object 對
當開發人員在搜索框中輸入動詞後按下空格鍵時，Sando 將從存儲庫組件中檢索動詞是否對應到 Verb-Direct-Object 對。如果 Sando 找到多個 Verb-Direct-Object 對，則 Sando 使用共現矩陣對它們進行排序；動詞和直接賓語出現的次數越多，該對出現在下拉框中的位置就越靠前。當開發人員在搜索框中輸入“update”時，圖 3b 中的下拉菜單示例了 Verb-Direct-Object 推薦。因為“update”相比其他對象更常與“Status”同時出現。因此，“update Status”是最為推薦的搜索查詢
2.2.3 頻繁共現術語
第三種搜索前推薦通過使用術語共現矩陣來推薦頻繁共現的術語。在搜索框中輸入一個或多個術語後，開發人員可以單擊搜索框附近的雲按鈕以顯示標籤雲。標籤雲中的術語是與搜索框中的術語最常共現的術語。標籤雲中的字體越大，則該詞與搜索框中的詞共現頻率越高。圖 3c 顯示了一個示例—該標籤雲顯示的術語與“parent”經常同時出現。 “children”一詞與“parent”比“define”更常見。單擊標籤雲中的術語可將其添加到原始搜索查詢的末尾。
對於頻繁出現的術語，我們選擇在標籤雲中可視化術語，而不是像標識符和 Verb-Direct-Object 對那樣的常規下拉列表。我們之所以選擇這個選項，是因為早期實驗表明，對於給定的代碼庫，與標識符或 Verb-Direct-Object 對相比，共現術語更多。因此，由於標籤雲比下拉列表能更有效地使用屏幕空間，因此我們使用這種方式來共現術語。在之後的討論中，我們將頻繁出現的術語稱為標籤雲推薦。
2.3 搜索後推薦
除了幫助開發人員完成查詢之外，Coronado 還在開發人員單擊搜索按鈕並且未返回搜索結果後給出建議。在這種情況下，開發人員的查詢包含了代碼庫中不存在的術語。為了幫助她編寫新查詢，Coronado 根據代碼庫術語、軟件工程詞庫和英語詞庫在搜索中推薦代碼庫中語義相似的術語。假設原始查詢具有多個以空格分隔的術語，那麼 Coronado 首先查詢代碼庫術語組件以檢查代碼庫中每個術語是否存在。如果不存在則搜索失敗，那麼 Coronado 使用以下三個步驟來生成新查詢。
2.3.1 預處理
儘管代碼庫中不存在某個術語，但該術語的某些部分可能會存在。因此，Coronado 貪婪地拆分該術語，並將本地術語中存在的部分合併到推薦的查詢中。更具體地說，對於查詢中的給定術語，Coronado 會嘗試查找本地術語中存在的最長前綴和後綴，而後以遞歸方式拆分術語的中間部分，直到找不到匹配的前綴或後綴。
例如，假設開發人員搜索“getelementname”，它在代碼庫中不存在。如果本地術語包含“get”和“name”，則將搜索到的術語拆分為三個新術語：“get”，“element”和“name”。
2.3.2 同義推薦
拆分後，如果拆分詞不存在於本地術語中，則 Coronado 會嘗試在詞庫中找到它們的同義詞。 Coronado 首先是軟件工程詞庫，因為它的相關性比英語詞庫高。如果在軟件工程同義詞庫中找不到同義詞，則 Coronado 會嘗試在英語同義詞庫中查找同義詞。在檢索同義詞之後，該技術接下來將那些不在本地術語中的同義詞排除在外。其餘的同義詞將被推薦給開發人員以代替原始術語。如果找到多個同義詞進行推薦，Coronado 將使用 2.1 節中所述的術語“共現矩陣”對它們進行排名。輸入查詢的其他術語中出現頻率更高的同義詞排名更高。 我們在圖 4 中說明了查找同義詞的過程。
2.3.3 錯詞校正
對於那些既不存在於本地術語中又不存在同義詞庫中的同義詞的術語，Coronado 將其視為本地術語中的拼寫錯誤。因此，Coronado 嘗試更正它們。校正算法採用 2-gram 索引，可以快速找到與錯誤拼寫相似的術語。
具體地說，此校正算法首先創建一個具有 416（26 * 26）行的校正表，其中每一行都用一對字母（從“ aa”，“ ab”，“ ac”到“ zz”）標記。接下來，對於本地的每個術語，Coronado 將該術語插入到表中其標籤屬於該術語一部分的行中。例如，假設術語“example”是本地術語，則插入到“ ex”，“ xa”，“ am”，“ mp”，“ pl”和“ le”的行中。插入完成後，Coronado 準備通過以下步驟使用此表來糾正給定的錯誤拼寫：
- 對於錯誤拼寫，我們首先計算其將插入的行。
- 接下來，我們分析這些行中的現有術語，並找出與錯誤拼寫共享行最多的術語，作為其更正。如果找到多個這樣的術語，我們進一步選擇距錯誤拼寫編輯距離最小的那個作為校正術語。
計算完搜索後推薦，Sando 在搜索框下顯示推薦的查詢。每個查詢都是一個超鏈接，單擊該鏈接將導致 Sando 搜索相應的查詢，如圖 5 所示。
3. 進一步工作
通過改進和完善搜索推薦技術，可以在我們的工作基礎上做進一步的研究。例如，未來的搜索工具可以使用興趣度模型來更好地對推薦的查詢進行排名，使用上下文信息來推薦與開發人員的近期活動相關的搜索查詢。
改進推薦技術的第二種方法是為搜索中的軟件集成特定領域的詞彙知識。在當前的 Coronado 實施中，在開發人員的手動搜索失敗後，我們僅使用軟件工程詞庫和英語詞庫來推薦相關術語。我們相信特定領域的詞庫可以進一步提高推薦字詞的質量。例如，如果開發人員在醫學應用程序中進行搜索，則在醫學領域推薦相關術語可能會導致更有希望的查詢。
改善推薦效果的另一種方法是根據其他人員的成功查詢向開發人員推薦查詢。這樣的技術可以利用相同代碼庫的開發人員的數據進行協同過濾，以推薦更好和更相關的查詢。在開發更好的推薦技術之前，本地代碼搜索工具的用戶經驗會有所幫助。分析日誌文件固然可以挖掘使用模式，但無法理解開發人員行為的原因。例如，我們知道用戶使用搜索前推薦的頻率要比搜索後推薦的頻率低，但如果不進行用戶研究，我們就不知道為什麼會這樣。
推薦查詢的另一個改善方面是讓用戶快速建立對推薦系統的信任，有幾種實現此目標的方法，例如改善工具的用戶界面，給出具體建議，演示或提供可見的外部學習材料。
致謝
感謝國家重點研發計劃課題：基於協同編程現場的智能實時質量提升方法與技術（2018YFB1003901）和國家自然科學基金項目：基於可理解信息融合的人機協同移動應用測試研究（61802171）支持！
本文由南京大學軟件學院 2018 級碩士生袁陽陽翻譯轉述。
閱讀更多 慕測科技 的文章
