Title :
A parallel decoder for LZ2 compression using the ID update heuristic
Author :
De Agostino, Sergio
Author_Institution :
Dipt. di Sci. dell´´Inf., Rome Univ., Italy
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 for the next character heuristic. We show an other parallel decoding algorithm for LZ2 compression using the ID update heuristic. The algorithm works in O(log2n) time with O(n/log(n)) processors on a PRAM EREW, where n is the length of the output string
Keywords :
data compression; decoding; parallel algorithms; LZ2 compression; P-complete; PRAM EREW; character heuristic; output string length; parallel decoder; parallel decoding algorithm; Algorithm design and analysis; Books; Decoding; Dictionaries; Heuristic algorithms; Phase change random access memory; Polynomials; Remuneration;
Conference_Titel :
Compression and Complexity of Sequences 1997. Proceedings
Conference_Location :
Salerno
Print_ISBN :
0-8186-8132-2
DOI :
10.1109/SEQUEN.1997.666931
