Fast code recommendation via approximate sub-tree matching

Yichao SHAO; Zhiqiu HUANG; Weiwei LI; Yaoshen YU

doi:10.1631/FITEE.2100379

Your Location：

Home >

Browse articles >

Fast code recommendation via approximate sub-tree matching

Regular Papers | Updated：2022-09-08

- Fast code recommendation via approximate sub-tree matching
- 基于近似子树匹配的快速代码推荐方法
- Frontiers of Information Technology & Electronic Engineering Vol. 23, Issue 8, Pages: 1205-1216(2022)
- Affiliations：
  
  1.School of Computer Science and Technology, Nanjing University of Aeronautics and Astronautics, Nanjing211100, China
  2.Key Laboratory of Safety-Critical Software, Ministry of Industry and Information Technology, Nanjing211100, China
  3.Collaborative Innovation Center of Novel Software Technology and Industrialization, Nanjing210016, China
- Author bio：
  
  †E-mail: shaoyichao@nuaa.edu.cn;
  ‡Corresponding authors
- Funds：
- DOI：10.1631/FITEE.2100379
  CLC： TP311
- Received：07 August 2021，
  
  Revised：2022-03-24，
  
  Published：23 August 2022
- Accepted：
Scan QR Code
Yichao SHAO, Zhiqiu HUANG, Weiwei LI, et al. Fast code recommendation via approximate sub-tree matching[J]. Frontiers of Information Technology & Electronic Engineering, 2022, 23(8): 1205-1216.
DOI：

Yichao SHAO, Zhiqiu HUANG, Weiwei LI, et al. Fast code recommendation via approximate sub-tree matching[J]. Frontiers of Information Technology & Electronic Engineering, 2022, 23(8): 1205-1216. DOI： 10.1631/FITEE.2100379.

摘要

软件开发人员通常需编写与已有代码具有类似功能的代码，而帮助开发人员重用这些代码片段的代码推荐工具可显著提高软件开发效率。近年来许多研究者开始关注这一领域，并提出多种代码推荐方法。一些研究者使用序列匹配算法得到相关代码，这些方法往往效率较低，且只能利用代码中的文本信息。另一些研究者从代码中提取特征并形成特征向量，从而计算代码间相似性并得到推荐结果。然而特征向量相似往往不代表原始代码相似，在将抽象语法树转换为向量的过程中存在结构信息丢失问题。对此，我们提出一种基于近似子树匹配的代码推荐方法。与现有基于特征向量匹配的方法不同，该方法在匹配过程中保留了查询代码的树型结构，从而找到与当前查询在结构上最为相似的代码片段。此外，通过哈希思想将子树匹配问题转化为树与列表间的匹配，使得抽象语法树信息可以用于对时间要求较高的代码推荐任务。为评估方法的有效性，构建了多个涵盖不同语言和粒度的代码数据集。实验结果表明，该方法在所有数据集上的召回率均优于两种对比方法——SENSORY和Aroma，且可以应用于大型数据集。

Abstract

Software developers often write code that has similar functionality to existing code segments. A code recommendation tool that helps developers reuse these code fragments can significantly improve their efficiency. Several methods have been proposed in recent years. Some use sequence matching algorithms to find the related recommendations. Most of these methods are time-consuming and can leverage only low-level textual information from code. Others extract features from code and obtain similarity using numerical feature vectors. However

the similarity of feature vectors is often not equivalent to the original code’s similarity. Structural information is lost during the process of transforming abstract syntax trees into vectors. We propose an approximate sub-tree matching based method to solve this problem. Unlike existing tree-based approaches that match feature vectors

it retains the tree structure of the query code in the matching process to find code fragments that best match the current query. It uses a fast approximation sub-tree matching algorithm by transforming the sub-tree matching problem into the match between the tree and the list. In this way

the structural information can be used for code recommendation tasks that have high time requirements. We have constructed several real-world code databases covering different languages and granularities to evaluate the effectiveness of our method. The results show that our method outperforms two compared methods

SENSORY and Aroma

in terms of the recall value on all the datasets

and can be applied to large datasets.

关键词

Keywords

references

Ai L , Huang ZQ , Li WW , et al. , 2019 . SENSORY: leveraging code statement sequence information for code snippets recommendation . Proc IEEE 43 rd Annual Computer Software and Applications Conf , p. 27 - 36 . https://doi.org/10.1109/COMPSAC.2019.00014 https://doi.org/10.1109/COMPSAC.2019.00014

Antunes B , Furtado B , Gomes P , 2014 . Context-based search, recommendation and browsing in software development . In: Brézillon P , Gonzalez AJ (Eds.), Context in Computing: a Cross-Disciplinary Approach for Modeling the Real World . Springer , New York, USA , p. 45 - 62 . https://doi.org/10.1007/978-1-4939-1887-4_4 https://doi.org/10.1007/978-1-4939-1887-4_4

Baxter ID , Yahin A , Moura L , et al. , 1998 . Clone detection using abstract syntax trees . Proc Int Conf on Software Maintenance , p. 368 - 377 . https://doi.org/10.1109/ICSM.1998.738528 https://doi.org/10.1109/ICSM.1998.738528

