Efficient Parameterized Matching Using BurrowsWheeler Transform
Journal: The International Arab Journal of Information Technology (Vol.15, No. 1)Publication Date: 2018-01-01
Authors : Anjali Goel Rajesh Prasad Suneeta Agarwal Amit Sangal;
Page : 44-49
Keywords : Suffix array; burrow-wheeler transform; backward DAWG matching and parameterized matching;
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.
Other Latest Articles
- Bag-of-Visual-Words Model for Fingerprint Classification
- A Framework for Recognition and Animation of Chess Moves Printed on a Chess Book
- Opinion within Opinion: Segmentation Approach for Urdu Sentiment Analysis
- New Six-Phase On-line Resource Management Process for Energy and SLA Efficient Consolidation in Cloud Data Centers
- Clustering Based on Correlation Fractal Dimension Over an Evolving Data Stream
Last modified: 2019-04-29 18:30:23