Hatena::Groupsicp

SICP in the blanket

2008-11-22

2.3.4 Huffman符号化木

00:58 | はてなブックマーク -  2.3.4 Huffman符号化木 - SICP in the blanket  2.3.4 Huffman符号化木 - SICP in the blanket のブックマークコメント

ex2.68: エンコード

一文字ごとにDFSする実装.

最初に符号化表みたいなものを作ってからメッセージ全体を一気に符号化する方が素直だと思うけれど.

;; ex2.68
(define (encode message tree)
  (if (null? message)
      '()
      (append (encode-symbol (car message) tree)
              (encode (cdr message) tree))))

(define (encode-symbol sym tree)
  (define (dfs tree code)
    (if (leaf? tree)
        (if (eq? (symbol-leaf tree) sym)
            (reverse code)
            #f)
        (or (dfs (left-branch tree)  (cons 0 code))
            (dfs (right-branch tree) (cons 1 code)))))
  (or (dfs tree '())
      (error "symbol not found" sym)))

ex2.69: ハフマン木の構成

集合から重みの小さいの二個取って一つにまとめて再度つっ込む,の繰り返し.Priority Queue 使うと効率よく実装できる.

;; 2.69
(define (generate-huffman-tree pairs)
  (successive-merge (make-leaf-set pairs)))

(define (successive-merge trees)
  (cond [(null? trees) (error "empty tree")]
        [(null? (cdr trees)) (car trees)]
        [else
         (successive-merge
          (adjoin-set (make-code-tree (car trees)
                                      (cadr trees))
                      (cddr trees)))]))

ex2.70

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

(define (symbol-upcase sym)
  (use srfi-13)
  (string->symbol (string-upcase (symbol->string sym))))

(define rock-message
  (map symbol-upcase
       '(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)))

; gosh> (encode rock-message rock-tree)
; (1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 0 1 1)
; gosh> (length (encode rock-message rock-tree))
; 84
; gosh> (* 3 (length rock-message))
; 108

ex2.71

最も偏った二分木になる.

  • 最高頻度の記号: 1 bit
  • 最低頻度の記号: n-1 bits

ex2.72

Huffman木の葉の数(アルファベット数)をNとする.

上記の実装だと 2.71 のケースにおいて,generate-huffman-tree は左に偏った木を作り,encode時のdfsは左の枝から先に探すので

  • 最高頻度の記号が一番遅く,木の節数(2N) steps
  • 最低頻度の記号が一番早く,N steps

dfsの順番を逆にして右の枝から探索するようにすると,

  • 最高頻度の記号が一番早く,1 step
  • 最低頻度の記号が一番遅く,木の節数(2N) steps

DFSの探索ステップ数は平均的にはO(N).

RobbieRobbie 2012/01/09 22:55 Always a good job right here. Keep roillng on through.

ifuyjqzhueifuyjqzhue 2012/01/10 17:19 xo9nFb <a href="http://nuuzbpzyrbml.com/">nuuzbpzyrbml</a>

spewhjgcspewhjgc 2012/01/10 23:52 9WTfCu , [url=http://pzosbgnunhso.com/]pzosbgnunhso[/url], [link=http://ltmlodiuszzd.com/]ltmlodiuszzd[/link], http://sybfvrkmnfar.com/

tyympnlcohltyympnlcohl 2012/01/12 23:09 wPxYOw <a href="http://kddcgdripmrb.com/">kddcgdripmrb</a>

nfqvxevcvnfqvxevcv 2012/01/15 02:05 p23W6g , [url=http://odzdgzibyvgi.com/]odzdgzibyvgi[/url], [link=http://jgzvkadsolqy.com/]jgzvkadsolqy[/link], http://urvnnvejqneu.com/

ゲスト



トラックバック - http://sicp.g.hatena.ne.jp/blanketsky/20081122