Not Yet Answered # Huffman coding help

Duoas 1,025 Discussion Starter AutoC Duoas 1,025 Need some help with this Array. I am trying to get the sum of the even numbers and the sum of the odd numbers using a for each loop. I know the answers to what I am trying to achive are sum of even = 84 and the sum of ...

0

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.

0

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

1

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.

This article has been dead for over six months. Start a new discussion instead.

Recommended Articles

When I execute this progammatically, I get a table with row heights much larger than when I do this manually.

Note : Sel is the Word.Selection object and the Clipboard contains an Excel Table.

```
public void AddClipboard()
{
Sel.PasteExcelTable(false,false, false);
var t = Sel.Tables[Sel.Tables.Count];
t.AutoFitBehavior(Word.WdAutoFitBehavior.wdAutoFitContent);
}
```

the function that I created to find the ...