LZW compression/decompression under low memory con

Question

Can anybody give pointers how I can implement lzw compression/decompression in low memory conditions (< 2k). is that possible?

Answer 1

It has been over 15 years since I last played with the LZW compression algorithm, so take the following with a grain of salt.

Given the memory constraints, this is going to be difficult at best. The dictionary you build is going to consume the vast majority of what you have available. (Assuming that code + memory <= 2k.)

Pick a small fixed size for your dictionary. Say 1024 entries.

Let each dictionary entry take the form of ....

 struct entry {
    intType   prevIdx;
    charType  newChar;
 };

This structure makes the dictionary recursive. You need the item at the previous index to be valid in order for it to work properly. Is this workable? I'm not sure. However, let us assume for the moment that it is and find out where it leads us ....

If you use the standard types for int and char, you are going to run out of memory fast. You will want to pack things together as tightly as possible. 1024 entries will take 10 bits to store. Your new character, will likely take 8 bits. Total = 18 bits.

18 bits * 1024 entries = 18432 bits or 2304 bytes.

At first glance this appears too large. What do we do? Take advantage of the fact that the first 256 entries are already known--your typical extended ascii set or what have you. This means we really need 768 entries.

768 * 18 bits = 13824 bits or 1728 bytes.

This leaves you with about 320 bytes to play with for code. Naturally, you can play around with the dictionary size and see what's good for you, but you will not end up with very much space for your code. Since you are looking at so little code space, I would expect that you would end up coding in assembly.

I hope this helps.

Answer 2

The lowest dictionary for lzw is trie on linked list. See original implementation in LZW AB. I've rewrited it in fork LZWS. Fork is compatible with ncompress. Detailed documentation here.

n bit dictionary requires (2 ** n) * sizeof(code) + ((2 ** n) - 257) * sizeof(code) + (2 ** n) - 257.

So:

1. 9 bit code - 1789 bytes.
2. 12 bit code - 19709 bytes.
3. 16 bit code - 326909 bytes.

Please be aware that it is a requirements for dictionary. You need to have about 100-150 bytes for state or variables in stack.

Decompressor will use less memory than compressor.

So I think that you can try to compress your data with 9 bit version. But it won't provide good compression ratio. More bits you have - ratio is better.