Conference Proceeding Article
Detecting code clones has many software engineering applications. Existing approaches either do not scale to large code bases or are not robust against minor code modifications. In this paper, we present an efficient algorithm for identifying similar subtrees and apply it to tree representations of source code. Our algorithm is based on a novel characterization of subtrees with numerical vectors in the Euclidean Rn and an efficient algorithm to cluster these vectors w.r.t. the Euclidean distance metric. Subtrees with vectors in one cluster are considered similar. We have implemented our tree similarity algorithm as a clone detection tool called DECKARD and evaluated it on large code bases written in C and Java including the Linux kernel and JDK. Our experiments show that DECKARD is both scalable and accurate. It is also language independent, applicable to any language with a formally specified grammar.
detection of code clones, software engineering applications, efficient algorithm
Software and Cyber-Physical Systems
ICSE 2007: Proceedings of the 29th International Conference on Software Engineering: Minneapolis, 20-26 May 2007
IEEE Computer Society
City or Country
Los Alamitos, CA
JIANG, Lingxiao; MISHERGHI, Ghassan; SU, Zhendong; and GLONDU, Stephane.
DECKARD: Scalable and accurate tree-based detection of code clones. (2007). ICSE 2007: Proceedings of the 29th International Conference on Software Engineering: Minneapolis, 20-26 May 2007. 96-105. Research Collection School Of Information Systems.
Available at: http://ink.library.smu.edu.sg/sis_research/1011
Copyright Owner and License
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.