基于序列到序列模型的代碼片段推薦*

閆 鑫，周 宇+，黃志球

1.南京航空航天大學 計算機科學與技術學院，南京 210016

2.南京航空航天大學 高安全系統的軟件開發與驗證技術工信部重點實驗室，南京 210016

1 引言

在當前開源的軟件生態環境下，海量代碼及多種相關代碼描述信息可以公開、免費地獲取，而且軟件數量及規模正在迅速擴大，這也就為代碼復用奠定了基礎。Gabel 等人[1]對超過6 000 個開源項目的約4.2 億行代碼進行了統計和研究，發現軟件通常缺少唯一性（uniqueness），即程序代碼經常是重復的，這也為代碼復用提供了理論支撐。有效的代碼復用可以提高開發者的開發效率，降低開發成本。

在實際軟件開發過程中，代碼推薦是一種常用的實現代碼復用的方法。為了實現一個特有的代碼功能，開發者通常會通過給定一個用戶查詢，從代碼庫中檢索和復用已有的代碼。

當前存在有很多的代碼推薦方法[2-3]，這些方法通常是基于信息檢索技術來實現。McMillan 等人[4]提出了Portfolio。它通過關鍵字匹配和佩奇排名（Page-Rank）返回一個函數鏈。Lv 等人[5]提出了CodeHow，通過一個拓展的布爾模型把文本相似度和應用編程接口匹配相結合，來實現代碼檢索和推薦。

基于信息檢索的代碼檢索和推薦方法存在的一個根本的問題在于自然語言查詢的高層級的意圖與代碼的低層級的實現細節不匹配[6]。它們兩者之間或許并沒有共同的詞匯、同義詞、近義詞和語言結構，只是存在一定的語義相關性，而基于信息檢索的方法并不能解決這個問題。

針對上述問題，本文提出了一種基于序列到序列模型的代碼片段推薦方法，該方法不再是直接計算自然語言查詢和代碼之間的相似度，而是首先訓練一個自然語言查詢生成模型用于實現代碼到對應的自然語言查詢的生成。然后，通過計算用戶輸入的自然語言查詢與代碼片段對應的生成查詢之間的相似度,檢索并推薦相關度高的代碼片段給開發人員。自然語言查詢之間的相似度不再存在語義差的問題，這也就解決了自然語言查詢與代碼之間語義差的問題。

本文從StackOverflow 問答網站上提取數據并構建語料庫，確保數據是真實的自然語言查詢和相匹配的代碼片段。通過計算推薦結果的平均倒數排名（mean reciprocal rank，MRR）來驗證方法的有效性。實驗結果表明，基于序列到序列模型的代碼推薦方法DeepCR 能有效提高代碼推薦效果，優于現有研究工作，能夠很好地完成代碼推薦任務，為開發人員輸入的自然語言查詢提供精準的代碼推薦。

本文工作的主要貢獻在于以下兩方面：

（1）利用程序靜態分析技術，設計啟發式規則，對Stack Overflow 問答網站上積累的龐大數據進行了清洗和篩選，構建了一個干凈的代碼庫，用于代碼片段推薦的研究工作；

（2）結合深度神經網絡技術和程序靜態分析技術，訓練自然語言查詢生成模型，為代碼片段生成自然語言查詢，執行生成的查詢與用戶輸入的查詢之間的相似度計算，進而提出一種基于序列到序列模型的代碼片段推薦方法DeepCR，致力于解決自然語言查詢與代碼片段之間語義差的問題。

2 相關工作

當前，存在很多傳統的基于信息檢索的代碼推薦方法。Ohloh、Krugle 和Sando[7]都是代碼推薦引擎，可以根據自然語言查詢中出現的關鍵字或者正則表達式來推薦代碼片段。Linstead 等人[3]提出了Sourcerer。它是一個基于Lucene 的用于大規模代碼庫的代碼推薦工具。它通過把代碼的文本信息和結構信息相結合來實現代碼推薦。SNIFF[8]則整合了代碼片段中包含的Java APIs 的注解信息，執行與自然語言查詢的相似度計算過程，進而實現代碼片段的推薦。這些傳統的信息檢索方法存在的一個基本問題是自然語言查詢的高層級的意圖與代碼的低層級的實現細節不匹配。

