Huffman vs adaptive huffman

2
votes

I know that adaptive huffman has better performance than huffman algorhitm, but I can't figure out why.

In Huffman, when you build a tree and encode your text, you must send frequencies for each letter in text with encoded text. So when decoding, you build a tree, like you did when you were encoding, and then decode the message.

But in adaptive huffman, when you build a tree and encode text, I guess you must send message with built huffman tree? I may be wrong, but it seems that it's easier to send table containing letter frequencies, than whole tree.

Where am I wrong?

1
huffman-code
You don't have to send frequencies, you can send lengths. – harold
Yes, that what I meant... but adaptive huffman is supposed to be better.. so why is it better to send whole tree, than send just lengths? – user2090925
If a file (or block) has different letter frequencies in different regions, then adaptive huffman can use shorter codes for frequent letters in each of those regions, whereas static huffman can only use the average for the whole file. If the file is so short that you can't get any benefit from that then you instead benefit from not having to attach any header (whether it be tree or frequency data). – sh1
@sh1 But then, when decoding, you must have multiple trees, for different regions in file? – user2090925
Most lengths will be very similar and can be compressed in a way that exploits this. Frequencies of similar-length codes, however, can still vary significantly and carry a lot of information you don't want. – sh1

1 Answers

2
votes

No, you don't send the code. An adaptive Huffman code is adjusted incrementally using the data already received. That process is replicated on the receiving end.