テキスト処理入門：Pythonで高速な辞書を作ろう（その2）

ダブル配列の作成

ダブル配列ではTrie木をどのようにして実現しているのでしょうか。

まず「base」と呼ばれる整数の一次元配列を用意します。
この配列の１つの要素が、１つのノードを表しています。
base配列のインデックスは1から始まります。（0の位置は使いません）
つまり１番のノードがrootです。ここには1が入っています。
base[1] = 1 です。

見出し語の先頭の文字は、先ほどの例では「で」と「ど」ですね。
では、rootが「で」によって遷移した次のノードはどこになるのでしょうか。

準備として、見出し語のそれぞれの文字に識別番号を振ります。
何らかのエンコーディングの文字コードをそのまま使っても良いのですが、
文字数が少ないこともあり、ここでは１から始めて適当に文字IDを振ります。
単語と文字の登場順にすると以下のようになります。

で: 1　ん: 2　ど: 3　こ: 4　ち: 5　ゃ: 6　べ: 7　ぇ: 8

「で」が１、「ど」が３になりました。code[‘で’]=1, code[‘ど’]=3 と書きます。
ちなみに、後ほどご説明しますが、文字IDの0番は語末（葉ノードへの遷移）です。
葉ノードの話が出ましたので、単語にも登場順にIDを振っておきます。

でん:1　どこ:2　どん:3　どんちゃん:4　どんどん:5　どんべぇ:6

さてこのようにした時、rootから文字「で」によって遷移するノードの位置は、
rootのbaseの値に文字IDを加えた値を取ります。つまり：

base[1] + code[‘で’] = 1 + 1 = 2

となります。「ど」の場合も同様にして、

base[1] + code[‘ど’] = 1 + 3 = 4

これで、base配列の2, 4番が新たに埋まりました。
このように遷移先のノード位置は、「baseの値＋文字ID」の値です。
何だかすごいです。文字情報が「遷移の移動量」に吸収されてしまいました。

ここで問題となるのは、base[1]の値に適当な任意の文字IDの値を足すことで
rootからどのノードへでも遷移できてしまうのではないか、ということです。
次の文字は「で」と「ど」だけにしたいので、これでは困ります。
そこで、もう１本「check」と呼ばれる整数の一次元配列を用意します。
そしてcheckには、どこから来たのか（＝親ノードのインデックス）を入れます。
親ノードがrootなら1です。さらにroot自身のcheckは0にします。式で書くと：

check[1] = 0
check[2] = 1
check[4] = 1

このようにbaseとcheckという２本の配列でTrie木を表すのが
「ダブル配列」という名前の由来です。
「ダブル配列におけるノードは、位置情報とbase成分とcheck成分を持つ」と考えるのが
良いかもしれません。
ここまでを表にしておきましょう。

今、ノードは1，2，4番が埋まっています。3はまだ空いています。
2，4番のbaseの値がまだですが、どのようにして決めるのでしょうか。

位置sから文字cによって位置tに遷移するときは、次のようになるのでした。

t = base[s] + code[c]
check[t] = s

仮にbase[s]の値を好きなように決めてしまうと、今後ノードがどんどん増えた時に、
前から存在するノードとの位置のバッティングが発生します。
逆に言うと、そうならないように、つまりうまく空いている場所に次のノードが遷移するように
base[s]の値を決めるわけです。

見出し語：「でん」「どこ」「どん」「どんちゃん」「どんどん」「どんべぇ」を見ると、
例えば「どん」の２文字目の「ん」からは、「語末」「ち」「ど」「べ」と
子ノードへの分岐が４つもあるので、その全てが他とバッティングしないようにしなければなりません。
base成分はオフセット値と呼んでも良いと思います。
一般に、オフセット値は最小になるように、つまり遷移先の組み合わせがなるべく左側に入るように決めます。
ダブル配列の成長とともに、左側から空きが詰まって行く感じですね。

では、ここからしばらく、ダブル配列の成長の様子を１ステップずつ見て行きたいと思います。
実は、説明すべき重要な概念は、あと１つ「葉ノードの処理」のことしか残っていないので、気楽にお読み下さい。
１度でピンと来なくても、メモを取りながら何度か読んでいただければきっと頭に入ると思います。

ちなみに、今回は単語ID順に登録して行くので、
深さ優先（depth-first）の作成ということになります。
他のやり方として、まずrootから１文字目への遷移を全見出し語について登録した後に、
１文字目→２文字目の全見出し語での遷移…と登録して行くやり方も考えられます。
それだと幅優先（breadth-first）の作成になります。

