スライス構造をもつ octa-gridに対するグラフ文法 ソフトウェア科学研究室 下山恵一 1 目次 1. 2. 3. 4. 5. はじめに 準備 スライスと非スライス構造の識別問題 作成した文法 まとめ 2 1.1 背景 （1/2） • 表は多くの分野で情報の整理，視覚化の ツールとして利用されている • 表は矩形分割図形と捉えられる 3 1.1 背景 （2/2） • これまでに，我々は表をグラフで定式化し， グラフ文法によりそのグラフのクラスを定義 してきた – 格子状の表についてのグラフ文法 – 非スライス構造を含む任意の表についての グラフ文法 • スライス，非スライス構造を識別するための グラフ文法については未着手 4 1.2 目的 • 汎用の表の中でスライス構造のみを 生成するグラフ文法を定義 →スライスと非スライスを文法的に識別 5 2.1 edNCEグラフ文法 （1/3） • 定義2.1 Σ：ノードラベルのアルファベット Γ：エッジラベルのアルファベット Σ，Γ上のグラフ H＝（Ｖ，E，λ) Ｖ：ノードの有限集合 Ｅ：エッジの有限集合 λ：ノードのラベル付けをする関数 6 2.1 edNCEグラフ文法 （2/3） • 定義2.2 edNCEグラフ文法GG=（Σ，Δ，Γ，Ω，P，S） (edge labeled directed Neighbourhood Controlled Embedding) Σ：ノードラベルの有限集合 Δ：終端ノードラベルの集合，Δ⊆Σ Γ：エッジラベルの有限集合 Ω：最終エッジラベルの集合，Ω⊆Γ Ｐ：生成規則の集合 Ｓ：開始記号，Ｓ∈Σ－Δ 7 2.1 edNCEグラフ文法 （3/3） • 定義2.2 （続き） 生成規則 p：X→（D，C） X：非終端ノードラベル，X ∈Σ－Δ Ｄ： Σ，Γ上のグラフ Ｃ：接続関係，Ｃ⊆ Σ×Γ×Γ×ＶＤ×｛in，out｝， 接続命令の集合 8 2.2 表とグラフ （1/2） • octa-grid – 表のグラフ表現 – 表の周囲に基準となるperimeterセルを持つ – セルをノードで表し、辺の位置が等しいセルと の関係をエッジで定義 – ノードの最大次数は８ 9 2.2 表とグラフ （2/2） • 不均一な大きさのセルを持つ矩形図 （表の罫線図）の例とそれに対応する octa-grid d d c 矩形図（表の罫線図） d c octa-grid 10 2.3 表構造の文法 表構造のグラフ文法（CSedNCEGGT） （2004, 切島他） • 非スライス構造を含む任意の表構造を定義 • パーザを想定して構成 （現在、パーザを開発中 一部実装済み） • 文脈依存グラフ文法 • 生成規則数：17080 11 2.4 スライス構造 （1/2） • 矩形分割の構造 – ひとつの矩形を複数の矩形に分割する構造 – スライス構造と非スライス構造 • スライス構造 – ｢各矩形をその周囲まで届く水平/垂直線分で 分割する｣という操作を再帰的に繰り返して 得られる構造 • 非スライス構造 – 上記の操作では得られない構造 12 2.4 スライス構造 （2/2） • スライス構造，非スライス構造の例 スライス構造 非スライス構造 13 ３．スライスと非スライス構造の 識別問題 （1/5） • スライス構造 – 階層的構造 →木で表現可能 14 ３．スライスと非スライス構造の 識別問題 （2/5） 木によるスライス構造の表現 • 木の葉 – 極小な矩形に対応 • その他の点 – 子に対応する矩形を並べてできる矩形に対応 – 水平/垂直分割に対応した記号 • 上から下あるいは左から右に子に対応す る矩形を並べる 15 ３．スライスと非スライス構造の 識別問題 （3/5） • スライス構造の例とそれに対応する 前述の規則で表現される木 ↓ Ａ → Ｂ Ｄ Ｃ → ↓ Ａ Ｆ Ｄ スライス構造 Ｆ → Ｃ Ｅ Ｂ Ｅ 木による表現 16 ３．スライスと非スライス構造の 識別問題 （4/5） • スライス構造の木による表現 – 木の離れた矩形に関する情報がない →木からはスライス構造が一意に定まらない – 非スライス構造は表現できない • 表のスライス，非スライスの識別 – 各セルの辺の位置情報が必要 – スライス，非スライス構造を表現できる 枠組みが必要 17 ３．スライスと非スライス構造の 識別問題 （5/5） • これらのことから，スライス構造の文法による 定義は，octa-gridの表現に対して行う – 表の各セルの辺の位置関係を持つ →グラフと表が一意に対応 – スライス，非スライス構造の表現が可能 →非スライスとの識別につながる有効な方法 18 4.1作成した文法GSL1の概要 • • • • 文脈依存グラフ文法 生成規則数：１１２ 規則が適用できる部分は常に１箇所 表のセルを（水平/垂直）分割する操作を定義 →非スライス構造の表は導出されない 19 4.2分割操作について • 左上のセルから分割 →生成の手順を制限 • ２種類の操作を定義 – perimeterノードの南壁(東壁)の位置で分割 – 新たにperimeterノードを作り，その位置で分割 • 四隅以外の上下/左右の対応する perimeterノードにエッジを張る →片側のperimeterのみで分割位置が決定できる 20 4.2分割操作について（続き） • 左上のセルから分割 ① ① ④ ② ② ③ ⑤ 21 4.2分割操作について（続き） • perimeterノードの南壁の位置で分割 22 4.2分割操作について（続き） • 新たにperimeterノードを作り分割 23 4.3ノードラベルについて • ノードラベル（主なもの） – – – – – S : 開始ノード F : 分割操作を終了したノード A, H, V : 現在操作しているノード W : まだ操作していないノード P-* : 周辺ノードのラベル 24 4.4生成規則について • 生成規則の例１ 25 4.4生成規則について（続き） • 生成規則の例２ 26 4.4生成規則について（続き） • 生成規則の例２（接続命令） 周辺ノードのラベル（左）と接続命令（右） 27 4.4生成規則について（続き） • 導出の概要 1. 開始規則の適用 2. 内部ノードの操作 • • 分割操作（水平/垂直） 操作終了 3. ノードを終端にする 28 4.4生成規則について（続き） • 分割の方針（水平分割の場合） 1. 対象のノードを２つに分割 2. 上のノードと北壁の位置が等しい perimeterにエッジを張る 3. 下のノードと南壁の位置が等しい perimeterにエッジを張る 4. エッジを移動して分割する位置を決める 29 4.4生成規則について（続き） • 水平分割の例 30 4.4生成規則について（続き） １．対象のノードを分割 P-NW P-N P-W P-W P-N P-N P-E F P-E F P-W F P-W F P-SW P-S P-NE W A P-E P-E P-S P-S P-SE 31 4.4生成規則について（続き） １．対象のノードを分割 P-NW P-N P-W P-W P-N P-N P-E F F P-NE P-E H-0 P-W F P-W F H’-0 P-SW P-S P-S W P-E P-E P-S P-SE 32 4.4生成規則について（続き） ２．上のノードと北壁の位置が等しいperimeterにエッジを 張る P-NW P-N P-W P-W P-N P-N P-E F F P-NE P-E H-0 P-W F P-W F H’-0 P-SW P-S P-S W P-E P-E P-S P-SE 33 4.4生成規則について（続き） ２．上のノードと北壁の位置が等しいperimeterにエッジを 張る P-NW P-N P-W P-W P-N P-N P-E F F P-NE T H-2 P-W F P-W F H’-0 P-SW P-S P-S W P-E P-E P-S P-SE 34 4.4生成規則について（続き） ３．下のノードと南壁の位置が等しいperimeterにエッジを 張る P-NW P-N P-W P-W P-N P-N P-E F F P-NE T H-2 P-W F P-W F H’-0 P-SW P-S P-S W P-E P-E P-S P-SE 35 4.4生成規則について（続き） ３．下のノードと南壁の位置が等しいperimeterにエッジを 張る P-NW P-N P-W P-W P-N P-N P-E F F P-NE T H-2 P-W F P-W F H’-1 P-SW P-S P-S W P-E P-E P-S P-SE 36 4.4生成規則について（続き） ３．下のノードと南壁の位置が等しいperimeterにエッジを 張る P-NW P-N P-W P-W P-N P-N P-E F F P-NE T H-2 P-W F P-W F H’-1 P-SW P-S P-S W P-E P-E P-S P-SE 37 4.4生成規則について（続き） ３．下のノードと南壁の位置が等しいperimeterにエッジを 張る P-NW P-N P-W P-W P-N P-N P-E F F P-NE T H-2 P-W F P-W F H’-2 P-SW P-S P-S W-n P-E P-E P-S P-SE 38 4.4生成規則について（続き） ３．下のノードと南壁の位置が等しいperimeterにエッジを 張る P-NW P-N P-W P-W P-N P-N P-E F F P-NE T H-2 P-W F P-W F H’-2 P-SW P-S P-S W-n P-E P-E P-S P-SE 39 4.4生成規則について（続き） ３．下のノードと南壁の位置が等しいperimeterにエッジを 張る P-NW P-N P-W P-W P-N P-N P-E F F P-NE T H-2 P-W F P-W F H’-2 P-SW P-S P-S W P-E B P-S P-SE 40 4.4生成規則について（続き） ３．下のノードと南壁の位置が等しいperimeterにエッジを 張る P-NW P-N P-W P-W P-N P-N P-E F F P-NE T H-2 P-W F P-W F H’-2 P-SW P-S P-S W P-E B P-S P-SE 41 4.4生成規則について（続き） ３．下のノードと南壁の位置が等しいperimeterにエッジを 張る P-NW P-N P-W P-W P-N P-N P-E F F P-NE T H-2 P-W F P-W F H’-3 P-SW P-S P-S W P-E B P-S P-SE 42 4.4生成規則について（続き） ４．エッジを移動して分割する位置を決める P-NW P-N P-W P-W P-N P-N P-E F F P-NE T H-2 P-W F P-W F H’-3 P-SW P-S P-S W P-E B P-S P-SE 43 4.4生成規則について（続き） ４．エッジを移動して分割する位置を決める P-NW P-N P-W P-W P-N P-N P-E F F P-NE T H-3 P-W F P-W F H’-3 P-SW P-S P-S W P-E B P-S P-SE 44 4.4生成規則について（続き） ４．エッジを移動して分割する位置を決める P-NW P-N P-W P-W P-N P-N P-E F F P-NE T H-3 P-W F P-W F H’-3 P-SW P-S P-S W P-E B P-S P-SE 45 4.4生成規則について（続き） ４．エッジを移動して分割する位置を決める P-NW P-N P-W P-W P-N P-N P-E F F P-NE T-1 H-3 P-W F P-W F H’-3 P-SW P-S P-S W P-E B P-S P-SE 46 4.4生成規則について（続き） ４．エッジを移動して分割する位置を決める P-NW P-N P-W P-W P-N P-N P-E F F P-NE T-1 H-3 P-W F P-W F H’-3 P-SW P-S P-S W P-E B P-S P-SE 47 4.4生成規則について（続き） ４．エッジを移動して分割する位置を決める P-NW P-N P-W P-W P-N P-N P-E F F P-NE P-E H-3 P-W F P-W F H’-3 P-SW P-S P-S W T-1 B P-S P-SE 48 4.4生成規則について（続き） ４．エッジを移動して分割する位置を決める P-NW P-N P-W P-W P-N P-N P-E F F P-NE P-E H-3 P-W F P-W F H’-3 P-SW P-S P-S W T-1 B P-S P-SE 49 4.4生成規則について（続き） ４．エッジを移動して分割する位置を決める P-NW P-N P-W P-W P-N P-N P-E F F P-NE P-E H-3 P-W F P-W F H’-3 P-SW P-S P-S W T’-1 B P-S P-SE 50 4.4生成規則について（続き） ４．エッジを移動して分割する位置を決める P-NW P-N P-W P-W P-N P-N P-E F F P-NE P-E H-3 P-W F P-W F H’-3 P-SW P-S P-S W T’-1 B P-S P-SE 51 4.4生成規則について（続き） ４．エッジを移動して分割する位置を決める P-NW P-N P-W P-W P-N P-N P-E F F P-NE P-E H-3 P-W F P-W F H’-3 P-SW P-S P-S W T’-3 T’-4 P-S P-SE 52 4.4生成規則について（続き） ４．エッジを移動して分割する位置を決める P-NW P-N P-W P-W P-N P-N P-E F F P-NE P-E H-3 P-W F P-W F H’-3 P-SW P-S P-S W T’-3 T’-4 P-S P-SE 53 4.4生成規則について（続き） ４．エッジを移動して分割する位置を決める P-NW P-N P-W P-W P-N P-N P-E F F P-NE P-E H-3 P-W F P-W F H’-3 P-SW P-S P-S W T’-3 T’-5 P-S P-SE 54 4.4生成規則について（続き） ４．エッジを移動して分割する位置を決める P-NW P-N P-W P-W P-N P-N P-E F F P-NE P-E H-3 P-W F P-W F H’-3 P-SW P-S P-S W T’-3 T’-5 P-S P-SE 55 4.4生成規則について（続き） ４．エッジを移動して分割する位置を決める P-NW P-N P-W P-W P-N P-N P-E F F P-NE P-E H-3 P-W F P-W F H’-3 P-SW P-S P-S W T’-6 P-E P-S P-SE 56 4.4生成規則について（続き） ４．エッジを移動して分割する位置を決める P-NW P-N P-W P-W P-N P-N P-E F F P-NE P-E H-3 P-W F P-W F H’-3 P-SW P-S P-S W T’-6 P-E P-S P-SE 57 4.4生成規則について（続き） ４．エッジを移動して分割する位置を決める P-NW P-N P-W P-W P-N P-N P-NE P-E F P-E F H-3 P-W F P-W F H’-3 P-SW P-S P-S W T’-7 P-E P-S P-SE 58 4.4生成規則について（続き） ４．エッジを移動して分割する位置を決める P-NW P-N P-W P-W P-N P-N P-NE P-E F P-E F H-3 P-W F P-W F H’-3 P-SW P-S P-S W T’-7 P-E P-S P-SE 59 4.4生成規則について（続き） ４．エッジを移動して分割する位置を決める P-NW P-N P-W P-W P-N P-N P-NE P-E F P-E F H-4 P-W F P-W F H’-3 P-SW P-S P-S W P-E P-E P-S P-SE 60 4.4生成規則について（続き） ４．エッジを移動して分割する位置を決める P-NW P-N P-W P-W P-N P-N P-NE P-E F P-E F H-4 P-W F P-W F H’-3 P-SW P-S P-S W P-E P-E P-S P-SE 61 4.4生成規則について（続き） ４．エッジを移動して分割する位置を決める P-NW P-N P-W P-W P-N P-N P-NE P-E F P-E F H P-W F P-W F W P-SW P-S P-S W P-E P-E P-S P-SE 62 ５．まとめ（1/2） • octa-gridでスライス構造である必要十分条 件をグラフ文法で定義した （予想） 「すなわち、文法GSL1で生成される任意の グラフはocta-gridでありその矩形分割図形 はスライス構造である また、矩形分割図形がスライス構造である 任意のocta-gridはGSL1で生成できる。」 63 ５．まとめ（2/2） • 文法GSL1はあいまい性があるのでパーザ 向きではない（計算量が膨大） • 現在、あいまい性のない文法を構成中 64
© Copyright 2024 ExpyDoc
