Effects of an Apriori-based Data-mining Algorithm for Detecting Type 3 Clones
Effects of an Apriori-based Data-mining Algorithm for Detecting Type 3 Clones
复制标题
DOI：
--
复制
发表时间：
2018
影响因子：
2.4
通讯作者：
Yoshihisa Udagawa
中科院分区：
文献类型：
--
作者：
Yoshihisa Udagawa
— 代码克隆是在软件源代码中至少出现两次的源代码片段。代码克隆给软件维护带来了困难，因为一个片段中的错误会在代码克隆中重现。检测每个代码克隆对于使软件维护变得简单可靠具有重要意义。本文描述了使用基于 Apriori 的顺序数据挖掘算法的软件克隆检测技术。使用基于 Apriori 的算法是因为它旨在查找出现次数不少于用户指定的阈值（称为最小支持度 (minSup)）的所有频繁项。由于通常通过添加、删除或更改源代码来稍微修改克隆，因此用于检测代码克隆的算法必须处理源代码的匹配和不匹配部分。所提出方法的基本思想是使用最长公共子序列（LCS）的部分字符串匹配和用于查找频繁序列的基于 Apriori 的算法的组合。一般来说，基于 Apriori 的算法会提取大量频繁序列，特别是当 minSup 很小时，这给代码克隆的检测带来了障碍。我们方法的新颖之处包括取决于编程语言特性的修剪过程、减少频繁序列数量的技术以及控制重复子序列的函数。我们根据使用 Java SDK SWING 图形包的源代码的实验结果评估了所提出算法的有效性。结果表明，所提出的顺序数据挖掘算法在 minSup 达到 2 之前将性能保持在实用水平。本文还展示了一些挖掘的序列和源代码，以证明所提出的算法可以从短序列到长序列。
—A code clone is a fragment of source code that appears at least twice in software source code. Code clones introduce difficulties in software maintenance because an error in one fragment is reproduced in code clones. It is significant to detect every code clones for making software maintenance easy and reliable. This paper describes software clone detection techniques using an Apriori -based sequential data mining algorithm. The Apriori -based algorithm is used because it is designed to find all frequent items that occur no less than a user-specified threshold named the minimum support (minSup). Since clones are slightly modified by adding, removing, or changing source code in general, the algorithm for detecting code clones has to deal with both match and mismatch portions of source code. The essential idea of the proposed approach is a combination of a partial string match using the longest-common-subsequence (LCS) and an Apriori -based algorithm for finding frequent sequences. Generally, Apriori -based algorithms extract vast numbers of frequent sequences especially when the minSup is small, creating an obstacle to the detection of code clones. The novelties of our approach include pruning processes that depend on characteristics of a programming language, techniques to reduce the number of frequent sequences, and functions to control repetitive subsequences. We evaluate the effectiveness of the proposed algorithm based on experimental results using the source code of the Java SDK SWING graphics package. The results show that the proposed sequential data mining algorithm maintains the performance at a practical level until the minSup reaches two. This paper also shows some mined sequences and source code to demonstrate that the proposed algorithm works from short sequences to long ones.