データのモデル
モデル化
情報に限らず何かを扱うにはモデル化が必要である。そこでまずモデル化について説明する。
- モデル: 単純化/抽象化された事物/事象/概念
- モデル化: 実際の事物/事象のモデルを作ること
以下の"モデル"では、対象の何が取り出され、何が捨てられているか？
- プラモデル
- ファッションモデル
- モデル住宅
- モデル事業
情報のモデル化の例
- 表
- 図
- グラフ: 「何か」と何かの「接続関係」を抽象化したもの。折れ線グラフのようなグラフとは(一応)違うもの。
- 階層構造: 分岐の関係。
これまでにビットを組合わせることで、
文字,
数,
画像などを表現した。
文字を利用してウェブとクライアント/サーバに出てきたHTMLのような表現を考えた。
表現とは別に情報を抽象化とものとしてデータモデルがある。
- データモデル: データの抽象的な見方。ビットよりもハイレベル。多くのプログラムで扱うデータに共通するもの。
ネットワークモデル
- ネットワークモデル: つながり方に関するモデル
- グラフ: ノードとエッジからなるデータ。ネットワークモデルの一種
- ノード: エッジでつなげられるもの
- エッジ: ノードをつないでいるもの。向きがあるものとないものがある。
ネットワークモデルで表されるもの
- ケーニヒスベルクの橋(抽象化,抽象化)
表現: 陸地=ノード, 橋=エッジ
問題: すべてのエッジを重複なく辿る。(オイラー路)
- ウェブ(抽象化)
表現: ウェブページ=ノード, リンク=エッジ
問題: 「重要なページ(ノード)からリンクされている(エッジがある)ページ(ノード)は重要である。」というような規則から、ページ(ノード)のスコアを計算。
(Google/PageRank)
問題: ウェブ全体の構造を知りたい。(Bow Tie)
-
有限オートマトン [教科書6.2.1(a)]
表現: 状態=ノード, 遷移=エッジ
問題: 入力に従ってエッジを辿る。
問題: オオカミと羊とキャベツと人間がボートで川を渡ろうとしている。
ボートは人間がこぐ必要があり、また、人間以外にはどれか一つ／一匹しか乗せられないものとする。
人間がいなくなってもオオカミや羊が逃げたりはしないが、オオカミは羊を食べ、羊はキャベツを食べてしまう。
全員(キャベツも含めて)が無事川を渡るにはどのように渡れば良いか？
(状態の関係)
- 路線図
表現: 駅=ノード, 線路=エッジ
問題: ある駅(ノード)から電車にのって(エッジを辿り)別の駅(ノード)に行くためのできるだけ短い路を求める。(最短路問題)
(ekitan)
- 世界一周ゲーム, セールスマン問題
表現: 都市=ノード, 移動=エッジ
問題: 全てのノードを重複なく辿る。(ハミルトン路)
問題: 全てのノードを重複なく辿る一番短い路を探す。(巡回セールスマン問題)
- 実体関連モデル
表現: 実体,属性=ノード, 関連=エッジ
問題: 関係モデルでの表現を生成する。
- 意味ネットワーク,
Concept Map
(Peak Oil)
表現: 概念=ノード, 関係=エッジ
問題: 概念の類似度を求める。
階層モデル
[教科書4.3.3]
- 階層モデル: 1層目、2層目、3層目のように層分けになっているモデル
- 木構造: 根以外のノードは親ノードを1つ(だけ)持ち、どのノードも親を辿ると根に至る構造
- 根: 木構造のノードの一つで、どのノードも親を辿るとこのノードに至るようなノード。このノードだけは親を持たない。
- 生物の分類階層
表現: カテゴリー=ノード、属すという関係=親子
- 階層的ファイルシステム
表現: フォルダ, ファイル=ノード、含む関係=親子
- 住所
表現: 地名=ノード、含む関係=親子
- 図書の分類
表現: 分類項目=ノード、項目の大小=親子
- 式の構造
表現: 演算子, 数値=ノード、演算子と被演算子の関係=親子
- ゲーム探索木
表現: 譜面=ノード、譜面と一手後の譜面=親子
- 決定木
表現: 条件の指定=ノード、場合分けの関係=親子
- DNS [教科書3.4.7]
表現: ドメイン名=ノード、ドメインとサブドメインの関係=親子
- mind map
表現: 概念=ノード、概念とその概念から想起される概念の関係=親子
- argument map
表現: 主張=ノード、支持、反対などの主張の間の関係=親子
以下のものはネットワークモデルでモデル化するのが適当か？それとも階層モデル(木構造)でモデル化するのが適当か？
ノードとエッジまたは親子関係を示せ。
- 友人関係
- 会社の組織
- 文書の改訂における、版の間の関係
yamaguch@mail.ecc.u-tokyo.ac.jp Copyright 2011 Kazunori Yamaguchi 山口和紀@東京大学総合文化研究科
