情報系修士にもわかるダブル配列

最近話題の「日本語入力を支える技術」を途中まで読んだ。

3章がものすごく気合いが入っている。

trie（トライ）というデータ構造の2つの実装、「ダブル配列」と「LOUDS」について詳しく説明がされている。

ダブル配列については、ぼくは以前論文を読んで勉強しようとしたのだが、その時は難しくてあきらめた覚えがある。しかし、この本の説明を読むことで理解ができた。

ありがたい。

感銘を受けたので、この本を教材に友達と2人勉強会をした。

この2人勉強会というのは、ぼくが復習を兼ねて友達に教えるというのがだいたいのスタイル。

しかし、いざやってみるといろいろと難しい。

次のようなところでひっかかるようだ。

例のサイズが小さく、イメージを喚起するのが難しい。
最初の図のノード番号と、最終的なダブル配列上の位置が異なるため、混乱する。
単語終端について言及がないので、どのノードが単語を表しているかがわからない。

これらはぼくが読んだ時にはひっかからなかったので、対象読者層の問題といえばそうだろう。

しかし、その友達も情報系の修士を取っている。ぼくほどアルゴリズム好きではないが、それなりの素養はあるはず。

彼にわかるぐらいの資料があればいいのだが。

というわけで、「情報系修士にもわかるダブル配列」というものを書いてみる。

木構造については知っていることが前提。

実際にプログラム上でどう構築するかというより、ダブル配列によってどうして検索ができるかということが中心。

まず、trie について。

trie というのは、「共通接頭辞検索」というものをしたい時によく使われる、木構造をベースにしたデータ構造。

共通接頭辞検索というのは、蓄えられたデータの中から、検索文字列の前部分に一致するものを返すというもの。

例えば、日本語の単語が入った辞書に対して「くるまで」という文字列で検索したら、「くるま（車）」・「くる（来る）」・「く（区）」といった、「くるまで」の前部分に一致するものを返す。

以下の例では、

ace
ad
ade
cab
dab
dad

という単語が入った辞書を考える。

この場合、次のような trie で表せる。

イ・ロ・ハ…はノードのラベル。

「イ」が根。

太枠で囲ったノードは単語終端ノード。

検索時には、エッジに添えられたアルファベットを見る。

例えば、"ace" という単語があるかどうか調べる時は、次のようになる。

根である「イ」から、最初のアルファベット "a" というラベルのエッジがあるかどうか調べる。
エッジがあり、移動先は「ロ」なので、「ロ」に移動。
「ロ」から "c" というラベルのエッジがあるか調べる。
エッジがあり、移動先は「ホ」なので、「ホ」に移動。
「ホ」から "e" というラベルのエッジがあるか調べる。
エッジがあり、移動先は「リ」なので、「リ」に移動。
検索文字列の末尾まで移動したので、「リ」が太枠のノードかどうか調べる。
「リ」は太枠なので、辞書に "ace" というエントリが存在する。

これが、"ca" なら次のようになる。

根である「イ」から、最初のアルファベット "c" というラベルのエッジがあるかどうか調べる。
エッジがあり、移動先は「ハ」なので、「ハ」に移動。
「ハ」から "a" というラベルのエッジがあるか調べる。
エッジがあり、移動先は「ト」なので、「ト」に移動。
検索文字列の末尾まで移動したので、「ト」が太枠のノードかどうか調べる。
「ト」は太枠でないので、辞書に "ca" というエントリは存在しない。

"bad" なら次の通り。

根である「イ」から、最初のアルファベット "b" というラベルのエッジがあるかどうか調べる。
エッジがないので、辞書に "bad" というエントリは存在しない。

次は共通接頭辞検索を考える。与える文字列は "adea" とする。

根である「イ」から、最初のアルファベット "a" というラベルのエッジがあるかどうか調べる。
エッジがあり、移動先は「ロ」なので、「ロ」に移動。
「ロ」は太枠ノードでないので、"a" という単語はない。
「ロ」から "d" というラベルのエッジがあるか調べる。
エッジがあり、移動先は「ヘ」なので、「ヘ」に移動。
「ヘ」は太枠ノードなので、"ad" という単語を検索結果に追加。
「ヘ」から "e" というラベルのエッジがあるか調べる。
エッジがあり、移動先は「ヌ」なので、「ヌ」に移動。
「ヌ」は太枠ノードなので、"ade" という単語を検索結果に追加。
「ヌ」から "a" というラベルのエッジがあるか調べる。
エッジがないので、探索を中止。検索結果（"ad", "ade"）を返す。

