Abstract Two strings P[1, ..., m] and T[1, ..., n] with m≤n, are said to be parameterized match, if one can be transformed into the other via some bijective mapping. It is used in software maintenance, plagiarism detection and detecting isomorphism in a graph. In recent year, Directed Acyclic Word Graph (DAWG). Backward DAWG Matching (BDM) algorithm for exact string matching has been combined with compressed indexing technique: Burrows Wheeler Transform (BWT), to achieve less search time and small space. In this paper, we develop a new efficient Parameterized Burrows Wheeler Transform (PBWT) matching algorithm using the concept of BWT indexing technique. The proposed algorithm requires less space as compared to existing parameterized suffix tree based algorithm.

References

[1] Baker B., Parameterized Duplication in Strings: Algorithms and an Application to Software Maintenance, SIAM Journal of Computing, vol. 26, no. 5, pp. 1343-1362, 1997.

[2] Beller T., Zwerger M., Gog S., and Ohlebusch E., Space-Efficient Construction of the Burrows- Wheeler Transform, in Proceedings of International Symposium on String Processing and Information Retrieval, Jerusalem, pp. 5-16, 2013.

[3] Burrows M. and Wheeler D., A Block-sorting Lossless Data Compression Algorithm, Technical Report 124, DEC Systems Research Centre, 1994. Efficient Parameterized Matching Using Burrows-Wheeler Transform 49

[4] Faro S. and Lecroq T., An Efficient Matching Algorithm for Encoded DNA Sequences and Binary Strings, in Proceedings of Combinatorial Pattern Matching, Lille, pp. 106-115, 2009.

[5] Fredriksson K., Succinct Backward-DAWG- Matching, Journal of Experimental Algorithmics, vol. 13, no. 1, pp. 8- 26, 2009.

[6] Goel A. and Prasad R., Efficient Record Matching using Indexing Techniques and Deduplication, International Journal of Computational Vision and Robotics, vol. 4, no. 1- 2, pp. 75-85, 2014.

[7] Huynh T., Hon W., Lam T., and Sung W., Approximate String Matching using Compressed Suffix Arrays, Theoretical Computer Science, vol. 352, no. 1-3, pp. 240- 249, 2006.

[8] Mendivelso J., Kim S., Elnikety S., He Y., Hwang S., and Pinzon Y., Solving Graph Isomorphism Using Parameterized Matching, in Proceedings of the 20th International Symposium on String Processing and Information Retrieva, Jerusalem, pp. 230-242, 2013.

[9] Prasad R., Sharma A., Singh A., Agarwal S., and Misra S., Efficient Bit-Parallel Multi-Patterns Approximate String Matching Algorithms, Scientific Research and Essays, vol. 6, no. 4, pp. 876-881, 2011. Anjali Goel holds a B. Tech in Computer Science and Engineering from Sunder Deep Engineering College, Ghaziabad, India. She has completed her M. Tech. in Computer Science and Engineering from AKGEC, Ghaziabad, India. Rajesh Prasad is currently, working as Professor and Head in the Department of Computer Science, Yobe State University, Damaturu, Nigeria. He received his M. Tech (SE) and Ph. D (CSE) from MNNIT, Allahabad, India. He is active member of IEEE. Suneeta Agarwal is currently, working as a Professor in the Department of Computer Science at MNNIT, Allahabad, India. She received BSc, MSc & M.Tech (CS) degrees in 1973, 1975 and 2007 respectively. She did Ph. D from IIT, Kanpur in 1980. She is active member of IEEE, ISTE and CSI. Amit Sangal received his B. Tech in Computer Science and Engineering from Sunder Deep Engineering College, Ghaziabad, India. He is SIX Sigma, ISTQB certified and GATE qualified.