LZW File Compressor? Been There, Done That.

From Joel on Software:

“The assignments are very serious for a college class: implement a Unix command-line shell, implement a ZLW file compressor, etc.”

I found it funny that we did a project that was, as Joel puts it, “very serious for a college class”. It was an honors class, but oh boy, was it hard. I thought I knew C++, but I was wrong. Aparently there’s this thing called the command line, and bits and bytes. Oh, and bit shifting. Why wasn’t I taught this stuff before now? I mean, I knew that the operators meant to right shift and left shift, but I was clueless, until probably this very project as to what bit shifting actually was.

So, for those of you who care and don’t know, here is bit shifting in a walnut shell. (Its a little bit bigger than a nut shell. Oh wait, walnuts are nuts. Whatever…)

So, lets say you have a char in C++. It is represented as 8 bits. Each bit is either on or off. Remember how to count in binary? I think I learned it in fourth grade or something. Sadly, I needed to refresh. I’m not going to explain how to count in binary here. Anyway, convert to decimal, then go find an ascii table and convert to an ascii character. There you go. You have one letter in a text file.

If for example you only have 4 cahracters in you alphabet, you only need 2 bits. So, to compress this file with only four characters, you could compress the 8-bit chars to 2-bit chars by storing 4 chars within 8-bits. Since the computer, and/or C++ doesn’t work with less than 8 bits (aka a byte) at a time, we need to take the last byte in the file, move the bits over to the right spot, then do an or operation to add on the 2 bits to the end of the file.

If that didn’t make sense, maybe I need some diagrams or a better explaination. Let me know.

Oh, and when I start my own software company in the next few years, how am I supposed to hire the right people? How am I supposed to measure the programmers if the programmers can’t be measured AT ALL. Hmm… I’ll have to think about that one.

Here’s the article:
Hitting the High Notes

Leave a Reply