Efficient parameterized matching using burrows-wheeler transform

Abstract EN

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 dTwo 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 algorithmetecting 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