An efficient approach towards compressed parameterized word matching using wavelet tree
Radhika Khetan, Suneeta Agarwal, Rajesh Prasad · Journal of Information and Optimization Sciences · 2016
Parameterized matching is said to exist between two strings, if either string is convertible to another using any bijective mapping. It is applicable in various fields such as: detecting isomorphism in graphs, plagiarism detection, software maintenance, molecular biology and image processing. Compressed parameterized matching performs matching on text and pattern both in compressed form without decompressing any one of them. Compressing the text gives the advantage of reduced saving space and reduction in execution time. This paper presents an algorithm that tries to optimize parameterized word matching on compressed domain. The proposed algorithm uses Word Based Tagged Code (WBTC) for compression and Wavelet tree for efficient searching. Major advantage of the algorithm is that it does not require any additional verification process unlike in existing algorithms. The proposed algorithm has better execution time also.