一种基于调用序列网络的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.

（責任编辑：刘亭亭）