近年來，研究者也提出了一些基于深度神經網絡技術的代碼推薦方法。Gu 等人[9]提出了DeepCS，通過神經網絡模型將代碼和自然語言描述映射到高維度向量中，使得代碼片段和其對應的自然語言查詢具有相似的向量呈現，通過計算兩者之間的余弦相似度來實現代碼推薦。Yao 等人[10]提出了CoaCor。它結合強化學習相關技術訓練一個代碼注解模型，為代碼生成注解，并結合DeepCS 中所提出方法的基本框架訓練代碼檢索模型，綜合計算兩者之間的相似度得分，進而實現代碼推薦任務。

3 代碼推薦方法DeepCR

本章將對所提出的代碼推薦方法DeepCR 進行詳細介紹。DeepCR 的整體架構圖如圖1 所示。DeepCR 致力于根據開發人員輸入的自然語言查詢，推薦Java 相關的代碼片段。DeepCR 由三個核心模塊組成：數據準備、自然語言查詢生成模型訓練以及基于序列到序列模型的代碼片段推薦。

3.1 數據準備

考慮到代碼推薦的應用場景中開發人員輸入的均為自然語言查詢，且考慮到一些問答網站上的問題都是真實的自然語言查詢，為了保證所收集的數據的真實性和可靠性，本文選擇從Stack Overflow 上收集數據。數據準備過程包括數據收集和清洗、代碼信息提取和代碼標識符替換。

3.1.1 數據收集和清洗

Stack Overflow 問答網站上包含超過1 790 萬個問題，考慮到本文所提出的方法DeepCR 是針對Java編程語言相關的代碼推薦，因此只將標簽中包含Java的問題集合作為數據候選集，問題總量超過150 萬。

只做到這一步，所提取的數據候選集的質量依舊參差不齊。圖2 展示了一個來自于Stack Overflow問答網站的問題示例。如圖2 所示，每個用戶的自然語言查詢都對應著一系列的標簽，以及不定數量的答案，而每個答案的主體部分則可能包含著不定數量的代碼片段。

為了構建一個干凈的數據集，需要針對每個自然語言查詢，提取和篩選出與自然語言查詢匹配的代碼片段，構建高質量數據集。因此，本文利用程序靜態分析技術，尤其是抽象語法樹解析技術，設計啟發式規則，對數據候選集進行清洗和篩選，具體體現在以下幾方面。

Fig.1 Overall framework of DeepCR圖1 DeepCR 的整體架構

Fig.2 Example of question from Stack Overflow圖2 一個來自于Stack Overflow 上的問題示例

（1）答案主體中不包含代碼片段。本文的目標是做代碼片段推薦，如果與自然語言查詢相對應的答案中沒有任何的代碼片段，顯而易見，此類答案不能作為數據集的一部分，則將其濾除。

（2）答案主體中的代碼片段不是Java 代碼。本文是針對Java 語言做代碼片段推薦，不涉及其他編程語言，如Python、C++、SQL，甚至是偽代碼等。因此，對不是由Java語言構成的代碼片段進行過濾。

（3）答案主體中的代碼片段粒度不符合要求。本文的代碼推薦的最大粒度是單個Java 方法，但答案主體中包含的代碼片段可能是一個完整的Java類、包含兩個或更多的Java 方法、構造函數或者靜態代碼塊等。這些代碼片段雖然都是Java 代碼，但與本文的代碼推薦粒度不符，因此此類代碼片段也會被濾除。

（4）答案主體中的代碼片段包含不屬于JDK（Java development kit）的方法調用。當前存在著海量的Jar包，把所有相關的Jar 包中包含的方法調用囊括到一個代碼推薦方法中務必會使推薦方法的準確性和可靠性大大降低，而JDK 是Java 軟件開發必不可少的軟件開發工具包，且功能強大。因此，本文出于代碼推薦的準確率和可靠性的考量，針對的是與JDK 相關的代碼推薦，對于包含不屬于JDK 的方法調用的代碼片段也會被濾除。

（5）自然語言查詢不是一個具體的編程任務。一個自然語言查詢，由于其開放性和自由性，所涉及的可能并不是一個具體的Java 編程任務，而是詢問不同點、原因等。例如，“What is the difference between an int and an Integer in Java and C#?”“Why can’t I use a try block around my super() call?”。這類自然語言查詢均不涉及一個具體的編程任務，均不可作為有效數據集的一部分而存在，為此人工對數據進行了研究和總結，設計了一些啟發式規則，進而實現對此類冗余數據進行過濾和清洗。

3.1.2 代碼信息提取

在此步驟中，結合抽象語法樹解析技術，并調用Eclipse JDT提供的大量應用編程接口（application programming interfaces，APIs）來實現代碼信息的提取。

