Your metric on compression (how good it is) is the Shannon Limit. Read up on Shannon, who just passed away this last year.

Huffman is the best compression possible under the constraints that each input symbol maps to a single output symbol. It''s nothing to sneeze at, but it is a limitation.

Arithmetic codes and codebook (Ziv-Lempel family) compressions schemes are ways to represent groups of input symbols with groups of output symbols.

For now, something you''ve sort of hinted at is truncated huffman coding--symbol probability families can fall under a single huffman "code", and can trigger a switch to different coding. This is useful if you have a large set but 1/10th of the symbols are a very small probability (e.g.)--just group them all under a single ''key'' symbol and when it''s detected you switch to a different encoding method.

So, things to google for:
shannon
ziv lempel
arithmetic code
truncated huffman

Have fun--there''s lots to learn in this field.

quote:
For now, something you''ve sort of hinted at is truncated huffman coding--symbol probability families can fall under a single huffman "code", and can trigger a switch to different coding. This is useful if you have a large set but 1/10th of the symbols are a very small probability (e.g.)--just group them all under a single ''key'' symbol and when it''s detected you switch to a different encoding method.

I read the following about Truncated Huffman Coding:

http://www.cs.technion.ac.il/Labs/Isl/Project/Projects_done/VisionClasses/DIP/Lossless_Compression/node10.html

It sounds like you pick a threshold for encoding via Huffman style and the remaining symbols you mark with a special code and just put them in literally or with another encoding scheme? The line I don''t really understand from the above URL is:

quote:
The J-K less probable source symbols are assigned the Huffman code of that hypothetical symbol concatenated with natural binary code of length $\log_{2}(J-K)$

Too bad the forums don''t have a TeX interpreter. Anyways, I don''t see what they mean by the "natural binary code of length log2(J-K)". Why would the number of symbols not above a certain frequency threshold determine what goes after the dummy-symbol?

Huffman encoding and arithmetic encoding are pure entropy encoders. That is, all they do is remove the entropy from a set of bytes. This uses only character frequency information, and leaves out and information based on the order of the characters. Of the two, Huffman is simpler, but arithmetic is slightly better as it can share bits between multiple characters.

Dictionary-based encoding, like all of the Lempel-Ziv algorithms, are a different type of encoding. They look for repeated byte sequences, and replace them with an index into a dictionary. These algorithms look much more at byte order than the frequency of individual bytes.

Typical compression algorithms tend to use two passes. The first is usually a dictionary system. The second is an entropy encoding pass, to further compress the results of the first.

You''ll usually get the best compression by combinining different algorithms. One good combination is to compress the data using LZW or LZC(adaptive dictionary) and then run the output codes through an adaptive huffman filter using only the last 8 bits for it and just output the rest.
Adaptive Huffman can be slow as hell though. Compressing a file of 2mb in my first version took over two hours but after I''ve done some tweeking (many many hash tables) I got down to 6 seconds. Regarding the LZW algorithm, well, Unisys still have patent on it but it will expire next year in June or July I think.

link of the day: www.datacompression.info