; 固

第4章 2進ディジタル探索 (BDS)木の改善 4.4.  パトリシアトライへの拡I炭による空間効宅の改必

buckct 1 bucket2 

't

‑q

ι 

1・l

e‑ c 

k‑k ﹁

tw

‑ P︑

u

‑ u  

LU‑hu rE‑rI 

o‑ o 

cd

圃 官

︑d

eぉ‑P3 9 i v

‑

・v‑vaPしv

Au

‑A u 

du

‑A

u 

a‑ a 

まず， ( 1 )は何人キーに対応するパケットが見つかり，そのパケットに登録済みのキー 数が B̲SIZE‑1以下の場合である.この場合は，単純に挿入キーをそのパケットにそそ 録するだけで実現できる.

また， ( 2 )は

t

iP入キーに対応するパケットは見つかるのだが，そのパケットには既に

s̲SIZE偶のキーが登録されている場合である.この場合は， 3.  5で示したOrdinary BDS木の更新処理と同線に，オーバーフローを起こしたバケットに対応する葉を内部ノー

ドに変換する必変ーがある.但し， Ordinary BDS木では，パケット内に格納されるべきキー の共通桜頭部分を校として生成し，その下に新たな 2つの葉を追加していたが，パトリシ アBDS木の場合には，フルパケット以下の共通接頭部分は 1個の内部ノードとしてのみ 牛^a成し，共通ピット値，あるいは，共通ピットの個数は削除ノードに関する情報として，

柿助的に格納する必要がある.そして 新たに生成された内部ノードの下に 2つの葉を追 加し，追加された業に対応した新たなパケットをそれぞれ生成し，各パケットにキーを分 類格納することになる.

1在後に， ( 3 )は検索の結果パケットには辿り着くのであるが，そのパケットが挿入キー を絡納すべきパケットではない場合である.つまり，本手法で用いるパトリシア構造で は，削除ノードに関する情報として，削除ノードに対するピット値そのものではなく，削 除ノードの個数のみが保持されている.そのため，検索処理において削除ノードを含む内 部ノードを辿る際には，キーとなるピット列を削除ノードの個数分スキップするだけで，

スキップされたピット値の検証は行っていない.登録済みのキーを検索する場合には，こ のような処理で支障ないが， (更新処理の前処理として行われる)未登録語を検索する場 合には，実際の削除ノード値と異なるピット値がマッチングされてしまう可能性がある.

このようなミスマッチングをフォルスドロップ (falsedrop)と呼ぶ.もし，フォルスド ロップが起こった後に辿り着いたパケットに挿入キーを登録すれば，削除ノードに関する 情報の一意性が欠われてしまうため，正しい検索処理ができなくなる.

そこで， ( 3 )のような場合には，まず，フォルスドロップが発生した内部ノードを確 定する.そして，その内部ノードの親ノードとして新たな内部ノードを作成し，新たな内 部ノードに対応する校と葉を 1個ずつ生成した後，それぞれの内部ノードに対応する削除 ノード数を割り振ることになる.

次に， (1)‑‑‑(3) の各処理への分類方法，また， ( 3 )の処理において如何にしてフォ ルスドロップが発生したノードを発見するか，更に，削除ノードの割り振り方等の詳細に

