1

I have given message encoded with non-optimal Huffman code. I need to decode the message and encode it again, but this time with optimal Huffman code, so after that I can find average_number_of_bits_per_symbols = num_of_bits_in_message / num_of_characters_in_message

Example:

input:

6
A 11
B 10
C 01
D 0001
E 001
F 0000
101100000001000010001001100011000000010001010010000000100001000110001100011000000010000000000000100110001000100000000000000011011111010100100101011001010000111001010110000100000010010000000111010000001100100100001010001000100000000001

output:

2.469

Here is what I got from decoding:

// Third column is occurrence of the letter
A 11 5
B 10 19
C 01 12
D 0001 8
E 001 18
F 0000 19

BAFDFBEEBEBFEDCEFDFBEBEBEBFEFFFCEBEDFFFDBAABBBCECCBCCFABCCCBDFEEFDACFEBCEFBBEDFFE

num_of_characters: 81

So now I have to find optimal codes for these letters. I've tried tree like this one:

19      19     18     12      8     5
  B      F      E      C      D     A
   \     /       \     /      \     /
   0\   /1       0\   /1      0\   /1
     \ /           \ /          \ /
      \             \            /
       \             \          /
        \            0\        /1
         \             \      /
          \             \    /
           \             \  /
          0 \             \/
             \            /
              \          /
               \        /1
                \______/

And with this I will get:

A 111 => 3 * 5  = 15
D 110 => 3 * 8  = 24
C 101 => 3 * 12 = 36
E 100 => 3 * 18 = 54
F 01  => 2 * 19 = 38
B 00  => 2 * 19 = 38
num_of_bits     = 205

So 205 / 81 = 2.530 => which is not equal with the example output...

So what I am doing wrong?

Jovan Meshkov
  • 111
  • 3
  • 1
    D and A together have 8+5=13 which you should combine with the C node before C and E combine – ratchet freak Jul 14 '14 at 16:14
  • 3
    Ok... So? What's the question? – Ordous Jul 14 '14 at 16:17
  • The question is: What I am doing wrong? @ratchetfreak How can I do that? – Jovan Meshkov Jul 14 '14 at 16:46
  • @JovanMeshkov What ratchet is trying to say is: You built your tree incorrectly. Wiki has a pretty coherent explanation on how to build a good one. Also - this question is better suited for http://cs.stackexchange.com/ in this formulation. – Ordous Jul 14 '14 at 17:38
  • I know, I found out how to build the tree, now i have problem how to implement it without using trees in c++ – Jovan Meshkov Jul 14 '14 at 18:06
  • For the actual building of the tree, you want to learn how to work with binary heaps. In C++ this is built in as `std::priority_queue`, but you will need to use a custom comparison for this problem. Once you have a heap, it's just a matter of popping the two smallest elements out of the heap, combining them, and then sticking the combined element back into the heap. Repeat until you've exhausted all heap elements. I could go more into it, but we're getting far from the original question here which @ratchet-freak correctly answered. – QuestionC Jul 14 '14 at 19:36
  • Thanks for the point, but i am kinda not allowed to use queues, don't ask why :D Thanks all – Jovan Meshkov Jul 15 '14 at 00:03

0 Answers0