University of Maryland DRUM  
University of Maryland Digital Repository at the University of Maryland

Digital Repository at the University of Maryland (DRUM) >
College of Computer, Mathematical & Natural Sciences >
Computer Science >
Computer Science Research Works >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1903/13299

Title: Parallel Algorithms for Burrows-Wheeler Compression and Decompression
Authors: Edwards, James A.
Vishkin, Uzi
Type: Technical Report
Keywords: Parallel algorithms
PRAM
Burrow Wheeler
Compression
Issue Date: 12-Nov-2012
Abstract: We present work-optimal PRAM algorithms for Burrows-Wheeler compression and decompression of strings over a constant alphabet. For a string of length n, the depth of the compression algorithm is O(log2 n), and the depth of the the corresponding decompression algorithm is O(log n). These appear to be the first polylogarithmic-time work-optimal parallel algorithms for any standard lossless compression scheme. The algorithms for the individual stages of compression and decompression may also be of independent interest: 1. a novel O(log n)-time, O(n)-work PRAM algorithm for Huffman decoding; 2. original insights into the stages of the BW compression and decompression problems, bringing out parallelism that was not readily apparent, allowing them to be mapped to elementary parallel routines that have O(log n)-time, O(n)-work solutions, such as: (i) prefix-sums problems with an appropriately-defined associative binary operator for several stages, and (ii) list ranking for the final stage of decompression.
URI: http://hdl.handle.net/1903/13299
Appears in Collections:Electrical & Computer Engineering Research Works
Computer Science Research Works

Files in This Item:

File Description SizeFormatNo. of Downloads
bw_compression_drum.pdf195.49 kBAdobe PDF329View/Open

All items in DRUM are protected by copyright, with all rights reserved.

 

DRUM is brought to you by the University of Maryland Libraries
University of Maryland, College Park, MD 20742-7011 (301)314-1328.
Please send us your comments