0 一

D

且

a m e e r

'EA

︑ 目矛・ '

tL rA

e a

r‑

‑は

e

u ‑

づ

' hU

吋U

︑o C

円l J 2・g・置 ︑

可

To bucket 2

{ j o b }

pointer to the next

separated tree

v t r e e m a P 2 : ￨ o l o l 1 1 1 f l l

￨ t l 1 1 1 1 1 1 i 1 1 1 1 0 1

s e p a r a t e d t r e e 2

To bucket 5

{ z o o } leafmaPJ l e a f m a P 2 :

B̲TBL ₁ ^: ^b ^u ^c ^k ^e ^t ^a ^d ^d ^r ^e ^s ^s ^f ^o ^r ¹

v v 2 b u c k e t a d d r e s s f o r 2

To bucket

3

To bucket

4 3 1 ^‑2 { p e n } { s e a ， s u n }

4~蹴ta蜘ss ^f ^o ^r ⁵

図

4 . 3

図

3 . 1

の

BDS

木を基にした階層化

BDS

木

B̲TBL _2: 1 I b u c k e t a d d r e s s f o r 3

4 . 3 . 2 階層化 BDS 木の圧縮法 2 I b u c k e t a d d r e s s f o r 4

階層化

BDS

木の第 i番目の分割木に対する先行順ピット列は，

分割木の状態を示す treemα，Pi;

葉の状態を示すleafmαPi;

バケットのアドレスを格納したパケット表B..TBL_i1Pら構成される.

図

4 . 4

図

4 . 3

の階層化

BDS

木に対する先行順ピット列

