基于后缀数组的克隆检测

摘要

The activities of the programmers for copying, pasting and modifying result in a lot of code clones in the software systems, and increase the cost of software development and maintenance. Aiming at this problem, this paper presents a new clone detection method which uses algorithm based on suffix array to efficiently search repeated token substrings and to detect code clones at last. It develops a clone detection tool SaCD and detects twenty-nine open source software systems of C language. Experimental results show that the SaCD can fastly and efficiently detect Type-1 and Type-2 statement clones in the software. The detection speed of SaCD is twenty times than that of CCFinderx.%程序员对源代码的拷贝、粘贴及修改活动会导致软件中出现大量克隆代码，增加软件开发和维护的成本。为解决该问题，提出一种新的克隆检测方法。利用基于后缀数组的算法查找重复的 Token 子串，进而检测出克隆代码，开发相应的克隆检测工具SaCD，用其检测29款C语言开源软件。实验结果表明，SaCD能快速有效地检测软件中的Type-1和Type-2语句克隆，其检测速度比传统的克隆检测工具CCFinderx快了近20倍。