Browsing by Author "Agarwal,S."

Now showing 1 - 3 of 3

Citation Count: 7
Efficient Bit-Parallel Multi-Patterns Approximate String Matching Algorithms
(2011) Prasad,R.; Mısra, Sanjay; Sharma,A.K.; Singh,A.; Agarwal,S.; Misra,S.; Computer Engineering
Multi-patterns approximate string matching (MASM) problem is to find all the occurrences of set of patterns P0, P1, P2...Pr-1, r≥1, in the given text T[0...n-1], allowing limited number of errors in the matches. This problem has many applications in computational biology viz. finding DNA subsequences after possible mutations, locating positions of a disease(s) in a genome etc. The MASM problem has been previously solved by Baeza-Yates and Navarro by extending the bit-parallel automata (BPA) of approximate matching and using the concept of classes of characters. The drawbacks of this approach are: (a) It requires verification for the potential matches and, (b) It can handle patterns of length less than or equal to word length (w) of computer used. In this paper, we propose two new bit-parallel algorithms to solve the same problem. These new algorithms requires no verification and can handle patterns of length > w. These two techniques also use the same BPA of approximate matching and concatenation to form a single pattern from the set of r patterns. We compare the performance of new algorithms with existing algorithms and found that our algorithms have better running time than the previous algorithms. © 2011 Academic Journals.
Citation Count: 1
Maintaining Software Through Bit-Parallelism and Hashing the Parameterized Q-Grams;
(2012) Prasad,R.; Mısra, Sanjay; Agarwal,S.; Misra,S.; Sharma,A.K.; Singh,A.; Computer Engineering
In the software maintenance, it is often required to find duplicity present in the codes. Two code fragments are equivalent, if one can be transformed into the other via consistent renaming of identifiers, literals and variables. This equivalency can be detected by parameterized string matching. In this matching, a given pattern P is said to match with a substring of the text T, if there exists a one-to-one correspondence between symbols of and symbols of P. In this paper, we propose an efficient algorithm for this problem by using both the overlapping and non-overlapping -gram.We show the effect of running time of the algorithm on increasing the duplicity present in the code.
Citation Count: 1
Plagiarism Detection in Software Using Efficient String Matching
(2012) Pandey,K.L.; Mısra, Sanjay; Agarwal,S.; Misra,S.; Prasad,R.; Computer Engineering
String matching refers to the problem of finding occurrence(s) of a pattern string within another string or body of a text. It plays a vital role in plagiarism detection in software codes, where it is required to identify similar program in a large populations. String matching has been used as a tool in a software metrics, which is used to measure the quality of software development process. In the recent years, many algorithms exist for solving the string matching problem. Among them, Berry-Ravindran algorithm was found to be fairly efficient. Further refinement of this algorithm is made in TVSBS and SSABS algorithms. However, these algorithms do not give the best possible shift in the search phase. In this paper, we propose an algorithm which gives the best possible shift in the search phase and is faster than the previously known algorithms. This algorithm behaves like Berry-Ravindran in the worst case. Further extension of this algorithm has been made for parameterized string matching which is able to detect plagiarism in a software code. © 2012 Springer-Verlag.