1
$\begingroup$

I am trying to implement decompression algorithm based on huffman trees. I am trying to validate my assumptions.

Assume that you have alphabet of 350 symbols. Maximum encoded code length is 15 bits. How many different combinations of first 9 bits of each code longer than 9 bits can be encoded in this tree ?

I am only interested in these first 9 bits of codes which have length > 9 bits, since they determine memory requirement of the algorithm..

Tree is ordered by bit length, so that shorter codes lexicographically precede longer ones.


By my thinking there are 2 edge cases:

  1. Each code has same length: whole tree can be encoded on $log2(350) \approx 8.5 < 9$ bits and i don't need to worry about codes with length > 9, since there aren't any.

  2. Tree is maximally right-heavy, as many code as possible have length of 15 bits. Last 6 bits can encode $2^6 = 64$ symbols, since we need to encode 350 symbols, we can get the factor of 6 to cover all symbols by extending maximally branching tree upwards 3 bits. In this case codes which have maximum bit length share 6 bit prefix, have 3 bits different and then have 6 bit suffix that is irrelevant at this point.

Thanks to the ordering constraint, codes with similar lexicographic value and similar lengths will be grouped (will share same region of the tree, therefore same prefix)


In other cases, there is no way to create tree(provided maximum code length, number of encoded symbols and ordering of the code is satisfied) that would require more space.

If I assume most codes have bit length of let's say 11, that means I need to store $$2^{11-9=2} = 4 $$ codes for each prefix. In order to encode 350 symbols, I would extend the branching upwards 7 bits, creating at most 128 unique blocks(each block groups codes with same 9 bit prefix) , and I would need to store $128*4=512$ additional codes.

And since tree is ordered, longest codes will always be on the "right" and will be lexicographically grouped.


By these assumptions I came to the conclusion that I need to be able to store $512 + (8 * 64) = 1024$ codes. first 9 bits can be stored directly, and if code has length > 9, there is maximum of 8 different 9-bit prefixes, and for each unique prefix I need to store $2^6=64$ available combinations for 6 bit suffix.

Seems about right, but I would still like for someone to prove me wrong if I am.

$\endgroup$
  • 2
    $\begingroup$ Can you define what you mean by a "combination of first 9 bits of each code"? What do you mean by a combination? Do you mean, the number of ways to assign a 9-bit value to each symbol (well, each symbol that will receive a code of length > 9 bits)? It doesn't seem like you're asking quite the right question yet, given your goals -- but I'm not sure what the right question is, because I'm not clear on how you plan to measure the "space" needed to store one of these trees. $\endgroup$ – D.W. Jun 17 '16 at 18:03
  • $\begingroup$ I don't understand the 2nd of your edge cases. It seems like your reasoning there is confused. You want to argue about what is the worst possible case, but you actually seem to be discussing what is the best kind of tree such that all codes have length 15 bits. If so, that analysis is flawed. There might be other trees (where all codes are 15 bits long) that don't have the structure you hypothesize. Anyway, it's not clear how you measure the space of the tree, so it seems like the question is not answerable in its current form. $\endgroup$ – D.W. Jun 17 '16 at 18:08
  • $\begingroup$ I mean unique 9 bit prefixes on codes that are longer than 9 bits, provided the constraints(maximum code length, number of symbols, ordering of codes) is held. By space I mean: (number of unique prefixes)* (2^(maximum length of code with this prefix - 9) $\endgroup$ – semtexzv Jun 17 '16 at 18:11
  • $\begingroup$ There might be other valid huffman trees, but if the order of the tree is satisfied ( shorter codes are lexicographically smaller (on the "left") than longer ones ) it will always right-heavy or balanced $\endgroup$ – semtexzv Jun 17 '16 at 18:13
  • $\begingroup$ Also, thanks to the order constraint, codes with similar length and similar lexicographical values will be grouped, and will share same prefix $\endgroup$ – semtexzv Jun 17 '16 at 18:28

Your Answer

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

Browse other questions tagged or ask your own question.