CODEWITHSUNDEEP
c++huffman-code
MrD
MrD

Reputation: 2481

How to generate Huffman codes from huffman tree

I'm making jpeg encoder in C++. I successfully create Huffman tree, but how do I generate huffman codes from tree? One way I tried was to assign 0 to left branch and 1 to right branch, just like in the picture, but there is a problem in this approach, because one element will be coded with all ones (like sibol E in picture bellow which is coded with 11), but jpeg standard doesn't allow huffman codes with all ones.

enter image description here

Upvotes: 3

Views: 1954

Answers (3)

MrD
MrD

Reputation: 2481

I found that this is totally wrong approach in generating jpeg huffman codes. A Huffman table is generated from a collection of statistics in two steps, which are given in Annex K of JPEG standard. Also, few details are given in Annex C of the same document.

Upvotes: 0

Sebastian
Sebastian

Reputation: 8164

JPEG is using a fixed tree based on statistics. So you'll never get an optimal code. The fixed tree has to be used because it is the only way of distributing the Huffman tree in an efficient way (otherwise you would have to keep the tree within the file and this makes the file much bigger). I assume the tree is described within the standard documents.

Upvotes: 1

Steve Jessop
Steve Jessop

Reputation: 279255

If you can't use a string of all 1s, then you can't necessarily get an optimal code (optimal within certain constraints, I mean).

If you append a "0" to the string that's all "1"s, then it won't be all "1"s any more. You'll still have a prefix code, just not an optimal one. So that might suffice, but I don't know whether that's what jpeg encoders are supposed to do. I'd have thought there would be a standard solution.

Upvotes: 1

Related Questions