Scheme - Huffman 符号化木(可変長符号と固定長符号での符号化に必要なビット数の比較、一意的な相対頻度の記号と最低頻度、最高頻度の記号の必要ビット数)

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の2(データによる抽象の構築)、2.3(記号データ)、2.3.4(例: Huffman 符号化木)、Huffman 木の生成、Huffman 木の表現、複合化手続き、重みつき要素の集合の問題 2.70、問題2.71を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 2.70

コード

sample.scm

(define pairs (list '(A 2) '(NA 16) '(BOOM 1) '(SHA 3) 
                   '(GET 2) '(YIP 9) '(JOB 2) '(WAH 1)))

(define tree (generate-huffman-tree pairs))

(define message '(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))

(define code-variable (encode message tree))

(define variable-length-code (length code-variable))

(define (bit-symbol n)
  (define (iter n result)
    (let ((a (/ n 2)))
      (if (or (= a 1)
              (< a 1))
          result
          (iter a (+ result 1)))))
  (iter n 1))

(define fixed-length-code (* (length message)
                             (bit-symbol 8)))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

1 ]=> code-variable

;Value 2: (0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 1 1 1 1 1 1 1 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 1 0 0)

1 ]=> variable-length-code

;Value: 84

1 ]=> fixed-length-code

;Value: 108

Huffmanの木を生成して可変長符号を使って符号化したのがcode-variable。この符号化には84ビット必要。bit-symbolは記号がn個のときの、一つの記号当たり必要なビット数を求める手続き。固定長符号を使って符号化するのに必要な最小ビット数は108ビット。

問題 2.71

同じ相対頻度の記号がないHuffman 木では、最高頻度の記号を符号化するのに必要なビット数は1(0)、最低頻度の記号を符号化するのに必要なビット数はn-1ビット(11・・・(n-2個)1)。

上記の前問の5と10の場合で最高頻度、最低頻度がそれぞれ1と4、1と9になるかどうか確認。

コード

sample.scm

(define (most-frequent-symbol-bit tree)
  (define (iter tree result)
    (if (leaf? tree)
        (- result 1)
        (iter (left-branch tree) (+ result 1))))
  (iter tree 1))

(define (least-frequent-symbol-bit tree)
  (define (iter tree result)
    (if (leaf? tree)
        (- result 1)
        (iter (right-branch tree) (+ result 1))))
  (iter tree 1))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

1 ]=> (most-frequent-symbol-bit 5-tree)

;Value: 1

1 ]=> (least-frequent-symbol-bit 5-tree)

;Value: 4

1 ]=> (most-frequent-symbol-bit 10-tree)

;Value: 1

1 ]=> (least-frequent-symbol-bit 10-tree)

;Value: 9