このように、図のような構造によって、共通接頭辞検索ができる。

次は、これをどのように実装するかという問題。

まずは、テーブルによる実装を考える。

次のようなもの。

"a", "b", "c", "d", "e" に対して、ここでは仮に文字コードが 0, 1, 2, 3, 4 だとする。また、下線が引いてあるノードが単語終端だとする。

例えば、上でやった "ca" に対する検索を考える。

根である「イ」の行で、"c" に対応する文字コードである 2 の列に文字が書き込まれているかどうか調べる。
「ハ」という文字があるので「ハ」に移動。
「ハ」の行で、"a" に対応する文字コードである 0 の列に文字が書き込まれているかどうか調べる。
「ト」という文字がある。また、単語末まで移動したので、「ト」に下線が引いてあるかどうか調べる。
「ト」に下線は引かれていないので、辞書に "ca" というエントリは存在しない。

この実装は単純で速いので、容量に問題がなければ使うのもいい。しかし、図を見るとわかるように、データが入っているところが少なく、かなりスカスカだ。

このスカスカを埋めようというのがダブル配列。キーワードは「ずらしてガッチャンコ」。

まず、上の図を一行ずつ切り離す。子がない行は省略。

これを適当にずらして重ね合わせたら、いい感じにギッチリ埋められるんじゃないだろうかというのがアイデア。

そのずらし方をどうやって見つけるかがアルゴリズムの肝心なところだと思うけど、ここではとりあえず適当なずらし方を与える。

次のようにする。

ずらして組み合わせた結果が一番下の行。
この時、どれだけずらしたかを覚えておかないと後で検索ができないので、それを書き添えておく。

子を持たないノードに対しては、-1 を埋めてある。

検索する時には、この「ずらした量」を使う。

例えば、この表を使って、上と同じように "ca" という単語が辞書にあるかどうか調べると、次のようになる。

根である「イ」に対するずらし量を調べ、それが +1 であることを得る。
ずらし量である +1 に、 "c" に対応する文字コードである 2 を加えた、3 の位置に文字が書き込まれているかどうか調べる。
「ハ」という文字があるので「ハ」に移動。
「ハ」に対するずらし量を調べ、それが +2 であることを得る。
ずらし量である +2 に、"a" に対応する文字コードである 0 を加えた、2 の位置に文字が書き込まれているかどうか調べる。
「ト」という文字がある。また、単語末まで移動したので、「ト」に下線が引いてあるかどうか調べる。
「ト」に下線は引かれていないので、辞書に "ca" というエントリは存在しない。

まったく同じように検索ができる。

しかし、ここで一つ問題がある。

元々のテーブルでは、"bad " というエントリがあるかどうか調べるには、根である「イ」の行で、"b" に対応する文字コード 1 の位置を調べれば、そこは空欄であり根から "b" への移動はできない、つまり辞書に "bad" というエントリは存在しない、ということがわかった。

しかし、組み合わせたテーブルで同じことをしようとするとどうなるか。

根である「イ」に対応するずらし量は +1 なので、それに "b" に対応する文字コード 1 を加えた 2 の位置を調べることになる。そうすると、そこには「ト」という文字が書いてある。しかし、この「ト」は「ハ」の子であって「イ」の子ではない。それにもかかわらず、「イ」から "b" で「ト」に移動できるように見えてしまう。

これを防ぐには、それぞれのノードの親ノードがどれであるかを格納するもう一つの配列があればいい。例えば、「イ」の子に対して、親が「イ」であるということを次のように表す。

「イ」は根なので、-1 でも入れておく。こうすると、別の親の子ノードを自分の子ノードだと勘違いすることはなくなる。全ノードについて埋めると次のようになる。

さて、この配列にインデックスを付けてみる。

ノードに対するラベル、「イ」・「ロ」…は特に意味があるわけではないので、ラベルをインデックスで置き換える。

どのノードが単語終端かという情報は失われてしまうが、それを格納する方法は他にも考えられるので、ここでは気にしないことにする。例えば、ずらす量のデータの 1 ビットを使うとかでもいい。