0 引 言

代碼的重用性在軟件工程領域是一個很重要的課題。通過面向對象分析、模塊化編程，開發者可以很大程度地提升代碼的重用性。但在具體編碼時，仍然會遇到很多在方法層面上需要重用的情況?？紤]如尋找一段可直接使用的尋路算法，或者是矩陣打包算法。這些具有特定功能的源碼在目前通過關鍵字搜索的方式下很難在海量源碼中被搜索到。原因有3 個: 1\\) 源碼中變量名的命名法通常使用縮寫，并以大寫字母進行分詞，如 preNode，inＲect 等，而用戶進行搜索輸入的關鍵字更偏向自然語言，如 previousnode，input rect。這導致很多源碼無法通過關鍵字匹配算法匹配。2\\) 在 Sourceforge 或者 Github 即使存在匹配的關鍵字，更多的搜索結果是頭文件或接口，很少有實際可用的源碼。3\\) 自然語言存在同義詞問題，語義相近的源碼會由于無法被字符串匹配而錯過。如用戶輸入 draw node，draw\\( vertex［］v\\) 就不會被搜索到。

文獻通過以語義網絡為文本關鍵字建立近義詞索引的方法，改善了文本搜索問題中近義詞無法被關鍵字匹配算法所匹配的問題。本文將該方法運用于源碼搜索，并結合傳統的程序分析技術，提出一種海量源碼分析的新方法，解決上文提到的源碼搜索遇到的 3 方面問題。

1、 相關工作

1． 1 基于關鍵字的海量源碼搜索引擎

傳統源碼搜索引擎采用關鍵字匹配的算法，如Github 的代碼搜索服務，其優勢是搜索迅速，可以用通用的文本搜索引擎檢索源碼，而缺陷如引言所述，無法匹配源碼中的縮寫，以及搜索結果大部分是無數據流的方法聲明。

1． 2 基于自然語言的源碼定位

Emily Hill在基于自然語言的源碼定位方面做了很多建設性的工作。其主要目的為了解決軟件開發過程中由于缺少文檔而導致的軟件維護困難問題，幫助開發者更方便地定位系統模塊，了解系統結構。其核心思想是通過分析制定項目，為項目中的標識符建立源碼索引，如 strtPt: start point，srcNode: sourcenode。最后通過用戶輸入的自然語言詞素與標識符拓展后的詞素進行匹配達到源碼定位的目的。

2、 分析及搜索方法描述

本文將 Emily Hill的自然語言源碼定位應用于海量數據，并構建一個包含海量源碼變量使用關系與詞素拓展集的數據庫。在此之上運用關鍵字匹配算法定位相關源代碼。

2． 1 源碼 identify 縮寫拓展到自然語言單詞

本文提出一種樹狀單詞樹用以解決將標識符從縮寫到完整詞素的拓展算法。如圖 1 所示。

構造完成的單詞樹是一種包含所有英語詞素的樹狀數據結構，其中每個節點有且僅有一個字符信息，并附帶標志位 isWord，其中自頂向下的路徑表示一個詞素序列，當節點上 isWord 被標記時，代表路徑到此為止構成的序列是一個完整詞素。圖 1 以“． ”作為完整詞素標記。以下是節點數據結構的定義：

如圖 2 所示，對一棵單詞樹 T，插入詞素 w1w2…wn的過程如下:令 T［wi］表示字符 wi在第 i 層對應的節點。則 T［w1］是根節點下字符為 w1的節點。倘若不存在，則創建對應節點。對每個 wk，k ＞1，尋找 T［wk － 1］節點下是否存在字符為 wk的節點，倘若存在，則 T［wk］為該節點，若不存在則創建字符為 wk的子節點。圖 1 所示為在一棵空單詞樹上插入 act，active，activity，black，actual 幾個詞后的示意圖。

將全詞素列表的每條詞素按上述算法插入一棵空樹，最后得到的結果即包含全詞素的單詞樹。在已建立的單詞樹基礎上，對標識符 I 拓展完整詞素備選集的問題可劃歸為樹路徑搜索問題，令 I［i］表示 I 中第 i 個字符，滿足條件的路徑必須依次\\( 不必連續\\) 包含內容為 I［1］，I［2］，I［3］，…，I［n －1］字符的節點，并以 isWord 標記為 true 的節點終止，該問題是一個深度優先搜索問題。圖 1 示例中，對“actv”尋找完整詞素拓展集合的結果即為{ activity，active} 。

以下為詞素擴展過程偽代碼。

