表の格子グラフモデルと 編集アルゴリズム ○山澤聡3, 吉住寿洋1, 土田賢省1, 本橋友江2,夜久竹夫3 1東洋大学, 2関東学院大学, 3日本大学 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 1 1

目次 1. はじめに 2. 準備 3. 単一ページの表編集 4. 複数ページの表編集 5. 終わりに 数理モデル化と問題解決研究会 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 2

1. はじめに 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

対象 表(不均一なセルを含む(矩形分割)) 単一ページの表の例 複数ページの表の例 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 表を表す手法である 複数ページの表の例 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 4

背景(1) 表編集における問題点 様々な表が多くの分野で情報の整理や視覚化の ツールとして利用されている． 表を扱う既存の表処理モジュールの編集操作で は，しばしばユーザが予期しない結果を招くことが ある． これは，表の基本データ構造を形式的に定義して いない，あるいは，その構造がユーザに公開されて いないこと等が一因と考えられる． 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 5

背景(2) 予期しない例 セル２の左側に1列挿入した時の例 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

背景(3) 矩形分割のセルの操作について 4分木( Bentley他, 1975 ) 双対グラフ ( Kozminski & Kinne, 1985 ) 8分格子グラフ( Yaku他, 2001 ) 16分格子グラフ(Yaku他, 2005) 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 7

位置付け 矩形分割の編集操作の一部比較 (東壁を移動する際の計算時間) ※ n行m列の場合 モデル 計算時間 4分木 O(nm) 双対グラフ 8分格子グラフ O(n) 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 8

動機 表を編集する際の問題点を解決した形式的 な編集手法を格子グラフに基づいて構築す る． 数理モデル化と問題解決研究会 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 9

目的 編集作業で予期しない結果を避けるために 単一ページの表の編集のためのアルゴリズ ムの提案． 複数ページの表の編集のためのアルゴリズ ムとその実装． 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 10

結果 8分格子グラフに基づいた表に対し，次の 表編集アルゴリズムを構築する． 16分格子グラフに基づく複数ページの表編 集の手法 セル分割 1行削除 複数行削除 16分格子グラフに基づく複数ページの表編 集の手法 データフォーマットH5CODEを提案する． 南壁移動の実装 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 11

2. 準備 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 12

2.1　矩形分割の定義 定義　矩形分割は D = ( T, P, g ),ただし T : Table （例 (下図)　(2,3)-table) P : Partition （例 (下図)　P = {{(2,2),(2,3)},….} g : Grid 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

セルの壁について 北壁 矩形分割内のセル 西壁 東壁 南壁 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 14

周辺セルについて 周辺セル 周辺セルは壁の厚さを持たない 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

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つの頂点は、１つのセルに対応している。 vd vc d c 矩形分割 D 8分格子グラフ G 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

8分格子グラフの定義 (2/3) c d d (2) E, L, λ は、それぞれ辺、辺のラベル、辺にラベルをつける写像を表す 　　　 D = (T, P, g) 　　　　　vｃ　 　　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 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

8分格子グラフの定義 (3/3) vc c (3) A, αは、属性集合、頂点に属性を持たす写像とする α(vc)= (0,2,0,2) 矩形分割 D 8分格子グラフの頂点 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

矩形分割と 8分格子グラフの対応例 矩形分割D Dに対応する 8分格子グラフ 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

2.3 8分格子グラフの データフォーマット H3-Code ： 8分格子グラフを扱うためのファイル形式. 2.3　8分格子グラフの 　　　データフォーマット H3-Code ： 8分格子グラフを扱うためのファイル形式. 8分格子グラフに基づいた表形式文書を表現 するために使用される． 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

H3-Codeの中のあるセルのフィールドの例 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

3. 単一ページの表編集 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 22

3.1 周辺セルを数えるアルゴリズム アルゴリズムCountColumns 入力 GD: 矩形分割Dの8分格子グラフ vｘ： GDの中のノード 出力 m: vｘの北側の周辺セルの個数 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

入力例 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

METHOD Step 1: mに1を代入し，vmをvxの西壁辺を たどった北側の周辺セル， vaをvxの東壁辺 をたどった北側の周辺セルとする． v m v a （例） v x 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

Step 2: mに1を加え， vmをvm-1から北壁辺 をたどりひとつ右側のノードとする． v a （例） v x 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

Step 3: vm≠vaを満たすならStep 2に戻る （例） この例ではvm=vaなので終 了 vm- 2 vm- 1 vm, va v x 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

