Parallel algorithms for Burrows-Wheeler compression and decompression

DOI10.1016/j.tcs.2013.10.009zbMath1358.68095OpenAlexW2164996008MaRDI 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 algorithmsPRAMlossless data compressionHuffman codingBurrows-Wheeler compressionmove-to-front coding

Mathematics Subject Classification ID

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

Related Items (3)

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

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

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