🔒 Locked

Huffman encoding

Started by Lode Jan 26, 2007 at 12:37 PM 2 replies 600+ views

Original Post

Jan 26, 2007 at 12:37 PM

Hi, When Huffman encoding, would it give a higher compression, to use a single huffman tree for the whole datastream, based on the frequency of the values in the whole stream, or is it better to calculate a separate tree for different chunks of the data stream (e.g. every 64K)? Also, what is a good way to store such a Huffman tree in C++ code? Currently I use an array that contains of each bit to what node of the tree to jump, but I was wondering if there exist better and/or faster implementations. Thanks.

nmi

Jan 26, 2007 at 1:27 PM

Quote:
Original post by Lode
Hi,

When Huffman encoding, would it give a higher compression, to use a single huffman tree for the whole datastream, based on the frequency of the values in the whole stream, or is it better to calculate a separate tree for different chunks of the data stream (e.g. every 64K)?

If the chunks each have a different structure (meaning the characteristic symbol frequencies are different), then encoding them seperately can result in better compression. If your chunks are just arbitrarily chosen (i.e. every 64kb from a 1mb file), then compression ratio would probably decrease compared to compression all at once.

Quote:

Also, what is a good way to store such a Huffman tree in C++ code? Currently I use an array that contains of each bit to what node of the tree to jump, but I was wondering if there exist better and/or faster implementations.

Read here:
http://en.wikipedia.org/wiki/Canonical_Huffman_code

Vorpy

Jan 26, 2007 at 4:36 PM

Storing the tree explicitly is surely the easiest method to understand.

For decoding, I think a more optimized version might build lookup tables. The keys would be bitstrings of up to a certain length and the values would contain information about the decoded characters and the state the decoder should enter to continue decoding.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.