一種基于調(diào)用序列網(wǎng)絡(luò)的API推薦方法

肖海濤 王鵬 包義祥 何鵬

摘要：隨著計(jì)算機(jī)程序的日益復(fù)雜，代碼自動(dòng)補(bǔ)全功能需求越來越迫切。圍繞軟件編碼過程中API調(diào)用問題進(jìn)行探究，利用代碼中API之間的調(diào)用序列，構(gòu)建API關(guān)系網(wǎng)絡(luò)模型，從服務(wù)推薦角度實(shí)現(xiàn)精準(zhǔn)的API推薦，從而提高軟件項(xiàng)目開發(fā)效率。實(shí)驗(yàn)結(jié)果表明，基于API序列關(guān)系網(wǎng)絡(luò)模型推薦方法具有可行性，且在推薦列表長度較大的情況下方法更具優(yōu)勢(shì)，相比基準(zhǔn)方法推薦精度可提高7.5%。在推薦過程中提供的API子序列越長，推薦結(jié)果越準(zhǔn)確，但耗時(shí)明顯增加。在子序列長度為5時(shí)，方法推薦精度與運(yùn)行時(shí)間可達(dá)到相對(duì)適中的效果。

關(guān)鍵詞：API推薦；服務(wù)計(jì)算；復(fù)雜網(wǎng)絡(luò)

DOI：10.11907/rjdk.173166

中圖分類號(hào)：TP301

文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：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引言

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

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

這些問題的存在使開發(fā)人員在代碼編寫過程中，由于不熟悉API使用方法，導(dǎo)致不能快速有效地找到下一個(gè)需要使用的API，從而降低了開發(fā)速度?，F(xiàn)有API推薦方法普遍沒有利用API調(diào)用序列信息。本文通過API調(diào)用序列關(guān)系構(gòu)建API調(diào)用關(guān)系網(wǎng)絡(luò)，利用復(fù)雜網(wǎng)絡(luò)理論進(jìn)行有向路徑匹配，從而準(zhǔn)確地實(shí)現(xiàn)了API推薦。

1相關(guān)工作

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

為提高API推薦準(zhǔn)確率，有研究者提出利用數(shù)據(jù)挖掘算法挖掘API使用模式進(jìn)行推薦，從而提高開發(fā)者的開發(fā)效率。如DynaMine使用Apriori算法，F(xiàn)rUit使用Opus算法[5]等。將API使用模式根據(jù)結(jié)構(gòu)與語義分為不同的組，根據(jù)相關(guān)程度進(jìn)行推薦[6]。而數(shù)據(jù)挖掘忽略了API元素調(diào)用順序信息，實(shí)際推薦過程中，推薦順序?qū)ν扑]結(jié)果有至關(guān)重要的作用，因此有必要考慮API的調(diào)用序列模式。

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

本文所采用的方式是利用代碼中各種依賴關(guān)系生成API調(diào)用關(guān)系網(wǎng)絡(luò)模型，再利用復(fù)雜網(wǎng)絡(luò)理論進(jìn)行匹配、

過濾形成API推薦結(jié)果。

主要工作概括為兩個(gè)方面：

①利用開源工具PPA對(duì)Github上的開源軟件進(jìn)行代碼解析，獲得代碼中API序列庫，根據(jù)API序列關(guān)系構(gòu)建API序列關(guān)系網(wǎng)絡(luò)模型；

②利用復(fù)雜網(wǎng)絡(luò)理論，提出一種基于API序列關(guān)系網(wǎng)絡(luò)模型的API推薦方法，并驗(yàn)證方法的有效性。

2理論基礎(chǔ)

2.1API序列

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

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

2.2API推薦

API推薦可劃分為兩部分：①對(duì)測(cè)試的源代碼對(duì)應(yīng)的API調(diào)用序列進(jìn)行標(biāo)記，確定預(yù)測(cè)位置（如標(biāo)記為L），從API調(diào)用序列中預(yù)測(cè)位置L為參考位置，向前選擇所有長度小于閾值γ（γ≤10）的子序列；②按照閾值長度選擇子序列作為測(cè)試序列，輸入到基于調(diào)用關(guān)系得到的API調(diào)用網(wǎng)絡(luò)模型，根據(jù)路徑匹配結(jié)果形成API推薦列表。

3實(shí)驗(yàn)分析

3.1實(shí)驗(yàn)數(shù)據(jù)

本文實(shí)驗(yàn)所用數(shù)據(jù)集如表1所示。為確保實(shí)驗(yàn)結(jié)果可靠有效，從Github平臺(tái)上下載大量數(shù)據(jù)集，并從中提取一個(gè)數(shù)據(jù)量龐大的代碼庫，數(shù)據(jù)集包含1000個(gè)開源Java項(xiàng)目，共計(jì)104645個(gè)類，638293個(gè)函數(shù)，對(duì)應(yīng)2039687個(gè)API。在數(shù)據(jù)選取過程中，過濾一些小程序以及PPA工具解析失敗項(xiàng)目。

3.2實(shí)驗(yàn)步驟

