Paper Info
Title
Work-Optimal Parallel Decoders for LZ2 Data Compression
Abstract
The LZ2 compression method seems hardly parallelizable since some related heuristics are known to be P-complete. In spite of such negative result, the decoding process can be parallelized efficiently.In this paper, we show a work-optimal parallel decoding Las Vegas algorithm for text compressed by a standard implementation of the LZ2 algorithm (next character heuristic). The algorithm works in expected logarithmic time on a PRAM CRCW.We also address a different implementation called identity heuristic. In this case, we need to make the realistic assumption that the length of the dictionary elements is logarithmic in order to decode with optimal parallel work. The algorithm takes deterministic logarithmic time on a PRAM CREW.
Year
DOI
Venue
2000
10.1109/DCC.2000.838179
Data Compression Conference
Keywords
Field
DocType
computational complexity,concurrency theory,data compression,decoding,deterministic algorithms,optimisation,parallel algorithms,text analysis,LZ2 data compression,Las Vegas algorithm,PRAM CRCW,PRAM CREW,deterministic algorithm,identity heuristic,logarithmic time,text compression,work-optimal parallel decoders
Heuristic,Parallel algorithm,Computer science,Parallel computing,Algorithm,Theoretical computer science,Heuristics,Decoding methods,Data compression,Las Vegas algorithm,Lossless compression,Computational complexity theory
Conference
ISBN
Citations 
PageRank 
0-7695-0592-9
2
0.37
References 
Authors
11
1
Name
Order
Citations
PageRank
Sergio De Agostino110216.51