直歯 ^{( 凶}

第4章 2進ディジタル探索(BDS)木の改善 ついて説明する.

まず，挿入キーは検索の後，未登録語と判定されるのだが，その帰入キーを η長のピッ ト列X として以下のように定義する;

.)(  = Xo Xl X2… Zπ‑1 

但し，Xi (0

三

t

三

η ‑1)は， 0または1のピット値を表す.

また，検索の結果，辿り着いたパケットに既に登録されている任意のキーを m 長のピッ ト列Bとして以下のように定義する;

B = bo b₁ b2… b_{m ‑t} 

但し，b_i (0三 i

: S

m‑1)は， 0または 1のピット値を表す.

次に，ピ ット夢JI

X

とBとのピット単位の比較演算を行い，双方とも第αピット目まで がすべて同一値であったと仮定する.~p ち，以下のようにピット列 X と B とを以下のよ

うに再定義すると，

x 

= Xo Xl X2…Zαー1Xα…Xn‑l 

B二 bob1 b2…αb‑1 bα… bm‑1 

但し，Xo = bo， Xl = b1，...，  Xα‑1 = b^α‑1， Xα#b^α，...とする.

尚，この段階で行われるピット単位の比較演算は，ピット列XとBとの排他的論理和 を求めることにより実現でき，演算結果がOのピットは双方とも同一値であり， 1のピッ トは異なる値を持つことになる.~p ち，排他的論理和の演算結果において，最初にピット 値 1が出現するピット位置がα+1となる.

ここで，ビットヂIJsが格納されているバケットに対応する葉までの木の深さをd(O三d

三

m ‑ 1)とする.但し，dはOrdinaryBDS木での木の深さを表すものとし，dの値は，パトリ

シア BDS木でのバケットまでの深さに，そのパケットまでの経路に含まれる削除ノード 数を加えることにより求める.

そして，dとαとの大小関係より，以下のように各極処理に分類する.但し，検ポの結 果辿り着いたパケットに既に登録済みのキー数を

K

̲N

UM

とする.

. d

壬 α，かつ，

K

̲N

UM  <  B

̲S

IZE

ならば， ( 1 )の処理を行う;

4.4.  パトリシアトライへの拡張による空間効率の改善

b u c k e t  1  b u c k e t 2   b u c k e t 3   b u c k e t 4  

図 4.20 図 4.14‑(b)にキー you"追加後のパトリシア BDS木

. d

三α，かつ，

K

̲N

UM  =  B

̲5

IZE

ならば， ( 2 )の処理を行う;

・

^d

^>

^{αならば， ( 3 )の処理を行う ;}

次に，各処理内容の詳細を説明する

( 1 )の場合は，単純に挿入キーを対応するバケットに格納した後，K ̲NUj¥l!の値を 1つ 増すだけでよい.例として，図 4.14‑(b)のパトリシアBDS木 に キ ‑"you" (H(you)=11000…) 

を挿入した後の構造を図 4.20に示す.尚，先行順ピット列の内容は変化しない.

( 2 )の場合は，

(i)  : Ordinary BDS木と同様に，フルバケットに対応した葉を単位木に変換する;

(ii)  : Ordinary BDS木のようなパケットの再オーバーフロー処理は行わず，共通接頭 部分は削除ノードとして新たに生成された内部ノード(単位木のルートノード)内

に格納される;

但し，その内部ノードが保持する削除ノード数はα‑d個 と す る ;

(iii)  :単位木内の 2つの葉に各キーを割り振るため，各キーピット列のα+1番目のピッ トイ直がOならば単位木の左の葉が示すバケットに， α+1番目のピット値が 1なら ば単位木の右の葉が示すパケットに各キーを格納する;

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

以 下 に ， 新 し い 先 行 順 ピ ッ ト 列 に よ り 表 現 さ れ た パ ト リ シ ア BDS木のパターン ( 2 )  に対する更新アルゴリズムを示す.但し， 3 . 5で 述 べ た BDS木 の 史 新 ア ル ゴ リ ズ ム で 用 い た 変 数I<..BETを用いる.

[1 ~トリシア BDS 木の更新アルゴリズム・パターン ( 2 】) 入 力 :key :検索の後， 登 録 さ れ る キ ー ;

出力:なし・

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

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

Z E

にする;

手 順(1"‑2‑2)  : {単位木の挿入処理}

treemap上のtreepos位置のピット値を単位木を去すピット列 011"に 変 更 す る ;

手1)慎(1"‑2‑3) : {削除ノード数の設定処理}

α‑d個 の ピ ッ ト 値 Iとその後に続く 1個のピット値0から成るピット列を nodernap 上 のηodepos位 置 の 次 に 挿 入 す る ;

手 順(1"‑2‑4) : {K..BET内 の 各 キ ー の 格 納 処 理 }

K̲SET内の各キーにおいて， キーピット列のα+1番 目 がOならば，単位木の左の 葉が示すパケットに， α+1番 目 が1ならば，単位木の右の葉が示すパケットに，各 キ ー を 格 納 す る ;

例として， 図 4.14‑(b)のパトリシア BDS木， および図 4.16の 先 行1}1ftピット列にキー tax" (H(tax)ニ100110...  )を挿入する場合に行われる手順を図 4.21，図 4.22に 従って 説明する.

まず，パケット 3ま で 検 索 が 行 わ れ た 際 の 各 変 数 値 を 図 4.21に示す. treeposは 第6

ピット目を示し， ηodeposは最終ピットである第6ピット目を示している. また 菜番号 3までの木の深さは dは2である.更に， H(tax)， H(tea)， H(try)の各ピット列をピット 単位に比較演算すると， 第5ピ ッ ト 目 ま で の ピ ッ ト 値 が す べ て の キ ー に 対 し て 等 し い の で， αの値は5となる.その結果，dくαで，かつ，パケットがオーバーフローするので，

ノfターン ( 2 ) の 更 新 処 理 が 行 わ れ る . 以 下 に 手)11買を示す.

手1)慎(1"‑2‑1) _{:挿入キーとフルパケット内の各キーとを K}..BETに代入し，

K 

̲S ET={ tax，もea，try} 

よ0 

ν 、守

I air I  I bag I  I art I  I bωl  bucket 1 bucket2 

4.4.  パトリシアトライへの拡張による空間効ギーの改苦ー

H(tax) :  H(tea)  :  H(try)  : 

r ^込

^{山 辺}

司 内

^treemap:

^{1 0 1 0 1 1  11111} 

ket3 bucket4 nodemap: 

I 0 1 1 1 1 1 1 1 0 [ 0 1  

図 4.21 図 4.14‑(b)で キ ‑"tax"検 索 後 の パ ト リ シ ア BDS木

由函

ap : I 

0 

I 

0 

I 

1 

I 

1 

I 

0 

I

宣 告

f  c f 川 白

^emap:

^{1  0  1 1   1 1   1 1   1  0  1} 山

由町

^ω

図 4.22 図 4.14‑(b)に キ ‑"tax"挿 入 後 の パ ト リ シ ア BDS木

と す る ;

手 順 (1"‑2・2) : trecrnapの 第6ピット値をピット列 011"に 変 更 す る ;

手 順 (1"‑2^司3) :各キーの第3""'第5ピットまでのピット列"011"を削除ノードとするた め， ピット列 1110"をnodemapの 最 終 ピ ッ ト の 後 に 追 加 す る ;

手1)慎(1"‑2‑4) ト3に

: H( tax)， H( tea)の 第6ピット値がOなのでキー tax"と"tea"はバケツ H(try)の 第6ピット値は lなのでキー try"はパケット 5に 格 納 す る ; 以上，キ一%以"を挿入後のパトリシアBDS木 及 び 対 応 す る 先 行1)原ピット列を図 4.22に 示す.

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

次に， ( 3 )の場合は，木構造の特徴からピッ ト列XとBとの問で最初に異なるビット 位置に相当する枝を 1本 だ け を 増 や し て や れ ば よ い の で ， 双 方 の ピ ッ ト 列 問 の 相 違 部 分

内で最初にフォルスドロップが起こった位置，即ち，X(l'  bαの周辺にだけ注目する.尚，

最初にフォルスドロップが起こったピット，bαの隣接ピットには削除ノードが存夜するの で，ビットヂjIBを以下のように再定義する.

B 

= 

bo b1…bi…αb_…bj_…b_m‑1 

但し， i三

α : : ;

j， i 

= 1  

^{jとしする.ここで，bi ~ bj}のビット列が削除ノードがぶす ピットである.

( 3 )の場合に行われるパトリシア BDS木上の手順を以下に示す.

( i)  :フォルスドロップを起こしたノード(フォルスドロップノードと呼ぶ)を確定す るため，挿入キーピット列Xを再度ルートノードから検索する;

この際，d=lに初期化した後，dの値を設定しながら検索を行い，d=α+1となった 時点で辿り着いた内部ノードをフォルスドロップノード (falsedrop nodc)とする;

(i  i)  :フォルスドロップノードの親ノードとして新たな内部ノードを挿入し，この内郎 ノードを挿入ノード (insertednode)と呼ぶ;

(iii)  :挿入ノードが保持する削除ノード数をα-~佃，フォルスドロ ップノードが保持 する削除ノード数を J‑α^{個 と す る ;}

(iv)  : x_αの値がOならば，挿入ノードから左の枝と葉を l個ずつ生成し，x_αの値が 1な らば，挿入ノードから右の枝と葉を 1個 ず つ 生 成 す る ;

(v)  :九の値がOならば，左の葉が示すパケットに ，xαの値が 1ならば，右の葉が示す パ ケ ッ ト に 挿 入 キ ー を 格 納 す る ;

以下に，新しい先行順ピット列により表現されたパトリシア BDS木 の パ タ ー ン (3 ) 

に対する更新アルゴリズムを示す.

{パトリシアBDS木 の 更 新 ア ル ゴ リ ズ ム ・ パ タ ー ン (3 】) 入 力 :key :検索の後，登録されるキー;

出力:なし;

4.4.  パトリシアトライへの拡張による空間効率の改善 手 順 (1"‑3‑1)  : {フォルスドロップノードの確定処理}

挿入キーピット列Xを4. 4.  3に示したアルゴリズムにより，

r f 2 =

α+1に な る ま で 検 索 す る ;

尚，検索終了後に辿り若いたノードがフォルスドロップノードであり，この時点で treeposはフォルスドロップノード，nodeposはαbに対応するピットを指す;

手 順 (1"ー3^・2) : {挿入ノードの挿入処理}

trccmap上のtreepos位置の次にピット値0を挿入する;これで，treeposは挿入ノー ドを指し示すことになる;

手 順(1"‑3^・3) : {削除ノード数の設定処理}

nodeposが抱し示す位置で削除ノード数をフォルスドロップノードと挿入ノードの 2つの内部ノードに分割するため， nodemap上の^ηodepos位置のビット値を Oに変 更 す る ;

手11慎(1"‑3‑4) : {挿入ノードかららの値に対応する枝の作成処理}

Zαの値がOならば，挿入ノードの左側に 1個の枝葉を作成するため， treemap上の treepos位置の次に 1個の枝葉を表すピット値lを挿入し，

Zαの値がIならば，挿入ノードの右側に l個の枝葉を作成するため， treemap上で 挿入ノードの左部分木をスキップした後のピット位置，即ち ，treepos位置から 1の ピット数がOのピット数より lつ多くなるまでかeeposを進めた後，treepos位置の 次にピットイ直1を挿入する;

手 順(1"‑3^圃5) : {挿入キーの格納処理}

新たに作成された葉に対応するパケットに挿入キーを格納する;

例として，図 4.14‑(b)のパトリシアBDS木，および図 4.16の先行順ビット列へのキー car"  (H(ear)=OOlOO… ) の 挿 入 処 理 を 図 4.23^‑....図 4.25に従って説明する.

ま ず ， キ ‑"car"を検索すると，パケット 1に辿り着き，パケット 1内部の検索の結果，

未登録語と判断される.そこで， H(ωr)， H (air) ， H (art)をピット単位で比較演算すると，

第2ピット

L I

までのピット値が等しいので， α=2となる.また，パケット lまでの木の深 さdは，内部ノード 2が削除ノードを 3伺含んでいるので，d=5である.よって，d 

>

^α 

な の で ， パ タ ー ン (3 )の更新処理が行われる.以下に手順を示す.

24. 4.  3に示したアルゴリズム内で用いられた keyposがdの値と一致する.

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