對于每一個Java 方法，對其做抽象語法樹解析，提取方法名、常量、變量名、類型名、方法調用名以及內部方法聲明信息。

形式上而言，給定一個Java 方法的抽象語法樹，采用深度優先搜索對其做遍歷操作。具體地，通過解析抽象語法樹的MethodDeclaration 節點來獲取方法名和內部方法聲明信息；通過解析NumberLiteral、StringLiteral 和CharacterLiteral 節點來獲取常量信息；通過解析SimpleType、PrimitiveType、QualifiedType 等節點來獲取類型名信息；通過解析MethodInvocation等節點來獲取方法調用名信息；通過解析SimpleName節點來獲取變量名信息。

圖3 給出了一個代碼片段示例，圖4 則給出了代碼片段對應的抽象語法樹示例。出于空間的考慮，只展示代碼片段對應的抽象語法樹到語句層級。

Fig.3 Example of code snippet圖3 一個代碼片段實例

通過調用相關API，抽象語法樹中的節點可以被精確定位，并且代碼信息可以輕松地獲取到，并將所提取的信息與對應的代碼片段形成映射，一一對應，至此代碼信息提取工作完成。

3.1.3 代碼標識符替換

由于標識符命名的開放性，當代碼片段的量級達到一定程度時，則代碼片段的詞匯表的數量會很自然地超出一個合理的詞匯表的大小。因此，合理的詞匯表壓縮方法是極其有必要的。

為了合理地對詞匯表進行壓縮，采用了一種標識符替換方法來把代碼的詞匯表大小壓縮到一個合理的范圍內。具體而言，利用從Java 方法中提取到的代碼信息將代碼片段中的一些標識符替換為一些特定的詞匯。首先，計算所有代碼片段中每個詞匯的出現頻次，并選取出現頻次最高的30 000 個詞匯作為代碼片段的初始詞匯表；其次，根據初始詞匯表以及提取到的代碼信息對代碼片段執行標識符替換操作。標識符替換操作可以被分為6 類，具體包括方法名替換、常量替換、變量名替換、類型名替換、方法調用名替換以及內部方法聲明替換。相應地，引入了一些特定的詞匯作為替代詞匯，標識符替換類別和引入的特定詞匯如表1 所示，其中k是一個從0 開始計數的正整數。

Table 1 Categories and rules of identifier replacement表1 標識符替換類別及替換規則

Fig.4 Example of abstract syntax tree for code snippet圖4 一個代碼片段的抽象語法樹示例

具體而言，考慮到對每一個Java 方法而言，只存在唯一的一個方法名，因此引入一個固定的詞匯METHODNAME 作為方法名的替代詞匯。考慮到去區分不同的字符串常量、字符常量和數字常量意義不大，因此，分別引入特定的詞匯STRINGLITERAL、CHARACTERLITERAL 和NUMBERLITERAL 來 作為字符串常量、字符常量和數字常量的替換詞匯。至于其他的特定詞匯都包含一個變量k，用來表示當前Java方法中出現的特定類別的第k個標識符。

舉例而言，圖5 展示了一個經過標識符替換操作的代碼片段示例。變量vari和alist由于出現頻次過低，不存在于初始詞匯表中，因此執行變量名替換操作，即用SIMPLENAME_k的形式替換變量vari和alist，k為從1 開始計數的正整數。因此，vari和alist被分別替換為SIMPLENAME_1 和SIMPLENAME_2。

Fig.5 Example of identifier replacement圖5 一個標識符替換示例

經過標識符替換操作后，超出初始詞匯表的標識符均會被替換為表1 中引入的特定詞匯。進而，所有代碼片段的詞匯表大小就會被壓縮到一個合理的范圍內。最終，用于后續自然語言查詢生成模型訓練的代碼片段的詞匯表以及數據集也會被確定，構建一個＜代碼，查詢＞對的數據集。

3.2 自然語言查詢生成模型訓練

在此步驟中，致力于訓練一個基于序列到序列模型的自然語言查詢生成模型。序列到序列模型已經被廣泛應用于各種神經網絡機器翻譯（neural machine translation，NMT）任務[11-12]中。

