Compressed-domain pattern matching with the Burrows-Wheeler transform
dc.contributor.author | Powell, Matt | |
dc.date.accessioned | 2014-10-06T01:13:56Z | |
dc.date.available | 2014-10-06T01:13:56Z | |
dc.date.issued | 2001 | en |
dc.description.abstract | This report investigates two approaches for online pattern-matching in files compressed with the Burrows-Wheeler transform (Burrows & Wheeler 1994). The first is based on the Boyer-Moore pattern matching algorithm (Boyer & Moore 1977), and the second is based on binary search. The new methods use the special structure of the Burrows-Wheeler transform to achieve efficient, robust pattern matching algorithms that can be used on files that have been only partly decompressed. Experimental results show that both new methods perform considerably faster than a decompress-and-search approach for most applications, with binary search being faster than Boyer-Moore at the expense of increased memory usage. The binary search in particular is strongly related to efficient indexing strategies such as binary trees, and suggests a number of new applications of the Burrows-Wheeler transform in data storage and retrieval. | en |
dc.identifier.uri | http://hdl.handle.net/10092/9672 | |
dc.language.iso | en | |
dc.publisher | University of Canterbury. Computer Science and Software Engineering | en |
dc.relation.isreferencedby | NZCU | en |
dc.rights | Copyright Matt Powell | en |
dc.rights.uri | https://canterbury.libguides.com/rights/theses | en |
dc.subject.anzsrc | Field of Research::08 - Information and Computing Sciences::0801 - Artificial Intelligence and Image Processing::080109 - Pattern Recognition and Data Mining | en |
dc.subject.anzsrc | Field of Research::08 - Information and Computing Sciences::0806 - Information Systems::080604 - Database Management | en |
dc.title | Compressed-domain pattern matching with the Burrows-Wheeler transform | en |
dc.type | Reports | |
uc.college | Faculty of Engineering | en |
Files
Original bundle
1 - 1 of 1