We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
ALMOST WORK-OPTIMAL PRAM EREW DECODERS OF LZ COMPRESSED TEXT.
- Authors
de Agostino, Sergio
- Abstract
We show nearly work-optimal parallel decoding algorithms which run on the PRAM EREW in O(log n) time with O(n/(log n)½) processors for text compressed with LZ1 and LZ2 methods, where n is the length of the out put string. We also present pseudo work-optimal PRAM EREW decoders for finite window compression and LZ2 compression requiring logarithmic time with O(dn) work, where d is the window size and the alphabet size respectively. Finally, we observe that PRAM EREW decoders requiring O(log n) time and O(n/ log n) processors are possible with the non-conservative assumption that the computer word length is O(log² a) bits.
- Subjects
COMPUTER architecture; SYSTEMS development; PARALLEL processing; DECODERS (Electronics); DECODERS &; decoding; PARALLEL programming
- Publication
Parallel Processing Letters, 2004, Vol 14, Issue 3/4, p351
- ISSN
0129-6264
- Publication type
Article
- DOI
10.1142/S0129626404001933