[A83] Re: Is compression possible?


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

[A83] Re: Is compression possible?






Thomas Lutz wrote:

> I'm sure it wouldn't be too hard to implement the Huffman Compression
> Algorithm...The question is: would it be worth it? Compression works
> better for large files because you have to store the resulting Huffman
> tree. Of course it would be very interesting to have a Zip app on the
> calculator...

If you implemented Huffman in a way similar to the Deflate algorithm, the
Huffman tree takes no more than 128 bytes:

The problem with storing a Huffman tree is that one input can produce more
than one tree. Deflate avoids this problem by using two additional rules
while building the Huffman tree:

1) Symbols with shorter codes are place to the left of those with longer
codes.
2) If two symbols have the same code length, the one that comes first in the
symbol alphabet is placed on the left.

If you follow these rules, there is only 1 possible tree for every input, so
all you need to store to reconstruct a tree is the code lengths of the
symbols. Deflate constructs the Huffman tree in a fashion to ensure no
symbol has a code length larger than 15 - allowing the use of just 4 bits to
store each symbol.

My gut feeling is that the Z80 would be much more suited to LZ77. I have a
long weekend coming up... I might investigate this a bit more.




References: