第15回： 7月29日

情報システム基礎論２：第 15 回 (担当：古賀)
区間/領域に対する探索
2014 年 7 月 29 日
レジュメ URL: http://sd.is.uec.ac.jp/koga/lecture/IF2/
1
はじめに
これまで、ユークリッド空間の点、集合、文字列など様々なデータに対する探索を取り扱って来た。今
回はユークリッド空間における区間 (Interval) を対象とする探索を議論する。
Definition 1 (区間 (Interval)) l, h を l ≤ h を満たす実数とする。左端点 l、右端点 h で定まる線分の
ことを、区間 I = [l, h] と表記する。
2
Stabbing Query
Stabbing Query は区間を対象とする代表的な探索問題。
• データベース S: n 個の区間 {I1 , I2 , I3 , · · · , In } が登録される。ただし、Ii = [li , hi ].
• クエリ q: 1 次元の点
• 出力: q を内包する区間。return all the intervals in S which contain q.
q
I3
I1
I5
I6
I4
I7
I2
図 1: stabbing query
Stabbing Query は 2 次元空間におけるレイアウト検証において線分の交差判定のサブルーチンとして
使われる。例えば、VLSI の部品のレイアウト検証など。
自明な解法
Stabbing Query はクエリと S の全区間を比較すれば O(n) で解ける。q の座標と区間 Ii の左端 li 、右端
ri との大小関係から、Ii が q を含むかがわかる。
より高速に解くためのデータ構造 → Interval Tree
1
3
Interval Tree
2 分探索木を stabbing query 用に拡張したもの。2 分探索木では根ノードの値を val とすると、根ノー
ドが S を以下の 3 要素に分割する。
(1) 左部分木 Sl = {x : x < val}, (2)val, (3) 右部分木 Sr = {x : x > val}
13
9
15
7
図 2: 1 次元の 2 分探索木
これに対して Interval Tree では S を以下の 3 要素に分割する。
1. 左部分木 Sl = {I ∈ S : 右端 < val}.
2. 根ノード Sc = {I ∈ S| 左端 ≤ val ≤ 右端 }.
3. 右部分木 Sr = {I ∈ S : 左端 > val}.
3.1
アルゴリズム
S から interval tree を作るアルゴリズム interval(S) を示す。
/*
Step
Step
Step
以下は S 6= φ の時に実行する。 */
1: S の 2n 個の端点の中央値 val を根ノード root とする。
2: val と重なる区間の集合 Sc を決定する。S 0 = S/Sc とする。
3: S 0 を Sl と Sr に分割する。
Sl = {I ∈ S : r < val}
Sr = {I ∈ S : l > val}
Step 4: 左部分木 Tl を生成する。Tl = interval(Sl )
Step 5: 右部分木 Tr を生成する。Tr = interval(Sr )
Step 6: root が根で Tl と Tr をそれぞれ左子ノード、右子ノードとした木 T を構築して終了。
Step 2 において Sc は root に格納する。
性質: Interval Tree の高さは O(log n)。再起呼び出しの度に端点数が半減するため。
図 1 の区間集合に対する Interval Tree を図 3 に示す。
2
l5
I2,I5
l4
r6
I3,I4
I6,I7
r1
I1
図 3: Interval Tree
3.2
検索アルゴリズム
2 分探索木と同様に木の根からスタートして木を降りながらデータ検索を行う。クエリの値を q とする。
Step 1: /* root ノードでの処理 */
• Sc に含まれる区間が q を含むかを調べる。
• q と root に格納されたデータ val との比較を行う。q = val であれば検索完了。q 6= val で root に子
ノードがある場合は Step 2 へ Step 2: 木を降りた後、Step 1 に戻る。
• if q < val であれば木を左下にたどる。
• if q > val であれば木を右下にたどる。
空間計算量: O(n): 木のノード数は 2n より小さい。また、S の区間は木のノードにちょうど 1 度ずつ登録
される。
時間計算量: このアルゴリズムの計算量は木の高さが O(log n) なので、O(log n) に思えるがそうではない。
log n +
X
(Scv と q との比較にかかる時間)
探索パス上のノード v
q
val
図 4: SC = S となる例
3
(1)
3.3
Sc と q との比較処理の高速化
「Sc に含まれる区間が q を含むかを調べる」処理の計算量はいくらにできるだろうか？O(|Sc |) 回の比
較で解けるのは明らか。逆に計算量の下限は、Sc の中で q を含む区関数を k とすると Ω(k)。
ここでは、この O(k) を実現する手法を述べる。本手法では 2 個の配列を使用する。
• AL: Sc に含まれる区間の左端の座標を昇順にソートした配列
• AR: Sc に含まれる区間の右端の座標を降順にソートした配列
処理は q の値により場合分け。
• q < val: ∀I ∈ Sc の右端は q より大。よって I の左端が q 以下 → I は q を含む。よって、次のよう
に処理すればよい。
AL の要素を先頭から調べ、対応する区間を出力。値が q より大きくなったら終了
• q = val: Sc の全区間が q を含む。
• q > val: ∀I ∈ Sc の左端は q より小。よって I の右端が q 以上 → I は q を含む。
AR の要素を先頭から調べ、対応する区間を出力。値が q より小さくなったら終了
調べる区関数は k + 1 個なので、計算量は O(k)。
式 (1) の全体の計算量は
log n +
X
O(kv + 1)
探索パス上のノード v
X
≤ log n + O(log n) +
(2)
O(kv )
(3)
探索パス上のノード v
= O(log n + K).
となる。K =
X
(4)
kv = (q を包含する区関数)
探索パス上のノード v
このように計算量が出力される解の数に依存するアルゴリズムを output-sensitive という。
4
Range Search
区間を多次元へ拡張すると矩形領域になる。今回の講義では 2 次元矩形領域を取り扱う (図 5)。
Definition 2 (矩形領域 (Range)) xl , xh , yl , yh を xl ≤ xh , yl ≤ yh を満たす実数とする。[xl , xh ]×[yl , yh ]
のことを矩形領域と呼ぶ。
4
Yh
R
Yl
0
xh
xl
図 5: 矩形領域
4.1
問題の定義
指定された領域 q 内に存在する点をすべて回答する問題を Range Search と呼ぶ (図 6)。Range Search
は地理情報処理で大変よく使われる。例えば、指定された地域に含まれる施設を列挙する問題は Range
Search に帰着される。
• データベース S: n 個の点 p = (px , py ) が登録される。
• クエリ q ：領域 [xl , xh ] × [yl , yh ]
• 出力: q が内包する点。return all the points inside q out of S.
Yh
R
Yl
0
xh
xl
図 6: Range Search
領域 q と S の全点を比較すれば O(n) で解ける。より高速に解くためのデータ構造 → Range Tree
5
Range Tree
5.1
探索木の構築
S から Range tree を作るアルゴリズム Range(S) を示す。
/* 以下は S 6= φ の時に実行 */
Step 1: S に含まれる点の y 座標の中央値 val を根ノード root とする。
Step 2: S を x 座標の昇順に並べた配列 A を root に格納
Step 3: if |S| ≥ 2, S を Sl と Sr に分割する。
Sl = {p ∈ S : py ≤ val}
5
Sr = {p ∈ S : py > val}
Step 4,5,6 は Interal Tree と同じなので省略。
• Step 2 を除けば y 座標に関して 2 分探索木を作っているだけ。Step 3 で Sl を「py < val」ではなく、
「py ≤ val」とすることで、すべての点が葉に出現。
• Step 2 では各ノードを根とする部分木が含む点を記憶する。配列 A は検索時に x 座標に関する 1 次
元 range search を実行するのに使用される。
y4 4,2,1,3,6,5
p1
p5
p3
4,2,6 y2
y5
p4
1,3,5
3,5
y4
4
2,6 y6
p2
p6
y6
6
y2
2
y3
3
y3
y1
1
y5
5
図 7: Range Tree
5.2
5.2.1
探索手順
基本方針
(1) まず y 座標に関して条件を満たす点集合を発見する。(2) それらの中で x 座標に関して条件を満たす
点を絞り込む。(1) のために、yl と yh を range tree 上で探索。
5.2.2
アルゴリズム
Step 1: yl と yh を探索し、探索パスが分岐するノード div を見つける。図 8 左参照。div を根とする部分
木は yl 以上、yh 以下の点を含む可能性がある。
• 分岐なく葉ノード lf まで到達した場合は、yl ≤ lf ≤ yh を確認後、lf の配列 A に対して 1 次元の range
search を実行して結果を出力。
Step 2: div の左部分木 Tldiv 内で yl の探索を続ける。図 8 右参照。
Step 3: div の右部分木 Trdiv 内で yh の探索を続ける
6
root
ldiv
div
Tl
v
vleft
yl div yr
ldiv
div
Tl
vright
rdiv
div
Tr
<yr
T1
T2
yl<T2< yr
>yl
図 8: Range Tree の探索
Tldiv における yl の探索通常の 2 分探索木と同様に、根ノード ldiv からスタートして、ノードが持つ値
と yl との大小関係によって木を降りていく。具体的には、現在のノードを v とすると
• yl ≤ v なら v の左子ノード vlef t に降りる。
• yl > v なら v の右子ノード vright に降りる。
ただし、左子ノード vlef t に降りる時は、vright が持つ配列 A に対して 1 次元の range search を実行して結
果を出力。左子ノード vlef t に降りたという事実から、yl < T2 < yr が確定する。
• Tldiv 内の点の y 座標は yr より小さい。
• yl ≤ v より、vright を根とする部分木 (図 8 の T2 ) 内の点は yl より大。
以上から yL < T2 < yr が確定する。
Trdiv での yr の探索右子ノード vright に降りる時に、vlef t が持つ配列 A に対して 1 次元の range search
を実行して結果を出力。
5.2.3
計算量
木の各階層で高々2 回の 1 次元 range search が実行される。よって計算量は
X
O(log n + kH ) = O(log2 n + K)
木の階層 H
K は range search の解の数。
データ構造を少し工夫すれば、計算量は O(log n + K) に下げられる。
7
Appendix: 1 次元の Range Search
1 次元の range search は簡単。クエリ q を区間 [xl , xh ] とする。S を昇順にソートした配列 A を事前に
作成しておく。
1
3
6
9
11
13
14
17
1. 2 分探索で A に対して xl を探索し、S の中で xl 以上の最小のデータ head を決定。
2. head から A を後方へスキャン。xh より大きいデータが出現したら終了。
計算量は O(log n + K)。K は range search の解の数。
8

Download Report