SICP 問題 2.71（数式に従って生成されるシンボルと頻度のペアでHuffman木を生成）

問題

n 記号のアルファベットの Huffman 木があるとし、記号の相対頻度が、

としよう。
n = 5, n = 10 の木を描け。
（一般の n の）こういう木で、最高頻度の記号を符号化するのに必要なビット数はいくらか。
最低頻度の記号ではどうか。

解答

まずは入力されるデータを生成する手続きを考えようか。

;iota を使用したいので。
(use srfi-1)

(define (create-test-data n)
  (map (lambda (x)
	 (expt 2 (- x 1))) ;2^(n-1) を返却する手続き
       ;初期値 1 で、MAX が n の数列を生成
       (iota n 1)))

確認してみる。

gosh> (create-test-data 5)

(1 2 4 8 16)

gosh> (create-test-data 10)

(1 2 4 8 16 32 64 128 256 512)

gosh> 

いいねぇ。あ、でもアルファベットとこの求めた頻度を対にしなきゃならんな。ちょっと改造したいが、n を元にしてアルファベットに変換できねーかな。int->char 的な関数ねぇか？探すには apropos 手続きを使う。

gosh> (apropos 'int)
（※中略※）
integer->char                  (scheme)

integer->digit                 (gauche)

integer-length                 (gauche)

integer?                       (scheme)
（※中略※）
gosh> 

お〜、integer->char ってアヤシイ感じのがあるね。じゃあ d 手続きでもう少し詳しく。

gosh> (d integer->char)

#char> is an instance of class 

slots:

  required  : 1

  optional  : #f

  locked    : #f

  info      : "integer->char"

  setter    : #f

gosh> 

更に詳しい情報を。

gosh> (info "integer->char")

6.8 Characters

==============
（※中略※）
 -- Function: char->integer char

 -- Function: integer->char n

     [R5RS] `char->integer' returns an exact integer that represents

     internal encoding of the character CHAR.  `integer->char' returns

     a character whose internal encoding is an exact integer N.  The

     following expression is always true for valid character CHAR:

          (eq? char (integer->char (char->integer char)))
     The result is undefined if you pass N to `integer->char' that

     doesn't have a corresponding character.
（※中略※）
gosh> 

あくまでも「文字」を返す感じ。シンボルに変化させることってできないのかな。

gosh> (apropos 'sym)

                  (gauche)

                       (gauche)

gensym                         (gauche)

identifier->symbol             (gauche)

string->symbol                 (scheme)

symbol->string                 (scheme)

symbol-bound?                  (gauche)

symbol?                        (scheme)

sys-symlink                    (gauche)

gosh> 

お、string->symbol ってのがあるな。じゃ、char->string 的なものは・・・ざっと見た感じなさげ。Google 先生に聞いてみたら、make-string ってのがそれっぽいことができそうな感じ。
呼び出し時の引数を確認してみよう。

gosh> (apropos 'make-string)

make-string                    (scheme)

make-string-pointer            (gauche)

gosh> (d make-string)

# is an instance of class 

slots:

  required  : 1

  optional  : #t

  locked    : #f

  info      : "make-string"

  setter    : #f

gosh> (info "make-string")

6.10.3 String Constructors


















































-
























 -- Function: make-string k &optional char

     [R5RS] Returns a string of length K.  If optional CHAR is given,

     the new string is filled with it.  Otherwise, the string is filled

     with a whitespace.  The result string is always complete.
          (make-string 5 #\x) => "xxxxx"
     Note that the algorithm to allocate a string by `make-string' and

     then fills it one character at a time is _extremely_ inefficient

     in Gauche, and should be avoided.   That kind of algorithms

     unnecessarily assumes underlying string allocation and

     representation mechanism, which Gauche doesn't follow.  You can

     use an output string port for a string construction (*Note String

     ports::).  Even creating a list of characters and using

     `list->string' is faster than using `make-string' and

     `string-set!'.
（※後略※）
gosh> 

第１引数に何回繰り返すかを、第２引数に該当する文字を渡すみたいだな。では実験。

gosh> (make-string 1 (integer->char 70))

"F"

gosh> (string->symbol (make-string 1 (integer->char 70)))

F

gosh> 

できた！よ〜しよしよし、これでやりたい処理ができそうだぞ。n と文字（コード）の関係はこんな感じ。

n = 1 → A（64 + 1 = 65）

n = 2 → B（64 + 2 = 66）

n = 3 → C（64 + 3 = 67）

・

・

・

こいつを create-test-data に組み込んでやる。

;iota を使用したいので。
(use srfi-1)

(define (create-test-data n)
  (map (lambda (x)
	 (list 
	  ;x を元にシンボルを生成
	  (string->symbol (make-string 1 (integer->char (+ 64 x))))
	  ;出現頻度を数列式 2^(n-1) で生成。
	  (expt 2 (- x 1))))
       ;初期値 1 で、MAX が n の数列を生成
       (iota n 1)))

こんな感じか。では実験。

gosh> (create-test-data 5)

( (A 1) (B 2) (C 4) (D 8) (E 16))

gosh> (create-test-data 10)

( (A 1) (B 2) (C 4) (D 8) (E 16) (F 32) (G 64) (H 128) (I 256) (J 512))

gosh> 

お、いいねぇ。じゃ、データできたから Huffman 木を生成しよう。

gosh> (generate-huffman-tree (create-test-data 5))

(((((leaf A 1) (leaf B 2) (A B) 3) (leaf C 4) (A B C) 7) (leaf D 8) (A B C D) 15) (leaf E 16) (A B C D E) 31)

gosh> 

さて、木にしてみようか。

                 (A B C D E)31

                     ／ ＼

           (A B C D)15  (E 16)

              ／ ＼

       (A B C)7   (D 8)

        ／ ＼

   (A B)3   (C 4)

   ／ ＼

(A 1) (B 2)

こんな感じ。n = 10 の場合は・・・

gosh> (generate-huffman-tree (create-test-data 10))

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

gosh> 

木にすると・・・

                                                        (A B C D E F G H I J)1023

                                                                     ／ ＼

                                                 (A B C D E F G H I)511  (J 512)

                                                          ／ ＼

                                        (A B C D E F G H)255  (I 256)

                                                ／ ＼

                               (A B C D E F G)127  (H 128)

                                      ／ ＼

                        (A B C D E F)63  (G 64)

                             ／ ＼

                 (A B C D E)31  (F 32)

                     ／ ＼

           (A B C D)15  (E 16)

              ／ ＼

       (A B C)7   (D 8)

        ／ ＼

   (A B)3   (C 4)

   ／ ＼

(A 1) (B 2)

最高頻度の記号を符号化するのに必要なビット数は、1ビットでOK。これは n に依存しない。頻度が多いから1ビットで表現するのがHuffman符号化木なわけで。

さて、最低頻度について。
n = 5 の時は、最低頻度の A を表現するのに必要なビット数は、4 ビット。
n = 10 の時は、最低頻度の A を表現するのに必要なビット数は、9 ビット。
これを見ると思いっきり n-1 になってるんだが、ちゃんと証明するにはどうしたもんかな。。