Huffman JavaScript Compression

Huffman encoding is based on the principle that letters that appear more frequently should have a smaller code than the ones that are used more often. So, in the English language, vowels would be used more than the letter z, and would get shorter codes. This javascript-based compression example uses this method to compress whatever you give it. It can work on web pages, javascript code, and tons more. The downfall is that it is extremely slow. It also re-encodes the binary data in a method similar to UUEncode?, which inflates 3 bytes of binary data to 4 bytes of textual data, so some of the awesome compression that is possible will be eliminated from the expansion of data.

Here are my thoughts on this experiment:

Good Bad
  • It works!
  • The decompression code really isn't all that big.
  • The decompression code isn't all that slow either.
  • The array for the nodes looks like it consumes way too much space.
  • Re-encoding the binary data with UUE negates the compression savings.
  • JavaScript shouldn't be used for compressing data (too slow)

Test it out for yourself. Insert web pages, javascript, or just simple text and then press the button. It can take quite a while (15k of a web page takes minutes on my computer). The advantages of having it run all client-side in JavaScript are that it is all client-side (you don't send any confidential data to my server) and it's quick to write. Start with small files and work your way larger.

I have a feeling that this would work great if you performed the compression across all of your pages if you could generate the "l" array based on the letter frequency of all of your web pages, and then put the decompression code and the "l" array in an external .js file. You could do this with only moderate difficulty with this script -- just edit the code and make a static Letters[] array.

Original:



View results of the compression in a popup window.

Compressed:


<disabled IFRAME id=topicif name=topicif src="/topic.php/compression?page=%2Ftools%2Fcompression%2Fcompress_huff.php&theme=normal&topic=compression" frameBorder=1 width="100%" height=150 allowTransparency> <disabled script language="javascript"><disabled /script>
    
A single death is a tragedy, a million deaths is a statistic.
-- Joseph Stalin


Tyler Akins < <disabled SCRIPT language=JavaScript><disabled /SCRIPT> fidian@tiny.net>