SICP読書会 2.3.4 – …

問題と解答

問題 2.69

次の手続きは引数として記号と頻度の対のリストをとり, (どの記号も一つの対以外には現れない.) Huffmanアルゴリズムに従い, Huffman符号化木を生成する.
(define (generate-huffman-tree pairs)
(successive-merge (make-leaf-set pairs)))
make-leaf-setは上にある手続きで, 対のリストを葉の順序づけられた集合へ変換する. successive-mergeは自分で書く手続きで, make-code-treeを使い, 集合の最小重みの要素を順に合体させ, 要素が一つになったら止める. それが目的のHuffman木である. (この手続きは多少ややこしいが, 複雑ではない. 複雑な手続きを設計していると思ったら, 確実にどこか違っている. 順序づけられた集合の表現を使っていることを活用しなければならない.)

記号とその頻度の対のリストからHuffman符号化木を作成するための, 再帰処理部分を実装せよ, という問題です.

(define (successive-merge leaf-set)
  (if (= (length leaf-set) 1) (car leaf-set)
    (successive-merge
      (adjoin-set (make-code-tree (car leaf-set)
                                  (cadr leaf-set))
                  (cddr leaf-set)))))

問題 2.70

次の八記号のアルファベットと相対頻度は, 1950年代のロックの歌の叙情詩を効率よく符号化するよう設計された. (「アルファベット」の「記号」は必ずしも個々の文字ではないことに注意)
A 2 NA 16
BOOM 1 SHA 3
GET 2 YIP 9
JOB 2 WAH 1
(問題2.69の)generate-huffman-treeを使って対応するHuffman木を生成し, (問題2.68の)encodeを使って次の通信文を符号化せよ:

Get a job
Sha na na na na na na na na
Get a job
Sha na na na na na na na na
Wah yip yip yip yip yip yip yip yip yip
Sha boom

符号化に何ビット必要か. 八記号アルファベットの固定長符号を使うとこの歌を符号化するのに必要な最小ビット数はいくらか.

ロックの歌からHuffman符号化木を作成してみて, Huffman符号で符号化した場合と固定長符号による場合を比較せよ, という問題です.

(define rock (generate-huffman-tree '((BOOM 1) (WAH 1) (A 2) (GET 2) (JOB 2) (SHA 3) (YIP 9) (NA 16))))
(define song
  '(GET A JOB
    SHA NA NA NA NA NA NA NA NA
    GET A JOB
    SHA NA NA NA NA NA NA NA NA
    WAH YIP YIP YIP YIP YIP YIP YIP YIP YIP
    SHA BOOM))

(print (length (encode song rock)))
; 84

(print (* 3 (length song)))
; 108

問題の通信文をHuffman符号化して長さを取ると, 84ビット必要だとわかります.
一方固定長符号で表す場合, 1記号あたりlog₂8 = 3ビット必要です.
通信文の長さとの積により108ビットと求まります.
よって, Huffman符号では 84 ビット, 固定長符号では 108 ビット必要です.

問題 2.71

n記号のアルファベットのHuffman木があるとし, 記号の相対頻度が1, 2, 4, … ,2n-1としよう. n=5とn=10の木を描け. (一般のnの)こういう木で, 最高頻度の記号を符号化するのに必要なビット数はいくらか. 最低頻度の記号ではどうか.

相対頻度がA=1, B=2, C=4, … とした時, n=5 の木は下記の図のようになります.

31 {A B C D E}
          / \
15 {A B C D} E
        / \
 7 {A B C} D
      / \
 3 {A B} C
    / \
   A   B

n=10の木は下記の図のようになります.

1023 {A B C D E F G H I J}
                      / \
 511 {A B C D E F G H I} J
                    / \
 255 {A B C D E F G H} I
                  / \
 127 {A B C D E F G} H
                / \
  63 {A B C D E F} G
              / \
  31 {A B C D E} F
            / \
  15 {A B C D} E
          / \
   7 {A B C} D
        / \
   3 {A B} C
      / \
     A   B

(一般のnの)こういう木で, 最高頻度の記号を符号化するのに必要なビット数はいくらか.

最高頻度の記号を符号化すると (1) , すなわち 1 ビットです.
一方最高頻度の記号の場合, (0 0 0 ... 0) のように0の列で表されます.
葉に到達するまでn-1回枝を辿るため, n-1 ビットです.

問題 2.72

問題2.68で設計した符号化手続きを考える. 記号を符号化するのに必要なステップ数の増加の程度は何か. 各節で記号のリストを探索するのに必要なステップ数を忘れないように. この問題に一般的に答えるのは難しい. n個の記号の相対頻度が問題2.71にあるような特別な場合を考え, アルファベットの最高頻度と最低頻度の記号を符号化するのに必要なステップ数の(nの関数としての) 増加の程度を答えよ.

問題の通り, 一般的なケースではなく, 問題2.71にあるような符号化木を持つ時の最高頻度および最低頻度の記号について考えます.

まず最高頻度の記号の場合について考えます.
最高頻度の記号を符号化する場合, ルートの左の枝と右の枝, どちらに含まれているか調べますが, 右の枝がその記号の葉であるため1回のループで探索終了となります.
この時にかかるステップ数は, 左の枝の長さn-1のリストに含まれているか調べるので, O(n) とみなせます.
ただし符号化木が効率的な実装をされており, 記号が頻度順でソートされていればJは先頭かもしれません. その場合は定数オーダーで判定できるので, O(1) となります.

次に最低頻度の記号の場合について考えます.
先の要領で木を調べていきますが, 今度は順に左に下ってn-1個の節を調べる必要があります.
この時, 長さが n-1, n-2, … ,2, 1 のリストを順に走査していく形になります.
走査にかかるステップ数は級数の和とみなせるので, オーダーは, O(1 + 2 + 3 + .. + (n - 1)) = O(1/2 * (n - 1) * n) ですので, O(n^2) です.

次回

次回は SICP読書会 2.4.3 です.
2.4.3 データ主導プログラミングと加法性 の問題 2.73から問題 2.76までを解きます.