一種基于調用序列網絡的API推薦方法

肖海濤 王鵬 包義祥 何鵬

摘要：隨著計算機程序的日益復雜，代碼自動補全功能需求越來越迫切。圍繞軟件編碼過程中API調用問題進行探究，利用代碼中API之間的調用序列，構建API關系網絡模型，從服務推薦角度實現精準的API推薦，從而提高軟件項目開發效率。實驗結果表明，基于API序列關系網絡模型推薦方法具有可行性，且在推薦列表長度較大的情況下方法更具優勢，相比基準方法推薦精度可提高7.5%。在推薦過程中提供的API子序列越長，推薦結果越準確，但耗時明顯增加。在子序列長度為5時，方法推薦精度與運行時間可達到相對適中的效果。

關鍵詞：API推薦；服務計算；復雜網絡

DOI：10.11907/rjdk.173166

中圖分類號：TP301

文獻標識碼：A文章編號：1672-7800（2018）007-0079-04

Abstract：Withthecomplexityofcomputerprogramgrows，thefunctionalrequirementofautomaticcodecompletionbecomesmoreandmoreurgent.ThepaperexplorestheproblemofAPIcallsinsoftwarecoding，usingthecallsequencebetweencodeofAPIandbuildingAPInetworkmodel.ItachieveaccurateAPIrecommendationfromtheperspectiveofservicerecommendationsoastoimprovetheefficiencyofsoftwaredevelopmentprojects.TheexperimentalresultsverifythefeasibilityoftherecommendedmethodbasedonAPIsequencerelationnetworkmodels，andthemethodismoreadvantageouswhentherecomendationlistislongerfortherecommendationaccuracycanbeincreasedby7.5%comparedwiththebenchmarkmethod.TherecommendedresultismoreaccuratewhentheAPIsequenceislongerintheprocessofrecommendation.Onthewhole，whenthesubsequencelengthis5，therecommendationaccuracyandrunningtimecanachieverelativelymodestresults.

KeyWords：APIrecommendation；servicecomputing；complexnetwork

0引言

隨著計算機程序的復雜性與計算能力并行增長，軟件開發逐漸成為一項由多個開發人員共同合作完成的工作，其需要復雜的源代碼管理與調試工具對開發人員的工作進行調整。IDE開發工具的核心包括代碼自動補全功能，而代碼自動補全功能中API推薦是指通過系統提示幫助開發者更準確地找到需要調用的API。在軟件系統規模與復雜性加劇時，想要通過調用相應的API重用現有的類庫或框架，就必須了解使用哪些API及其調用順序。

API增長速度非常快，如JDK最新版本中類的數量已增長到3000個左右，相比最初的212個增長了數倍。對于API存在不準確代碼樣例、不完整文檔以及自身復雜性等因素，靈活使用這些API將面臨挑戰，同時發現潛在的服務或API也變得越來越困難[1]。微軟的一項調查顯示，67.6%的受訪者提到在學習API時面臨資源不足或缺乏的困擾[2]。有研究表明，API用戶面臨的挑戰是如何發現可以幫助完成任務的API子集[3]。API的可用性成為影響開發人員效率的關鍵，使用API降低了開發人員的工作效率[4]。從搜索引擎中尋找特定功能的API，效率低且大多數搜索引擎都是通過關鍵字匹配完成的，準確率較低。

這些問題的存在使開發人員在代碼編寫過程中，由于不熟悉API使用方法，導致不能快速有效地找到下一個需要使用的API，從而降低了開發速度。現有API推薦方法普遍沒有利用API調用序列信息。本文通過API調用序列關系構建API調用關系網絡，利用復雜網絡理論進行有向路徑匹配，從而準確地實現了API推薦。

1相關工作

代碼補全系統通過API元素（方法、字段等）提示的方式幫助開發者使用API。傳統的代碼補全系統一般只考慮API的兼容性與可見性，推薦大量的API元素并按照字母表排序，使得面對復雜編碼時，推薦的API準確率較低。

為提高API推薦準確率，有研究者提出利用數據挖掘算法挖掘API使用模式進行推薦，從而提高開發者的開發效率。如DynaMine使用Apriori算法，FrUit使用Opus算法[5]等。將API使用模式根據結構與語義分為不同的組，根據相關程度進行推薦[6]。而數據挖掘忽略了API元素調用順序信息，實際推薦過程中，推薦順序對推薦結果有至關重要的作用，因此有必要考慮API的調用序列模式。

