『2.3 記号データ』
まとめ
これまではデータを数値の集合としか扱ってこなかったけれど、「データ」として任意の記号に対して作業できる能力を説明している。ここでいう「データ」とは何か、というと、
- リストや記号を表記する式。
- （定義段階では）評価されない式
とのこと。文字列は二重引用符で括られた部位のことをいうので、ちょっと違うらしい。
各小節の内容
2.3.1 クォート
新しい「クォート」という要素が導入される。といっても使い方は簡単で、記号そのものを取り扱いたい式の先頭に「'」を付けるだけ。ちなみにquoteを使うこともできて、「'X」と「(quote X)」は同じ意味になる。
(define a 1) (define b 2) (List 'a b) → (a 2)
簡単に言えば、与えたリストや記号を評価される式としてではなく「意味」もしくは「データ」として表現する、ということ。うぅん、便利だ。
実際はリストを作るにも簡単だったので、従来でも使っていたけれどね。
実際はリストを作るにも簡単だったので、従来でも使っていたけれどね。
あと、ここでは「'()」の定義によって「nil(Gaucheでは())」と同じ意味のものが構成できるようなることも注目。
抽象データによる微分プログラム
以下の手続きが実際に存在すると仮定すれば（これから作るわけだけど）、微分規則を表すことが出来るようになる。
| 式 | 意味 |
| (variable? e) | eは変数か？ |
| (same-variable? v1 v2) | v1とv2は同じ変数か |
| (sum? e) | eは和/加算式（＋）か |
| (addend e) | eの加数 |
| (augend e) | eの被加数 |
| (make-sum a1 a2) | a1とa2の和を構成（計算ではない） |
| (product? e) | eは積/積算式（*）か |
| (multiplier e) | eの乗数 |
| (multiplicand e) | eの被乗数 |
| (make-product m1 m2) | m1とm2の積を構成 |
ここで学ぶ上式のポイントは、手続きの中のデータが全て抽象データとであることを前提として設計されていること。つまり、選択子＆構成子の設計さえすれば、微分アルゴリズムの表現とは分離できるということに他ならない。
というわけで、本節ではその手続き１つ１つを構築していくわけだ。
というわけで、本節ではその手続き１つ１つを構築していくわけだ。
代数式の表現
ここではLisp(Scheme)の表現記法である前置記法を用いて表現する。上表の各手続きはそのままテキストに載っているが、それだけだと式をバカ正直に微分して、値の省略をいっさい行わない（(+ a 0)をそのまま表示したり）。
そこで、代数式の表現の中で、省略表記が行える部位で変更を加えていくことになる。
ここで、問題2.57を解くために少し復習。手続きにおいて任意個の引数をとるにはどうしたらよいかという話。
任意個の引数を取りたい場合、defineで「ドット末尾記法(dotted-tail notation)」を使うこと。たとえば（本の受け売りだけど）
(define (f x y . z) <body>)
とすれば、第1引数はxに、第2引数はyに、残りはzにリストとして格納される。(f 1 2 3 4 5 6)ならば、
- x
- 1
- y
- 2
- z
- (3 4 5 6)
となる。これをふまえて、問題を解いてみよう。
2.3.3 例:集合の表現
ここでは様々な形式の「集合」というものを考えて、その表現と効率について学ぶ。
まず集合とは、
まず集合とは、
- 相異なるオブジェクトの集まり
であり、
- 集合に対する演算を定義することが「集合」を定義することになる
とのこと。
何だか禅問答のようだけれど、本書では演算の定義イコール集合の形式を作り出すこと、という意味で使っている。ある形式を持ったデータが先にあるのではなく、集合の演算によってデータが（演算に沿った形式の）集合に形作られていくわけだ。
何だか禅問答のようだけれど、本書では演算の定義イコール集合の形式を作り出すこと、という意味で使っている。ある形式を持ったデータが先にあるのではなく、集合の演算によってデータが（演算に沿った形式の）集合に形作られていくわけだ。
この演算はインタフェースであって、抽象化の対象になる。中でどのような実装をしているかに関わらず、とりあえず「集合」にはなっていく。気に入らなければ、演算が形作る集合の形式を変えさえすれば、同じインタフェースでデータはより良い形式で集合になっていくよ。という話。
ただしここでは話を簡単にするために、予め定めようとする演算に従った集合があることを仮定している。それに対して
- union-set （２つの集合の和集合を返す）
- intersection-set （２つの集合の積集合を返す）
- element-of-set? （与えられた要素が集合に含まれているか）
- adjoin-set （元の集合の要素と、追加する要素を含む集合を返す）
というデータ操作を定義している。操作に適した集合を作成するのは、この節の後半に入ってからだ。
あと、本書ではそこからさらに各形式の効率についても言及している。Θ(...)、そう、ビッグオーノーテーション。大学時代に習った概念だ。なつかしいなぁ。今でも意識しているけどさ。
順序づけられないリストとしての集合
まずは一番簡単な、重複の無い、順序も決まっていない要素のリストを扱う。
それぞれの効率を見ると、
それぞれの効率を見ると、
| element-of-set? | Θ(n) |
| adjoin-set | Θ(n) |
| intersection-set | Θ(n^2) |
| union-set | Θ(n^2) |
となっていて、あんまり効率が良くないことが分かる。ただ、問題2.60で重複を許す集合の場合も考えると、
| element-of-set? | Θ(n) |
| adjoin-set | Θ(1) |
| intersection-set | Θ(n^2) |
| union-set | Θ(1) |
というように計算によっては相当の高速化を図れるようになってくるから面白い。
とはいえ、n^2オーダーの処理が1個でもあるとボトルネックは確実だからあまり良い解決策とは言えないなあ。
順序づけられたリストとしての集合
続いて集合が順序付けられている場合。この場合はn^2が無くなり、
| element-of-set? | Θ(n/2) |
| adjoin-set | Θ(n/2) |
| intersection-set | Θ(n) |
| union-set | Θ(n) |
で済む。
こうした処理の場合、どうしても一番遅い処理に足を引っ張られるので、n^2が消えたというのは問題2.60に比べても効果は目覚ましいといえる。
二進木としての集合
さて、バイナリツリー。これは木を辿るごとに対象となる集合が小さくなるので全く効率が良くなってくる。
| element-of-set? | Θ(log n) |
| adjoin-set | Θ(log n) |
| intersection-set | Θ(n) |
| union-set | Θ(n) |
ここから色々なデータ構造でよく使われているB木やAVL木、B+木などに派生していくわけで、つまりツリーを理解することは重要なんだな、と再認識。
集合と情報検索
この節で言いたいことは、ズバリ
- データを構成する際に抽象的/階層的な選択子・構成子を用意しておくことで
- 最初はプロトタイプ(順序の無い単なるリスト)でさっと作ってしまい、後から精密かつ高速なデータ構造(たとえば二進木)に変更することが容易になる
ということ。
ただ、この前提はあくまでデータベースをいつでも再構築できる環境でのみ有効であることに注意しないと行けない。どこかのページで言ったことを繰り返すけれど、データ構造の変更はデータそのものに対する変更を伴わなければならないケースが多いので、作業の手戻りが甚大になってしまいかねないからね。
2.3.4 例：Huffman符号化木
データ圧縮で「超」有名なHuffman符号化木を実装してみましょう、という節。
ここでは細かい説明は他に譲るとして、「BACADAEAFABBAAAGAH」という文字列を「最良」符号化するときの木の作成手順について、資料から転載する（勉強のためだから）。
ここでは細かい説明は他に譲るとして、「BACADAEAFABBAAAGAH」という文字列を「最良」符号化するときの木の作成手順について、資料から転載する（勉強のためだから）。
最小頻度の記号を木のルートから最も遠くに置くという発想から、
- 初期データを、記号と頻度からなる葉の節の集合を作成
- {(A 8) (B 3) (C 1) (D 1) (E 1) (F 1) (G 1) (H 1)}
- 最小の重み（頻度）を持つ２つの葉を見つけ、合体させてこの節を左右に持つ節を作り、集合からもとの2つの節を除去する
- {(A 8) (B 3) ({C D} 2) (E 1) (F 1) (G 1) (H 1)}
- この「最小重みの節を合体した節で、元の2つの節と取り替える」を全体が1つの節になるまで繰り返す
- {(A 8) (B 3) ({C D} 2) ({E F} 2) (G 1) (H 1)}
- {(A 8) (B 3) ({C D} 2) ({E F} 2) ({G H} 2)}
- {(A 8) (B 3) ({C D} 2) ({E F G H} 4)}
- {(A 8) ({B C D} 5) ({E F G H} 4)}
- {(A 8) ({B C D E F G H} 9)}
- {(A B C D E F G H} 17)} ← 終了
という流れで木を作成する。注意点は、「このアルゴリズムは同じ文字列でも生成される木が異なる可能性がある」ということ。最小重みの節を選ぶときに、毎回同じ節が選ばれない可能性もあるし、合体させるときに木の左右どちらに配置するか、ということもあるためだ。
