数理解析研究所講究録
第 1799 巻 2012 年 118-122

118
8 次格子モデルによる表の行/列操作
日本大学

高加 晋司 (Shinji Koka)
Nihon Univelsity

電気通信大学後藤 隆彰 (Takaaki Goto)

The University of Eledro-Communicatims
土田 賢省 (Kensei Tsuchida)

東洋大学

Toyo University
電気通信大学 西野 哲朗 (Tetsuro Nishino)
The University of Electro-Communications
夜久 竹夫 (Takeo Yaku)

日本大学

Nihon University

概要
不均一矩形分割のための 8 次格子グラフモ
デルに基づく 1 行削除，複数行削除，1 列削除，複数列削除のアルゴリズムについて述べ，計算時間の評価を行う．

本稿は，2 節で準備として 8 次格子グラフモデルについて解説し，3 節で，表編集アルゴリズムを提案し，計算時間の比較を行う．

2 準備
2.1 矩形分割 (例えば，[2])1

はじめに表編集ソフトウェアは数多く存在する．これらのソフトウェアの編集操作ではユーザが予期しない動作を引き起こすことがある．また多くの計算時間を必要としていると思われる．このため，信頼性の高い効率的な表 (矩形分割) 編集処理の実現が望まれている．そこで本論文では，表編集に適したグラフモデ

ルの導入と，そのグラフモデルに基づく効果的な表編集アルゴリズムを提案する．
R. A. Finkel と J. L. Bentley[l] は，1974 年に 4分木を導入した．さらに，K. Kozminsky と E.
Kinnen[2] は，1985 年に矩形分割のデータ構造である双対グラフの性質を導入している．
Yaku 等 (例えば，[3], [4], [5]) は，8 次格子グラフの導入と，それを用いた壁の移動，セルの合併と 1 つの列の挿入などのシンプルなアルゴリズムを提案している．しかし，必要な操作の中で，まだ研究されていないものがある．
そこで，本論文では，必要な表編集アルゴリズムを提案し，計算時間の評価を行う (cf.
[6], [7] .
$)$共通部分のない幾つかの矩形による平面上の矩形領域の分割のことを，矩形分割という．
矩形は 2 種類に分類され，分割されていない矩形をセルと呼び，行もしくは列を表すための周辺の矩形を周辺セルと呼ぶ．また，セルの境界を形成している線を罫線 (壁) という．
1 っのセルに対して，上下左右に位置する壁をそれぞれ北壁 $(nw)$ , 南壁 $(sw)$ , 西壁 $(ww)$ ,東壁 $(ew)$ という．
図 1 は，矩形分割の例である．太線の矩形
1 っが内部セルであり，太線で形成している矩形の周りに存在する矩形が行や列を表す周辺セルである．図 1 の数値は “座標値” である．
例えば，セル の北壁，南壁，西壁，東壁は，$c$それぞれ $0,2,0,2$ である．
1$0$

$)$

$\square$:内董立2$\dot{s}$$\bullet$4

4: 周遼セル

図 1: 矩形分割の図．

119
2.2 8 次格子グラフ [5]

セル ,

$d$

$c$が最も近い位置にあるとき，辺はに属し，東壁辺と呼ぶ．

$[v_{c}, eew, v_{d}]$矩形分割から図 2 のように構成されるグラ
フを，矩形分割に対する 8 次格子グラフと言$E_{D}$$e\iota\iota\langle\epsilon\succ^{-}c\iota!Xd)$$,c$.

い，以下で定義する．

