CODEWITHSUNDEEP
filehuffman-code
user366312
user366312

Reputation: 16998

What is the basic technique of storing Huffman Tree along with Encoded bit stream as a file?

How can I store a Huffman Encoded bit stream as a binary file?

Upvotes: 1

Views: 784

Answers (1)

templatetypedef
templatetypedef

Reputation: 373002

To store the encoding, you'll need to have three things:

  1. Some way of reconstructing the encoding tree mapping each character to a bit pattern.
  2. The actual encoding of the stream.
  3. Some way of detecting the end of the encoded data.

There are many ways to solve each of these problems. You could explicitly store the bit patterns for each character in a table, or could just use the same encoding table for all streams you compress. As for how to detect the end of the stream, one option might be to use a pseudo-EOF character to terminate this stream. To do this, as you build up the Huffman encoding tree, add to it a new character with multiplicity one that will serve as a sentinel delineating the end of the stream. On writing the result, you write this character at the end so that you can tell where the stream ends even if it doesn't use a number of bits that fits perfectly into a byte.

To store the actual contents I'd suggest buffering the encoded representation into a bit vector that automatically flushes into a file stream on a multiple of eight bits. Of course, this isn't the only way to do this, so go with whatever works best.

Upvotes: 3

Related Questions