Efficient
Parameterized Matching Using Burrows-Wheeler Transform
Anjali
Goel1, Rajesh Prasad2, Suneeta Agarwal3, and Amit
Sangal4
1Department of Computer Science and
Engineering, Ajay Kumar Garg Engineering College, India
2Department of Computer Science and
Engineering, Yobe State University, Nigeria
3Department of Computer Science and
Engineering, Motilal Nehru National Institute of Technology, India
4Department of Computer Science and
Engineering, Sunder
Deep Engineering College, India
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.
Keywords: Suffix array,
burrow-wheeler transform, backward DAWG matching and parameterized matching.