大體而言，序列到序列模型可以簡單地分為兩個循環神經網絡（recurrent neural network,RNN）結構，即一個編碼器、一個解碼器。編碼器負責把輸入序列通過非線性變化映射到一個固定維度向量中去，而解碼器則是把固定維度的向量映射到相應的目標序列。當輸入序列較長時，這個中間向量難以存儲足夠的信息，就成為序列到序列模型的一個瓶頸。因此，引入注意力機制（attention mechanism）[13]對編碼器每個隱藏狀態做加權處理，允許解碼器隨時查閱輸入序列中的部分單詞或片段，因此不再需要在中間向量中存儲所有信息。本文選用長短期記憶網絡（long short-term memory，LSTM）——循環神經網絡的一種變體，作為序列到序列模型的基本神經單元，模型示意圖如圖6 所示。

編碼器的輸入對應于代碼片段的向量表示。以編碼器為例，輸入序列是(x1,x2,…,xm)，其對應的輸出隱藏狀態序列則為(h1,h2,…,hm)，而當前隱藏狀態ht的更新是根據當前輸入xt以及前一隱藏狀態ht-1實現，其對應的計算公式如下：

解碼器則是給定上下文向量Ct以及先前預測的輸出序列(y1,y2,…,yt-1)來預測下一個輸出詞匯yt出現的概率，最終產生輸出序列(y1,y2,…,yn)，計算公式如下：

其中，st是解碼器在t時刻的隱藏狀態，公式如下：

Ct是根據編碼層的編碼器的隱藏狀態作加權，計算公式如下：

其中，hk為編碼層輸出的隱藏狀態，αtk為對應的權重，其計算公式如下：

Fig.6 Seq2Seq model with attention mechanism圖6 結合注意力機制的序列到序列模型

3.3 基于序列到序列模型的代碼片段推薦

DeepCR 通過以下幾個模塊實現方法層級的代碼推薦：

（1）自然語言查詢生成。自然語言查詢生成模型訓練的目的即為對推薦代碼庫的代碼片段生成相匹配的自然語言查詢。由此，每個代碼片段也就存在了一個與之匹配的由模型生成的自然語言查詢。推薦代碼庫中的元素也就以＜代碼片段，生成的查詢＞對的形式存在。

（2）相似度計算。由于推薦代碼庫中每個代碼片段都有了與之對應的生成的查詢，因此用戶查詢與代碼之間的相似度可以轉化為計算生成的查詢與用戶查詢之間的相似度。在計算相似度之前，結合較為流行的Stanford POS Tagger（詞性標注器）[14]對生成的查詢和用戶查詢執行小寫化、停止詞刪除和詞干提取等操作，對自然語言查詢執行數據預處理操作。在此基礎上，本文采用TF-IDF（term frequencyinverse document frequency）[15]來進行兩者之間相似度的計算。Lucene 是一套用于全文檢索和搜尋的開源程序庫，由Apache軟件基金會支持和提供。Lucene提供了一個簡單卻強大的API 庫，能夠做全文索引和搜尋。在Java 開發環境里Lucene 是一個成熟的免費開放源代碼工具，使用Lucene 提供的TF-IDF 算法來進行相似度計算。

（3）代碼片段推薦。通過上述步驟中相似度計算結果，確定相似度得分最高的生成的查詢的列表。由于代碼和生成的查詢之間存在映射關系，則從推薦代碼庫中檢索相對應的代碼片段，并將其呈現給用戶，作為代碼片段推薦結果。

4 實驗評估

4.1 實驗設置

本文的實驗平臺為Intel i7-6700 3.4 GHz處理器、GeForce GTX 1070 Ti 的GPU 以 及32.0 GB RAM 的臺式機，搭載Ubuntu 18.04 LTS操作系統，使用JDK1.8版本，并使用Eclipse 作為數據處理的集成開發環境，使用Python3，結合Tensorflow 框架作為自然語言查詢生成模型訓練和預測的運行環境。

針對自然語言查詢生成模型的訓練，使用隨機梯度下降算法來訓練和更新模型參數，LSTM 隱藏狀態和詞嵌入的維度均設為512，學習速率初始值設為0.99，對應的影響因子設為0.8。為避免過擬合，設置模型參數dropout的值為0.3。

4.1.1 數據準備

從Stack Overflow 官方的數據倉庫下載了原始數據，解壓后數據集的大小超過70 GB，與Java 相關的問題總數超過150 萬。基于3.1 節所述的數據清洗操作，最終獲得了48 003 條有效數據，每條數據中問題（即自然語言查詢）和答案（即代碼片段）一一對應。接著按照9∶1 的比例將數據劃分為訓練集和測試集，即訓練集包含43 203 條，測試集包含4 800 條數據。按照Iyer 等人[16]的方法，從測試集中隨機抽取200 條數據用來評估代碼片段推薦方法的性能。

4.1.2 評估指標

