SICP 2.3.4 Example: Huffman Encoding Trees - プログラミング再入門

木を使った実用例としてデータ圧縮で使われるハフマン符合の話。

ノート

ハフマン符号化に使う木は、葉に各文字とその発生頻度、節にはその下に含まれる全ての文字と発生頻度の合計を持つ。ここでは枝を左に辿ると０、右に辿ると１で符号化する。復号する時には根から始めて０なら左、１なら右に降りて文字に辿り着いたら根に戻る事で各文字が復号出来る。

Generating Huffman trees

ハフマン木の構築。ハフマンが考えたアルゴリズム。

シンボルと頻度のペアが一列のリストになっているのが出発点
最も頻度が低い方から二つ（シンボルあるいは節）を選んでひとつの節を作る。選ばれた二つは節の下に左右にぶら下がり、節の頻度はぶら下がった二つの頻度の合計
この工程をリストの中に節がひとつだけになるまで繰り返す。

Representing Huffman trees

ハフマン木の実装。
葉を表すリストはleafと言うシンボル（タグ）、シンボル（ここでは文字）、頻度で構成する。
節（ここでは木と同じに扱われる）は左の枝、右の枝、左右の枝のシンボル（文字）、左右の枝の頻度の合計からなるリスト。
ここでgeneric procedureが少し顔を出す。葉と木とでは処理が異なるがどちらも扱えるsymbolsとweightを実装している。

The decoding procedure

まず復号する方から。
ビットと言うよりは0か1の（整数の）リストとハフマン木を引数に取り復号した文字列（シンボルのリスト）を返す。
復号しながら葉まで辿り着くと、ビットのリスト残りと最初のハフマン木を引数に残りを復号する為に再帰呼び出し、そこから戻って来たシンボルのリストに葉のシンボルを追加（consなので先頭に追加）する。
decode-1は内部関数なのでtree（ハフマン木全体）とcurrent-branch（現在の位置）の両方にアクセス可能。なので再帰呼び出しの際に振り出しに戻る事が出来る。

Sets of weighted elements

ハフマン木を構築する際のリストは頻度によって順序付けられたリストであると好都合。

Exercise 2.67

例示してあるコードを実行してみる。

> (decode sample-message sample-tree)
(A D A B B C A)
>

Exercise 2.68

左の葉に一致すればビット列に０を追加して終了、そうでなければ１を追加して一致する葉が見つかるまで右の枝を下降して行く。最後右の葉に到達した場合、その葉と一致すればそこで終了。一致しなければエラー。木が持っているシンボルリストに所望のシンボルが入っているかチェックするexist?を補助関数とする。

(define (exist? symbol symbol-list)
  (cond ((null? symbol-list) #f)
        ((eq? symbol (car symbol-list)) #t)
        (else
         (exist? symbol (cdr symbol-list)))))
      
(define (encode-symbol symbol tree)
  (if (exist? symbol (symbols tree))
      (cond ((leaf? tree) '())
            ((exist? symbol (symbols (left-branch tree))) (cons 0 (encode-symbol symbol (left-branch tree))))
            ((exist? symbol (symbols (right-branch tree))) (cons 1 (encode-symbol symbol (right-branch tree)))))
      (error "bad symbol -- encode-symbol:" symbol)))

実行してみる。

> (encode '(A D A B B C A) sample-tree)
(0 1 1 0 0 1 0 1 0 1 1 1 0)
>

Exercise 2.67と同じビット列に符号化出来ている。

Exercise 2.69

頻度が最小の二つの葉または木をマージする部分では、頻度のリストが昇順に並べられている事から、単純に先頭の二つをマージすれば良い事になる。マージするとは二つの葉または木を取り出してmake-code-treeに渡す事を意味する。マージした結果をどうするかと言えば、二つの葉または木を取り除いたリストに加える（adjoin-set）事になる。以上をコードにすると

(define (successive-merge leaf-set)
  (if (= 1 (length leaf-set))
      (car leaf-set)
      (successive-merge (adjoin-set          ; put it back to the rest of leaf-set
                         (make-code-tree     ;  merge two lowest weighted (first two leaves)
                          (car leaf-set)     ;   the first one
                          (cadr leaf-set))   ;   the second one
                         (cddr leaf-set))))) ;  the rest of the leaf-set

実行結果

> (define tree (generate-huffman-tree '((A 4) (B 2) (C 1) (D 1))))
> (encode '(A D A B B C A) tree)
(0 1 1 0 0 1 0 1 0 1 1 1 0)
> (decode (encode '(A D A B B C A) tree) tree)
(A D A B B C A)
>

Exercise 2.70

兎に角実行してみる。

> (define tree (generate-huffman-tree '((a 2)
                                        (na 16)
                                        (boom 1)
                                        (sha 3)
                                        (get 2)
                                        (yip 9)
                                        (job 2)
                                        (wah 1))))
> (define lyric '(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))
> (encode lyric tree)
(1
 1
 1
…中略
 1
 0
 1
 1)
> (decode (encode lyric tree) tree)
(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)
> (length (encode lyric tree))
84
>

84ビットに符号化出来た。
固定長だと単語の種類は8なので3ビットで表現可能。歌詞は36語あるので108ビット必要。

Exercise 2.71

同じ頻度のシンボルは存在せず、頻度が少ない方から1, 2, 4, 8...といった具合に2の冪乗になっている場合。
n=5だと頻度は(1 2 4 8 16)。マージすると
(1+2=3 4 8 16)
(3+4=7 8 16)
(7+8=15 16)
(15+16=32)
と行った具合。最初の２個の頻度を足すと３つ目の頻度より必ず１少ない。なので最も下の段だけ二つの葉を持つが、それより上は全て左側に葉、右側にそれ以下の木となって両側に木を持つ節は生まれない。最後の節は両側に葉を持つので節の数はn-1段。
n=10だと
(1 2 4 8 16 32 64 128 256 512 1024)
(1+2=3 4 8 16 32 64 128 256 512 1024)
(3+4=7 8 16 32 64 128 256 512 1024)
(7+8=15 16 32 64 128 256 512 1024)
(15+16=31 32 64 128 256 512 1024)
(31+32=63 64 128 256 512 1024)
(63+64=127 128 256 512 1024)
(127+128=255 256 512 1024)
(255+256=511 512 1024)
(511+512=1023 1024)
(1023+1024=2047)
となる。
ハフマン符号の場合、最頻のシンボルに割り当てられるビット数は常に１。n-1段あるので最も頻度が低いシンボルに割り当てられるビット数はn-1ビット。n=5の時は4ビット、n=10の時は9ビットとなる。

Exercise 2.72

最頻の文字は全体のシンボルの数には関わらずΘ(1)。
Exercise 2.71のハフマン木で最小頻度のシンボルを探し当てるには、各節で左側の葉と一致するか、右側のリストに存在するかをチェックする事になる。各節でのチェックの回数はn-1回なのでΘ(n)。左側の葉との比較は定数なのでΘ(1)。リストの比較は木を下降するに従って短くはなるが単純なリストの場合Θ(n)。なので都合Θ(n²)と言えそう。