Chen S , Zhang KZ , 2014 . An improved algorithm for tree edit distance with applications for RNA secondary structure comparison . J Comb Optim , 27 ( 4 ): 778 - 797 . https://doi.org/10.1007/s10878-012-9552-1 https://doi.org/10.1007/s10878-012-9552-1

Ďuračík M , Kršák E , Hrkút P , 2020 . Searching source code fragments using incremental clustering . Concurr Comput Pract Exp , 32 ( 13 ): e5416 . https://doi.org/10.1002/cpe.5416 https://doi.org/10.1002/cpe.5416

Holmes R , Murphy GC , 2005 . Using structural context to recommend source code examples . Proc 27th Int Conf on Software Engineering . https://doi.org/10.1109/ICSE.2005.1553554 https://doi.org/10.1109/ICSE.2005.1553554

Jiang H , Nie LM , Sun ZY , et al. , 2019 . ROSF: leveraging information retrieval and supervised learning for recommending code snippets . IEEE Trans Serv Comput , 12 ( 1 ): 34 - 46 . https://doi.org/10.1109/TSC.2016.2592909 https://doi.org/10.1109/TSC.2016.2592909

Jiang LX , Misherghi G , Su ZD , et al. , 2007 . DECKARD: scalable and accurate tree-based detection of code clones . Proc 29 th Int Conf on Software Engineering , p. 96 - 105 . https://doi.org/10.1109/ICSE.2007.30 https://doi.org/10.1109/ICSE.2007.30

Kamalpriya CM , Singh P , 2018 . Enhancing program dependency graph based clone detection using approximate subgraph matching . Proc IEEE 11 th Int Workshop on Software Clones , p. 1 - 7 . https://doi.org/10.1109/IWSC.2017.7880511 https://doi.org/10.1109/IWSC.2017.7880511

Luan SF , Yang D , Barnaby C , et al. , 2018 . Aroma: code recommendation via structural code search . Proc ACM Program Lang , 3 : 152 . https://doi.org/10.1145/3361527 https://doi.org/10.1145/3361527

Mou LL , Li G , Zhang L , et al. , 2016 . Convolutional neural networks over tree structures for programming language processing . Proc 31 st AAAI Conf on Artificial Intelligence , p. 1287 - 1293 .

Rahman MM , Roy CK , 2014 . On the use of context in recommending exception handling code examples . Proc IEEE 14 th Int Working Conf on Source Code Analysis and Manipulation , p. 285 - 294 . https://doi.org/10.1109/SCAM.2014.15 https://doi.org/10.1109/SCAM.2014.15

Rahman MM , Roy CK , Lo D , 2016 . RACK: automatic API recommendation using crowdsourced knowledge . Proc IEEE 23 rd Int Conf on Software Analysis, Evolution, and Reengineering , p. 349 - 359 . https://doi.org/10.1109/SANER.2016.80 https://doi.org/10.1109/SANER.2016.80

Sahavechaphan N , Claypool K , 2006 . XSnippet: mining for sample code . Proc 21 st Annual ACM SIGPLAN Conf on Object-Oriented Programming Systems, Languages, and Applications , p. 413 - 430 . https://doi.org/10.1145/1167473.1167508 https://doi.org/10.1145/1167473.1167508

Saini V , Farmahinifarahani F , Lu YD , et al. , 2018 . Oreo: detection of clones in the twilight zone . Proc 26 th ACM Joint Meeting on European Software Engineering Conf and Symp on the Foundations of Software Engineering , p. 354 - 365 . https://doi.org/10.1145/3236024.3236026 https://doi.org/10.1145/3236024.3236026

Shasha D , Wang JTL , Zhang KZ , et al. , 1994 . Exact and approximate algorithms for unordered tree matching . IEEE Trans Syst Man Cybern , 24 ( 4 ): 668 - 678 . https://doi.org/10.1109/21.286387 https://doi.org/10.1109/21.286387

Smith TF , Waterman MS , 1981 . Identification of common molecular subsequences . J Mol Biol , 147 ( 1 ): 195 - 197 . https://doi.org/10.1016/0022-2836(81)90087-5 https://doi.org/10.1016/0022-2836(81)90087-5

Svajlenko J , Roy CK , 2021 . The mutation and injection framework: evaluating clone detection tools with mutation analysis . IEEE Trans Soft Eng , 47 ( 5 ): 1060 - 1087 . https://doi.org/10.1109/TSE.2019.2912962 https://doi.org/10.1109/TSE.2019.2912962

Yang YM , Ren ZL , Chen X , et al. , 2018 . Structural function based code clone detection using a new hybrid technique . Proc IEEE 42 nd Annual Computer Software and Applications Conf , p. 286 - 291 . https://doi.org/10.1109/COMPSAC.2018.00045 https://doi.org/10.1109/COMPSAC.2018.00045

Ye YW , Fischer G , 2002 . Supporting reuse by delivering task-relevant and personalized information . Proc 24th Int Conf on Software Engineering . https://doi.org/10.1109/ICSE.2002.1007995 https://doi.org/10.1109/ICSE.2002.1007995

Zhang KZ , Shasha D , 1989 . Simple fast algorithms for the editing distance between trees and related problems . SIAM J Comput , 18 : 1245 - 1262 . https://doi.org/10.1137/0218082 https://doi.org/10.1137/0218082

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