付 録 C findclose, findopen, enclose 命令
C.2 概要
S ( ( ( ( ( ) ))))
i x
previous pioneer of S[i]
k p j y ql
far far
far far
図 C.2: 背理法の仮定におけるS[j]とS[l]の状況
する. j = f indclose(i)とする. S[k] = ‘(’をS[i]の直前のpioneerな括弧とし, l =f indclose(k)とする. このとき, 次が言える.
補題 C.1.1 S[j]とS[l]は同じブロックに含まれる.
証明. S[i]の直前のfarな括弧がS[k]である場合, 明らかに上の主張が成立する.
そうでない場合を考えよう. S[j]とS[l]は異なるブロックに含まれると仮定する.
S[k]の直後に現れるfarな括弧をS[p] = ‘(’とし, f indclose(p) =qとする. このと き, S[q]はS[l]と同じブロックに含まれる. なぜならば, そうでないとするとS[p]
がpioneerでないことに矛盾するからである. 図C.2に位置関係を示す. S[p]の直
後のfarな括弧についても同様の議論ができる. これを繰り返すことにより, S[i]
の直前のfarな括弧S[x] = ‘(’に対応する括弧S[y] = ‘)’もS[l]と同じブロックに 含まれる. これはS[i]がpioneerでないことに矛盾する. 以上により, S[j]とS[l]は 同じブロックに含まれる. Q.E.D. したがって, もし, 直前のpioneerな括弧の位置kが計算できたならば, pioneer な括弧のテーブルからlを得ることができる. その結果, jを含むブロックを得る.
このようにしてjが存在し得る範囲をせばめることができる.
以上がf indclose(i)を計算するための主なアイデアである. (1)と(3)について
はf indclose(i)の範囲を1ブロック分にせばめただけである. しかし, そのブロッ
クをさらに小さなブロックに分割し同様のアイデアを適用することにより,さらに 範囲をせばめることができる. f indclose(i)の範囲が十分に小さくなった後, ユニ バーサルテーブルを用いることにより, f indclose(i)の値を計算する.
C.2 概要
本節では, f indclose(i)を計算するアルゴリズムの概要を述べる.
いくつかの準備からはじめよう.
116 付 録C findclose, findopen, enclose命令 入れ子構造をもった‘(’と‘)’からなる符号Sが与えられたとする. Sの長さを 2nとする. はじめに,符号Sを次のように3段階に分割する. まず,長さlg2nのブ ロックにSを分割する. 長さlg2nのブロックを大ブロックと呼ぶことにする. 次 に,各大ブロックを長さ4(lg lgn)2のブロックに分割する. このブロックを中ブロッ クと呼ぶことにする. さらに,各中ブロックを長さ2 lg lgnのブロックに分割する.
このブロックを小ブロックと呼ぶことにする.
S[i] = ‘(’であるようなS上の位置iが与えられたとき, j =f indclose(i)を次の ように計算する. はじめに, iを含む中ブロック内でjを探索する. もし, iとjが 同じ中ブロックに含まれているならば, このときにjの値を得る. そうでないなら ば, iと異なる中ブロックにjは含まれることが分かる. 次に, iと同じ大ブロック 内でjを探索する. もし, jが見つかればアルゴリズムは終了する. そうでないな らば, iと異なる大ブロックにjが含まれていることが分かる. 最後に, jを含む大 ブロックを計算し, その中でjを探索する.
説明が前後するが,はじめに,iとjが異なる大ブロックに含まれている場合につ いて説明する. 次に, iとjが同じ大ブロックに含まれているが, 異なる中ブロック に含まれている場合の探索方法を説明する. 最後に同じ中ブロックに含まれている 場合について説明する.
C.3 j = f indclose(i) を含む大ブロックの計算方法
S[i] = ‘(’であるようなS上の位置iが与えられたとし,S[i]はfarであるとする.
j =f indclose(i)とする. このとき, o(n) bit の補助テーブルを用いることにより, j =f indclose(i)をO(1)時間で計算する方法を説明する.
はじめに,jを含む大ブロックを計算する方法を説明する.
jを含む大ブロックを計算するために次の5つのテーブルを用いる.
テーブル1: 大ブロックについてのpioneer.
大ブロックについてpioneerであるような各S[i] = ‘(’に対して, S[i]と対応する
‘)’の位置を保存する.
テーブル2: pioneerな‘(’に関する長さ4(lg lgn)2のビットマップ.
pioneerな‘(’を含む全ての中ブロックに対して, 中ブロックのk番目の文字が
pioneerな‘(’であるならば, ‘1’, そうでないならば ‘0’であるようなビットマップ
を保存する. ビットマップの長さは中ブロックの長さと等しい.
テーブル3: 中ブロックについてのユニバーサルテーブル.
このテーブルは, 長さ4(lg lgn)2の2進符号についてのユニバーサルテーブルで
C.3. j =f indclose(i)を含む大ブロックの計算方法 117
ある. 長さ4(lg lgn)2の2進符号が取り得る全ての符号の各位置に対して, 直前に
出現する‘1’の位置を保存する. 直前に出現する‘1’がない場合は0を保存する.
テーブル4: 中ブロックについての直前のpioneerな‘(’.
M を中ブロックとし, M を含む大ブロックをBとする. Bの中でM の直前に
現れるpioneerな‘(’の位置を保存する. もし, Bの中にそのような‘(’がないなら
ば0を保存する.
テーブル5: 大ブロックについての直前のpioneerな‘(’.
各大ブロックに対して直前に現れるpioneerな‘(’の位置を保存する.
上記の補助テーブルを利用してjを含む大ブロックを計算する. 大ブロックに ついてfarな括弧S[i] = ‘(’が与えられたとする. 補題C.1.1より, S[i]の直前の
pioneerな‘(’に対応する‘)’とjとは同じ大ブロックに含まれている. したがって,
S[i]の直前のpioneerな‘(’が計算できたならば, テーブル1を使ってj を含むブ
ロックを計算できる. では, S[i]の直前のpioneerな‘(’を求めることを考えよう. i を含む中ブロックをMiとする. 次の3つのステップによりjを含む大ブロックを 計算することができる.
ステップ1: pioneerであるかどうかのチェック.
はじめに, S[i]がpioneerであるかどうかをテーブル1より調べる. もし, S[i]が
pioneerであるならば, テーブル1よりjの値を得る. そうでないならばステップ2
へ進む.
ステップ2: pioneerな‘(’をMiが含む場合.
iを含む中ブロックにpioneerな‘(’が含まれるかどうかをテーブル2より調べる.
もしMiがテーブル2のエントリに含まれていないならばMiはpioneerな‘(’を含 まない. その場合はステップ3へ進む. そうでないならば, iの直前のpioneerな‘(’
をMiの中から探し出すことを試みる. テーブル2より得られるMiのpioneerビッ トマップと位置iをテーブル3へ渡すことにより, iの直前のpioneerな‘(’の位置 を得る. もし, テーブル3から0を得たときは, iの直前のpioneerな‘(’が異なる中 ブロックに含まれることを意味する. そのような場合はステップ3へ進む.
ステップ3:
ステップ2までで,iの直前のpioneerな‘(’はMiの中にないことが分かった. Mi を含む大ブロックをBiとする. テーブル4より, iの直前のpioneerな‘(’がBiの 中にあるかどうかを調べる. もし見つからなかった場合, iの直前のpioneerな‘(’
はBiの中に含まれていないことになる. そのような場合, テーブル5より, Biの 直前のpioneerな‘(’を得る. これが, iの直前のpioneerな‘(’である.
118 付 録C findclose, findopen, enclose命令 それでは, テーブル1–5のサイズをそれぞれ見積もる. 各テーブルのサイズが
o(n) bit で抑えられることを示す. はじめにテーブル1について考える. 大ブロッ
クの個数はlgn2nなので,大ブロックに関するpioneerな‘(’の個数は高々2·lg2n2n−3 個である[17, 18]. したがって, テーブル1のエントリは高々O(lgn2n
)
個である. 各 エントリ当たりO(lgn) bitの記憶領域が必要なので, 全体の記憶領域はO(lgnn) bit である. 次に,テーブル2のサイズを見積もる. 大ブロックに関するpioneerな‘(’の 個数は高々2·lg2n2n−3個なので,テーブル2のサイズはO(lgn2n)·4(lg lgn)2 =O(lgnn) bit である. 次にテーブル3のサイズを見積もる. 長さ4(lg lgn)2の各符号がとり 得る全ての符号は24(lg lgn)2通りである. ここで, 24(lg lgn)2 =Aとおき,両辺のlg を とると次のようになる.
lgA = lg(24(lg lgn)2)
= 4(lg lgn)2
= 4(lg lgn)(lg lgn)
= lg (lgn)4(lg lgn)
したがって, 24(lg lgn)2 = (lgn)4(lg lgn)である. 2進符号の各位置について情報を覚 えるので, テーブル3の全エントリはO((lgn)4(lg lgn)(lg lgn)2)個である. 各エン トリにつきO(lg lg lgn) bit の記憶領域が必要となるので, テーブル3のサイズは O((lgn)4(lg lgn)(lg lgn)2lg lg lgn) bit である. 次にテーブル4を見積もる. テーブル 4のエントリは全ての中ブロックである. ゆえにO((lg lgnn)2)個である. 各エントリ 当たりO(lg lgn) bit 必要である. したがって, テーブル4のサイズはO(lg lgnn) bit である. 最後にテーブル5を見積もる. テーブル5のエントリ全ての大ブロックで ある. ゆえにO((lgnn)2)個である. 各エントリ当たりO(lgn) bit 必要である. した がって, テーブル4のサイズはO(lgnn) bit である.