↑ 仏

紅

白

↑

/ t

¥ . バu c u

η

川町

百ハ

Z A

手

このリンク関数の統合は， KEYID [ p ] = { s ，

ア}において，

D F [

ァ]へのポインタ値ァを，

lレートノードのノード香号とすることで

簡単に実現できるが汎用的な拡張を目指して以下を定義する .

(

変更終)

ダブル配列のルートノード叫に対し，識別番号 nro を定義し，これを

この変更は，ルートノードが複数存在することにより，初期化時にルートノードを決定

する必要があることによる

.出力については関数

T r i e ̲ I n s e r t .T r i e ̲ D e l e t e

についても同

様に KEYID

pとなる.

[定義

5 . 2 J

ROOTID [ n r D ]

^二

η T

_[関数

_A

_̲_I

NSERT

の変更]

( a ‑ 8 )

行の前に以下を挿入する. として表

ROOTID

で管理する. また，ルートノード

η T

の

CHECK

値には，

CHECK [ η r ]

‑nro ( a a ‑ l ) e l s e i f BASE[ ] t > 0 then b e g i n

ゼ← E l I I PTY ̲H EAD

、

¥

̲ C HECK ( t ' ， C HECK [ t ] ) ;

¥V ̲ BASE ( t ' ， BASE [ t ] ) ;

のように識別番号

η [ D

を格納する.

(

定義終)

( a a ‑ 2 ) ( a a ‑ 3 ) ( a a ‑ 4 )

7 0 ₇ ₁

第

3

章リンクトライ

( a a ‑ 5 ) f o r each

such that C HE C K [ q l = t do

( a a ‑ 6 ) ( ω f )

( a a ‑ 8 ) ( a a ‑ 9 )

end

¥ ¥ 二 CH EC K ( q

^司

t ' )

i f t = i n 巾 . rthen i n d eI ← t ' :

\\二CHEC~(t.

0 ) ;

¥ ¥ 二 BASE ( t . O ) ; ROOTID [

凡

I D 1 4‑L

(変更終)

この変更は，ルートノードを移動する必要があるときの更新処理である

. ( a a ‑ 5 )

行から

( a a ‑ 8 )

行は，関数

MODIFY

での

( m ‑ 8 )

行から

( m ‑ 1 3 )

行に相当するので，関数化するこ

とも可能である.

[関数 X ̲ CHECK

の変更]

( x ‑ 6 )

行の変更

( x ‑ 6 ) i f BASE [ q q + N [ c ] ] <> 0 a nd CHECK[qq + N [ c ] l > 0 th e n f l g ← f a l s e ;

(変更終)

[関数 W̲C H EC K

の変更]

( w c ‑ l

)行の変更

( w c ‑ l ) i f BASE [ i d x ]

0 a n d CHECK[idx] < 0 t h en

(変更終)

これらの変更は空ノードの判定方法の変更による.

以上のデータ構造によるリンクトライのアルゴリズムを以下に示す.

72 5 . 5 .

リンクトライのデータ構造

[アル

ゴ

リズム LT ̲ SearchJ 入力̲¥， 1 ' ，

0..

，

:I:I

力 :

̲¥，

l

'に

α

が定義されていれば，その

α

を含むレコード

REC (

γ:

u )

に対応するポインタ値

r

，7J. 定義されていなければ，

r = 0

， LL

= 0

を返す.

トライ部のルートノード香号を

ROOTID [ l ] = 1

とする.

手順 ( S 2 ‑ 1 ) :

1トライ部のダブル配列

D ( l )

における̲¥，

γ

の検索l

X ， l ' に対してダブル配列 D(l) を検索し，

= T r i e ̲ S e a r c h ( D ( l )

， .¥)と

，

= T r i e ̲ S e a r c h (D(l) ， γ ) を得る • p ， q

のいずれかが

O

ならば，

̲ ¥ ， i ' のいずれかがトライに格納されて

いないので，r

= 0

， u

= 0

を出力し，アルゴリズムを終了する.そうでなければ，次へ進

む.

手順 ( S 2 ‑ 2 ) :

1リンク関数とレコード情報の検索￨

X の識別番号 p で指定されるリンク関数の KEYID[p] = { s )

ア}なる γ，キー

γ

における識別番号

q

のバイトコード列

ω

，

及び α のバイトコード列 υ

に対して

u = T r i e ̲ S e a r c h ( D ( ァ )

，'U

w )

を検索し，r

，

を出力する

(アルゴリズム終)

アルゴリズム LT ̲ GetA l l

を定義するにあたって，次の関数を使用する

.

T r i e ̲ G e tAll(D( η

D ) ) : ダブル配列 D ( η I D ) に登録されているキー全ての集合を取得する

ダブル配列

(

トライ

)

は，ルートノードからの深さ優先探索によって全てのキーを取得することが可能である

[

アルゴリズム

LT ̲ G e tAll J 入力 : X .

出力 :.x~ との関係が定義されている全ての共起情報の集合 C

. X が存在しない場合は，

仇

手

⁾¹¹貢

( Gl‑1 ) : L Y のトライ上の検索

￨

7 3

第

5

章リンクトライ

X

に対してダブル配列

D ( l )

を検索し，

ρ

^二

T r i c ̲ S c a r c b ( D ( 1 )

._\)を得る• jJが

O

ならば，

X

カfトライに倍納されていないので，

C

ニ

o

を出

) J

し，アルゴリズムを終了する.そう

でなければ，次へ進む.

手)11f{

( G l ‑ 2 ) :

!関係定義の探索と出力処理￨

X

の識別番号 p で指定されるリンク関数の

h~EYID

[ρ]=

{

s ，7'

} なる r から， C

_v_ω=

T r i c ̲ G c t A l l ( D ( r ) )

なるリンク関数集合

C

_vwを取得し，

C

_vw_{中の全ての要素 υ}ω に対し，

K EYID

[ w ] = { t . T T }

なる

t ， i

= Rc

刊

r s e ̲ O u t ( t )

を得，

C U

(̲¥，

i ' ， α u )

とする.最後に

C

を出)] し，アルゴリズムを終了する.

[アルコリズム

LT

̲l

n s e r t J

入力 :リンクトライに登録されていない

( ̲ X

，)

" α ) .

出力:なし.

手)11買

( A ‑ l ): I

キ

‑ X ， Y

の登録￨

(アルゴリズム終)

p = T r i e ̲ j n s e r t ( D ( l )

，

‑ . . Y )

，

q = T r i e ̲ I n s e r t ( D ( l )

，

Y )

より，キ

‑ X ， Y

をダブル配列に登録し，

KEY I D P 3 q

を得る

.

手)11

貢 ( A ‑ 2 ) : I

関係の定義￨

α

のバイトコードチIj

V

，

q

のバイトコード列

ω

，

K EY ID [ p ] =

{ム

T }

なる γに対し，

T r i e ̲ I n s e r t ( D (

ァ)，

v

ω)により

υ ω

を登録する.

[アルゴリズム

LT ̲ D e l e t e J

入力 :リンクトライに登録されている

(X ，

)，'

α ) .

出力 :なし.

手順

( D ‑ l ):

!キ ‑J.)¥̲，

γ

の検索￨

7 4

(アルゴリズム終)

5 . 6

結言

̲¥，

i .

に対してダブル配列

D ( l )

を検索し，

s = T r i e ̲ S c a r c h ( D ( l ) . ̲ ¥ )

と

t = T r i e ̲ S e a r c h ( D ( l ) . i

')を得る.

手JiI買

( D ‑ 2 ) :

!関係の削除￨

s

と

t

のどちらかが

O

ならば，共起情報は未定義なので終了する.どちらも

0

でなければ、

α

のノてイトコード列 V

，q

のバイトコード列

w ， KEYID [ p ] =

{S.l・}なる

r

に対し，

T r i e ̲ D e l e t e ( D ( r ， ) v ω )

により U町を削除する

.

手JiI買

( D‑ 3

)

: I

キーの削除￨

T r i c ̲ G e t A l l ( D (

ァ))=ゆとなれば，全ての関係がなくなるので，

T r i c ̲ D c l

付

e ( D ( l ) . . ¥ )

により，キ

‑ X '

を削除する

.

(アルゴリズム終)

[

例

5 . 1 1 J

共起情報集合

Cl

をリンクトライに登録した例を図

5 . 7

に，図

5 . 7

をトライで表現した例を図

5 . 8

に示す.図

5 . 7

でのダブル配列は，図

5 . 3

と同じ内部表現値を使用し，空ノードリンク法，複数のダブル配列統合法が利用されている.また配列

TA I L

は通常

1

次元の配列であるが，簡単のため

2

次元の配列で表記し，

KEY ID

，

R OOTI D

は配列

T A I L

に吸収されている.理解を深めるために，ダブル配列中のリンク関数に相当する要素は斜体で示している

.

また，図

5 . 8

でのノード番号は，図

5 . 7

のインデックス番号と一致させている

.

(例終)

5 . 6 結言

本章では，共起情報を効率的に記憶検索する手法として，リンクトライを提案し，リンクトライを用いた共起情報の検索，更新アルゴリズムを説明した.また，ダブル配列を用いたリンクトライのデータ構造についても説明し，リンクトライでのダブル配列の管理を効率化するために複数のダブル配列を

l

つに統合する手法も述べこれらについての検索，更新アルゴリズムを説明した.

次章では，リンクトライの有効性を確認するために理論的評価と実験による評価を行う .

1 ' 5

ドキュメント内トライ構造を用いた共起情報の効率的記憶検索法に関する研究 (ページ 45-48)

η

手

このリンク関数の統合は， KEYID [ p ] = { s ，

D F [

簡 単 に 実 現 で き る が 汎 用 的 な 拡 張 を 目 指 し て 以下を定義する .

変 更 終)

ダ ブ ル 配 列 の ル ー ト ノ ー ド 叫 に 対 し ， 識 別 番 号 nro を定義し，これを

する必要があることによる

T r i e ̲ I n s e r t .T r i e ̲ D e l e t e

様に KEYID

5 . 2 J

ROOTID [ n r D ]

η T

A

NSERT

( a ‑ 8 )

ROOTID

η T

CHECK

CHECK [ η r ]

‑nro ( a a ‑ l ) e l s e i f BASE[ ] t > 0 then b e g i n

ゼ← E l I I PTY ̲H EAD

¥

̲ C HECK ( t ' ， C HECK [ t ] ) ;

¥V ̲ BASE ( t ' ， BASE [ t ] ) ;

η [ D

定 義 終)

( a a ‑ 2 ) ( a a ‑ 3 ) ( a a ‑ 4 )

7 0 7 1

3

( a a ‑ 5 ) f o r each

such that C HE C K [ q l = t do

( a a ‑ 6 ) ( ω f )

( a a ‑ 8 ) ( a a ‑ 9 )

end

¥ ¥ 二 CH EC K ( q

t ' )

i f t = i n 巾 . rthen i n d eI ← t ' :

0 ) ;

¥ ¥ 二 BASE ( t . O ) ; ROOTID [

I D 1 4‑L

. ( a a ‑ 5 )

( a a ‑ 8 )

MODIFY

( m ‑ 8 )

( m ‑ 1 3 )

[関数 X ̲ CHECK

( x ‑ 6 )

( x ‑ 6 ) i f BASE [ q q + N [ c ] ] <> 0 a nd CHECK[qq + N [ c ] l > 0 th e n f l g ← f a l s e ;

[関数 W̲C H EC K

( w c ‑ l

( w c ‑ l ) i f BASE [ i d x ]

0 a n d CHECK[idx] < 0 t h en

72

5 . 5 .

[アル

リズム LT ̲ SearchJ 入力̲¥， 1 ' ，

力 :

l

α

α

REC (

u )

r

r = 0

= 0

ROOTID [ l ] = 1

手順 ( S 2 ‑ 1 ) :

D ( l )

γ

X ， l ' に対してダブル配列 D(l) を検索し ，

= T r i e ̲ S e a r c h ( D ( l )

，

= T r i e ̲ S e a r c h (D(l) ， γ ) を得る • p ， q

O

̲ ¥ ， i ' のいずれかがトライに格納されて

= 0

= 0

む.

簡単に実現できるが汎用的な拡張を目指して以下を定義する .

変更終)

ダブル配列のルートノード叫に対し，識別番号 nro を定義し，これを

_A

定義終)

7 0 ₇ ₁

X ， l ' に対してダブル配列 D(l) を検索し，

及び α のバイトコード列 υ

は，ルートノードからの深さ優先探索によって全てのキーを取得することが可能である