Choosing a compression algorithm to implement
c, compression, encoding, information-theory
Solution
Just LZW, with no other coding, is pretty darned simple and works surprisingly well. No one would actually use LZW nowadays, since there are other algorithms that can compress better faster. However for an assignment, you can't beat the simplicity of LZW. No Huffman, dynamic or otherwise. No Shannon-Fano. No arithmetic or range coding. And yes, the memory usage is independent of the length of the message. Mark Nelson has written a very good explanation.
You can do it in C or Java, though C might be less error-prone since it has unsigned types.
Problem
I've been given some coursework to implement a compression algorithm of my choice. It can be any language, however the languages I know best would be Java, followed by C. It will be evaluated based on - The decompressed output must match the original input, so I can only look at loss less algorithms. The run time must be proportional to the length of the message. The memory requirement must be independent of the length of the message. Our implementations will be tested as follows - A standard text file A binary file with byte values from 0-255 A large file ~10mb of unspecified content. My initial thought is to use dynamic arithmetic coding, but I'm wondering if there is an algorithm better suited to the constraints above? Secondly, is it a better idea to do it in C rather than Java? I ask this because I think C will have a smaller memory foot print but I'm unsure if that's actually the case. I've spent some time Googling this question, and a few sites mention LZW coding combined with dynamic Huffman coding. Would this be a sensible avenue to pursue? Our lecturer did warn us that 90% of the submissions that tried dynamic Huffman coding over the years were not correctly implemented. That said, I'm not afraid to give it a try, but I would value some opinions before I begin. Any feedback would be much appreciated.