Desperately need a bit of help with Huffman coding

SarcasticDwarf

Diamond Member
Jun 8, 2001
9,574
0
76
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?

 

hypn0tik

Diamond Member
Jul 5, 2005
5,867
2
0
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

Diamond Member
Jun 1, 2000
6,541
33
91
i know what you are talking about, i just don't know how to do it anymore
 

SarcasticDwarf

Diamond Member
Jun 8, 2001
9,574
0
76
YGPM Hypnotik

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

hypn0tik

Diamond Member
Jul 5, 2005
5,867
2
0
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...
 

ASK THE COMMUNITY