基本クエリ

44 第4章 クエリをサポートする方形描画の符号 まず,いくつかの定義を与える. 符号Sの部分符号で,i文字目からj文字目まで からなるものを, S[i, j]と書く. 特にS[i, i] =S[i]とする.

S₁は‘(’と‘)’からなる符号とする. S₁[1, i]中の‘(’の個数をrank(i)と書く. S₁ 中のk番目の‘(’がS₁ のj文字目であるときselect(k) =j とする. j =select(k)

ならば, k = rank(j)であることに注意しよう. 例えば, 図 4.3のようにS₁ =

((())(()(()))()()) ならば, rank(6) = 4,select(4) = 6である.

次に, 入れ子構造を次のように定義する. 符号S_a =()は入れ子構造である. 符 号S_bとS_cが入れ子構造のとき, 符号S_d =S_bS_cとS_e =(S_b)は入れ子構造である.

入れ子構造をもつ符号において, ‘(’と ‘)’の間には自然な1対 1対応がある.

S₁[i] = ‘(’とS₁[j] = ‘)’が対応するとき, S₁[i]とS₁[j]は対応するという. この とき, f indclose(i) =j, または, f indopen(j) =iと書く.

次に, S₁上でenclose(i)を定義しよう. 2つの場合にわけて定義する. はじめに

S₁[i] = ‘(’の場合を扱う. f indclose(i) =jとしよう. このとき, S₁[i, j]を真に含む 最小の長さの入れ子構造をもつ部分符号をS₁[a, b]とする. このとき, S₁[i]とS₁[j]

からなる括弧の組を,S₁[a]とS₁[b]からなる括弧の組が囲んでいることに注意しよ う. 次に, S₁[i] = ‘)’の場合を扱う. f indopen(i) = jとする. このとき, S₁[j, i]を 真に含む最小の長さの入れ子構造をもつ部分符号をS₁[a, b]とする. 2つのいずれ の場合もenclose(i) = aと定義する. また,S₁[a]とS₁[b]はS₁[i]とS₁[j]をenclose するという. 例えば, 図4.3のS₁について, enclose(9) = 6である.

次に,S₁上でwrapped(i)を定義しよう. 2つの場合にわけて定義する. はじめに

S₁[i] = ‘(’の場合を扱う. このとき,enclose(k) = iを満たすkの個数をcとしよう.

次にS₁[i] = ‘)’の場合を扱う. f indopen(i) = jとしよう. このとき,enclose(k) = j を満たすkの個数をcとしよう. 2つのいずれの場合もwrapped(i) = cとする. S₁ は入れ子構造であるので, wrapped(i)の値は常に偶数になることに気をつけよう.

次がいえる.

補題 4.2.1 ([6, 10, 17, 18, 25, 26])

S₁の長さを2n bit とする. このとき, o(n) bit のサイズの補助テーブルS₁^Aを S₁に追加することにより, 次の値をO(1)時間で求めることができる.

(1) rank(i) [10, 17, 18], (付録A参照).

(2) select(k) [10], (付録B参照).

(3) f indclose(i)およびf indopen(i) [25, 26], (付録C参照).

(4) enclose(i) [25, 26], (付録C参照).

(5) wrapped(i) [6], (付録D参照).

また, S₁^AをO(n)時間で生成できる. (各命令の詳細は付録, または, 文献を参照 されたい.)

4.2. 基本クエリ 45 S₂⁰ は‘[’と‘]’からなる符号とする. S₂は, 3章で示した方法によって得られた符 号とする. このとき, S₂⁰ の入れ子構造によりS₂の入れ子構造を定義できる. この 入れ子構造にもとづいてS2についても同様にrank, select, f indclose, f indopen, enclose,wrapped を定める. S₂についても補題4.2.1と同様のことがいえる.

次に, 符号S_R =S₁+S₂から基本的な情報を高速に取り出す基本クエリについ て説明する.

S₁中にはD_Rの各点に対応して1組の‘(’と‘)’が存在する. i番目の点に対応す る‘(’と‘)’の位置は, それぞれS₁上のselect(i)とf indclose(select(i))である.

定義より, S2 は, 各west(i)やeast(i)に対応した(|S1| −6)個の部分符号に分 割できる.(図4.3参照.) west(1), west(2), west(3), east(1), east(3), east(f + 3) に対応する部分符号は存在しないことに注意しよう. ここで, f は面の個数であ る. S2中のwest(i)に対応する部分符号をLi としよう. S2 中からLi を次のよ うにしてさがすことができる. S₁ 上でselect(i) = aとしよう. このとき, L_i = S₂[select(a−4), select(a−3)−1]である. 例えば図4.3のS₁上においてi= 5とす ると, a =select(5) = 7である. S₁中の最初の4文字に対応する部分符号がS₂中 にないので(図4.3参照), S₂中で7−4 = 3番目の‘1’からL₅がはじまる. すなわ ちselect(7−4) = 4文字目からL₅がはじまる. また,L₅の次の部分符号はS₂中で 4番目の‘1’からはじまることより,L₅はselect(7−4 + 1)−1 = 4文字目で終わる.

よって,L₅ =S₂[4,4]である. S₂中の‘1’は必ずwest(i)やeast(i)の区切りとなって いることに注意しよう. L_iは, i番目の点から西方向に接続する|west(i)|=|L_i|個 の各辺に対応する. このとき,L_iの先頭からk番目の‘]’は,真北から反時計回りに k番目の辺に対応する. 特に, 1番目の‘]’, すなわちselect(a−4)(=p₁とする)と, これに対応する‘[’,すなわちf indopen(p₁)(=p₂とする)の組は,i番目の点に対応 する面f_iと,f_iの西方向に隣接する面のうち最も北にある面f_{W N}との隣接関係に 対応する(図4.5参照). 面f_{W N} に対応する点をv_jとする. このとき, f_{W N}(i) =j と書こう. すなわち, 面f_iの西(=W)方向に隣接する面のうち最も北(=N)にある 面がf_{W N}である. S₂上でq₁ =rank(p₂) + 4とすると, S₁上で,

f_{W N}(i) =rank(f indopen(q₁))

である. 図4.5にf_iとf_{W N}の符号上での位置関係を示す. 同様に, 面f_iの西方向に 隣接する面のうち最も南にある面をf_{W S} とする. S₂上でp₃ =select(a−3)−1と し, p₄ =f indopen(p₃)とする. このとき, S₂[p₄] = ‘[’とS₂[p₃] = ‘]’からなる括弧 の組は, f_iとf_{W S}との隣接関係に対応する(図4.5参照). S₂上でrank(p₄) + 4 =q₂ とすると, S₁上で

f_{W S}(i) = rank(f indclose(q₂))

である. すなわち, 1章で挙げた(例3)のクエリの解をO(1)時間で求めることがで

46 第4章 クエリをサポートする方形描画の符号

S1=

fWN i

fWS

S'₂ =

p1 p2 p4

q1 a

q2

p3

( ) ( ) ( )

] ] ] ] ] [

[ [

[ [

edge( f , f )_{i WN} edge( f , f )_{i WS}

図 4.5: f_{W N} とf_{W S} の計算

きる.

同様に, S₂中のeast(i)に対応する部分符号をR_iとしよう. S₂からR_iを次のよ うにしてさがすことができる. S₁上でselect(i) = aとし, f indclose(a) =bとしよ う. このとき,S₂上でR_i =S₂[select(b−4), select(b−3)−1]である. R_iは,i番目 の点から東方向に接続する|east(i)| =|R_i|個の各辺に対応する. このとき面f_iの 東方向に隣接する面のうち, 最も北にある面をfEN とし最も南にある面をfESと すると, 同様にf_EN(i)とf_ES(i)をそれぞれ次のように計算できる.

はじめにf_ENについて考える. S₂上でp⁰₁ =select(b−3)−1,p⁰₂ =f indclose(p⁰₁) とする(図4.5参照). このとき, S2[p⁰₁] = ‘[’とS2[p⁰₂] = ‘]’からなる括弧の組は, fi

とf_ENとの隣接関係に対応する. S₂上でq₁⁰ =rank(p⁰₂) + 4とすると,S₁上で f_EN(i) =rank(q₁⁰)

である.

次にfESについて考える. S2上でp⁰₃ =select(b−4), p⁰₄ =f indclose(p⁰₃)とする.

S₂上でq⁰₂ =rank(p⁰₄) + 4とすると, S₁上で f_ES(i) =rank(q₂⁰) となる.

以上により次の補題がいえる.

補題 4.2.2 S_Rに長さo(n)の符号を追加することによりL_i, R_i, f_{W N}(i), f_{W S}(i), f_EN(i), f_ES(i)をO(1)時間で求めることができる.

証明. 補題4.2.1より明らかである.

Q.E.D.

4.2. 基本クエリ 47

S1=

f_EN

i ^fES

S'₂=

p'1 p'

2 p'

4 q'1

a b q'

2

p'3

( ) ( ) ( )

] ] ]

] ] ]

[ [ [ [

edge( f , f )_{i EN}

edge( f , f )_{i ES}

図 4.6: fEN とfESの計算

(a) (b)

fWS(i)

i f

ES f

WS(i)

( )

‚

f_i v

i = f_ES f

WS(i)

( )

fWS(i) f_i

v

図 4.7: s-miss(i, SW)の計算

i番目の点に対応する面f_iの左下隅の点をvとしよう. このときvはs-missing, もしくは, w-missingのいずれかである. もし, v が s-missingであるならば, s-miss(i, W S) =T rueとし,そうでないときs-miss(i, W S) =F alseとする. 次のよう にしてs-miss(i, W S)を計算できる. もしf_ES(f_{W S}(i)) =iならばs-miss(i, W S) = T rueである. (図4.7(a)参照.) もしf_ES(f_{W S}(i))6=iならばs-miss(i, W S) = F alse である. (図4.7(b)参照.) 次の補題がいえる.

補題 4.2.3 指定された面の4隅の各点について, どの方向がmissingであるかを O(1)時間で判定できる.

すなわち, 1で挙げた(例4)のクエリの解をO(1)時間で求めることができる.

48 第4章 クエリをサポートする方形描画の符号