Talk:Canonical Huffman code

Untitled

This article probably needs the examples rewriting as Canonical Huffman coding starts with all-zeros for the shortest code and ends with all-ones for the longest code:

A   0
B  10
C 110
D 111

This is opposite to the examples as given. The method for construction is then:

code = 0
while more symbols:
    print symbol, code
    code = code + 1
    if next bit length:
        code = code << 1

Sladen 13:54, 15 December 2006 (UTC)

Done this and attempted to clean up. Please check over that it actually makes sense and is correct. Sladen 02:25, 20 December 2006 (UTC)

3 March 2007

The reason the longest codes typically have all-zeros is that this version of canonical Huffman coding guarantees that all non-zero bits will appear in the final ceil(log2(alphabetsize)) bits of the pattern. This allows the pattern to be stored in a fixed-size variable since the leading 0s don't need to be stored.

21 August 2007

The pseudo code in this article seems not working, perapse it's just me but... I get an invalid huffman tree if I follow it. But the one on this page is working perfectly. Somebody who know this better than me must check the validity of the pseudo code given in this article. (bad-self-learned-english, sorry...) —The preceding unsigned comment was added by 83.77.85.224 (talk) 09:28, August 21, 2007 (UTC)

Better examples

Two good example words might be headache and beachhead. Both of these words are at least 8 letters long, contain repeated letters and only use the first eight letters in the alphabet. cabbage and baggage are seven letters a piece.

headache

symbol weight Huffman bits code canonical
a      2      00      2    0    00
b      0              0
c      1      110     3    6    110
d      1      111     3    7    111
e      2      01      2    1    01
f      0              0
g      0              0
h      2      10      2    2    10

         8,-
   4,-           4,-
2,a   2,e   2,h      2,-
                  c,1   d,1
00    01    10    110   111

2,0,3,3,2,0,0,2

Could be combined with ace headache, abba had a bad headache.

symbol weight Huffman bits code canonical
a      7        00    2    0     00
b      3        10    2    1     01
c      1       111    3    4    100
d      3       110    3    5    101
e      2       101    3    6    110
f      0              0
g      0              0
h      2       110    3    7    111

                    19,-
         10,-                9,-
      7,a    3,b       6,-         3,-
                    3,d   2,e   2,h   1,c
      00     01     100   101   110   111

2,2,3,3,3,0,0,3

beachhead

symbol weight huffman? code bits
a      2        00      0   2
b      1       110      6   3
c      1      1110     14   4
d      1      1111     15   4
e      2        01      1   2
f      0                -   0
g      0                -   0
h      2        10      2   2

Could be combined with faded beachhead cafe.

Holes in bit length sequences?

It seems to me that the pseudo-code given only works if the number of bits in the code only ever goes up by 1.

Take this, for example:

1 bit: A
3 bits: BCDE

The correct code would be as follows:

A: 0
B: 100
C: 101
D: 110
E: 111

But the pseudo-code given will generate this:

A: 0
B: 10
C: 11
D: 100
E: 101

Which is not prefix-free.

I think the outer loop needs to be on bit length, and then have an inner loop over symbols with that bit length, so the shift happens for every unit increase in code length. —Preceding unsigned comment added by 131.107.0.86 (talk) 18:36, 26 May 2009 (UTC)

Avoiding holes?

I think there is confusion between numbers and codes: "010" and "10" are the same number but are different codes, so the algorithm should be something like:

code = as many zeros as the first code length
while more symbols:
    print symbol, code
    code = code + 1
    if old bit length > code bit length
        insert a zero in front of code
    if old bit length > code bit length
        append a zero to the code  — Preceding unsigned comment added by 109.52.150.177 (talk) 19:19, 12 January 2013 (UTC) 

Bad example?

The example makes no sense to me. The article states,

With our canonical version we have the knowledge that the symbols are in sequential alphabetical order and that a later code will always be higher in value than an earlier one.

But look at the canonical code book that we generated in the example:

By following these three rules, the canonical version of the code book produced will be:

B = 0
A = 10
C = 110
D = 111

But "the symbols are in sequential alphabetical order" does not hold. We could reorder them, but "that a later code will always be higher in value" would not hold. It seems either the example is wrong, the assumptions made about canonical code books are wrong, or I'm unable to build an understanding of what the article is discussing. (And it cites no references for me to try a paraphrasing of the article, either!) —Deathanatos (talk) 03:51, 22 July 2020 (UTC)

Article should focus on speed, not space; also, alphabetical sorting is optional

The main reason for this article's problems (as alluded to in previous comments here on this talk page) is that it's focusing way too much on space savings. In reality, the main reason codecs use canonical huffman codes is for the decoding performance improvement that a single sentence of this article alludes to and dramatically understates. (To non-programmers: dramatically simplifying code does not usually make it dramatically faster, quite the opposite, so the word "dramatically" as it's used ATM is not emphasizing the speed benefit.)

Here's what I think should happen:

1) A new section should be written about specifically the decoder optimization. Strings encoded with canonical huffman codes can be decoded without traversing a tree, instead keeping track of the value below which the code terminates and above which it continues. This causes dramatically less memory pressure and compiles down to much more efficient assembly.

2) The notes about the "alphabetical sorting" of symbols are a space saving optimization applied *on top* of canonical huffman codes. They are not a detail of canonical huffman codes as such. It's frankly silly to think that a code can't be canonical if its alphabet isn't sorted within a given code length; some alphabets don't have properly-defined sorting functions! The sorting details should be in their own dedicated section and framed as an extension of the technique, not a core part. 67.246.18.8 (talk) 21:32, 9 December 2023 (UTC)