数理解析研究所講究録
第 1849 巻 2013 年 83-87

83

16 次格子モデルによる不均一型多層矩形分割の層の操作
Layer Operation in the Heterogeneous Tabular Forms with a
Hexadecimal Grid Graph Model
日本大学

高加晋司 (Shinji Koka)

Nihon University
早稲田大学高等学院 穴田 浩一 (Koichi Anada)
Waseda University Senior High School
日本大学

夜久竹夫 (Takeo Yaku)

Nihon University

本稿は，2 節で準備として，Octgrid,

概要

Hexadeci-grid について解説し，Hexadeci-gridを用いた複数ページの表編集アルゴリズムの既存の方法として層削除アルゴリズムについ不均一多層矩形分割のための 16 次格子グ

ラフモデルに基づく層の挿入操作について述て解説する．3 節で，複数ページの表編集アルゴリズムとして層挿入アルゴリズムを提案し，4 節で複数ページの表処理への応用につべる．

1

いて示す．

はじめに従来の研究では，単層表形式のためのいくつかのデータ構造が知られている．Finkel と2準備

Bentley[l] は，1974 年に矩形分割の表現と探索

2.1

矩形分割のための4 分木を導入し，Kozminsky とKinnen[2] は，1985 年に矩形双対グラフの性質を解説した．
Yaku[4] は，8 次格子グラフモデルの一種である Octgrid と呼ばれるデータ構造について議論した．Octgrid は罫線を維持する変形問題
に関して，矩形双対グラフのような良く知られた構造を使うよりも計算時間が少ないアル

共通部分のない幾つかの矩形による平面上の矩形分割を，不均一型単層矩形分割という，分割されていない矩形をセルと呼び，行もしくは列を表すための周辺の補助的な矩形を周辺セルと呼ぶ．また，セルの境界を形成している線を罫線 (壁) という．1 つのセルに対して，上下左右に位置する壁をそれぞれ北壁$(nw)$ ,ゴリズムを与える．
呉羽等 [5] は，Octgrid の一般化として複数ペのスプレッドシート (例えば，[3]) のよ
うな多層表形式のための Hexadeci-grid と呼ば

南壁 $(sw)$ , 東壁 $(ew)$ , 西壁 $(ww)$という．

$-\backslash \nearrow^{\backslash }\backslash \backslash$

れるデータ構造を導入した．Hexadeci-grid はOctgrid の利点を継承するため，同様に計算時間が少ないと考える．[5,6] では，複数ページの表形式の編集のための Hexadeci-grid に基づいた 1 行削除，層削除アルゴリズムを提案した．しかし，複数ページの表編集に対する変形アルゴリズムの一部が構築されてぃない．
そこで，本論文では，複数ページの表編集アルゴリズムの解説する [7].

図 1: 不均一型単層矩形分割の図．

図 1 は，不均一型単層矩形分割の例である．
い矩形 1 つ 1 つが内部セルであり，白い矩7 の周りに存在する矩形が行や列を表す周辺$\in\exists$$\mathfrak{k}$$\#//$

84
セルである．図 1 の数値-は “座標値” である$G_{D}=(V_{D}, E_{D},L,\lambda_{D},A_{D}, \alpha_{D})$$\acute{}$である．ただし，$V_{D}$

例えば，セル の北壁，南壁，東壁，西壁は，は不均一型単層矩形分割 D}こ対する頂点の集それぞれ $0,2,1,0$ である．

合， は無向辺の集合である．は，辺のラ$L=\{enw, esw, eew, eww\}$ とベル集合として，する．
ま，ラベノレ関数である．ただし頂点 とに対して，を，次のル(図 4) によって定義する． は属性集合 R4 であり， を頂点に属性を持たせ$\alpha_{D}(\nu_{c})=(nw(c),sw(c),ew(c)$,る写像とし，$c$

また，不均一型単層矩形分割を多層に一般化した矩形分割を，不均一型多層矩形分割という．層は 2 種類に分類され，内部セルを持つ層を内部層と呼び，全てのセルを表すために用意される最上層，最下層に位置する補助的な層を周辺層と呼ぶ．また，あるセルの 4つの角が異なる層のセルを繋ぐ線を罫線 (角辺 という．1 つのセルに対して，上下の層に位置する角をそれぞれ北東角 $(nec)$ , 北西
角 $(nwc)$ , 南東角 $(sec)$ , 南西角 $(swc)$ と$L$

$E_{D}$$\lambda_{D}:E_{D}arrow LI$$v_{c}$$\lambda_{D}[\nu_{c/}\nu_{d}]$$\nu_{d}$$-\prime\triangleright]\sim 4$$A_{D}$$\subset$$\alpha_{D}$$WW(C))$ とする．

