We have the word "w = aabceefgeebdaabbceeffghdcbbeefbbbbghhie ".

I have created a Huffman tree for the string w.

We get the following table:

enter image description here

Now I want to create a Huffman tree for a Block-Code with length of block $4$.

Do we maybe take each consecutive 4 letters, i.e., {aabc, eefg, eebd, aabb, ceef, fghd, cbbe, efbb, bbgh, hie} to make the tree?

But then the last one is of length 3 and not 4.

So, do we choose in an other way the blocks?


In your context, a block code of length $\ell$ encodes $\ell$ letters at a time. The domain thus consists of all words over the alphabet of length $\ell$. Unless you're told otherwise, the assumption is that the individual letters are independent - the probability of a word $\sigma_1 \dots \sigma_\ell$ is the product of the probabilities of the individual letters.

  • $\begingroup$ So do we have to find all the possible words with 4 letters and then we create the tree considering these words as the symbols? $\endgroup$ – Mary Star Dec 7 '16 at 7:59
  • $\begingroup$ Yes, that's the idea. $\endgroup$ – Yuval Filmus Dec 7 '16 at 8:03
  • $\begingroup$ The words: "befa" and "efba" are counted as the same word, or not? $\endgroup$ – Mary Star Dec 7 '16 at 10:14
  • $\begingroup$ The idea of the block code is to encode streams of letters more efficiently than one letter at a time. Given this rationale, you should be able to answer this question yourself. If you have any further questions, I suggest asking your TA or instructor. $\endgroup$ – Yuval Filmus Dec 7 '16 at 10:17
  • $\begingroup$ I am not taking that subject,... I am trying to learn it by myself, by looking at some examples/notes of the internet... Unfortunately, I haven't found an example for a Huffman tree for a block code.... So, do we have the following block? $$$$ idcf, idca, idce, idcb, idch, idcg, dcgh, dcgf, dcga, dcge, dcgb, cghf, cgha, cghe, cghb, ghfa, ghfe, ghfb, hfae, hfab, faeb $$$$ How do we know if we have found all the possibilities? $\endgroup$ – Mary Star Dec 7 '16 at 11:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.