采用MRR（mean reciprocal rank）[17]和Hit@K[18]來對代碼推薦性能進行評估。

對用來評估代碼推薦性能的數據集中的每一條數據＜代碼片段C，查詢Q＞對，把C作為有效代碼片段，并從數據集中隨機抽取K個與Q不匹配的代碼片段作為無效代碼片段。進而，給定查詢Q，計算代碼片段C在K+1 條候選集中的排序。按照文獻[10,16]中采用的方法將K設為49。代碼推薦性能則根據整個數據集D={＜C1,Q1＞,＜C2,Q2＞,…,＜C|D|,Q|D|＞} 上的MRR來進行評估：

其中，Ranki表示對于查詢Qi，代碼片段Ci的排序結果。MRR的值越高，則代碼片段推薦性能越好。

還采用Hit@K來評估DeepCR 的代碼片段推薦性能。Hit@K(K=1,3,5,10)的計算公式如下：

其中，Id表示對于查詢Qi，代碼片段Ci是否在前K個推薦結果中，如果在，Id取值為1，否則為0。

多次重復執行此實驗，來確保實驗結果的真實性和可靠性。

4.2 實驗結果

4.2.1 基準實驗

為了檢測DeepCR 在代碼推薦性能上的有效性，把DeepCR 與傳統的信息檢索方法BM25[19]和TF-IDF進行對比。BM25 和TF-IDF 是兩個比較具有代表性的計算文本相似度的算法。考慮到代碼和自然語言查詢之間的語義差，在用傳統的信息檢索方法計算代碼和自然語言查詢之間的相似度時，對代碼中的標識符做了駝峰式命名法分詞、小寫化、停止詞去除、詞干提取等操作。

4.2.2 實驗結果

表2 呈現了所提及到的3 種不同的代碼推薦方法以MRR 為度量指標重復執行20 次的實驗結果。DeepCR 嘗試訓練自然語言查詢生成模型為代碼片段生成查詢，以此來消除代碼和查詢之間的語義差。從表2 可以得知，DeepCR 的代碼推薦性能優于TFIDF 算法和BM25 算法。具體而言，DeepCR 的MRR得分相較于TF-IDF 算法提升了0.22，相較于BM25算法提升了0.18，由此可見DeepCR 代碼推薦方法的有效性。

Table 2 MRR of 3 methods for code recommendation表2 3 種不同代碼推薦方法的MRR 得分

表3 呈現了所提及的3 種不同的代碼推薦方法以Hit@K（K=1,3,5,10）為度量指標重復執行20 次的實驗結果的平均值。從表3 可以得知，BM25 的代碼推薦性能略優于TF-IDF算法，而DeepCR的Hit@K得分相較于TF-IDF 和BM25 算法均有明顯提升，DeepCR 在Hit@1 的得分達到了38.25%，相較于TF-IDF 和BM25，分別提升了23.17 個百分點和19.12 個百分點，由此可見DeepCR 代碼片段推薦方法的有效性。

Table 3 Hit@K of 3 methods for code recommendation表3 3 種不同代碼推薦方法的Hit@K 得分 %

5 有效性威脅

本文針對的是Java 相關的代碼片段推薦工作，而沒有拓展到其他編程語言，因此編程語言可能是一個對本文方法有效性產生威脅的一個因素。將來會結合不同編程語言各自的特點，將本文的方法擴展到其他的語言環境。

數據有效性。所提取的數據來源于Stack Overflow問答網站上的數據。由于問答網站對問題以及回答的開放性和自由性，所收集的數據集中存在大量低質量的數據，以至于對自然語言查詢生成模型的訓練造成威脅。鑒于此，對收集的數據做了一系列清洗和篩選操作，以保證數據質量的可靠性和有效性，盡可能減少存在于最終的數據集中的噪音。

6 結束語

本文提出了一種基于序列到序列模型的代碼片段推薦方法DeepCR。該方法結合程序靜態分析技術，對代碼做抽象語法樹解析，提取代碼信息，構建訓練集；運用序列到序列模型，訓練自然語言查詢生成模型；根據訓練好的查詢生成模型，對代碼庫的代碼生成對應的查詢；通過計算用戶輸入的自然語言查詢與代碼對應的生成查詢之間的相似度計算得分，檢索并推薦相關度高的代碼片段給開發人員。DeepCR 的MRR 和Hit@K得分均明顯優于傳統的信息檢索方法的代碼推薦性能，能夠有效提高代碼推薦效果，為開發人員提供精準的代碼片段推薦。