(例) グラフに対応している表 出力は3となる． m = 3 x 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

3.2 セルを分割するアルゴリズム このアルゴリズムで周辺セルは増減しないものとする アルゴリズムSplitCell 入力 出力 GD:矩形分割Dの8分格子グラフ vｘ：GDの中のノード．西壁辺と東壁辺に対応する北側の周辺セルが一 致しないもの m:vxの周辺セルの数(CountColumnsで得られたm) n(n<m):ｎ単位分で1セル,残りを1セル,合計で2セルに分割される 出力 GE：vxの西壁と東壁の間にある北側の周辺セルをn : m-nの位置で分 割して得られたグラフ 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 29

（入出力例） m=3, n=2 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 30

METHOD Step 1: vaを北壁で東側に接続されているノード， vbを南壁で東側に接続されているノードを見つけ， vyを加える． （例） v a v x v y v b 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 31

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 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

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

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

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

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

Step 7: nw(wj)＜nw(ve)を満たすならStep ６に戻 る． （例） この図では条件を 満たしていないので 次に進む 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

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

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

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

出力例 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

3.3 1行削除するアルゴリズム アルゴリズムDeleteRow-1 入力 GD:矩形分割Dの8分格子グラフ． vｘ：GDの中のノード 出力 GE：vxの北壁側1行を削除して得られた8分格子グラ フ． 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

METHOD Step 1: GE←GD, vxに北壁辺によってリンクされ た西側の周辺ノードをv0とする v0 （例） vx 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 44

Step 2: v0から北壁辺によってリンクされた全ての 頂点にNとマークする （例） vx 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 45

Step 3: v0から南壁辺によってリンクされたノードで Nとマークされた内部ノードを水平辺をリンクしなおし 削除する （例） vm vm+1 vx 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

Step 3:v0から北壁辺によってリンクされたノードでN とマークされた内部ノードを水平辺をリンクしなおし 削除する vm+1 （例） vx 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

Step 4: v0と北壁辺によってリンクされた内部ノード の北壁辺を直す （例） vi+1 vi vx 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

Step 4: v0と北壁辺によってリンクされた内部ノード の北壁辺を直す vk v0 （例） vi+1 xj-1 vx vi xj 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

Step 4: v0と北壁辺によってリンクされた内部ノード の北壁辺を直す vi （例） vx 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

Step 5: v0と南壁辺によってリンクされた内部ノード の南壁辺を直す （例） この例では南壁辺の リンクの直しは必要ない v0 vi vx 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

Step 6: v0とviを削除する v0 vi （例） 水平辺を削除す る vx 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

Step 6: v0とviを削除する v0 vi （例） 垂直辺のリンクを直 す vx 数理モデル化と問題解決研究会 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

Step 6: v0とviを削除する v0 vi （例） 垂直辺のリンクを直 す vx 数理モデル化と問題解決研究会 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

Step 6: v0とviを削除する （例） vx 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

Step 7: 1行分の高さを直す 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

出力例 x 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

3.4 複数行削除するアルゴリズム 指定したセルの高さの分だけ削除するアルゴリズム である． アルゴリズムDeleteRow 入力 GD:矩形分割Dの8分格子グラフ． vｘ：GDの中のノード． 出力 GE：vxの高さの分だけ削除して得られた8分格子グ ラフ． 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

METHOD Step 1: ｖxに南壁辺によってリンクされた西側の周 辺ノードをv0とする （例） v0 vx 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 60

Step 2: v0に隣接する下側のノードをvhとする （例） v0 vx vｈ 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 61

Step 3: vｘに北壁辺によってリンクされた西側の周 辺ノードをviとする （例） v0 vx vｈ 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 62

Step 4: viに隣接する下側のノードをvi+1とする （例） vi+1， v0 vx vｈ 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 63

Step 5: DeleteRow-1(GD, vx, GE) （例） vi+1， v0 vx vｈ 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 64

Step 6: iに1を加える． （例） vi, v0 vx vｈ 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 3/8/2017 65

Step 7: sw(vi) < sw(vh)ならStep 4に戻る （例） vi， v0 vx vｈ 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 66

出力例 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

4.複数ページの表編集 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

多層型矩形分割(左)と16分格子グラフの中のひとつのセルのまわりのリンク(右)の例 4.1　16分格子グラフ 多層型矩形分割を表現する方法として， 以 下の図のような16 分格子グラフ(hexadeci- grids)がある． 多層型矩形分割(左)と16分格子グラフの中のひとつのセルのまわりのリンク(右)の例 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

