問題 n 記号のアルファベットの Huffman 木があるとし、記号の相対頻度が、 としよう。 n = 5, n = 10 の木を描け。 （一般の n の）こういう木で、最高頻度の記号を符号化するのに必要なビット数はいくらか。 最低頻度の記号ではどうか。 解答 まずは入力さ…

問題2.70 次の８記号のアルファベットと相対頻度は、1950年代ロックの歌の叙情詩を効率よく符号化するよう設計された。（「アルファベット」の「記号」は必ずしも個々の文字ではないことに注意） A2 BOOM1 GET2 JOB2 NA16 SHA3 YIP9 WAH1 （問題 2.69の）gen…

毎年恒例の友人主催のクルージングにうちの奥さんが行けなかったので、二人だけで大瀬崎にシュノーケリングに行った。 つっても行ったのは昨日の2010/08/28。 備忘録 海岸線の道路で大瀬崎の看板が見えたら海の方へ降りていくんだが、途中で右折する箇所があ…

あまりの暑さに夫婦共々ちゃんと睡眠がとれていない。 これはマズイということで、二人で整体に行く車の中で対策を練る。 エアコン買うか、ジェルマット買うかという２本に絞られたが、 とにかく背中が暑いんじゃヴォケ！ という理由で、ジェルマットの購入…

問題 次の手続きは引数として記号と頻度の対のリストをとり、（どの記号も一つの対以外には現れない。）Huffmanアルゴリズムに従い、Huffman木を生成する。 (define (generate-huffman-tree pairs) (successive-merge (make-leaf-set pairs))) make-leaf-set…

