Title

Searching Bwt Compressed Text With The Boyer-Moore Algorithm And Binary Search

Keywords

Computer science; Data compression; Encoding; Image coding; Pattern matching; USA Councils

Abstract

This paper explores two techniques for on-line exact pattern matching in files that have been compressed using the Burrows-Wheeler transform. We investigate two approaches. The first is an application of the Boyer-Moore algorithm (1977) to a transformed string. The second approach is based on the observation that the transform effectively contains a sorted list of all substrings of the original text, which can be exploited for very rapid searching using a variant of binary search. Both methods are faster than a decompress-and-search approach for small numbers of queries, and binary search is much faster even for large numbers of queries.

Publication Date

1-1-2002

Publication Title

Data Compression Conference Proceedings

Volume

2002-January

Number of Pages

112-121

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

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

Socpus ID

84948415150 (Scopus)

Source API URL

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

This document is currently not available here.

Share

COinS