UNZ - minimal LZW decoder + source

[encode]

OK, check out a tiny unpacker for my new LZW algorithm (C++ source included):
unz.zip (33 KB)

Test files:
acrord32.z (2,290 KB)
rafale.z (1,305 KB)
world95.z (1,013 KB)
fp.z (2,055 KB)

reaktor.z (4,315 KB)
mptrack.z (716 KB)
pariah.z (9,870 KB)

You may test it for the decompression speed (including with your own compiled versions). Have fun!

[nimdamsk]

Please make -mem option like in QuickLz to test compression/decompression speed.

[encode]

Will do something after I'll finish working on encoder - currently it's too slow - even with my core 2 duo I cant properly test it - the compression takes too much time.

Anyway, I compared current version against other fast compressors like QuickLZ and LZOP - on many files my LZW shows higher compression, in addition, it has a smallest and simplest decoder ever - can you show me a smaller thing?

[nimdamsk]

RLE

[encode]

[encode]

Please make -mem option like in QuickLz to test compression/decompression speed.

OK, zbench:
zbench.zip 6,437 KB

This program loads the compressed file into memory and performs in-memory decompression 32 times, measuring the elapsed time in milliseconds and the decompression speed. Compressed 3200.txt from uclc.info is included.

[nimdamsk]

Hm... Good job!

Compressor/Archive size/Decompression time:
Thor e5 - 6,073,576 - ~30 MB/sec
Thor e4 - 6,421,776 - ~20 MB/sec
zbench - 6,550,482 - ~100 MB/sec
tor2 -4 - 6,611,654 - ~50 MB/sec

[encode]

Yep, LZW is well known for its text and image compression.
I also written a small super-fast LZP coder, however, the compression of this program is really poor.
Overall, new LZW is pretty cool! Howewer, I'm still trying to develop a reasonable efficient encoder.
Here are many approaches available so far:
1. Brute force:
i.e. at each step, we check ALL possible phrases (nodes) (65536-256). And even if we use a hash checking to skip actual match, the compression with such thing is really slow.
2. Use links:
Keep an array with links to a table entries:
[code]
unsigned short link[65536][BINSIZE];
// ..
b=*((unsigned short *)&buf[i]); // or buf[i]+(buf[i+1]<<;

for (int j=0; j<BINSIZE; j++)
int code=link[b][j];

tab

...

This works but eats too much memory...

I think I should use kind of a tree or tricky linked lists. One thing - we should able to keep each entry independent - i.e. no prefixes...
And note that each time we add from one to three new phrases - and all of these have a different beginning - i.e. ABCD, BCD, CD...

Any ideas?