方法整體框架如圖3所示。根據(jù)2.1中的方法獲得API調(diào)用序列庫，將其中一部分用作訓(xùn)練數(shù)據(jù)集，通過上下調(diào)用關(guān)系構(gòu)建API調(diào)用網(wǎng)絡(luò)模型，其中網(wǎng)絡(luò)模型相鄰兩個(gè)API元素關(guān)系出現(xiàn)的次數(shù)為其連邊權(quán)重。將測(cè)試集中的API元素作為輸入，在API調(diào)用網(wǎng)絡(luò)模型上進(jìn)行匹配；推薦最可能的K個(gè)API元素，得到API推薦列表。

3.3評(píng)價(jià)指標(biāo)

為了評(píng)價(jià)所提出的API推薦方法，使用如下判斷推薦成功的條件與常用的精度評(píng)價(jià)指標(biāo)：

（1）假設(shè)在推薦的K個(gè)列表中，有當(dāng)前測(cè)試API所需調(diào)用的下一個(gè)API，則認(rèn)為推薦成功。

（2）Top-k推薦平均準(zhǔn)確率。

該指標(biāo)需要計(jì)算每個(gè)測(cè)試API推薦列表中推薦成功位置的倒數(shù)1r（r（r≤k）為推薦成功時(shí)的位置），對(duì)所有測(cè)試成功位置倒數(shù)求平均值，Q為測(cè)試API個(gè)數(shù)，表示為：

4實(shí)驗(yàn)結(jié)果

4.1推薦方法有效性驗(yàn)證

在實(shí)驗(yàn)過程中，設(shè)置輸入測(cè)試的API子序列長度γ=1，即每個(gè)測(cè)試的API數(shù)據(jù)提供其前兩個(gè)調(diào)用API元素作為情景信息。在不同比例劃分訓(xùn)練數(shù)據(jù)集情況下，根據(jù)返回推薦列表長度K取值不同，API推薦結(jié)果精度有差異。如圖4所示，用于訓(xùn)練（構(gòu)建API調(diào)用關(guān)系網(wǎng)絡(luò)模型）的API調(diào)用序列比例越大，推薦結(jié)果的精度越高，最高可達(dá)到52.3%。推薦過程中返回的推薦列表長度K整體越長推薦效果越好，且與測(cè)試數(shù)據(jù)集比例關(guān)系不顯著。

為進(jìn)一步驗(yàn)證本文方法效果，選取文獻(xiàn)[9-10]中兩種方法進(jìn)行初步對(duì)比。為簡化實(shí)驗(yàn)步驟，對(duì)比過程中僅以本文方法在測(cè)試數(shù)據(jù)比例為10%以下結(jié)果為主。如圖5所示，在k=1時(shí)，Apriori方法最好，為33.9%；但隨K值的增大Apriori方法優(yōu)勢(shì)更明顯，其中Top-10結(jié)果達(dá)到52.3%的精度，相比兩種基準(zhǔn)方法分別提高了7.5%和2.6%。綜上所述，本文提出的基于API調(diào)用序列關(guān)系網(wǎng)絡(luò)方法更有助于API推薦。

4.2參數(shù)γ對(duì)推薦結(jié)果的影響

如圖6所示，可以發(fā)現(xiàn)，提供的API子序列長度越大，推薦結(jié)果越準(zhǔn)確，提供查找API元素的context信息越豐富，找到其下一個(gè)調(diào)用API元素可能性越大。如圖7所示，隨著參數(shù)γ增大算法耗時(shí)加長。由于提供的子序列長度γ越大，表示在關(guān)系網(wǎng)絡(luò)匹配過程中，需要對(duì)比的前綴元素越多，耗時(shí)越長。例如當(dāng)子序列長度γ=9時(shí)，Τοp-10的推薦精度達(dá)到86.1%，但運(yùn)行時(shí)間達(dá)21min。當(dāng)子序列長度γ=5時(shí)，Τοp-10整體推薦精度與運(yùn)行時(shí)間相對(duì)較為適中，精度為71.9%，運(yùn)行時(shí)間為10min。

5結(jié)語

本文圍繞軟件編碼過程中API調(diào)用問題進(jìn)行探究，利用API調(diào)用序列關(guān)系網(wǎng)絡(luò)模型，從API服務(wù)推薦角度實(shí)現(xiàn)精準(zhǔn)推薦，從而提高軟件項(xiàng)目開發(fā)效率。研究發(fā)現(xiàn)：基于API序列關(guān)系網(wǎng)絡(luò)模型的推薦方法效果可行，且在推薦列表長度越大的情況下方法更具優(yōu)勢(shì)，相比基準(zhǔn)方法推薦精度可提高7.5%；提供的API子序列長度越長，推薦準(zhǔn)確率越高，但耗時(shí)也越長，子序列長度為5時(shí)，方法推薦精度與運(yùn)行時(shí)間可達(dá)到相對(duì)適中的效果。

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

參考文獻(xiàn)：

[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，F(xiàn)URIACA，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.

（責(zé)任編輯：劉亭亭）