但し，次の分割木へのポインタとなる内部ノードを菜とみなし，その来に対応する tr('('rnapi とleαfmαPiのピット値は 1とし，バケット表中には次の分割木書号にマイナスをイ

J

けた

偵を格納する.図

4 . 3

の階層化

BDS

木に対する先行順ピット列を図

4

.4に示す.ここで，

treemαPiの上部に記述される<>内の値は，分割木へのポインタとなる内部ノード番号を表す.

第4章 2進ディジタル探索(BD8)木の改善

4 . 3 . 3 階層化 BDS 木の検索アルゴリズム

以下に，先行順ピット列を用いた階層化BD8木の検索アルゴリズムを示す.但し，次のような変数を用いる.

key .検索キー ;

i :現在探索している分割木の番号，初期状態として lに設定される;

keypos :瓦(key)における現在処理中のピット位置;

treepos : treemαPiにおける現在処理中のピット位置;

leαfpos : leαfmapiにおける現在処理中のビット位置;

仇dex : B̲TBLl内の検索すべきスロット番号;

αddress : B..T BLiより求められるパケットのアドレス;

{先行順ビット列を用いた階層化BD8木の検索アルゴリズム]

入力:key : :検索すべきキー;

出力:検索成功ならばTRUE，失敗ならばFALSE;

手順(8'‑1) : {各変数の初期化}

keypos

←

¹^，^t^r^e^e^p^o^s

←

¹^，^l^e^α^f^p^o^s

←

1 ; 手順(8'‑2) : {分割されたハッシュ値の検証}

Hi(key)のkeypos位置のピット値が1ならば手II}買(8'‑3)に，ピット値がOならば手I}頂(8'‑4)に進む;

手順(8'^軍 3) : {左部分木のスキップ処理}

treemαPi上の treepos位置から， 1のピット数がOのピット数より lつ多くなるまでかeepo.'3を進めた後，手順(8'‑4)に進む;

手1)慎(8'‑4) : {枝を lつ辿る処理}

treeposの位置を lつ進めた後，treemαPi上のtreepos位置のピット値が

o

(内部ノード)ならばkeyposの位置を lつ進め，手順(8'‑2)に戻り，ピット値が1(外部ノード)ならば手順(8'‑5)に進む;

4.3. 階層化による時間効率の改善手順(8'‑5) : {菜の状態がダミーか非ダミーかの検証}

treemαPi上で、先頭ピットから treepos位置までに存在するピット値 1のピット数をカウントし，その値を leαJposに代入する;

leαJmαPt上のleαfpos位置のピット値が

o

(ダミーリーフ)ならば FAL8Eを返し，

1 (非ダミーリーフ)ならば手I}頂(8'‑6)に進む;

手順 (8'‑6) : {パケットアドレスの獲得処理}

leαfmαPi上で、先頭ピットから leafpos位置までに存在するピット値が 1のピット数をカウントし，その値を indexに代入した後，B..T BL

i [

index]を参照し対応するバケットのアドレスを αddressに獲得する;

得られたαddressが負ならば手I}頂(8'‑7)，正ならば手順(8'‑8)を行う;

手順 (8'‑7) : {バケット内でのキーの検索}

αddressで、参照されるパケット内にkeyが存在すればTRUE，存在しなければFAL8E を返す;

先行順ピット列に表現された階層化BDS木の検索アルゴリズムは，基本的には従来の BD8木の検索アルゴリズムと同じである.しかしながら，通常は各パケットアドレスを蓄える B̲TBLtに各分割木の番号が負数として格納されているため，手II}夏(S'‑6)でB̲TBLi からパケットアドレスを獲得する際に，負数ならば分割木番号を獲得した後，対応する分割j木に検索処理を移す手lft買が追加される.

例として図 4.4の先行順ピット列からキ‑upen7Fを検索する手順を図 4.5‑‑‑‑図 4.8に従って，以下に示す.但し，初期状態として iの値は lとする.

手順(8'ー1) : keypos=l， treepos=l， leafpos=l;

手1)慎(8'・

2 ) :

H1(pen)=lOの第1ピット値がlなので手順 (S'・3)に進む;

手順(8'‑3) :図 4.2示される階層化BD8木において，分割木lのノード番号2をルートとする部分木をスキップし，treepos=4とする;

手順(8'‑4) :ノード番号3に進むため，treepos=5とした後，treemαPlの第5ビット値が Oなので，keypos=2とし，手II}買(8'‑2)に戻る(図 4.5) ;

手)11買 (8'‑2) : Hl (pen)=10の第2ピット値がOなので手1)頂(8'‑4)に進む;

第 4 ヰ~ 2進ディジタル探索 (sD8)木のL次予子 4.3. 階居化による時間効，干の改許可

H， (pen) ~ ~ I

，t.ypo.，

B TBL t: I

leafmap，

匝ヰ日

TobLkct2

(job)

同岡

n 山

q du

九UPU

‑ ‑ ‑

v附

∞

h山ヲι

申M 哩

To bucket 2

(job) TobudV .CI I

(cat. ear)

U‑ 3

P LV

汀・

AU P Lw

To b.:!:ket 3

{pcn}

To bu可cket <1

{s巴a.sunl

噌 Tob¥luCI I

[cat.ωj

To buV cket 5

(z∞l

indcx TobuιIV cet 3

{I光nl

To buV cket 4 {sea， sun}

図 4.5 図 4.4の先行順ピット列上でのキー pcn"の検索説明以JA ^凶4.7 図 4.4の先行順ピット列上でのキー pen"の検索説明図C

H， (pen) : I 9

t:cypos

{4) (5) [3J [4] [d] treemapz: 101011 11111

京、;け

町冒p伺

Hl(P

川:ミ 2

k今附 lreemap， : ⁽¹⁾⁽²⁾¹¹^]¹²¹⁽³⁾ <4>1.5)

101011111011111

、↑

t=po .<

。

Tobム回l {回t，出}

To buV clcet 2 tjob)

Tob[z匹∞v k回I 5leafmaOt .̲̲....‑1"

I T I I I I

囚

可胃 To bucke! ) To bl耳k回4

{pen} {s回，sun}

‑ }

剖M

nl v

同 '

.0 C

つ{

To bV uck目2

(job)

Tob凶官k剖5

(z∞}

fmapz: ~

Tobtkt3 (pen)

‑‑

d凶LAea

v k i

LDnd

o t

ThH 2 1 bucket address for 4 index

図4.6 図4.4の先行順ビット列上でのキー pen"の検索説明図B

手順 (S'‑4) :ノード番号4に進むため，treepos=6とした後，treemαPlの第 6ピットイlQ が lなので，手1)1買(8'‑5)に進む(図 4.6) ;

手1)頂(S'‑5) : treemαPlの第 lピットから第6ピットまでに値が 1のピットが3伺存在し，更に，leαfmαPlの第3ピット値が lなので手順 (8'‑6)に進む;

手順(S'‑6) : leafmaplの第Iピットから第3ピットまでに値がlのピットが3佃存在するので，index=3とし，B̲TBL

r [

3]を参照すると αddre88=‑2を符るが，その他

判 4.8 図4.4の先行順ピット列上でのキー pen"の検索説明図D

が負なので手順(8'‑7)を行う;

手順(S'‑7) : i= 2に変更し，手順(8'‑1)に戻る(図 4.7) ; 以後，分割j木2に対して分割木lと同様の走査を行う・

手順(S'‑I) : keypos= ，l treepos二 1，leαfpos=l ;

手順 (S'‑2) : H2(pen)=OOの第1ビット値がOなので手I}頂(8'‑4)に進む;

第4章 2進ディジタル探索 (BDS)木の改善 4.3. 階層化による時間効率の改善

手順(S'‑4) :ノード番号5に進むためt trcepos=2とした後，trecmαP2の第 2ピット伯がOなので，keypos=2とし，手順 (8'‑2)に戻る;

手順(S'‑2) : H₂(pen)=OOの第2ビット値がOなので手順 (8'‑4)に進む;

手JI[貢(S'‑4) :葉3に進むため，trccpos=3とした後.treemαP2の第3ピット値が 1なので，手順 (8'‑5)に進む;

手順(S'‑5) : treemαP2の第 lピットから第3ピットまでに値が lのピットが l佃あり，

更に，leα1mαP2の第 1ピット値がIなので手順 (8'‑6)に進む;

手順 (S'‑6) :leα1mαP2の第 lピット値がlなのでindex^二 1とし .B̲TsL2山からバケツト3のアドレスを得る(図 4.8) ;

s e p a r a t e d t r e e 1

V To bucket 1

{ c a t ， e a r }

V

To bucket 2

{ j o b }

pointer to the next

separ~~~d tree ~

To bucket 5

{ z o o }

手順

( S ' ‑ 8 )

:パケット

3

にkey=pen"が合まれているので，

TRUE

を返す;

s e p a r a t e d t r e e 2

また，特にキー ZOO"(H(zoo)=ll・..)の検索の場合.BD8木では先行順ピット列卜.のすべてのピットを走査する必要があったが，階層化BD8木では分割木lのみのピットをえ

査するがけで検索が行われるため，従来の BD8木に比べて検索時間が大幅に短縮される. pointer to the next

y

separated甘ee To bucket 3

{ p e n }

4 . 3 . 4 階層化 BDS 木の更新アルゴリズム

階層化BDS木の更新方法は， 3. 2で述べたBDS木の場合と同じく 3種類に分類される.ここでは，その中でもキー挿入後パケットがオーバーフローを起こし，パケットを分割する場合の処理について説明し，その他の場合は，簡単のため説明を省略する.まず，

図 4.3の階層化BD8木にキー sit"(H(sit)=10 / 01 / 10"')追加後の階層化BDS木を図4.9に示す.

登録キーを追加した後パケットがオーバーフローを起こした場合， BDS木では次の操作をオーバーフローが起こらなくなるまで繰り返す.まず，オーバーフローを起こしたバケット(フルパケットと呼ぶ)に対応した外部ノードを単位木に変換した後，フルパケット内のキー及び登録キーを単位木内のダミーリーフに割り振る.これに対して， [併層化BDS木においては，単位木を生成する際に，各分割木の高さが分訓深さを越える旬:に新しい分割木を生成する必要がある.

先行順ピット列を用いた階層化BDS木の更新処理は，単位木を点すピットダJI"011"とダミーリーフを表すピット夢JI"00"をtreemαPi.leα1mα，Piに適時挿入することになる. ま

v d

m d 3 u l

︐ . A U ρ l v

e

γA

e

φEL

a

紅

n r

ρしV

To buY cket 4

{ s e a ， s i t }

句

To bucket 6

{ s u n }

院14.9 図 4.3の階層化BDS木にキー sitηを挿入後の階層化BDS木

た，木の深さが分割深さを匙える毎に，新たな分割木に対する先行1)慎ビット列を生成する必要がある.以下に階層化BDS木の更新アルゴリズムを示す.但し，以下のような変数，

及び関数を用いる.

第

4 1

主

2

進ディジタル探会

( s D S )

本の改汚

λ‑̲S ET : B ̲S I Z E

+

1 f闘のキーから成るキ-~合;

scpa̲dcpth :分前深さ;

fulLdepth :フルバケットを示す業までの木の深さ ; AfOD(η

，

m) : nをmで割った余りを返す関数 ;

Separαte(η) :n番目の分割木の下に新たな分割木へのポインターを繋ぎ (B

: r

sL内に次の分割木番号に負数を付けた値を格納する)，その分割

l

木の香号を返す関数 ; SepαStoreI{ ey (n

，

f lαg

，

key) : flαgの値に従って，η香口のB̲TBLを更新し，バケツ

ト内に keyを格納する関数;

尚，更新は検索後に行われ，i， treepos

，

leafpos

，

index

，

fulLdσpth¹は検索の結洪，フルパケットに対応した位置を示しているものとする..

【先行順ビット列を用いた階層化BDS木の更新アルゴリズム} 入力:key :検索の後，登録されるキー;

出力:なし;

手順(1'‑1) : {フルパケット内のクリア}

フルパケット内のキーと登録キーをK̲SETに代入し，フルパケット内を空にする;

手順(1'‑2) : {新たな分割木の生成処理}

M O D(fulldepth

，

sepαdepth)=Oならば，

←

Separαte( i)， treepos

←

¹， leαfpos

←

1， index

←

1 ; 手順 (1'‑3) : {単位木の挿入処理}

treemαPi上のtreepos位置のピット値を

0 1 1

円に，

leαfmαPi上の leαfpos位置のビットを

0 0 "

に変更し，

full̲depth

←

fulLdepth+ 1とする;

手IJ慎(1'‑4) : {再オーバーフローを起こす場合の処理}

K̲SET内のキーにおいて，fulLdepth番目のピット値がすべてOならば，左の枝をlつ辿るため，

1 full̲depthは手I}国(S'‑4)でカウントすることによって設定する.

4.3.

I

常貯化による時間五力不の改汚 tT^，⁽^CjJO・・ち f trpcpos+l

とした後，手順(1'‑2)に反り，fulLdepth各二日のピット値がすべて 1ならば，むの伎を1つ辿るため，

tr^肘 po

芯 ←

tr引?P08十2 lpαfpos

←

leαfpo^.^'^J+1

とした後，下l}頂(1'‑2)に戻る ;

また，full̲depth呑日のピット値が異なれば，手順(1'‑5)に進む ; 手IJ慎(1'‑5) : {K ̲SET内の各キーの格納処理}

K̲SETからキーをl個取り出し，それをkeyとする;

H(kpy)のfull̲depth位置のピット値がOならば，

SepαStoreK ey( i，left

ぺ

key)を行い，

ピット値が1ならば，SepαStoreK ey( i， "right"， key)を行う;

手順(1'‑6) : {終了判定処理}

K̲SET=0ならば処理を終了し，そうでなければ手順(1'‑5)に戻る;

上記の更新アルゴリズムは，

BDS

木の更新アルゴリズムを各分割木の先行順ビット列に対して適用したものであり，基本的には同じである.しかしながら，手順 (1'‑2)において，フルパケットを指し示す葉までの深さが分割深さを越える度に木構造を分割する処理，即ち，新たな分割木に対する先行順ピット列の生成とそれに伴う B̲TBLの更新処理が追加される.

次に，関数Sepαγαte(n)の処理手順を示す.但し，次の変数を用いる. mαx̲ηum :現在までに使用されている分割木番号の最大値;

{関数Sepαrate(n)のアルゴリズム】入力:

n :

処理対象となる分割木の番号;

出力:ポインターで繋がれた新たな分割木の番号 ;

手順(sp‑1) : {新たな分割木へのポインターを持つ内部ノードの設定}

leαfmαPn上の lcαfpos位置のピット値を lに変更する;

手順(sp‑2) : {新たな分割木へのポインターを作成}

B̲T BLn[index]

←

‑1 X (mαx̲num+1) ;

第4章 2進ディジタル探索 (BDS)木の改善

手順(sp‑3) : {分割木番号の最大値を更新}

mαx̲ηumの値を 1つ増加した後，そのmαx̲numのイ直を返す;

また，関数SepαStoreKey(n，flag， key)の処理手)11買を以下に示す.{Q̲し，関数内で用いる変数full̲bucketおよびfree̲bucketは，関数StoreKeyで用いたものと同じである.

【関数SepαStoreKey(η

，

flag

，

key)のアルゴリズム}

入力:flα9 :左右どちらの葉に対応したパケットに登録するかを示すフラグ;

key:検索の後，登録されるキー;

出力:なし;

手順(ss‑l) : {flαgの判定処理}

flag="left"ならば手1)頂(88‑2)を，flαg=right"ならば手順(8s‑3)を行う;

手順(ss‑2) : {左の葉に対応したパケットへの keyの絡納処理) leαfmαPn上のたαfpos番目のピット値を 1に変更し，

B̲T BLn[index]

←

^fulLbucket^{とした後，}

fulLbucketで参照されるパケットに keyを格納する;

手順(ss‑3) : {右の葉に対応したパケットへの keyの格納処理}

leαfmαpη上のたαfpos+1番目のビット値を 1に変更し，

B̲TBLπ内のindex+1番目以降の要素を 1つ後方にずらし，

B̲TBLη[index+1] +‑‑free̲bucketとした後，

free̲bucketで参照されるバケットに keyを格納する;

次に，例として図 4.4の先行順ピット列にキー sit"(H(8it)= 10

1

⁰¹

1 1 0

… ) をな録する場合の各ビット値の変化の過程を図 4.10‑‑‑図 4.12に示しその処理下}II買を説明する.

尚，キー sit"を検索した後の各変数値は，図4，10に示すように treemαP2

，

lωfmap2に対して，treepos=4， leαfpos=2， fulLdepth=4， index=2となっている.但し，sepα̲depth

の値は 2とする.

手順(1'‑1) : K̲SET={sea

，

8Ull， sit}とし，フルパケット(パケット 1)内を空にする;

手順(1'‑2) : MOD(fulLdepth， sepa̲depth)=MOD(4， 2)=0より，Separαte(2)が行われる ;

手順(sp‑1) : leafrnαP2のleαfpos位置，第2ピット値を 1に変史する;

4.3. 階層化による時間効宅の改善

leafmaP2

B̲TBL₂

dummy leaf dummy leaf

(4) (5) [3J [4J [d]

0 0 1 1 1

o

1 1 1 1 0

O T _o

図 4.10 単位木の追加説明図

(4) (5) [3] <6> [d] z ^0 0

I

treemaP2 0 0 1 1 1

separatl凶 tr田 3

bUl当ket4 full bucket

一ア ‑

leafmaP2 1 1 0 B̲TBL₂

treemaP3 leafmaP3

I h，，~L，~令。|

(6) [dJ [4]

0 1 1

o

1 1

o

0↑O

図 4.11 再オーバーフローの説明図

手順 (sp‑2) : m ω̲num=2とすると，BIBL2^のindex番目のスロットをBIBL2[2]=‑1

X (2+1) =‑3に変更する;

手順 (sp‑3) : m，αx̲num=3 ;

手]11買(1'‑2) : i=3， treepos=l， leαfpos=l， index=lに変更される;

手]11買(1'‑3) :分割木3として単位木が生成され，

treemαP3ニ011，leαfmαP3=00， fulLdepth=4+ 1=5とする;

ドキュメント内 2進ディジタル探索木を用いた辞書検索法とその応用に関する研究 (ページ 33-39)

D

a m e e r

e a

e

u ‑

{ j o b }

v t r e e m a P 2 : ￨ o l o l 1 1 1 f l l

￨ t l 1 1 1 1 1 1 i 1 1 1 1 0 1

s e p a r a t e d t r e e 2

{ z o o } leafmaPJ l e a f m a P 2 :

B̲TBL 1 : b u c k e t a d d r e s s f o r 1

v v 2 b u c k e t a d d r e s s f o r 2

3

4

3 1 ‑2 { p e n } { s e a ， s u n }

4~蹴ta蜘ss f o r 5

4 . 3

3 . 1

BDS

BDS

B̲TBL 2: 1 I b u c k e t a d d r e s s f o r 3

4 . 3 . 2 階層化 BDS 木の圧縮法 2 I b u c k e t a d d r e s s f o r 4

BDS

4 . 4

4 . 3

BDS

J

4 . 3

BDS

4

4 . 3 . 3 階層化 BDS 木の検索アルゴリズム

←

←

←

o

o

i [

2 ) :

匝ヰ日

川:ミ 2

。

I T I I I I

r [

s e p a r a t e d t r e e 1

{ c a t ， e a r }

V

{ j o b }

{ z o o }

( S ' ‑ 8 )

3

TRUE

s e p a r a t e d t r e e 2

y

{ p e n }

4 . 3 . 4 階層化 BDS 木の更新アルゴリズム

v d

e

e

a

{ s e a ， s i t }

{ s u n }

4 1

2

( s D S )

+

，

: r

l

，

，

，

，

，

，

←

←

←

←

0 1 1

B̲TBL ₁ ^: ^b ^u ^c ^k ^e ^t ^a ^d ^d ^r ^e ^s ^s ^f ^o ^r ¹

3 1 ^‑2 { p e n } { s e a ， s u n }

4~蹴ta蜘ss ^f ^o ^r ⁵

B̲TBL _2: 1 I b u c k e t a d d r e s s f o r 3

O T _o

一ア ‑