SICP問題2.71

SICP

n = 5 の場合

(A 1) (B 2) (C 4) (D 8) (E 16)
    {A B C D E} 31
      /   \
  E 16     {A B C D} 15
             /   \
          D 8    {A B C} 7
                   / \
                C 4   {A B} 3
                       / \
                    B 2   A 1

このとき必用なビット数はそれぞれ

E 0 
D 10 
C 110 
B 1110 
A 1111

となり最低頻度の記号を符号化するのに必用なビット数は4 (n - 1), 最高頻度の記号を符号かするのに必用なビット数は1

n = 10 の場合

(A 1) (B 2) (C 4) (D 8) (E 16) (F 32) (G 64) (H 128) (I 256) (J 512)
        {A B C D E F G H I J} 1023
       / \
  J 512   {A B C D E F G H I} 511
          / \
     I 256   {A B C D E F G H} 255
             / \
        H 128   {A B C D E F G} 127
                / \
            G 64   {A B C D E F} 63
                   / \
               F 32   {A B C D E} 31
                      / \
                  E 16   {A B C D} 15
                         / \
                      D 8   {A B C} 7
                            / \
                         C 4   {A B} 3
                               / \
                            B 2   A 1

このとき必用なビット数はそれぞれ

J 0
I 10
H 110
G 1110
F 11110
E 111110
D 1111110
C 11111110
B 111111110
A 111111111

となり最低頻度の記号を符号化するのに必用なビット数は9 (n - 1), 最高頻度の記号を符号かするのに必用なビット数は1