基于后缀数组的克隆检测  

Clone Detection Based on Suffix Array

作　　者：史庆庆[1] 张丽萍[1] 尹丽丽[1] 刘东升[1] 

机构地区：[1]内蒙古师范大学计算机与信息工程学院,呼和浩特010022

出　　处：《计算机工程》2013年第9期123-127,共5页Computer Engineering

基　　金：内蒙古自然科学基金资助项目(2011MS0906)

摘　　要：程序员对源代码的拷贝、粘贴及修改活动会导致软件中出现大量克隆代码,增加软件开发和维护的成本。为解决该问题,提出一种新的克隆检测方法。利用基于后缀数组的算法查找重复的Token子串,进而检测出克隆代码,开发相应的克隆检测工具SaCD,用其检测29款C语言开源软件。实验结果表明,SaCD能快速有效地检测软件中的Type-1和Type-2语句克隆,其检测速度比传统的克隆检测工具CCFinderx快了近20倍。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串 后缀数组 重复子串 DC3算法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]