Parallel Algorithms for Burrows-Wheeler Compression and Decompression

Simple item page
dc.contributor.authorEdwards, James A.
dc.contributor.authorVishkin, Uzi
dc.date.accessioned2012-11-13T16:14:34Z
dc.date.available2012-11-13T16:14:34Z
dc.date.issued2012-11-12
dc.description.abstractWe 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.en_US
dc.description.sponsorshipNSF grant CCF-0811504en_US
dc.identifier.urihttp://hdl.handle.net/1903/13299
dc.language.isoen_USen_US
dc.relation.isAvailableAtCollege of Computer, Mathematical & Natural Sciencesen_us
dc.relation.isAvailableAtComputer Scienceen_us
dc.relation.isAvailableAtDigital Repository at the University of Marylanden_us
dc.relation.isAvailableAtUniversity of Maryland (College Park, MD)en_us
dc.subjectParallel algorithmsen_US
dc.subjectPRAMen_US
dc.subjectBurrow Wheeleren_US
dc.subjectCompressionen_US
dc.titleParallel Algorithms for Burrows-Wheeler Compression and Decompressionen_US
dc.typeTechnical Reporten_US

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
bw_compression_drum.pdf
Size:
195.49 KB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.57 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

Computer Science Research Works
Electrical & Computer Engineering Research Works