Fast parameterized word matching on compressed text
Rama Garg, Rajesh Prasad, Suneeta Agarwal · 2014
Two strings P[1...m] and T[1...n] with m ≤ n, are said to be parameterized match (p-match), if one can be transformed into the other via some bijective mapping. It is mainly used in software maintenance, plagiarism detection and detecting isomorphism in a graph. In the compressed parameterized matching problem, our task is to find all the parameterized occurrences of a pattern in the compressed text, without decompressing it. Compressing the text before matching reduces the size and minimizes the matching time also. In this paper, we mainly focus on the parameterized word matching on the compressed text, where both patterns and text are compressed before actual matching is performed. For compressing the pattern and text, we use efficient compression code: Word Based Tagged Code (WBTC). Experimental results show that our algorithm is up to three times faster than the search on uncompressed text.