Download presentation
Presentation is loading. Please wait.
1
表の格子グラフモデルと 編集アルゴリズム ○山澤聡3, 吉住寿洋1, 土田賢省1, 本橋友江2,夜久竹夫3
1東洋大学, 2関東学院大学, 3日本大学 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 1 1
2
目次 1. はじめに 2. 準備 3. 単一ページの表編集 4. 複数ページの表編集 5. 終わりに 数理モデル化と問題解決研究会
3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 2
3
1. はじめに 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
4
対象 表(不均一なセルを含む(矩形分割)) 単一ページの表の例 複数ページの表の例 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
表を表す手法である 複数ページの表の例 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 4
5
背景(1) 表編集における問題点 様々な表が多くの分野で情報の整理や視覚化の ツールとして利用されている.
表を扱う既存の表処理モジュールの編集操作で は,しばしばユーザが予期しない結果を招くことが ある. これは,表の基本データ構造を形式的に定義して いない,あるいは,その構造がユーザに公開されて いないこと等が一因と考えられる. 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 5
6
背景(2) 予期しない例 セル2の左側に1列挿入した時の例 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
7
背景(3) 矩形分割のセルの操作について 4分木( Bentley他, 1975 )
双対グラフ ( Kozminski & Kinne, 1985 ) 8分格子グラフ( Yaku他, 2001 ) 16分格子グラフ(Yaku他, 2005) 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 7
8
位置付け 矩形分割の編集操作の一部比較 (東壁を移動する際の計算時間) ※ n行m列の場合 モデル 計算時間 4分木 O(nm) 双対グラフ
8分格子グラフ O(n) 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 8
9
動機 表を編集する際の問題点を解決した形式的 な編集手法を格子グラフに基づいて構築す る. 数理モデル化と問題解決研究会
3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 9
10
目的 編集作業で予期しない結果を避けるために 単一ページの表の編集のためのアルゴリズ ムの提案.
複数ページの表の編集のためのアルゴリズ ムとその実装. 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 10
11
結果 8分格子グラフに基づいた表に対し,次の 表編集アルゴリズムを構築する. 16分格子グラフに基づく複数ページの表編 集の手法 セル分割
1行削除 複数行削除 16分格子グラフに基づく複数ページの表編 集の手法 データフォーマットH5CODEを提案する. 南壁移動の実装 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 11
12
2. 準備 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 12
13
2.1 矩形分割の定義 定義 矩形分割は D = ( T, P, g ),ただし T : Table (例 (下図) (2,3)-table) P : Partition (例 (下図) P = {{(2,2),(2,3)},….} g : Grid 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
14
セルの壁について 北壁 矩形分割内のセル 西壁 東壁 南壁 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 14
15
周辺セルについて 周辺セル 周辺セルは壁の厚さを持たない 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
16
2.2 8分格子グラフの定義(1/3) vd vc d c 矩形分割 D 8分格子グラフ G
2.2 8分格子グラフの定義(1/3) 定義 Gが矩形分割 D = (T, P, g)に対する8分格子グラフ ⇔(def) G = (V,E,L,λ,A,α), ただし (1) V : 1つの頂点は、1つのセルに対応している。 vd vc d c 矩形分割 D 分格子グラフ G 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
17
8分格子グラフの定義 (2/3) c d d (2) E, L, λ は、それぞれ辺、辺のラベル、辺にラベルをつける写像を表す
D = (T, P, g) vc vd E , L, λ(e) nw(c) =nw(d) sw(c) =sw(d) ew(c) =ew(d) ww(c) =ww(d) c d 北壁辺(実線) 南壁辺(点線) 東壁辺(実線) 西壁辺(点線) c d c d c d 頂点の最大次数は8 である 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
18
8分格子グラフの定義 (3/3) vc c (3) A, αは、属性集合、頂点に属性を持たす写像とする α(vc)= (0,2,0,2)
矩形分割 D 分格子グラフの頂点 A = R4 α(vc)= (nw(vc), sw(vc), ww(vc), ew(vc)) nw(vc)= 0, sw(vc) = 2, ww(vc) = 0, ew(vc) = 2 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 18
19
矩形分割と 8分格子グラフの対応例 矩形分割D Dに対応する 8分格子グラフ 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
20
2.3 8分格子グラフの データフォーマット H3-Code : 8分格子グラフを扱うためのファイル形式.
2.3 8分格子グラフの データフォーマット H3-Code : 8分格子グラフを扱うためのファイル形式. 8分格子グラフに基づいた表形式文書を表現 するために使用される. 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
21
H3-Codeの中のあるセルのフィールドの例
3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
22
3. 単一ページの表編集 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 22
23
3.1 周辺セルを数えるアルゴリズム アルゴリズムCountColumns 入力 GD: 矩形分割Dの8分格子グラフ
vx: GDの中のノード 出力 m: vxの北側の周辺セルの個数 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
24
入力例 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
25
METHOD Step 1: mに1を代入し,vmをvxの西壁辺を たどった北側の周辺セル, vaをvxの東壁辺 をたどった北側の周辺セルとする. v m v a (例) v x 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
26
Step 2: mに1を加え, vmをvm-1から北壁辺 をたどりひとつ右側のノードとする.
v a (例) v x 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
27
Step 3: vm≠vaを満たすならStep 2に戻る
(例) この例ではvm=vaなので終 了 vm- 2 vm- 1 vm, va v x 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
28
(例) グラフに対応している表 出力は3となる. m = 3 x 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
29
3.2 セルを分割するアルゴリズム このアルゴリズムで周辺セルは増減しないものとする アルゴリズムSplitCell 入力 出力
GD:矩形分割Dの8分格子グラフ vx:GDの中のノード.西壁辺と東壁辺に対応する北側の周辺セルが一 致しないもの m:vxの周辺セルの数(CountColumnsで得られたm) n(n<m):n単位分で1セル,残りを1セル,合計で2セルに分割される 出力 GE:vxの西壁と東壁の間にある北側の周辺セルをn : m-nの位置で分 割して得られたグラフ 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 29
30
(入出力例) m=3, n=2 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 30
31
METHOD Step 1: vaを北壁で東側に接続されているノード, vbを南壁で東側に接続されているノードを見つけ, vyを加える.
(例) v a v x v y v b 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 31
32
Step 2: vxに東壁辺に接続された北側ノードをvc, 南側ノードをvdとして,vxとvcの間の辺とvxとvdの間 の辺を削除し,vcとvyの間,vyとvdの間にそれぞれ 東壁辺を加える.
v a v y v b v x v d 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
33
Step 3: vxとvaの間の辺とvxとvbの間の辺を削除し, vxとvyの間に水平辺,vyとvaの間に北壁辺,vyとvb の間に南壁辺を加える.
(例) v c v a v y v x v b v d 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 33
34
Step 4: veをvxの北壁辺をたどった西側の周辺セ ルと,vfをvxの西壁辺をたどった北側の周辺セルを 見つける.
(例) v f v c v e v a v y v x v b v d 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 34
35
Step 5: jを1とし,wjを北西角のノード,viをvfから 北壁辺を使用してn-1東側に移動したノードとして, vj←viとする.
(例) wj v f vj = vi v c v e v y v x v d 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 35
36
Step 6: jに1を加え,vjを東壁辺によってvj-1にリン クされたひとつ下のノード,wjを西壁辺によってvjに リンクされた一番左のノードとする
(例) v f vj-1 = vi v j v c wj v e v y v x v d 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 36
37
Step 7: nw(wj)<nw(ve)を満たすならStep 6に戻 る.
(例) この図では条件を 満たしていないので 次に進む v f v i vj- 1 v c wj- 1 v e v y v x v j v d 3/8/2017 wj 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 37
38
Step 8: vxとvj-1の間の東壁辺を削除, vj-1とvx,vx とvjの間に東壁辺を挿入する.
(例) v f v i vj- 1 v c wj- 1 v e v y v x v j v d 3/8/2017 wj 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 38
39
Step 9: vk-1を南壁辺によってvj-1にリンクされたひ とつ右のノード,vkを西壁辺によってvk-1にリンクさ れたひとつ下のノードとする.
(例) v f v i vj- 1 vk-1, vc wj- 1 v e v y v x v j 3/8/2017 wj 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 39 vk, vd
40
Step 10: vyとvk-1の間の西壁辺を削除,vk-1とvy, vyとvkのそれぞれの間に西壁辺を挿入する.
(例) v f v c v e v y v x v d 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 40
41
出力例 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
42
3.3 1行削除するアルゴリズム アルゴリズムDeleteRow-1 入力 GD:矩形分割Dの8分格子グラフ. vx:GDの中のノード 出力
GE:vxの北壁側1行を削除して得られた8分格子グラ フ. 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
43
3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
44
METHOD Step 1: GE←GD, vxに北壁辺によってリンクされ た西側の周辺ノードをv0とする v0 (例) vx
3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 44
45
Step 2: v0から北壁辺によってリンクされた全ての 頂点にNとマークする
(例) vx 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 45
46
Step 3: v0から南壁辺によってリンクされたノードで Nとマークされた内部ノードを水平辺をリンクしなおし 削除する
(例) vm vm+1 vx 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
47
Step 3:v0から北壁辺によってリンクされたノードでN とマークされた内部ノードを水平辺をリンクしなおし 削除する
vm+1 (例) vx 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
48
Step 4: v0と北壁辺によってリンクされた内部ノード の北壁辺を直す
(例) vi+1 vi vx 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
49
Step 4: v0と北壁辺によってリンクされた内部ノード の北壁辺を直す
vk v0 (例) vi+1 xj-1 vx vi xj 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
50
Step 4: v0と北壁辺によってリンクされた内部ノード の北壁辺を直す
vi (例) vx 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
51
Step 5: v0と南壁辺によってリンクされた内部ノード の南壁辺を直す
(例) この例では南壁辺の リンクの直しは必要ない v0 vi vx 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
52
Step 6: v0とviを削除する v0 vi (例) 水平辺を削除す る vx 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
53
Step 6: v0とviを削除する v0 vi (例) 垂直辺のリンクを直 す vx 数理モデル化と問題解決研究会
3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
54
Step 6: v0とviを削除する v0 vi (例) 垂直辺のリンクを直 す vx 数理モデル化と問題解決研究会
3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
55
Step 6: v0とviを削除する (例) vx 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
56
Step 7: 1行分の高さを直す 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
57
出力例 x 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
58
3.4 複数行削除するアルゴリズム 指定したセルの高さの分だけ削除するアルゴリズム である. アルゴリズムDeleteRow 入力
GD:矩形分割Dの8分格子グラフ. vx:GDの中のノード. 出力 GE:vxの高さの分だけ削除して得られた8分格子グ ラフ. 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
59
3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
60
METHOD Step 1: vxに南壁辺によってリンクされた西側の周 辺ノードをv0とする (例) v0 vx
3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 60
61
Step 2: v0に隣接する下側のノードをvhとする
(例) v0 vx vh 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 61
62
Step 3: vxに北壁辺によってリンクされた西側の周 辺ノードをviとする
(例) v0 vx vh 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 62
63
Step 4: viに隣接する下側のノードをvi+1とする
(例) vi+1, v0 vx vh 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 63
64
Step 5: DeleteRow-1(GD, vx, GE)
(例) vi+1, v0 vx vh 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 64
65
Step 6: iに1を加える. (例) vi, v0 vx vh 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 3/8/2017
65
66
Step 7: sw(vi) < sw(vh)ならStep 4に戻る
(例) vi, v0 vx vh 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 66
67
出力例 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
68
4.複数ページの表編集 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
69
多層型矩形分割(左)と16分格子グラフの中のひとつのセルのまわりのリンク(右)の例
4.1 16分格子グラフ 多層型矩形分割を表現する方法として, 以 下の図のような16 分格子グラフ(hexadeci- grids)がある. 多層型矩形分割(左)と16分格子グラフの中のひとつのセルのまわりのリンク(右)の例 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
70
8分格子グラフの各セルの角に上下の層へ のリンクを持たせている.
多層型地形図の16 分格子グラフモデルを応 用して,複数ページの表を16 分格子グラフで 表現する. 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
71
4.2 データフォーマット H5CODE : H3-Codeを一般化した16 分格子 グラフのデータフォーマット.
4.2 データフォーマット H5CODE : H3-Codeを一般化した16 分格子 グラフのデータフォーマット. 不均一型矩形分割コード(H8CODE)を変形 したファイル形式である. 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
72
矩形分割のデータフォーマット H3CODE(有田・夜久) H7CODE(2007)(赤木・有田・本橋・野牧・土田・夜久)
Web掲載 H8CODE1.1(野牧・夜久)JSIAM05で発表 H8CODE1.2(呉羽・夜久)LA講究録08で発表・引用 H8CODE1.3(野牧・夜久) 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
73
目的 複数枚の矩形グラフ(不均一型表)の表現 XMLへの変換を前提 対象 複数枚の不均一型表 演算(例) 表示 行・列の挿入・削除
壁の移動 等 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
74
各レコードのフィールド (1)ヘッダー部 (2)リスト部 (3)コンテンツ部 (4)表レイヤー部 H5CODEに対応するリストの概念図
3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
75
H5CODE ヘッダー部 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
76
H5CODE リスト部 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
77
3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
78
3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
79
H5CODE コンテンツ部 コンテンツ部はセルに付随する 文字列,画像などの情報やコンテンツのリンク情 報を格納する
予備を含む8つのフィールドからなる 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
80
3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
81
H5CODE レイヤー部 複数の矩形分割を管理するためのブロック 複数の矩形分割に対応するために使用され る
表レイヤー部のフィールドの数は8 H5CODEは複数枚の表に対応しているた め,レイヤー部は使用しない 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
82
H5CODEの中の一つのレコードのフィールド
3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
83
4.3 アルゴリズム アルゴリズムはH5CODEの上で実装される. 説明は16分格子グラフの上で行う. 数理モデル化と問題解決研究会
4.3 アルゴリズム アルゴリズムはH5CODEの上で実装される. 説明は16分格子グラフの上で行う. 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
84
アルゴリズム MoveSouthWallInLayer(GD,v,δ,GE)
層の南壁移動のアルゴリズム アルゴリズム MoveSouthWallInLayer(GD,v,δ,GE) 入力 GD: 矩形分割Dのための16分格子グラフD vc: GDの中のノード δ≧0: 動き値 Δ> 0はcの南寄りに隣接する行の中の周辺セルの高さで あるのに対し,Δ>δとする. 出力 GE: Dから南壁移動で得られた16分格子グラフ. 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
85
入力 出力 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
86
Step 1: vcの西側の南壁辺でリンクされた周 辺ノードvaを見つける.
3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
87
Step 2: sw(va)←sw(va)+δとする.vaに南壁 辺によってリンクされたノードをvbとする.
vc va 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
88
Step 3: sw(vb)←sw(vb)+δ,vbを南壁辺でvb にリンクされた東側ノードに変更する.
vc va vb 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
89
Step 4: vbが内部ノードならstep 3に戻る.
vc va vb 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
90
Step 5: sw(vb)←sw(vb)+δ,vcから周辺ノー ドvaまで移動
3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
91
Step 6: vdをvaに西壁辺で南側にリンクされ たノードとする.
vc va vd 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
92
Step 7: nw(vd)←nw(vd)+δ,vdを北壁辺で vdにリンクされた東側ノードに変更する
vc va vd 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
93
Step 8: vdが内部セルならstep 7に戻る.
vc va vd 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
94
Step 9: nw(vd)←nw(vd)+δ
vc va vd 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
95
Step 10: 各層で同様の操作を行う. 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
96
5 終わりに 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
97
8分格子グラフに基づいた表に対し,次の表 編集アルゴリズムを構築した.
結果 8分格子グラフに基づいた表に対し,次の表 編集アルゴリズムを構築した. セル分割 1行削除 複数行削除 16分格子グラフに基づく複数ページの表編集 の手法 データフォーマットH5CODEを提案した. 南壁移動の実装 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
98
複数ページの表に対応した他の編集操作を 提案する
今後の課題 複数ページの表に対応した他の編集操作を 提案する 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構
99
END 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 99
Similar presentations
© 2024 slidesplayer.net Inc.
All rights reserved.