Desperately need a bit of help with Huffman coding

[SarcasticDwarf]

ok, first off, yes, this is homework. Unfortunately there is only one prof in the department who knows this stuff, he is not in today, and there are no TA's in our program.


See spreadsheet

I am working on encoding and decoding a paragraph. I have the frequencies in a spreadsheet. I have also encoded it and I *think* I did it correctly. What I am having trouble with is converting it binary. Basically, I am coming out with letters having duplicate binary associations. I have no clue why and my notes and google are failing me. Anyone have any idea what I am doing wrong?

 

[Koing]

I'm don't understand your notation we only ever did it with pen an paper.

http://en.wikipedia.org/wiki/Huffman_coding

Koing

 

[hypn0tik]

It looks like you built your Huffman code incorrectly. Remember, you always have to take the lowest 2.

Edit: To clarify...

Start with the smallest numbers 2 and 3. Together, you get 5. So now you have:

...
...
...
7
6
5

5

5

3-----------|
(........)----|---5
2-----------|

Now, with these, you take the smallest 2 again. In this case, two of the 5's.

...
...
...
7
6
5

5

5---------------------|
(.........................)|------------10
3-----------|(.........)|
(........)----|---5-----|
2-----------|

Now, the next smallest are the remaining 5's, and NOT the 6 and 5 that you seem to have taken in your spreadsheet.

 

[RichieZ]

i know what you are talking about, i just don't know how to do it anymore

 

[Leros]

You might find these slides useful. It has an example of building a tree and then converting it binary.

http://www.cs.utexas.edu/~scot...ts/Slides/lec19huf.pdf

 

[SarcasticDwarf]

YGPM Hypnotik

From what I can tell I did it correctly, since there is only one 5 left by that step.

 

[hypn0tik]

Originally posted by: SarcasticDwarf
YGPM Hypnotik

From what I can tell I did it correctly, since there is only one 5 left by that step.

YGPM.

You have three 5's in cells B40, B42 and B44. You create another one by combining B46 and B48. In total, you now have 4. These need to be combined to give you two 10's.

Then, you combine the 7 and the 6 in cells B38 and B36 to give you 13 and so on...

 

[Gibson486]

Man, it has been years since I have done that stuff..... fun class though