序列模式挖掘考慮了數據集中的元素調用先后信息，如Alattin和Xie[7]利用頻繁模式挖掘方法找出調用API前必須滿足的條件。Scenariographer等[8]通過字符串處理方式發現方法調用序列，并將序列規則表示為正則表達式。Asaduzzaman等[9]開發Eclipse插件CSCC，實現了根據當前編輯代碼的上下文信息，通過API推薦幫助用戶補全代碼。Perracotta[10]使用啟發式方法實現API推薦。Raychev等[11]提出一種基于圖（Groum）統計語言模型。GraLan利用貝葉斯推理進行子圖匹配。Raghothaman等[12]提出從用戶點擊數據中找到與用戶輸入的自由文本查詢相關的APIs，通過匹配GitHub代碼中API調用序列找到APIs相應的調用序列。Gu等[13]通過基于API調用序列的深度學習模型實現API推薦。Niu等[14]提出使用監督學習方法，在兩個階段基礎上，借助多種特征進行API推薦。Rahman等[15]從StackOverflow的問答中抽取與開發者自由文本查詢相關的API。

本文所采用的方式是利用代碼中各種依賴關系生成API調用關系網絡模型，再利用復雜網絡理論進行匹配、

過濾形成API推薦結果。

主要工作概括為兩個方面：

①利用開源工具PPA對Github上的開源軟件進行代碼解析，獲得代碼中API序列庫，根據API序列關系構建API序列關系網絡模型；

②利用復雜網絡理論，提出一種基于API序列關系網絡模型的API推薦方法，并驗證方法的有效性。

2理論基礎

2.1API序列

從大量軟件源代碼庫中提取API調用序列。PPA（PartialProgramAnalysisforJava）是一個靜態代碼分析工具，可將Java源代碼轉換為類型化的抽象語法樹，并可轉換為Jimple類型，用3地址表示，PPA在處理源代碼時，對于節點名稱與節點聯系并不作過多處理，只單純從中提取出API的調用及其調用順序信息。通過源代碼處理，可從源代碼中獲取API調用序列，形成一個API調用序列庫。

基于API調用序列庫，根據API序列中元素的上下關系，構建一條由上一個API元素指向下一個API元素的有向連邊，如圖1所示。為提高API調用關系網絡模型質量，對API調用序列庫作一定的預處理，將部分出現頻率極低的API調用序列過濾。具體處理流程：設置API序列長度閾值為10，將上述每個源代碼文件中得到的API調用序列切割成長度為10的API序列片段；②統計不同片段在整個庫中出現的頻率，此處只保留頻率大于等于2的API序列片段；③對保留的API序列片段構建API調用關系網絡。

2.2API推薦

API推薦可劃分為兩部分：①對測試的源代碼對應的API調用序列進行標記，確定預測位置（如標記為L），從API調用序列中預測位置L為參考位置，向前選擇所有長度小于閾值γ（γ≤10）的子序列；②按照閾值長度選擇子序列作為測試序列，輸入到基于調用關系得到的API調用網絡模型，根據路徑匹配結果形成API推薦列表。

3實驗分析

3.1實驗數據

本文實驗所用數據集如表1所示。為確保實驗結果可靠有效，從Github平臺上下載大量數據集，并從中提取一個數據量龐大的代碼庫，數據集包含1000個開源Java項目，共計104645個類，638293個函數，對應2039687個API。在數據選取過程中，過濾一些小程序以及PPA工具解析失敗項目。

3.2實驗步驟

方法整體框架如圖3所示。根據2.1中的方法獲得API調用序列庫，將其中一部分用作訓練數據集，通過上下調用關系構建API調用網絡模型，其中網絡模型相鄰兩個API元素關系出現的次數為其連邊權重。將測試集中的API元素作為輸入，在API調用網絡模型上進行匹配；推薦最可能的K個API元素，得到API推薦列表。

3.3評價指標

為了評價所提出的API推薦方法，使用如下判斷推薦成功的條件與常用的精度評價指標：

（1）假設在推薦的K個列表中，有當前測試API所需調用的下一個API，則認為推薦成功。

（2）Top-k推薦平均準確率。

該指標需要計算每個測試API推薦列表中推薦成功位置的倒數1r（r（r≤k）為推薦成功時的位置），對所有測試成功位置倒數求平均值，Q為測試API個數，表示為：

4實驗結果

4.1推薦方法有效性驗證

在實驗過程中，設置輸入測試的API子序列長度γ=1，即每個測試的API數據提供其前兩個調用API元素作為情景信息。在不同比例劃分訓練數據集情況下，根據返回推薦列表長度K取值不同，API推薦結果精度有差異。如圖4所示，用于訓練（構建API調用關系網絡模型）的API調用序列比例越大，推薦結果的精度越高，最高可達到52.3%。推薦過程中返回的推薦列表長度K整體越長推薦效果越好，且與測試數據集比例關系不顯著。

為進一步驗證本文方法效果，選取文獻[9-10]中兩種方法進行初步對比。為簡化實驗步驟，對比過程中僅以本文方法在測試數據比例為10%以下結果為主。如圖5所示，在k=1時，Apriori方法最好，為33.9%；但隨K值的增大Apriori方法優勢更明顯，其中Top-10結果達到52.3%的精度，相比兩種基準方法分別提高了7.5%和2.6%。綜上所述，本文提出的基于API調用序列關系網絡方法更有助于API推薦。

4.2參數γ對推薦結果的影響

