Parallel algorithms for Burrows-Wheeler compression and decompression

DOI10.1016/j.tcs.2013.10.009zbMath1358.68095MaRDI QIDQ2437742

Uzi Vishkin, James A. Edwards

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 algorithms; PRAM; lossless data compression; Huffman coding; Burrows-Wheeler compression; move-to-front coding

Mathematics Subject Classification ID

68W10: Parallel algorithms in computer science

68P30: Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science)

68W32: Algorithms on strings

Related Items

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

Uses Software

• SOAP3

Cites Work

• Unnamed Item
• Lempel-Ziv data compression on parallel and distributed systems
• Faster optimal parallel prefix sums and list ranking
• Lightweight data indexing and compression in external memory
• Space efficient linear time construction of suffix arrays
• Symmetry breaking for suffix tree construction
• Linear work suffix array construction
• Indexing compressed text
• On the Value of Multiple Read/Write Streams for Data Compression
• Deterministic coin tossing with applications to optimal parallel list ranking
• A universal algorithm for sequential data compression
• Parallel Huffman Decoding with Applications to JPEG Files
• Optimal parallel suffix tree construction