ステップ１：「で」→「でん」

遷移元s = 2からの遷移です。文字IDは、code[‘ん’] = 2 なので
base[2] = 1  とすれば遷移先がt = base[s] + code[c ] = 1 + 2 = 3 となり
空いている場所（の左端）に遷移できます。そこのcheckに親ノード位置を入れます。
check[3] = s = 2

さて、「でん」で語末まで来ました。他に「でん…」と続く見出し語がないので、
遷移に分岐がない（葉ノードには兄弟ノードがいない）状態です。
通常は、code[葉ノード] = 0 として遷移先を考え葉ノードを作成しますが、
分岐がない場合は、葉ノードをわざわざ作成せずに、base成分に
単語IDの符号を反転して負数にしたものを入れます。
メモリが節約でき、 検索速度も若干上がります。
「でん」の単語IDは1なので、base[3] = -1
上の表では、「で」→「でん」の遷移を、「で→ん」と簡略表示してあります。

ステップ２：「ど」→「どこ」「どん」

遷移元s = 4からの遷移です。
「ど」からは「こ」「ん」と２つ遷移先があります。
code[‘こ’] = 4 、code[‘ん’] = 2 なので、base[4] = 3 とすれば
遷移先のノード位置がうまく決まります。それぞれ見て行きましょう。

「ど」→「どこ」
遷移先t = base[4] + code[‘こ’] = 3 + 4 = 7、したがってcheck[7] = s = 4
「どこ」と語末に来ましたが、分岐がない（「どこ…」と続く見出し語が他にない）ので、
先ほどのように単語IDの2を符号反転して、base[4] = -2

「ど」→「どん」
遷移先t = base[4] + code[‘ん’] = 3 + 2 = 5、したがってcheck[5] = s = 4
「どん」と語末に来ましたが、「どん」からはそれ以外にも「ち」「ど」「べ」と分岐します。
base[t]に単語ID（の符号を反転したもの）を入れることが出来ず、葉ノードを新しく作ることになります。
今はここまでにしておいて、次のステップで考えます。

このように、ダブル配列においては、たとえ深さ優先方式で作成していても、次のノードへの
接続の幅（分岐数）を常に考慮しながら作成する必要があります。ちょっと興味深いです。

ステップ３：「どん」→「どん（語末）」、「どんち」、「どんど」、「どんべ」

遷移元s = 5からの遷移です。
code[語末] = 0 、code[‘ち’] = 5、code[‘ど’] = 3、code[‘べ’] = 7 なので、
base[5] = 6 とすれば遷移先のノード位置がうまく決まります。
それぞれ見て行きましょう。

「どん」→語末
先ほど後回しにした処理ですね。
遷移先 t = base[5] + code[語末] = 6、したがってcheck[6] = s = 5
語末なので「どん」の単語IDの3を符号反転して入れます。
base[6] = -3
分岐がある場合は、このように葉ノードを新しく作成してから、
そこに単語ID（の符号反転したもの）を入れるのが、
分岐がない語末の場合との処理の違いになります。

「どん」→「どんち」
遷移先t = base[5] + code[‘ち’] = 6 + 5 = 11、したがってcheck[11] = s = 5

「どん」→「どんど」
遷移先t = base[5] + code[‘ど’] = 6 + 3 = 9、したがってcheck[9] = s = 5

「どん」→「どんべ」
遷移先t = base[5] + code[‘べ’] = 6 + 7 = 13、したがってcheck[13] = s = 5

ステップ４：「どんち」→「どんちゃ」→「どんちゃん」

これまで１文字ずつ進んで来ましたが、「どんち」→「どんちゃん」は分岐がないので
２文字ぶんの説明をまとめます。

「どんち」→「どんちゃ」
遷移元s = 11 です。code[‘ゃ’] = 6なので、base[11] = 2とすれば遷移先t = base[11] + code[‘ゃ’] = 8
したがってcheck[8] = 11

「どんちゃ」→「どんちゃん」
遷移元s = 8 です。code[‘ん’] = 2なので、base[8] = 8とすれば遷移先t = base[8] + code[‘ん’] = 10
したがってcheck[10] = 8
語末まで来ましたが、葉ノードへの遷移にも分岐がありません。単語IDは4なので
符号を逆転させて、base[10] = -4

ステップ５：「どんど」→「どんどん」、「どんべ」→「どんべぇ」

ダブル配列は完成です。（あれ、説明…？）お付き合いいただき、ありがとうございました。
最後に、ダブル配列の作成について重要事項をまとめておきます。

1234コード