ResearchBib Share Your Research, Maximize Your Social Impacts
Sign for Notice Everyday Sign up >> Login

Efficient Parameterized Matching Using BurrowsWheeler Transform

Journal: The International Arab Journal of Information Technology (Vol.15, No. 1)

Publication Date:

Authors : ;

Page : 44-49

Keywords : Suffix array; burrow-wheeler transform; backward DAWG matching and parameterized matching;

Source : Downloadexternal Find it from : Google Scholarexternal

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.

Last modified: 2019-04-29 18:30:23