Talk:Canonical Huffman code

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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[edit]

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[edit]

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[edit]

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?[edit]

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?[edit]

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)