Rajesh Prasad
Suneeta Agarwal
Abstract
In the problem of parameterized string matching, a given pattern P is said to match with a sub-string t of the text T, if there exists a one-one correspondence between the symbols of P and the symbols of t. This problem has an important application in software maintenance, where it is often required to find equivalency between two sections of codes. Two sections of codes are said to be equivalent if one can be transformed into the other by renaming only identifiers and variables. In this paper, we propose two new algorithms for the said problem by using the q-gram approach. The first one is obtained by using this approach on an existing string matching algorithm (simplified backward non-deterministic directed acyclic word graph matching (SBNDM)).The second one is obtained by using the q-gram approach on the parameterized string matching algorithm (parameterized backward non-deterministic directed acyclic word graph matching (PBNDM)). Performance of both the algorithms is tested for various values of q and it has been observed that both show their best performance for q nearly equal to half of the pattern length. We also study the effect on running time of these algorithms with increasing the duplicity in the text.
- Baeza-Yates R A, Gonnet G H. (1992): A new approach to text searching. Communication of ACM, 35(10), pp. 74--82. Google Scholar
Digital Library
- Boyer R S, Moore J S. (1977): A fast string-searching algorithm. Communication of ACM, 20(10) : pp. 762--772. Google ScholarDigital Library
- Aho A V, Corasick M J. (1975): Efficient String Matching: An aid to bibliographic search. Communication of ACM 18(6), pp. 333--340. Google ScholarDigital Library
- Michailidis P D, Margaritis K G. (2001): On-line String matching Algorithms: Survey and Experimental Results. International Journal of Computer Mathematics, 76(4), pp. 411--434.Google ScholarCross Ref
- Navarro G, Raffinot M. (2001): Fast and Flexible String Matching by Combining Bit-parallelism and Suffix automata. ACM Journal of Experimental Algorithms, 5(4), pp. 1--36. Google ScholarDigital Library
- Baker, B. S., (1997): Parameterized Duplication in Strings: Algorithms and an Application to Software Maintenance, SIAM Journal of Computing 26(5), pp. 1343--1362. Google ScholarDigital Library
- Baker, B. S., (1996): Parameterized pattern matching: algorithms and applications. Journal of Computer and System Sciences, 52(1), pp. 28--42. Google ScholarDigital Library
- Amir, A., Farach, M., Muthukrishnan, S., (1994): Alphabet dependence in parameterized matching. Information Processing Letters, 49(3):pp. 111--115. Google ScholarDigital Library
- Fredriksson K, Mozgovoy M. (2006): Efficient parametrized string matching. In Information Processing Letters (IPL), 100(3): pp. 91--96. Google ScholarDigital Library
- Prasad R, Agarwal S. (2008): Parameterized Shift-And String Matching Algorithm using Super Alphabet. In proc. of International Conference on Computer and Communication (available on IEEE Xplore), Kuala Lumpur Malaysia, May 13-15, pp. 937--942.Google ScholarCross Ref
- Prasad R, Agarwal S. (2008): A New Parameterized String Matching Algorithm by Combining Bit-Parallelism and Suffix Automata. In proc. of IEEE 8th International Conference on Computer and Information Technology (available on IEEE Xplore), Sydney, Australia, July 8-11, pp.778--783.Google ScholarCross Ref
- Salmela L, Tarhio J. (2008): Fast Parameterized Matching with q-grams. Journal of Discrete Algorithms, 6(3), pp. 408--419. Google ScholarDigital Library
- Durian B, Holub J, Peltola H, Tarhio J. (2009): Tuning BNDM with q-grams. In proc. of Tength Workshops on Algorithm Engineering and Experiments, pp. 29--37.Google Scholar
- Lecroq T. (2007): Fast exact string matching algorithms. Information Processing Letter, 102(6), pp. 229--235. Google ScholarDigital Library
- Fredriksson K. (2003): Shift-or string matching with super alphabets. In Information Processing Letters (IPL), 87(4), pp. 201--204. Google ScholarDigital Library
- Peltola H, Tarhio J. (2003): Alternative algorithm for bit-parallel string matching. In String Processing and Information Retrieval, 10th International Symposium, SPIRE 2003, Volume 2857, LNCS, pp. 80--94.Google Scholar
Index Terms
- Parameterized string matching: an application to software maintenance
Recommendations
Software maintenance by multi-patterns parameterized string matching with q-gram
In the multi-patterns parameterized string matching problem, a set of patterns P0, P1, P2...Pr-1, r≥1, are said to match with a sub-string t of the text T, if there exists a one-one correspondence between the symbols of patterns and the symbols of t. ...
Multi-patterns parameterized shift-and string matching algorithm with super alphabets
ICAC3 '09: Proceedings of the International Conference on Advances in Computing, Communication and ControlIn the parameterized string matching, a given pattern P is said to match with a sub-string t of the text T, if there exist a bijection from the symbols of P to the symbols of t. This problem has an important application in software maintenance where it ...
An Efficient Multi-Patterns Parameterized String Matching Algorithm with Super Alphabet
ICCET '09: Proceedings of the 2009 International Conference on Computer Engineering and Technology - Volume 01In the parameterized string matching, a given pattern P is said to match with a sub-string t of the text T, if there exist a bijection from the symbols of P to the symbols of t. This problem has an important application in software maintenance where it ...
Comments