is it possible to make lzw compression/decompression parallel?

Question

i have read this article on how to compress/decompress data using LZW but i'm looking to make it use multiple threads... but i think it is not possible. what do you think? any papers or articles on this subject? or even hints on how to do it.

Answer 1

Parallelizing a compression algorithm at a low level will provide limited speedup and is likely to be more trouble than it's worth. The reason is that the real benefit would be in compressing large sets of data. In that case, it is far easier to simply break up the data into pieces and compress them individually with the normal algorithm.

LZW is old and not very effective. Other methods can compress faster and more effectively. You can look at various schemes from lz4 to zlib to lzma to ppmd, paq, etc., in a sequence from fastest with least compression to slowest with best compression. An example of parallelization is pigz, which uses zlib to compress large files to the gzip format using as many processors and cores as you have. It provides history from previous blocks to subsequent blocks in a parallel manner, so as to not lose compression effectiveness as compared to a serial, one-processor gzip compression.

Answer 2

You may want to read this paper, in particular Section 2.2 explains exactly how to parallelize a LZW scheme.

Answer 3

Parallelization of compression or decompression algorithm using multiple threads is reasonable when there are a lot of integer arithmetic to do. But lzw doesn't require it. You can see lzws source for example.

The amount of integer arithmetic is low. The main bottleneck is dictionary. You can receive more performance using memory overclocking and custom malloc realloc strategies.