如圖6所示，可以發現，提供的API子序列長度越大，推薦結果越準確，提供查找API元素的context信息越豐富，找到其下一個調用API元素可能性越大。如圖7所示，隨著參數γ增大算法耗時加長。由于提供的子序列長度γ越大，表示在關系網絡匹配過程中，需要對比的前綴元素越多，耗時越長。例如當子序列長度γ=9時，Τοp-10的推薦精度達到86.1%，但運行時間達21min。當子序列長度γ=5時，Τοp-10整體推薦精度與運行時間相對較為適中，精度為71.9%，運行時間為10min。

5結語

本文圍繞軟件編碼過程中API調用問題進行探究，利用API調用序列關系網絡模型，從API服務推薦角度實現精準推薦，從而提高軟件項目開發效率。研究發現：基于API序列關系網絡模型的推薦方法效果可行，且在推薦列表長度越大的情況下方法更具優勢，相比基準方法推薦精度可提高7.5%；提供的API子序列長度越長，推薦準確率越高，但耗時也越長，子序列長度為5時，方法推薦精度與運行時間可達到相對適中的效果。

本文存在一些不足：在收集數據時，由于受PPA工具限制，只選取了Github社區中Java項目，其它語言項目下的API推薦效果是否成立，還有待進一步驗證；在構建API序列關系網絡模型時，實際上會出現閉環現象，但對于網絡中路徑匹配不符，本文實驗過程中，進行了一定的人工處理，如何解決閉環問題，也是值得研究的課題。

參考文獻：

[1]LIC，ZHANGR，HUAIJ，etal.AnovelapproachforAPIrecommendationinmashupdevelopment[C].IEEEInternationalConferenceonWebServices.IEEE，2014：289-296.

[2]ROBILLARDMP.WhatmakesAPIshardtolearnanswersfromdevelopers[J].IEEESoftware，2009，26（6）：27-34.

[3]ROBILLARDMP，DELINER.AfieldstudyofAPIlearningobstacles[M].KluwerAcademicPublishers，2011.

[4]PICCIONIM，FURIACA，MEYERB.Anempiricalstudyofapiusability[C].ACM/IEEEInternationalSymposiumonEmpiricalSoftwareEngineeringandMeasurement.IEEE，2013：5-14.

[5]LIVSHITSB，ZIMMERMANNT.Dynamine：findingcommonerrorpatternsbyminingsoftwarerevisionhistories[C].EuropeanSoftwareEngineeringConferenceHeldJointlywithAcmSigsoftInternationalSymposiumonFoundationsofSoftwareEngineering，2005，30（5）：296-305.

[6]SAIEDMA，ABDEENH，BENOMARO，etal.Couldweinferunorderedapiusagepatternsonlyusingthelibrarysourcecode[C].IEEEInternationalConferenceonProgramComprehension，2015：71-81.

[7]THUMMALAPENTAS，XIET.Alattin：Miningalternativepatternsfordetectingneglectedconditions[C].IEEE/ACMInternationalConferenceonAutomatedSoftwareEngineering，2009：283-294.

[8]SALAHM，DENTONT，MANCORIDISS，etal.Scenariographer：atoolforreverseengineeringclassusagescenariosfrommethodinvocationsequences[C].IEEEInternationalConferenceonSoftwareMaintenance，2005：155-164.

[9]ASADUZZAMANM，ROYCK，SCHNEIDERKA，etal.Context-sensitivecodecompletiontoolforbetterapiusability[C].IEEEInternationalConferenceonSoftwareMaintenanceandEvolution，2014：621-624.

[10]YANGJ，EVANSD，BHARDWAJD，etal.Perracotta：miningtemporalAPIrulesfromimperfecttraces[C].InternationalConferenceonSoftwareEngineering，2006：282-291.

[11]RAYCHEVV，VECHEVM，YAHAVE.Codecompletionwithstatisticallanguagemodels[C].ACMSigplanSymposiumonProgrammingLanguageDesign&Implementation;，2014：419-428.

[12]RAGHOTHAMANM，WEIY，HAMADIY.SWIM：synthesizingwhatImean：codesearchandidiomaticsnippetsynthesis[C].Proceedingsofthe38thInternationalConferenceonSoftwareEngineering，2016：357-367.

[13]GUX，ZHANGH，ZHANGD，etal.DeepAPIlearning[C].Proceedingsofthe201624thACMSIGSOFTInternationalSymposiumonFoundationsofSoftwareEngineering，2016：631-642.

[14]NIUH，KEIVANLOOI，ZOUY.Learningtorankcodeexamplesforcodesearchengines[J].EmpiricalSoftwareEngineering，2017，22（1）：259-291.

[15]RAHMANMM，ROYCK，LOD.Rack：Automaticapirecommendationusingcrowdsourcedknowledge[C].2016IEEE23rdInternationalConferenceonSoftwareAnalysis，Evolution，andReengineering，2016，1：349-359.

（責任編輯：劉亭亭）