,$\frac{d}{}$$\{|$2$\theta$

4$\neg\partial$4

図 5: 東壁辺の接続．
ノレー/

欧$>\prec$D$\overline{\underline{|r|}\text{」}}$

図 2: 矩形分割 (左) に対する 8 次格子グラフ (右).

$\triangleright$

4$ww(c)=ww(d)$ (セル $c,$セル$c$,$d$$d$の西壁が共通) で，が最も近い位置にあるとき，辺$[v_{c}, eww, \nu_{d}]$は$E_{D}$に属し，西壁辺と呼ぶ．

定義 2.2.1$D$を矩形分割とする． に対する 8 次格子グラ$D$

フは，多重無向グラフ$\tau\alpha lt(c\succ\overline{\iota}W(d)$$G_{D}=(V_{D}, L_{J}E_{D},A_{D}, \alpha_{D})$である．ただし， は内部セルもしくは周辺$V_{D}$セルを表し，セル はノード に対応している．
$c$

図 6: 西壁辺の接続．

$v_{c}$

は，辺のラベル集合として，$L=\{enw_{J}esw, eew_{J}eww\}$ とする．
$L$

$E_{D}:E_{D}\subseteq$$V_{D}\cross L\cross V_{D}$は，ラベル付きの無向辺の集合で, ラベル に対して，ある 6. ただし頂点 V。と$[v_{C}, l, \nu_{d}]$$l$$v_{d}$と表し， は次のノレーノレ$E_{D}$$1\triangleleft$によって定義する．
ノレーノレ 1,$C$

$A_{D}$$\subseteq$

R4 (セルの左上隅の $xy$ 座標と，幅と高さの集まり) であり，$\alpha_{D}$が最も近い位置にあるとき，辺は砺に属し，北壁辺と呼ぶ．

$d$$[\nu_{c}, enw_{J}\nu_{d}]$を頂点に属性を持たせる写像」とし，$\alpha_{D}=(nw(c),$ $sw(c),$ $ew(c),$ $ww(c))$とする．
8 次格子グラフの頂点の次数は最大で 8 であることに注意する．
グラフ が 8 次格子グラフであるとは，に対応する矩形分割が存在すると定義する．
$G$

$G$

$nw(c)=nw(d)$ (セル $c,$ \’a の北壁が共通) で，セル

そして， は属性集合

2.3 8 次格子グラフの実装 [4]8 次格子グラフの実装の場合，H3CODE と呼ばれるファイル形式が導入され，図 7 に示すのが H3CODE のリスト構造である．

$\prime 2ll!(c\succ-lz_{\tilde{l}}v(d)$図 3: 北壁辺の接続．
ノレーノレ 2$sw(c)=sw(d)$ (セノレ c,
セル$C$,$d$$d$の南壁が共通) で，が最も近い位置にあるとき，辺はに属し，南壁辺と呼ぶ．

$[v_{c}, esw, V_{d}]$$E_{D}$

図 7:H3CODE のレコード (左)$t^{\backslash }\cdot\overline{\ell}\{\epsilon\rangle\approx\nu(d)$とリスト(右).

3 準備
図 4: 南壁辺の接続．

3.1 1 行削除アルゴリズム

ノレーノレ 3$ew(c)=ew(d)$ (セル $c,$$d$の東壁が共通) で，ここでは，焦点のセルと北壁を共有する行

120を削除するアルゴリズムを示す．図 8 がその例である．

5.

からリンクした内部セルに対応する頂点の北壁辺を変える．
からリンクした内部セルに対応する
6.
頂点の南壁辺を変える．
$v_{0}$$v_{0}$

図 8: 入力例と出力例．

アルゴリズムDeleteSingleRow

図 11 :DeleteSingleRow の Step5 6.
$\sim$$(G_{D}, v_{x}, G_{E})$[入力 1$G_{D}:n\cross m$

矩形分割 に対する 8 次格子グラ$D$

フ $(n\geq 4,m\geq 3)$$V_{x}$: 焦点のセル$x$($G_{D}$の内部セル) に対応

7. “D” とマークされた頂点の東西のリンクを変え，“D5’ とマークされた頂点を削除する．

8. 削除した行の高さを合わせて，高さを変える．

する頂点

[出力]
$G_{E}$:$G_{D}$から， と交差する行の中の一番上$\nu_{x}$の 1 行を削除した 8 次格子グラフ

[方法]

1.

から北壁辺をたどって西側の周辺セルに対応する頂点に と置く．
から北壁辺をたどって全ての頂点に
2.
$V_{x}$$\nu_{0}$図 12: DeleteSrngleRow の Step7-8$v_{0}$$N$”とマークする．

sStepl, 2, 3, 4 のそれぞれのリンクをたどっ$Step2\sim 3$ ,て，高々 $m$ 個の頂点を訪問する．
$Step3\prime A$の間では，右端の頂点から高々$m$個のリンクをたどって目的とする左端の頂点に戻る．各頂点の次数は高々 8 なので，各頂点における時間計算量は定数である．

したがって，全体としての時間計算量は，0 $(m)$ となる．
図 9: DeleteSingleRow の Stepl

3.

から南壁辺をたどって全ての頂点にとマークする．
から北壁辺にリンクした頂点の内，“S” とマークされた頂点を “D” とマークする．

3.2 複数行削除アルゴリズム$V_{0}$

$S$

4.

2.

$\sim$”$v_{0}$

図 10 :DeleteSingleRow の $Step3\sim 4$ .

ここでは，焦点のセル (高さ ) に交差する全ての行を削除するアルゴリズムを示す．図13 がその例である．
$k$

図 13 : 入力例と出力例．

121
もし $sw(v_{i})<sw(v_{h})$ のとき，Step4 から

7.

アルゴリズムDeleteMultipleRows

繰り返す．

$(G_{D}, \nu_{x}, G_{E})$[入力]$G_{D}:n\cross m$

矩形分割$D\ovalbox{\tt\small REJECT}$

こ対する 8 次格子グラ

フ $(n\geq 5,m\geq 3)$$v_{x}$: 焦点のセル(高さ ) に対応する頂点(北南壁に隣接するセルが周辺セルでない$G_{D}$$k$$\chi$の内部セル)

図 17: DeleteMultip leRows の Step6-7.

[出力]$G_{E}$:から， と交差する全ての行を削除した 8 次格子グラフ$G_{D}$$v_{x}$[方法]

1.

$\nu_{x}$から南壁辺をたどって西側の周辺セルに対応する頂点に2.

$v_{0}$$\nu_{0}$と置く．

から南壁に隣接した頂点に砺と置く．

Stepl, 3 のそれぞれのリンクをたどって，高々 個の頂点を訪問する．Step2, 4 では，2個の頂点を訪問する．Step2 3 の間では，高々$m$ 個のリンクをたどって目的とする左端の頂点に戻る．各頂点の次数は高々 8 なので，各頂点における時間計算量は定数である．
以上を の高さ $k\leq n$ だけ繰り返す．
したがって，全体としての時間計算量は，$m$$\sim$$x$$0(m\cross k)$となる．

331 列削除アルゴリズム
8 次格子グラフは，水平方向と垂直方向の構造を同等に扱うことが出来る為，1 行削除と同様のアルゴリズムで削除することができ

図 14: DeleteMultip leRows の Stepl-2.

3.

から北壁辺をたどって西側の周辺セルに対応する頂点に と置く．
から隣接した下の頂点に4.と置く．
$\nu_{x}$る．

$\nu_{i}$$v_{i+1}$$v_{i}$

図 18 : 入力例と出力例．

図 15: DeleteMultipleRows の $Step3\sim 4$ .

5. DeleteSingleRow アルゴリズムを用る．

$\backslash$

1 行削除アルゴリズムと同様に，全体としての時間計算量は $0(m)$ である．

3.4 複数列削除アルゴリズム
8 次格子グラフは，水平方向と垂直方向の構造を同等に扱うことが出来る為，1 行削除と同様のアルゴリズムで削除することができる．

図 16:DeleteMultipleRows の Step5.

6.

$i++$.

122
これらのアルゴリズムの計算時間は，既存のデータ構造より早いことがわかった．今後は，8 次格子グラフを特徴付けるグラフ文法を構成する．

謝辞
図 19 : 入力例と出力例．

1 行削除アルゴリズムと同様に，全体としての時間計算量は $0(m\cross k)$ である．

3.5 計算時間の比較
8 次格子グラフと，既存のデータ構造である 4 分木と双対グラフについての時間計算量の比較を行う．
行$m$ 列の表に対して，1 行削除を行う為の時間計算量は，4 分木の場合，グラフの性質貴重なコメントを頂いた早稲田大学高等学院の穴田浩一先生，日本大学の神藤悠希氏に深く感謝いたします．

参考文献[1] R. A. Finnkel and J. L. Bentley, Quad Trees:

A Data Structure for Retrieval on Composite
Keys, Acta Informatica, Vol. 4, No. 1, 1974,$n$上，想定外なので考えていない．頂点数 の双対グラフの場合，列数 $m$ に対して，最大で全ての頂点を見て回る必要があるので，

pp. 1-9.

$N$[2] K. Kozminsky and E. Kinnen, Rectangular

Duals of Planar Graphs, Networks 16, 1985,

である．1 列削除を行う為の時間計算量も同様なので，以下のようになる．
$0(m\cross(N))$

pp.145-157.
[3] T Yaku, ”Representation of Heterogenenous

表 1:1 行削除，1 列削除の計算時間．

Tessellation Structures by Graphs”, WAAP
108, research $repor\iota$ 1-6, Dec. 2001.
URL: $http://www.waap.yjp/waap-\pi lwaap-rr$-01-013.pdf[4] T. $K\ddot{m}shima$, T. Motohashi, K. Tsuchida, and$n$

T. Yaku, Table Processing based on Attribute
Graphs, Proc. 6th IASTED International
Conference on Software Engineering andApplications, 2002, pp.317-322.

行$m$ 列の表に対して，複数行削除を行う為の時間計算量は，4 分木の場合，グラフの性質上，想定外なので考えていない．頂点数 の双対グラフの場合，列数 $m$ に対して，最大で全ての頂点を見て回る必要がある．さらに，高さ $k\leq n$ だけ繰り返す．したがって，$N$$0(m\cross(N)\cross k)$である．複数列削除を行う為[5] 本橋友江，谷聖一，土田賢省，夜久竹夫，

表編集のアルゴリズム，数理解析研究所の時間計算量も同様なので，以下のようにな

講究録 Vo11325, 2003, pp.152-157.

る．

表 2: 複数行削除，複数列削除の計算時間．

[6]

土田賢省，本橋友江，夜久竹夫，山澤聡，
吉住寿洋，表の格子グラフモデルと編集
アルゴリズム，情報処理学会研究報告，
2009-MPS-073, 2009, pp.225-228.

[7] T. Yaku, K. Anada, S. Koka, Y. Shindo, and4

おわりに

本論文では，1 行削除，複数行削除，1 列削除，複数列削除のアルゴリズムを提案した．

K. Tsuchida, Row Manipulation in theHeterogeneous Tabular Forms with an Octal
Grid Model, Proc. 2011 IEEE Symposium onLanguages and Human-CentricComputing, 2011, pp.269-270.
$\nabla\iota asual$