8分格子グラフの各セルの角に上下の層へ のリンクを持たせている． 多層型地形図の16 分格子グラフモデルを応 用して，複数ページの表を16 分格子グラフで 表現する． 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

4.2 データフォーマット H5CODE : H3-Codeを一般化した16 分格子 グラフのデータフォーマット． 4.2　データフォーマット H5CODE : H3-Codeを一般化した16 分格子 グラフのデータフォーマット． 不均一型矩形分割コード（H8CODE）を変形 したファイル形式である． 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

矩形分割のデータフォーマット H3CODE（有田・夜久） H7CODE（2007）（赤木・有田・本橋・野牧・土田・夜久） Web掲載 H8CODE1.1（野牧・夜久）JSIAM05で発表 H8CODE1.2（呉羽・夜久）ＬＡ講究録０８で発表・引用 H8CODE1.3（野牧・夜久） 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

目的 複数枚の矩形グラフ（不均一型表）の表現 XMLへの変換を前提 対象 複数枚の不均一型表 演算（例） 表示 行・列の挿入・削除 壁の移動 等 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

各レコードのフィールド (1)ヘッダー部 (2)リスト部 (3)コンテンツ部 (4)表レイヤー部 H5CODEに対応するリストの概念図 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

H5CODE　ヘッダー部 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

H5CODE　リスト部 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

H5CODE コンテンツ部 コンテンツ部はセルに付随する 文字列，画像などの情報やコンテンツのリンク情 報を格納する 予備を含む8つのフィールドからなる 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

H5CODE レイヤー部 複数の矩形分割を管理するためのブロック 複数の矩形分割に対応するために使用され る 表レイヤー部のフィールドの数は8 H5CODEは複数枚の表に対応しているた め，レイヤー部は使用しない 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

H5CODEの中の一つのレコードのフィールド 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

4.3 アルゴリズム アルゴリズムはH5CODEの上で実装される． 説明は16分格子グラフの上で行う． 数理モデル化と問題解決研究会 4.3　アルゴリズム アルゴリズムはH5CODEの上で実装される． 説明は16分格子グラフの上で行う． 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

アルゴリズム MoveSouthWallInLayer(GD，v，δ，GE) 層の南壁移動のアルゴリズム アルゴリズム　MoveSouthWallInLayer(GD，v，δ，GE) 入力 GD: 矩形分割Dのための16分格子グラフD vｃ: GDの中のノード δ≧0: 動き値 Δ> 0はcの南寄りに隣接する行の中の周辺セルの高さで あるのに対し，Δ＞δとする． 出力 GE: Dから南壁移動で得られた16分格子グラフ． 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

入力 出力 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

Step 1: vcの西側の南壁辺でリンクされた周 辺ノードvaを見つける． 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

Step 2: sw(va)←sw(va)+δとする．vaに南壁 辺によってリンクされたノードをvbとする． vc va 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

Step 3: sw(vb)←sw(vb)+δ，vbを南壁辺でvb にリンクされた東側ノードに変更する． vc va vb 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

Step 4: vbが内部ノードならstep 3に戻る． vc va vb 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

Step 5: sw(vb)←sw(vb)＋δ，vcから周辺ノー ドvaまで移動 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

Step 6: vdをvaに西壁辺で南側にリンクされ たノードとする． vc va vd 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

Step 7: nw(vd)←nw(vd)＋δ，vdを北壁辺で vdにリンクされた東側ノードに変更する vc va vd 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

Step 8: vdが内部セルならstep 7に戻る． vc va vd 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

Step 9: nw(vd)←nw(vd)＋δ vc va vd 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

Step 10: 各層で同様の操作を行う． 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

5 終わりに 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

8分格子グラフに基づいた表に対し，次の表 編集アルゴリズムを構築した． 結果 8分格子グラフに基づいた表に対し，次の表 編集アルゴリズムを構築した． セル分割 1行削除 複数行削除 16分格子グラフに基づく複数ページの表編集 の手法 データフォーマットH5CODEを提案した． 南壁移動の実装 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

複数ページの表に対応した他の編集操作を 提案する 今後の課題 複数ページの表に対応した他の編集操作を 提案する 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構

END 3/8/2017 数理モデル化と問題解決研究会 沖縄科学技術研究基盤機構 99