Title

Approximate Pattern Matching Using The Burrows-Wheeler Transform

Keywords

Arithmetic; Automata; Computer science; Decoding; Doped fiber amplifiers; Filtering algorithms; Matched filters; Pattern matching; Testing; USA Councils

Abstract

Summary form only given. The approximate pattern matching on the text transformed by the Burrows-Wheeler transform (BWT) was considered. This is an important first step towards developing a compressed pattern matching algorithm for the BWT based compression system. Algorithms are proposed to solve the K-mismatch problem. Tests were performed on different pattern lengths using 133 selected files from the Canterbury, Calgary, and TREC corpus. The results on the K-mismatch pattern matching show that the running time and storage are superior to the fast suffix tree approach. Thus, once the index arrays are created, for repeated pattern search operations and for long patterns, the proposed algorithms perform significantly better than the agrep and ngrep. Using DFA verification, the search time is almost constant. The amortized cost is lower for multiple patterns search operations.

Publication Date

1-1-2003

Publication Title

Data Compression Conference Proceedings

Volume

2003-January

Number of Pages

458-

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/DCC.2003.1194077

Socpus ID

84873048024 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/84873048024

This document is currently not available here.

Share

COinS