$)$

いう．

図 4: ルール 1$\sim$

ノレーノレ 1

図 2: 不均一型多層矩形分割の図．

$nw(c)=nw(d)$ 同じ層のセノレの北壁が共通) で，セル $c,$が最も近い位置$($にあり，$\lambda_{D}[v_{c/}v_{d}]=enw$のとき，$SW(C)=sw(d)$の南壁が共通) で，セル $c,$[4] では，Yaku が Octgrid と呼ばれる 8 次格子グラフに基づいた不均一型単層矩形分割のためのデータ構造を導入した．

$d$となり，北壁辺と呼ぶ．
ノレーノレ 2

2.2 Octgrid$C,$$d$$[v_{c/}v_{d}]\in E_{D}$

図 2 は，不均一型多層矩形分割の例である．

4 の図．

$($同じ層のセノレ$d$$C,$が最も近い位置にあり，のとき，となり，南壁辺と呼ぶ．
ルール 3$ew(c)=ew(d)$ (同じ層のセル$\lambda_{D}[v_{c/}v_{d}|=esw$$[v_{\mathcal{C}/}v_{d}]\in E_{D}$の東壁が共通) で，セル $c,$にあり，$[v_{c/}v_{d}]\in E_{D}$

$d$

$d$

$c,$$d$が最も近い位置のとき，$\lambda_{D}[v_{C/}v_{d}|=eew$となり，東壁辺と呼ぶ．
ルール 4 $ww(c)=ww(d)$ (同じ層のセル $c,$$d$の西壁が共通)置にあり，が最も近い位で，セルのとき，$C,$$[v_{c/}\nu_{d}]\in E_{D}$

図 3: 不均一型単層矩形分割 (左) に対する Octgrid(右).

造より計算時間が少ないアルゴリズムを与えることができる (例えば，[9,11]). 図 3 は，不均一型多層矩形分割に対する Octgrid を示
し，以下で定義する．

定義 2.2.1$D$$D$を不均一型単層矩形分割とする．

に対する Octgridは，多重無向グラフ$\lambda_{D}[\nu_{C/}\nu_{d}]=$$eww$ となり，西壁辺と呼ぶ．

定義 2.2.2 グラフ が Octgrid であるとは，に対応する不均一型単層矩形分割が存在する．
$G$

また，いくつかの変形操作で，Octgrid が矩形双対グラフのような良く知られたデータ構

$d$

$G$

Octgrid の頂点の次数は最大で 8 であることに注意する．

2.3

Hexadeci-grid呉羽等 [5] は，Hexadeci-grid と呼ばれる多層表形式のための立体型 16 次格子グラフ (超格85子グラフ) に基づいたデータ構造を導入した．

$\lambda_{D}[v_{c/}\nu_{d}]=enwc$となり，北西角辺と呼ぶ．

このデータ構造は Octgrid を一般化したもの

ルール 7$=$sec(c) Sec(d)(異なる層のセル $c,$の南東角が共通) で，セル $c,$が最も近いで，罫線を維持するアルゴリズムに適している．図 5 は，不均一型多層矩形分割に対応する Hexadeci-grid を示し，Hexadeci-grid は以下位置にあり，のとき，esec となり，南東角辺と呼ぶ．のように定義する．

ルール 8$d$$d$$[v_{C/}v_{d}]\in E_{D}$$\lambda_{D}[\nu_{c/}v_{d}]_{n}=$$swc(c)=swc(d)$ (異なる層のセルの南西角が共通) で，セルが最も近のとき，い位置にあり，
$d$

$c,$

$C,$

$d$

$[\nu_{C/}v_{d}]\in E_{D}$$\lambda_{D}[\nu_{c/}v_{d}]=eswc$となり，南西角辺と呼ぶ．

定義 2.3.2 グラフ が Hexadeci-grid であるとは， に対応する不均一型多層矩形分割が存在する．
$G$

$G$

図 5: 対象の 2 層の内部セル (左), 不均一型多層矩形分割 (中央) に対する Hexadeci-grid (右).

定義 2.3.1$D$$D$

Hexadec -grid の頂点の次数は最大で 16 であることに注意する．
$i$を不均一型多層矩形分割とする．

に対する Hexadeci-grid は，多重無向グラフ$G_{D}=(V_{D\prime}E_{D},L,\lambda_{D\prime}A_{D\prime}a_{D})$は不均一型多層矩形分割である．ただし，2.4 既存の変形操作$V_{D}$$D\}_{\llcorner}^{\vee}$

対する頂点の集合， は無向辺の集合である．は，辺のラ$L$$E_{D}$

ベル集合と して，
$L=\{enw,$ $esw,$ $eew,$ $eww,$enec, $enw$ ら esec, eswc} とする．
は，$\lambda_{D}:E_{D}arrow L$

ここでは，先行研究である Hexadeci-grid での変形操作として焦点のセルの層を削除するアルゴリズムを示す．図 7 がその入力例と出力例である．

ラベル関数である．ただし頂点 v。と に対して，を，次のルール 1 4 (図 4) 及びルール 5 8 (図 6) によって定義する． は属性集合 R5 であり， を頂点に属性を持た$v_{d}$$\sim$$\lambda_{D}[\nu_{c/}\nu_{d}]$$\sim$$A_{D}$$\subseteq$$\alpha_{D}$$\alpha_{D}(v_{c})=(nw(c),sw(c),ew(c)$ ,せる写像とし，$WW(c),$ $layer(c))$ とする．

$-\cdots\cdot\cdot\ddot{u}::\ldots..\ldots..,\grave{\dot{u}}^{-}u$$ur\ldots.\dot{*}..\ddot{\dot{*}}\cdots*$$\ddot{r}\nu\cdots--\underline{w}\dot{.}\nu_{W}w=$$u\vee\sim r\nu nuww.w$$r\cdot\cdot ww^{-}\sim\ldots..\dot{c}\ldots..\nu\cdot\cdot\approx$$w..u.\ldots*\cdot.$$\vee-\infty\cdots\cdot\dot{u}\cdot\dot{w}..\cdot.\cdots\ddot{w}$$U^{-}\sim..$$u$ゆ

図 7:1 層削除アルゴリズムの入力例と出力例．

アルゴリズム :LayerDeletion16$(G_{D\prime}\nu_{x/}G_{E})$入力$G_{D}$

図 6: ルール 5
ルール 1$\sim$$\sim$

8 の図．

4 Octgrid と同様である．

$v_{\chi}$

ルール 5
$d$

$nec(c)=nec(d)$ (異なる層のセル $c,$の北東角が共通) で，セル $c,$が最も近い$d$位置にあり，のとき，enec となり，北東角辺と呼ぶ．
$[\nu_{c/}v_{d}]\in E_{D}$:

一層の不均一型多層 $n\cross m$ 矩形分割 に対する Hexadeci-grid $(n\geq 1,m\geq 1,s\geq 2)$ ,: 焦点のセル ( の内部セル) に対応する
頂点．
$x$

$d$

$nwc(c)=nwc(d)$ (異なる層のセルの北西角が共通) で，セル $c,$が最も近$d$

い位置にあり，$[\nu_{C/}\nu_{d}]\in$

恥のとき，$G_{D}$

出力$\lambda_{D}[\nu_{c/}v_{d}]=$$G_{E}$: $(s-1)$ 一層の不均一型多層割 $D|$ こ対する Hexadeci-grid.

ルール 6
$C,$

$D$$s$方法

Step 1. 初期化$G_{E}arrow G_{D}.$$n\cross m$

矩形分

86
Step 2.
Step 3.

$v_{x}$る．(図 10)

Step 4.

返す．

Step 4.

上方向のリンクの行き先と同じにすの上下層のリンクを繋ぎ直す．の層の全ての頂点で Step 2. を繰り$\nu_{x}$から上方向のリンクを削除し， か$V_{0}$に向かって下方向のリンク 4 本を繋ぐ．(図 10)
らの層の全ての頂点を削除する．

$v_{x}$$v_{x}$$\nu_{x}$3 層の挿入操作
この節では，Hexadeci-rid の変形操作として，層挿入アルゴリズムを提案する．ここでは，焦点のセルの上に 1 層挿入するアルゴリズムを示す．図 8 がその例である．

$,$$\circ$紗蝉蝉
ゆ$\sim$$\sim$$-$$-$– .. ゆ –$\ldots$$-$$\sim$$-$$\ldots$$\sim$$u$-$-$.

$. C V L$

ゆ$v$$C$$\sim$$\sim$.

図 10 :LayerTnsertion 16 の Step 3-4.

$W\ldots\sim\ldots V\ldots O\ldots W$

$C$

$V$

ゆ

ゆ$\sim$rり

Step 5. 新しい層に全ての頂点を加えるために， の層の全ての頂点で Step2-4$v_{x}$を繰り返す．(図 11)

Step 6.

を含む新しい層の水平方向のリンクを x の層と同様に繋げる．(図 11)$\nu_{0}$$\nu$

図 8:1 層挿入アルゴリズムの入力例と出力例．
アルゴリズム : $Layerlnsertion16(G_{D},v_{x/}G_{E})$入力$G_{D}$$v_{x}$:

一層の不均一型多層 $nxm$ 矩形分割 $D|$ こ
対する Hexadeci-grid $(n\geq 1,m\geq 1,s\geq 1)$ ,$s$

: 焦点のセル に対応する頂点．
$x$

図 11 : Layerlnsertion 16 の Step 5–6.

出力
$G_{E}$: $(s+1)$ 一層の不均一型多層 $nxm$ 矩形分
割 $D|$ こ対する Hexadeci-grid.

方法. (図 9)
Step 1. 初期化
Step 2. の上に新しい頂点 o を加える．(図 9)1 つの頂点の次数が最大で 16,1 つの頂点の周辺のリンクの繋ぎ替えが 16 本以下なので，全体としての計算時間は矩形双対グラフより少ないことが期待される．

$G_{E}arrow G_{D}$$V_{x}$$\nu$4

表処理への応用
この節では，Hexadeci-grid の表処理への応用の為の概念を示す．(図 12)

複数ページの表処理の中の操作として以下の操作が考えられる．
セルの合併/分割

行，列の挿入/削除
図 9 :Layerlnsertionl6 の Step 1–2.

Step 3.

$v_{0}$の上方向のリンクの行き先を層の挿入/削除$\nu_{x}$の以上の操作を行う場合，Hexadeci-grid を用

87
いると少ない計算時間で他のシートに結果を同期させることができる．

pp.145-157.
[3]

M.

M. Bumett, A. Sheretov, and G.
Rothermel, Scaling Up a “What You See Is
What You Test” Methodology to Spreadsheet
Grids, Proc. IEEE
1999, pp.30-37, 1999.
$VL$[4] T. Yaku, Representation of Heterogenenous

Tessellation Structures by Graphs, Memoir ofWAAP Meetings 108, $6p$ , Dec., 2001.
URL: http $//www$. waap. gr.jp/waap-rr/waap-rr-01-013.pdf[5]

呉羽彬，土田賢省，夜久竹夫，不均一型
多層矩形分割に対する 16 分格子グラフ

表現，数理解析研究所講究録，Vol.1599,
pp. 176-181, 2008.
[6]

K. Nomaki, T. Arita, S. Koka, K. Tsuchida,and T. Yaku, A Hexadecimal Grid Graph
Model for the Multiply Layered TabularForms, Proc. lCCSM2010, pp.40-44, 2010.

[7]

S. Koka, K. Anada, K. Nomaki, and T. Yaku,Tabular Form Editing with a Hexadecimal
Grid Graph Model, Proc. IEEE $VL/HCC$2011, pp.253-254, 2011.

[8]

Y Shindo, K. Anada, K. Anzai, S. Koka, andT. Yaku, A Graph Grammar Mode] for
Syntaxes of Financial Statements, Proc.
IEEE $VL/HCC$ 2011, pp.265-266, 2011.

[9]

T. Yaku, K. Anada, S. Koka, Y Shindo, andK. Tsuchida, Row Manipulation in theHeterogeneous Tabular Forms with an Octal
Grid Model, Proc. IEEE VUHCC 2011,

図 12 :LayerDeletion 16 と Layerlnsertion 16 の応用．

5

おわりに

本論文では，複数ページの表編集のための変形アルゴリズムとして，層挿入アルゴリズムについて提案し，それらの表処理への応用について述べた．

今後の課題として，計算時間の評価やアルゴリズムの実装，他の変形アルゴリズムの構
築 (例えば，[101), Hexadeci-grid を特徴付けるグラフ文法の構成 (例えば，[8]) などがあげられる．

謝辞
貴重なコメントを頂いた日本大学の野牧賢
志氏，神藤悠希氏，久保田彬仁氏に深く感謝いたします．

参考文献

pp.269-270, 2011.
[10] S. Koka, K. Anada, K. Nomaki, Y. Shindo,

and T. Yaku, Row Manipulation in theHeterogeneous Tabular Forms with a
Hexadecimal Grid Graph Model, Proc. $ACM$
SAC 2012, pp.792-793, 2012.

[1] R. A. Finnkel and J. L. Bentley, Quad Trees:[11] G. Akagi, K. Anada, S. Koka, Y. Nakayama,

A Data Structure for Retrieval on Composite
Keys, Acta Informatica, Vol. 4, No. 1, 1974,

K. Nomaki, and T. Yaku, A Resolution
Reduction Method for Multi-Resolution
Terrain Maps, Poster Proc. SIGGRAPH 2012,
DOI $=10$ . 1145/2342896.2342998, 2012

pp. 1-9.
[2]

K. Kozminsky and E. Kinnen, Rectangular
Duals of Planar Graphs, Networks 16, 1985,