A89: Re: Re: Huffman


[Prev][Next][Index][Thread]

A89: Re: Re: Huffman





>I wonder what other algorithms we might all be able to create if we put
>some effort towards this.  Certainly we are all of above average
>intelligence and have the capacity to create our own algorithms.


If it had been that easy .... better check out some documentation on
compression algorithms to avoid reinventing the wheel.

some pointers:
http://www.math.washington.edu/~hillman/entropy.html
http://wwwvms.utexas.edu/~cbloom/index.html

http://www.dogma.net/markn


>>It's the Huffman Algorithm.  We just studied it in my Data Structures
>>Class.  When used for text, a reference table is made, and all the
>>characters are assigned new codes.  The most commonly used letter is
>>giving
>>the code 1.  The next 01, the next 001, then 011, etc.  The decoding
>>table


This isnt huffman. Huffman is quite similar, but has a more advanced method
of building the entropy encoding tree (determining the bitpatterns used to
encode the symbols).

>>is used to take the code, and figure out which character it stands
>>for.
>>I don't know how this applies to graphics though, as I think it is
>>already
>>optimized down to single bits.  The text one, when encoding take 8
>>bits at a
>>t ime and iterprets it as an ASCII code, but maybe for graphics you
>>could do
>>the same thing, with the most common combination of 8 pixels is given


Anyways. Huffman encoding is just an encoder based on statistics. It
doesnt take care of the context. For example it isnt able to detect
repeating patterns and compress them by just storing references (like lz77).

The best way is to combine both a statistical and a context encoder.
By doing this it should be possible to enhance the compression ratio of
the hufflib (of course depending on the data).

btw. Something worth thinking about might be a compressor for
executable files, which is decompressing the files once they
have been executed. This would allow to decrease the size of the asm
programs stored on your ti89 without having to optimze them any
further.