blog: LZW compression

[nikos]

here's the comment area for today's blog post found at
http://zabkat.com/blog/24Jan10-lzw-compression-code.htm

[Kilmatead]

Back when I was teenager learning to program (in the DOS days) I thought it would be fun to experiment writing my own compression algorithm... 7-zip was the only kid on the block back then (or at least an early incarnation of it), and I was curious as to how it worked so well.

My approach was the boring bit-pattern recognition type (as that was the only one that made sense to me), and no matter how much I tweaked it, Zip always performed marginally better, which annoyed me no end - and this was only on text files, where at least you have a chance of some success.

Introduce the concept of recursive bit-patterning to an .EXE and you might as well take up yoga and try to get your legs in a pretzel instead of your brain.

It was a fun experiment, though.

A ceiling of ratios seems to have plateaued these days given the strides video compression has made... say, ripping a DVD with a combination of DVD Shrink and Handbrake software, you can end up with a decent quality 400-500 MB file... shove that into 7-Zip or WinRAR and you'll gain virtually nothing.

It's surprising the quality of video that can be achieved using the (increasingly popular) MKV container (Matroska) over the ageing AVI containers of days gone by.

[nikos]

[Kilmatead]

The best part was that I got to name my own filetype extension.

It's surprising how many different ways a 13 year old boy can think up compression acronyms that conform to spell .SEX files.  (Sequentially Executed Cross-patterning [X]!)

Hey, I was a teenager!  (My teacher in school was impressed and distraught at the same time, as they sanctioned the project in the first place.  I had the last laugh.)

[Kilmatead]

...following on the topic of file extensions, I'm bemused these days at the number of developers who "cheat" and just use ZIP's under a different name... spend any time playing around with Mozilla products and you'll find that all .XPI and .JAR files are nothing more than renamed .ZIP's.

I always bemoan the lack of imagination these days.  Such an opportunity lost!

[Mr.Pleasant]

Funny you came up with LZW compression. Anyone in the graphic industry (or just familiar with Photoshop) knows that LZW can be used to compress the size of your TIFF files. It's been tied to this particular field that I wasn't even aware of its usefulness in other fields!

[nikos]

it's also the compression behind GIFs and (probably) was protected by patents until not that long ago

[peregryne]

Nikos - very cool.  I wrote a really simple RLE compressor, since what I needed to compress had lots of single-character runs, but this could be very useful for some real compression.  thanks!