過程: Node［］expand \\( root，I，offset\\) 。
輸入: root 表示自然語言單詞樹根節點，I 表示要拓展的標識符字符串，offset 表示 I 的起始偏移量。
返回: Node［］表示每條滿足要求的路徑的最后節點，該節點 isWord 必須為 true。

通過該算法獲得的節點集合對每個節點不斷訪問 parent 即可獲得該節點對應的完整路徑，即一個完整詞素。

2． 2 海量數據庫建立

基于語義的搜索過程如圖 3 所示。

本文的核心思想是通過分析海量源碼，建立源碼數據庫，數據庫中包含源碼中標識符之間的關系，以及標識符對應的完整詞素的擴展。

源碼中標識符的關系主要包含以下 2 點:

1\\) 方法與變量的從屬關系;2\\) 同一方法體內變量的使用關系。以上 2 點主要通過傳統的程序分析方法建立，本文使用的工具是 JavaCC，對源代碼進行靜態的語法分析，最后以關系型數據庫 MySQL 持久化分析結果。

2． 3 搜索算法

令函數 Similarity\\( wi，wj\\) 代表 S 中 2 個單詞的語義近似度，其值域為［0，1］，該值的獲取方法通過 Dis-co Wiki 數據庫，其結構如圖 4 所示。

最后按降序排列的方法結果集合即為搜索結果。

3、 測試結果及分析

實驗從功能及性能 2 方面進行評測，通過不同難度的測試用例，統計使用者對本引擎的搜索結果與Github 搜索結果匹配度進行對比以評價引擎的可用性。

3． 1 搜索用例測試

測試用例實驗主要通過提供 4 組不同難度的測試用例，并召集 10 位志愿者分別在 Github 上與在本引擎上搜索測試用例，并將前 10 條結果匹配率作為反饋進行比較。當結果中包含具體源碼，源碼標識符內容與輸入所匹配時，算作一條匹配結果。

測試用例 1: 尋找圖表繪制 API 相關源碼。根據本文定義的格式，以{ chart; draw; Φ} 作為輸入。

測試用例 2: 本例采用實現較為多樣化的最大流問題作為搜索。以{ source，stream; max; Φ} 作為關鍵字進行查詢。

測試用例 3: 本例作為測試用例 2 的對比測試，以更精準的{ source，flow; max; Φ} 搜索最大流算法。該測試用例主要測試語義近似對搜索結果的影響。

測試用例 4: 尋路算法尋找，輸入{ start; find，path; Φ} 。

由圖 5、圖 6 可知，在匹配度上，4 組測試用例中本文的搜索結果均高于 Github，在實驗中，Github 的搜索結果大部分是接口聲明，本文的搜索結果均包含匹配關鍵字的數據流，具有可工作源碼。在語義近似的測試用例上，如最大流問題的 stream 與 flow，沒有flow 關鍵字時，Github 不存在匹配的結果，而本文的方法在前 10 項搜索結果中仍然包含匹配的源碼。4項測試的比較中，本文提出的方法搜索結果均強于Github 的搜索結果。

3． 2 性能測試

該測試根據參數擴展集最大容量 maxArg、被影響參數擴展集最大容量 maxAffected、調用圖搜索的最大深度 d、詞匯泛用性 v 為基準對搜索引擎性能進行評估。測試結果如表 1 所示。

表 1 中的數據表明，參數和被影響參數對搜索時間影響是線性的，被影響參數系數更大，原因是被影響參數集合大小決定了調用圖搜索的復雜度。而深度的增加對時間的增加是高于線性的，因為廣度優先搜索每多搜一層其元素將是上一層的 k 倍，k 取決于節點的平均子節點數量。單詞的泛用性，高的指 object等泛用名字，低的指詞義信息具體的名詞，對搜索時間影響得非常大，原因是單詞泛用性決定了搜索引擎構筑的語義網絡的出度，從而影響備選集的容量。

4、 結束語

本文通過結合程序分析與語義網絡，通過大數據分析的方法，為源碼中的標識符建立使用關系。本文基于縮寫拓展算法，設計適用于程序標識符縮寫的自然語言單詞拓展算法。通過使用自然語義近似網絡，將用戶的關鍵字進行拓展，與之前生成的源碼標識符拓展集合結合搜索，解決了以往源碼搜索引擎因源碼使用縮寫而導致的關鍵字不匹配或無法搜索到語義近似的源碼的問題。

在實際使用過程中，該引擎能夠搜到主流通用算法，如尋路、3D 飛行、圖像壓縮等。搜索時間取決于單詞的通用性與專業性，以及調用圖的深度。通過為開發者提供方法層面的可靠搜索引擎，能夠大幅度提升開發者的開發效率。