n = 5のとき，最高頻度の記号には4bit.最低頻度の記号には1bit必要． n = 10のとき，最高頻度の記号には9bit.最低頻度の記号には1bit必要．

gosh> (define q-pairs '((A 2) (BOOM 1) (GET 2) (JOB 2) (NA 16) (SHA 3) (YIP 9) (WAH 1))) q-pairs gosh> (define q-tree (successive-merge (make-leaf-set q-pairs))) q-tree gosh> (define message '(GET A JOB SHA NA NA NA NA NA NA NA NA GET A JO…

(define (generate-huffman-tree pairs) (successive-merge (make-leaf-set pairs))) ;; pairsは昇順に並んでいるので先頭の2要素をmake-code-pairsする． ;; それを(cddr pairs)にadjoin-setすればまた昇順に並んだpairsができるのでそれを繰り返す． (defi…

(define (encode message tree) (if (null? message) '() (append (encode-symbol (car message) tree) (encode (cdr message) tree)))) (define (encode-symbol msg tree) (if (leaf? tree) '() (cond ((memq msg (symbols (left-branch tree))) (cons 0 (e…

;; Huffman木 (define (make-leaf symbol weight) (list 'leaf symbol weight)) (define (leaf? object) (eq? (car object) 'leaf)) (define (symbol-leaf x) (cadr x)) (define (weight-leaf x) (caddr x)) (define (make-code-tree left right) (list left…

2.58b は解けそうになかったので解答を見てできるかぎり解説を入れてみました． 一部修正しています． 解答は↓から p2pu-sicp/2.58.scm at master · sarabander/p2pu-sicp · GitHub ;; partには'beforeか'afterが入り，symbolの位置でexpを前後に分ける． (d…

(define (lookup-tree given-key set-of-records) (cond (let ((key-record (key (car set-of-records)))) ((null? set-of-records) false) ((= given-key key-record) (car set-of-records)) ((< given-key key-record) (lookup-tree given-key (left-branc…

(define (union-tree s t) (list->tree (union-set (tree->list-2 s) (tree->list-2 t)))) (define (intersection-tree s t) (list->tree (intersection-set-local (tree->list-2 s) (tree->list-2 t))))

;a 先頭から(n-1)/2番目までをleft-treeとしてpartial-treeにかける． 残ったリストの先頭をthis-entryとしてこの木の分岐点におく． そのcdrをright-treeとしてpartial-treeにかける． これを繰り返して木を作る． 5 / \ 1 9 \ / \ 3 7 11 ;b O(n)