Parallel algorithms for Burrows-Wheeler compression and decompression

DOI10.1016/J.TCS.2013.10.009MaRDI QIDQ2437742zbMATH OpenOpenAlexFDO

Authors James A. Edwards, Uzi Vishkin

Publication date 13 March 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2013.10.009

zbMATH Keywords

parallel algorithmsPRAMHuffman codinglossless data compressionBurrows-Wheeler compressionmove-to-front coding

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Parallel algorithms in computer science (68W10) Algorithms on strings (68W32)

Recommendations

• Parallel computation of the Burrows Wheeler transform in compact space
• Parallel algorithms for data compression
• Computing the Burrows-Wheeler transform of a string and its reverse in parallel
• Parallelism and dictionary based data compression
• Parallel algorithms for encoding and decoding Blob code
• Burrows-Wheeler compression: Principles and reflections
• Parallelized Huffman and Hu-Tucker searching
• Compression boosting in optimal linear time using the Burrows-Wheeler transform
• Lempel-Ziv data compression on parallel and distributed systems

Cites work

• scientific article; zbMATH DE number 53772 (Why is no real title available?)
• A universal algorithm for sequential data compression
• Deterministic coin tossing with applications to optimal parallel list ranking
• Faster optimal parallel prefix sums and list ranking
• Indexing compressed text
• Lempel-Ziv data compression on parallel and distributed systems
• Lightweight data indexing and compression in external memory
• Linear work suffix array construction
• Optimal parallel suffix tree construction
• Parallel Huffman Decoding with Applications to JPEG Files
• Space efficient linear time construction of suffix arrays
• Symmetry breaking for suffix tree construction

Cited in

(4)

• Parallel lightweight wavelet tree, suffix array and FM-index construction
• Computing the Burrows-Wheeler transform of a string and its reverse in parallel
• Improved parallel construction of wavelet trees and rank/select structures
• Parallel computation of the Burrows Wheeler transform in compact space

Describes a project that uses

Uses Software

• SOAP3

This page was built for publication: Parallel algorithms for Burrows-Wheeler compression and decompression

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2437742)