なんでうまくいかねーのかさっぱりわからねぇ。。 （※2010/08/24追記：アホだった。。エラー情報をよく見れ！！） 問題 encode 手続は引数として通信文と木をとり、符号化された通信文のビットのリストを作る。 (define (encode message tree) (if (null? me…

お〜っし、久々の問題ゾーンです。 問題 符号化木と例題の通信文を定義する。 (define sample-tree (make-code-tree (make-leaf 'A 4) (make-code-tree (make-leaf 'B 2) (make-code-tree (make-leaf 'D 1) (make-leaf 'C 1))))) (define sample-message '(0…

う〜ん、このセクション何を言いたいのかいまいち確信が持てない。。 とりあえずコードを写経してコメントを付加していってみよう。 (define (adjoin-set x set) (cond (;母体となるリストが空なら新規生成する。 (null? set) (list x)) (;「挿入したい枝の…

昨日は会社のキックオフ会で帰宅が遅くなってしまったのでアップできなんだ。。では前エントリを元に、「語頭符号」のコードをどうやって「復号化」するかを考えていこう。 (define (decode bits tree) (define (decode-1 bits current-branch) (if (null? b…

次はそのHuffman木の表現だ。Haffman木は２種類のオブジェクトで構成されている。 葉「記号」と「重み」を持つ、枝の終端に相当するオブジェクト 枝「葉」または「枝」がぶら下がるようにして構成されるオブジェクト。 自分にぶら下がっている「記号」の集合…

前エントリで作成した Haffman 木、及び各記号（アルファベット）に割り当てる符号についてだけど、これは一体どうやって作るのか。本セクションでは割り当てる符号の最適性は割愛されているが、Haffman 木の構成方法についてはまとめられていたので俺もまと…

可変長の符号化体系をどう処理するかというお話。通信リソースが貴重だった昔は重要だったかもしれんが、インフラ的に恵まれた環境になってきた事と、標準が重視されている現代ではあんまり役にたたなさそうな話題。それとも他に応用できる場面があるんだろ…

会社でやった健康診断の結果が毎年順調に悪くなってるもんで、ちょっと老後が心配になってきた。 ここらで体にムチを入れないとマズイと思ったんで、夜ジョギングを始めてみた。 無理の無いペースなら夜風が結構気持ちいいという新鮮な発見が。（まぁホント…

問題 レコードの集合がキーの数値で順序づけられている二進木で構造化されている場合の lookup 手続きを実装せよ。 解答 今までやってきた順序づけられた二進木の検索だから、キーの値を比較する時に 等しい → そのレコードを返却 小さい → 左側の二進木で再…

前セクションまでで、様々な方式での集合の表現を見てきたが、なんでこんなことをしてきたかというと、「効率」というものを意識させるため。 で、もう一つ重要な事があって、それはここまでで学んできた各種手法が「情報検索」に関する応用に非常に重要な意…

問題 問題 2.63 と問題 2.64 の結果を使い、（釣り合った）二進木として実装されている集合の union-set と intersection-set を Θ(n) で実装せよ。 解答 ２つの集合（二進木）を、一度順序付けられたリストに変換して、その状態で和集合あるいは積集合を求…

問題 次の手続 list->tree は順序づけられたリストを釣り合っている二進木へ変換する。 補助手続 partial-tree は引数として、整数 n と少なくとも n 個の要素をとり、リストの最初の n 個の要素を含む、釣り合っている木を構成する。 partial-tree が返す結…

SICP解いてて、たまに数式を書かなきゃならない時があるんだが、特に何も疑問に思わずそれっぽく見えればいいや的な感じでゴリゴリ書いてた。 で、ふと「それこそTexみたいな綺麗な数式を出力できるサービスがあるんじゃね？と思って調べてみたらあった。 以…

問題 下の二つの手続はそれぞれ二進木をリストに変換する。 (define (tree->list-1 tree) (if (null? tree) '() (append (tree->list-1 (left-branch tree)) (cons (entry tree) (tree->list-1 (right-branch tree)))))) (define (tree->list-2 tree) (defin…

今度は「木」構造のデータを考える。このデータ構造は、前セクションでやった「順序づけられたリスト」よりももっとご利益があるらしい。構造のイメージとしてはこんな感じ。 ┌────── tree ──────┐ │ entry │ │ ┌────┴────┐ │ │left(tree) right(tree)│ └───…

問題 順序づけられたリストによる集合表現の union-set を、Θ(n) で実装せよ。 解答 intersection-set と同じ感じでやってみよう。 (define (union-set set1 set2) (cond ((null? set1) set2) ((null? set2) set1) (else (let ((x1 (car set1)) (x2 (car set…

問題 順序づけられた表現を使った adjoin-set の実装を示せ。 element-of-set? の類推で、順序付けられない表現に比べ、約半分のステップ数を必要とする手続を作るのに、順序の利点をどう用いるか示せ。 解答 element-of-set? の類推でいいんだからこんな感…

このセクションでは集合演算を加速（効率化？）するための内容が記載されている。 概略としては、要素をなんらかの規則（シンボルなら辞書順、あるいは要素に数値を付加するなりしてその大きさ順等）整列させて考えてみようという話。ここでは話を簡単にする…

問題 集合を重複のないリストで表現しようとしてきた。重複が許されるとしよう。例えば集合 {1, 2, 3} はリスト (2 3 2 1 3 2 2) で表現されるかもしれない。 この表現を操作する手続き、 element-of-set?、adjoin-set、union-set、及び intersection-set を…

問題 集合の順序づけられないリスト表現で union-set 演算を実装せよ。 解答 性能はさておき。set1とset2をひとつのリストにまとめて考えた方がわかりやすいのでそうしちゃう。 まとめたリストを src、解答となる和集合を ans とすると、こんな感じ。 (defin…

さて、ここから先は集合の話になるぞと。 ざーっと読んでみたら結構なボリュームがあるし、内容的にもヘビーな感じを受ける。 なので、ペインタの二の舞にならんよう、セクションの内容をきっちり追っていきたいと思う。 最初は、「順序なし」「重複なし」の…

問題 微分プログラムを修正し、前置演算子ではなく + や * が中置きになっている通常の数学の式に動作させたいと思う。微分のプログラムは抽象データを使って定義してあるので、微分プログラムが操作する代数式の表現を定義する述語、選択子、構成子だけを変…