輪講：アルゴルズムデザイン（第3回）

月曜の輪講のメモです。前回まではこちら↓
輪講：アルゴリズムデザイン（第2回）
輪講：アルゴリズムデザイン（第1回）

今回は、前回の最小全域木の実装、クラスタリング、Huffman符号です。(〜4章)

PrimとKruskanのアルゴリズムの実装（最小全域木問題）

頂点数がn個、辺の本数がm本のグラフを入力とした場合、どちらのアルゴリズムも、O(mlog(n))で実装可能です。ただし、そのためにはUnion-Findデータ構造というものを使用します。

Union-Findデータ構造

一つのノード集合を木構造で表します。ノード v が属している木の根が u の場合、ノード v が属する集合は u とする構造です。
ノード v が属しているグループを求めるためには O(log n) かかります。
利点は集合の併合が簡単にできることです。例えば、根がノード u の集合と根が w の集合を併合する場合には、u を w の子ノードとすれば併合できます。

クラスタリング

単連結法の紹介と最小全域木との関連をやりました。
最小全域木から最も辺の重さが大きい辺(k-1)本削除すると、k個のクラスタ（ノード集合）に分類できます。これは、単連結法のクラスタリングと等価です。

Huffman符号

文字列を0と1のビット列で符号化します。その際、全文章を表す01の文字列の長さが最小となるようにします。また、曖昧性が無いように、どの文字を表すビット列も他のビット列の接頭語にならないようにします。
そのためには二分木をT作成し、葉に文字をラベル付けします。葉に行き着くまでに左の辺を通ったら0、右を通ったら1で符号化します。
全文章を表す文字列の長さが最小となるためには、出現頻度が高い文字に対して短いビット列を与えます。この方法で木Tを作成すると、木の深さが浅い（根から近い）葉に出現頻度の高い文字が、深いところには出現頻度の低い文字がくるように接頭語の木Tを求めればいいことになります。そのために、最も出現頻度が低い文字から葉を割り当てていく、ボトムアップで木を作成します。