1
$\begingroup$

I was trying to store a Huffman tree in a binary file recently. I thought it wouldn't be a big problem since you actually have the binary codes already in front of you.

Well, the difference is that the file (in the hex editor) is logically coded in hex. So I tried to convert the "characters" from binary to hex. Without any success.

Let's take this tree as an example:

Huffman-tree

My first attempt was to simply convert Binary to Hex. So for example 01 became 0x01. But there is a problem now: There are duplicates. So 01 as well as just 1 both became 0x01.

So I couldn't use that. I also tried to just represent the zeros and ones in hex, for example: 10 1... (The equivalent of 1 01) but that wouldn't be really efficient anymore.


So how could I now make a Huffman tree in Hex? Would I maybe even have to use a different encoding?

I hope I could describe my problem well enough.

$\endgroup$
1
  • $\begingroup$ My guess would be binary tree for binary representation, and 16-ary tree for hexadecimal, but that may be a simple approach. $\endgroup$
    – Nathaniel
    Commented Feb 21, 2021 at 21:22

1 Answer 1

2
$\begingroup$

This practical problem comes up in JPEG, where you can define your own Huffman tables. The codewords are limited to 16 bits, and the table is stored as follows:

  • For $\ell=1,\ldots,16$, the number of codewords of length $\ell$ bits.
  • For each $\ell$, a list of the values encoded by the codewords of length $\ell$.

The codewords themselves need not be stored, since a Huffman code can be extracted from this description. See Imran Nazar's notes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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