Paper Info
Title
Efficient algorithm for detecting parameterized multiple clones in a large software system
Abstract
Two code fragments are said to be similar if they are similar in their program text or in their functionalities. The first kind of similarity can be detected with the help of parameterized string matching. In this type of matching, a given pattern P is said to match with a sub-string t of the text T, if there exists a bijection between the symbols of P and the symbols of t. The parameterized string matching problem has been efficiently solved by Fredriksson and Mozgovoy by using the shift-or (PSO) algorithm. The drawback of this algorithm is: it is unable to handle patterns of length greater than the word length (w) of a computer. In this paper, we solve this word length problem in a bitparallel parameterized matching by extending the BLIM algorithm of exact string matching. Extended algorithm is also suitable for searching multiple patterns simultaneously. Experimentally, it has been observed that our algorithm is comparable with PSO for pattern length ≤ w and has ability to handle longer patterns efficiently.
Year
Venue
Keywords
2011
ICCSA (5)
word length,longer pattern,parameterized string matching,parameterized string,word length problem,large software system,parameterized multiple clone,multiple pattern,pattern length,exact string matching,efficient algorithm,BLIM algorithm,extended algorithm
Field
DocType
Volume
String searching algorithm,Discrete mathematics,Parameterized complexity,Bijection,Existential quantification,Commentz-Walter algorithm,Computer science,Algorithm,Software system,Software maintenance,Boyer–Moore string search algorithm
Conference
6786
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
12
5
Name
Order
Citations
PageRank
Rajesh Prasad141.41
Suneeta Agarwal217426.32
Anuj Sharma319327.12
Alok Singh420117.15
Sanjay Misra510819.79