Subject: Parallel compression

From: [email-masked] (Stephen R. Tate)
Date: 15 Jul 92 14:45:18 GMT

When I posted a previous message about parallel compression, I
completely forgot to mention the most relevant paper to the current
discussion:

S. De Agostino and J. Storer.  "Parallel Algorithms for Optimal
Compression using Dictionaries with the Prefix Property", Proceedings
of the Data Compression Conference, 1992, pp. 52-61.

A summary:

They give parallel algorithms for compression using a fixed dictionary
with the "prefix property" --- in other words, if a string w is in
the dictionary, then all prefixes of w are also in the dictionary (note
that LZW satisfies this).  Their best algorithm runs in time O(log^2 n)
time with O(n) processors (on the CREW PRAM model).  This isn't
optimal in work, but it is very good (only off by a log^2(n) factor).

However, that is for a fixed dictionary, not one that is dynamically
changing like LZW...  as for dynamic dictionaries, they cite a result
that "Dynamic dictionary compression is shown to be P-complete".
Without more details, I'm not sure what that means --- I assume it
means that constructing the LZ parse tree is P-complete.  If that's
the correct interpretation, it means that polylog time parallel
algorithms are highly unlikely for LZW compression (for something
compatible with UNIX compress, for instance)...  that is, it's
impossible to have a polylog time parallel "compress" algorithm unless
P=NC (highly unlikely).

Of course, polylog algorithms don't always correspond to "practical
parallel algorithms", but it's the best that I know of that can be
clearly analyzed.

This paper is about as clear as mud in spots (they don't give any
intuition about why or how their algorithms work), but that was probably
to fit in the page limit for conference papers --- perhaps a fuller
version is available....

-- 
Steve Tate                         [email-masked]
Dept. of Computer Science
Duke University
Durham, NC  27706