付 録 C findclose, findopen, enclose 命令
C.5 far?
122 付 録C findclose, findopen, enclose命令 各エントリ当たりO(lg lgn) bit の記憶領域が必要なので, テーブル10のサイズは O(√
nlgnlg lgn) bitである. 最後に, テーブル11のサイズを見積もる. 長さがlg2n より長いexcessブロックの個数は符号全体で高々O(lgnn)個である. 各excessブ ロックのエントリは√
lgn個である. 各エントリにつきO(lg lgn) bitの記憶領域を 必要とする. ゆえに, テーブル11のサイズはO(lgnn·√
lgn·lg lgn)=O
(
n√lg lgn lgn
)
bit である.
以上により, 次がいえる.
補題 C.4.2 長さが2nの入れ子構造をもった符号S とfarでありpioneerでない
S[i] =‘(’が与えられたとする. このとき, o(n)bit の補助テーブルを利用すること
により, f indclose(i)をO(1)時間で計算できる.
C.5. far? 123 各中ブロックについて,ブロックの先頭の直前に出現するpioneerな‘(’を保存す る. 直前に出現するpioneerな‘(’が同じ大ブロックにない場合は特別な値として0 を保存する.
テーブル14: 各中ブロックに対するlef texcessの値.
各中ブロックM について, M を含む大ブロックの先頭からM の先頭のまでの lef texcess値(M の先頭は含まない)を保存する.
テーブル15: 各小ブロックに対するlef texcessの値.
各小ブロックTについて,Tを含む中ブロックの先頭からTの先頭までのlef texcess の値(T の先頭は含まない)を保存する.
テーブル16: 各小ブロックに対する直前のpioneerな‘(’.
各小ブロックT について,T の先頭の直前に現れるpioneerな‘(’を保存する. も し, そのような‘(’がT を含む中ブロックの中にないならば, 特別な値として0を 保存する.
テーブル17: pioneerな‘(’を含む小ブロックのビットマップ.
pioneerな‘(’を含む小ブロックそれぞれについて, (1) 長さが小ブロックと等し
く, (2) pioneerな‘(’と対応する位置‘1’, (3) そうでないならば‘0’であるような ビットマップを保存する.
テーブル18: サイズ2(lg lgn)の符号に対するユニバーサルテーブル
長さ2(lg lgn)の符号が取り得る全ての符号の各位置k, 1 ≤ k ≤ 2(lg lgn)に対 して次の2つの値を保存する.
(1) 直前の‘1’の位置(符号中になければ0を保存する).
(2) 符号の先頭からkまでのlef texcessの値(kは含まない).
テーブル19: 中ブロックに対するユニバーサルテーブル.
長さが4(lg lgn)2の2進符号がとり得る全ての符号の各位置kについて, S[k]が
中ブロックに関してfarでないならばf indclose[k]の値を保存する. そうでないな らば特別な値として0を保存する.
計算方法は次のようになる.
長さ 2n の入れ子構造をもった符号とS[i] = ‘(’が与えられたとする. j = f indclose(i)と表記する. はじめに, テーブル19によりS[i]が中ブロックに関して farであるかどうか調べる. テーブル19よりj = f indclose(i)の値を得たならば S[i]は大ブロックに関してfarでない. そうでない場合を考えよう. 次に,S[i]が中 ブロックに関してpioneerであるかどうか調べる. もしpioneerであるならばテー
124 付 録C findclose, findopen, enclose命令 ブル12よりjを得るのでS[i]がpioneerであるかどうか判断できる. そうでない 場合を考えよう. この場合は,直前のpioneerを計算することにより, jが属す中ブ ロックを得る. 得られたブロックが仮想ブロックであるならば, S[i]はfarである.
そうでないならばS[i]はfarでない.
S[i]がfarでない場合は, C.4節の方法と同様にしてf indclose(i)を計算できる.
計算のアイデアは次のようなものである. 補題C.4.1より, jを含む中ブロックMj の中でe =lef texcess(i)であるような位置のうち最小のものがjである. Mj の最 初と最後の位置をs, tとする. e0 =e−rightexcess(t+ 1)とする. このとき, jは, S[s, t]の中でrightexcessがe0であるような‘)’の位置のうち最小のものである. い くつかのテーブルを利用してこのような位置を計算する.
次の3つのテーブルを利用する. これらのテーブルはテーブル9–11と同様で ある.
テーブル20: √
lg lgnの倍数のrighexcessをとる位置.
各√
lg lgnの倍数k√
lg lgn(k = 1,2, . . .)について,中ブロックの中でrightexcess がk√
lg lgnであるような‘)’の位置のうち最小のものを保存する.
このテーブルにより, 各中ブロックをいくつかのブロックに分割できたことに なる. このようにして得られたブロックを中ブロックに関するexcessブロックと 呼ぶ.
テーブル21: 長さが高々lg lg2 n bit のexcessブロックについて.
長さが高々lg lg2 n bit の excessブロックに対してユニバーサルテーブルを用意
する. 長さ lg lg2 n bit の符号が取り得る全ての符号上で次の値を保存する. 各e
(e= 1,2, . . . ,√
lg lgn−1)について, rightexcessがeであるような‘)’の位置のう ち最小の位置を保存する.
テーブル22: 長さがlg lg2nより長いexcessブロックについて.
長さが lg lg2n より長い各excessブロックに対して次の値を保存する. 各e (e =
1,2, . . . ,√
lg lgn−1)について, rightexcessがeであるような‘)’の位置のうち最 小の位置を保存する.
以上のテーブルを利用して,指定した中ブロック内のj =f indclose(i)の値を計 算できる.
中ブロックに関してfarで, かつ, pioneerでないS[i] = ‘(’とjを含む中ブロッ クMj が与えられたとする. はじめに, C.4節で説明した方法によりlef texcess(i) を計算する. e = lef texcess(i)とする. 次に, Mj 中に含まれるj の値を計算す る. Mj の最後の位置をtとすると目的の ‘)’は, Mj の中でrightexcessがe0 = e−rightexcess(t+ 1)の‘)’のうち最小の位置をもつものである. e0が√
lg lgnの
C.5. far? 125 倍数であるならばテーブル20より解を得る. そうでないならば,jを含むexcessブ ロックの長さをテーブル20より計算し, その長さがlg lg2 n以下ならばテーブル21 より解を求め, lg lg2nより長いならばテーブル22より解を求めることができる.
それでは各テーブルのサイズを見積もる.
はじめにテーブル 12について考える. 各大ブロックは, 中ブロックに関する pioneerな‘(’を24(lg lglg2nn)2−3 =O((lg lglg2nn)2)個含む. 大ブロックの個数はO(lgn2n
)
な ので,テーブル12のエントリはO((lg lgnn)2)個である. 各エントリ当たりO(lg lgn) bit の記憶領域が必要なので, テーブル12のサイズはO(lg lgnn) bit である. 次に, テーブル13のサイズを見積もる. 各大ブロックはO((lg lglg2n)n2
)
個の中ブロックを含 み,大ブロックの個数はO(lgn2n
)
なので,テーブル13のエントリはO((lg lgnn)2
)
個で ある. 各エントリ当たりO(lg lgn) bitの記憶領域が必要なので,テーブル13のサイ ズはO
( n lg lgn
)
bit である. テーブル14も同様に見積もることができる. 次に,テー ブル15について考える. 符号S中に含まれる中ブロックの個数はO((lg lgnn)2
)
であ る. 各中ブロックに含まれる小ブロックの個数はO(lg lgn)個である. よって,テー ブル15のエントリはO(lg lgnn)個である. 各エントリ当たりlg lg lgnbitの記憶領域 が必要なので, テーブル15のサイズはO(nlg lg lglg lgnn)bitである. テーブル16も同様 に見積もることができる. 次に,テーブル17について考える. 各大ブロックは,高々 O((lg lglg2nn)2
)
個の中ブロックに関するpioneerな‘(’を含む. したがって,各大ブロッ クにつき長さO(lg lgn) bitのビットマップを高々O((lg lglg2nn)2
)
個だけ保存する. した がって,テーブル17のサイズは,O(lgn2n
)·O((lg lglg2nn)2
)·O(lg lgn) =O(lg lgnn)bitで ある. 次にテーブル18について考える. テーブル18のエントリはO(22 lg lgnlg lgn) 個であり,各エントリ当たりlg lg lgn bit の記憶領域が必要なので,テーブル18の サイズはO(22 lg lgnlg lgnlg lg lgn) bit である. ここで, 22 lg lgn = lg2nである. な ぜならば, A= 22 lg lgnとして両辺のlg をとると,
lgA = lg 22 lg lgn
= 2 lg lgn
= lg lg2n
となるからである. ゆえに, テーブル18のサイズはO(lg2nlg lgnlg lg lgn) bitで ある. テーブル19のサイズはテーブル3と同様である. 次に, テーブル20のサ イズを見積もる. 各中ブロックに対してO
(
(lg lg√ n)2 lg lgn
)
個のエントリがあり, 各エ
ントリはO(lg lg lgn) bit の記憶領域を必要とする. よって, 必要な記憶領域は
O
(
(lg lg√n)2lg lg lgn lg lgn
)
bit である. 符号全体で中ブロックの個数はO(lgn2n· (lg lglg2n)2)= 個なので, テーブル20のサイズはO
(
nlg lg lg√ n lg lgn
)
bit である. 次にテーブル21の
126 付 録C findclose, findopen, enclose命令 サイズを見積もる. テーブル21のエントリはO(2lg lg2nlg lgn) bit である. 各エ ントリにつきO(lg lg lgn) bit の記憶領域が必要なので,テーブル21の記憶領域は O(2lg lg2n lg lgnlg lg lgn)bitである. 2lg lg 22 =√
lgnなのでO(√
lgnlg lgnlg lg lgn) bitである. 最後にテーブル22のサイズを見積もる. 各中ブロックは,長さがlg lg2 nよ り長いexcessブロックを高々O((lg lg(lg lgn)/2n)2 )個もつ. 各エントリについてO(lg lg lgn) bit の記憶領域が必要なので, 各中ブロックに対してO(lg lgnlg lg lgn) bit の記 憶領域が必要である. よって, 符号全体ではO(lg lgnlg lg lgn·(lg lglg2nn)2 · lgn2n) = O(nlg lg lglg lgnn) bit の記憶領域が必要である.
以上の議論により,次の補題を得る.
補題 C.5.1 長さ2nの入れ子構造をもった符号と, S[i] = ‘(’が与えられたとき, o(n) bit の補助テーブルを利用することにより, S[i]がfarであるかどうかをO(1) 時間で調べることができる.
C.6 まとめ
本節はf indclose命令のまとめを行う. 長さ2n bit の入れ子構造をもった符号S
とS[i] = ‘(’が与えられたとき, j =f indclose(i)を次のようにして計算できる.
はじめにiを含む中ブロックの中にjが含まれるかどうかをテーブル19を使っ て調べる. もし, iとjが同じ中ブロックに含まれていたならばテーブル19よりj の値を得る. そうでない場合を考えよう. この場合, iが大ブロックに関してfarで あるかどうかをC.5節の方法を用いて調べる. iが大ブロックに関してfarでない ならばC.5節の方法によりjの値を得る. iが大ブロックに関してfarである場合 を考えよう. そのような場合は, C.3節の方法によりjを含む大ブロックを計算し, C.4節の方法によりjの値を得る.
次の定理を得る.
定理 C.6.1 長さ2nの入れ子構造をもった符号Sと, S[i] =‘(’が与えられたとき, o(n) bit の補助テーブルを利用することにより, f indclose(i)をO(1)時間で計算で きる.
同様にして, f indopen命令も計算できる. 次の定理を得る.
定理 C.6.2 長さ2nの入れ子構造をもった符号と, S[i] = ‘)’が与えられたとき, o(n) bit の補助テーブルを利用することにより, f indopen(i)をO(1)時間で計算で きる.