Huffman coding help

[AutoC]

Hi,

I'm trying to code Huffman coding.I've formed my huffman tree but dont understand how I'm gonna assign bits to it.How do I do bit operations and how do i maintain bits of length 3,5 etc?

Any help appreciated

[jencas]

Take a look at <<, >> (shift) and &, |, ^ (mask)

[Duoas]

Huffman codes are all variable-length --don't tack-on extra zeros (that would change the code).

Your tree should be organized top-down with branch 0 having a summed-weight <= branch 1. (Note: the tree will have a "random" balance.) The huffman code is just a list of branches taken in the path from root (MSB) to leaf (LSB).

To decode: starting at the root node, just peel one bit at a time from the input and follow that branch until you hit a leaf node, then emit the leaf's value. The next input bit will again be from the root node.

To encode is just a tad-bit trickier: for each leaf, collect all bits back to the root, then emit them in reverse order (without adding any other bits into the output stream).

For simple bit-packing and unpacking, use a bitvector (vector<bool>). You can then push and read individual bits easily enough...

Hope this helps.

[AutoC]

Thanks! I wanna do this without stl.Still not very clear on how I append odd bits

[Duoas]

You need to keep track of how many bits you have "output" so far. When you get eight or more, output a byte.

unsigned char bits = 0;  // the unwritten bits
int count = 0;  // the number of unwritten bits

// write_bit()
//    Write a single bit to the output stream
//
void write_bit( ostream& outs, bool bit )
  {
  // Add the latest bit into our "to-output" bits
  bits |= bit << count;

  // Track how many we have "output" so far
  if (++count < 8) return;

  // If we have "output" a whole byte, then
  // actually write it to the output stream
  outs.put( bits );

  // And reset
  bits  = 0;
  count = 0;
  }

// flush_bits()
//   Write any left-over bits --filling
//   with zeros to the even byte.
//
void flush_bits( ostream& outs )
  {
  if (count) outs.put( bits );
  bits  = 0;
  count = 0;
  }

I'm not sure how exactly you plan to avoid the STL in C++. The solution would be much nicer if you were to use it... but the above demonstrates the basics.

Notice how since we are dealing with a bit-stream, we must output bits in the same order as we get them -- meaning:

bit #   byte 1    byte 2
  1       .......@  ........
  2       ......@x  ........    These bytes are DISPLAYED
  3       .....@xx  ........    in the way that we humans
  4       ....@xxx  ........    like to read them, but what
  5       ...@xxxx  ........    is really IMPORTANT is that
  6       ..@xxxxx  ........    the bits fill in from the
  7       .@xxxxxx  ........    LEAST-significant bit to the
  8       @xxxxxxx  ........    MOST-significant bit in each byte.
  9       xxxxxxxx  .......@
  10      xxxxxxxx  ......@x

Input from the bitstream works the same way: read bits in order: first to last byte, lsb-to-msb in each byte.

Hope this helps.