詳解 LOUDS (12) trie として使う

ここまで、LOUDS のビット列を使って木構造をたどる方法を見てきました。

今回は、LOUDS のデータを使って trie を実現する方法を考えます。

まず、辞書には次の単語が入っているとします。

an
i
of
one
our
out

すると、trie は、これまで例として使ってきた木と同じ形になります。違いは、それぞれのエッジにラベルがついていることだけです。

エッジごとのラベルは、どのような形で覚えておくのがいいでしょうか。ここでは、それぞれのエッジの下にあるノード番号と関連付けて覚えておくことにします。すると、次のようになります。

例えば、2番ノードに入ってくるエッジについているラベルは "a" なので、ノードが "2" のところのラベルは "a" になります。ここでは仮想的な 0番ノードは使わないため、ノードが "0" のところのラベルは空欄になっています。また、根である 1番ノードには、そこに入ってくるエッジがないため、やはりラベルは空欄になります。

この補助データを使うと、木構造を trie として扱うことができます。親ノードからあるラベルを持つ子ノードに遷移させたい時、まず子ノードを列挙して、それぞれが持つラベルと比べてマッチするものがあるかどうかひとつずつ調べていくことになります。

例として、この trie で "our" を検索する時の手順を追ってみます。

いつもの LOUDS のビット列に加え、上で挙げたノード-ラベル対応表を使います。

1. 1番ノードの最初の子ノードのインデックスを知るため、ビット列を見て、「左から 1個目の "0" の、ひとつ右の位置」のインデックスを調べます。インデックスは 2 です。1番ノードの 1つ目の子ノードのインデックスが 2 だということがわかります。

2. その子ノードのノード番号を知るために、ビット列を見て、インデックス 2 の位置にある "1" のビットが、左から何個目の "1" であるかを調べます。2個目なので、左から 1つ目の子ノードのノード番号が 2番だということがわかります。

3. 2番ノードに対応するラベルを調べます。表によると、"a" です。探している文字列 "our" の 1文字目は "o" なのでマッチしません。

4. 2番ノードに対応するビットの右隣のビットを見ます。"1" なので、1番ノードの子ノードにはまだ続きがあるということです。ノード番号は、2番の次なので 3番です。

5. 3番ノードに対応するラベルを調べます。表によると、"i" です。探している文字列 "our" の 1文字目は "o" なのでマッチしません。

6. 3番ノードに対応するビットの右隣のビットを見ます。"1" なので、1番ノードの子ノードにはまだ続きがあるということです。ノード番号は、3番の次なので 4番です。

7. 4番ノードに対応するラベルを調べます。表によると、"o" です。探している文字列 "our" の 1文字目は "o" なのでマッチします。注目するノードを 4番ノードに移します。

8. 4番ノードの最初の子ノードのインデックスを知るため、ビット列を見て、「左から 4個目の "0" の、ひとつ右の位置」のインデックスを調べます。インデックスは 9 です。4番ノードの 1つ目の子ノードのインデックスが 9 だということがわかります。

9. その子ノードのノード番号を知るために、インデックス 9 の位置にある "1" のビットが、左から何個目の "1" であるかを調べます。6個目なので、左から 1つ目の子ノードのノード番号が 6番だということがわかります。

10. 6番ノードに対応するラベルを調べます。表によると、"f" です。探している文字列 "our" の 2文字目は "u" なのでマッチしません。

11. 6番ノードに対応するビットの右隣のビットを見ます。"1" なので、4番ノードの子ノードにはまだ続きがあるということです。ノード番号は、6番の次なので 7番です。

12. 7番ノードに対応するラベルを調べます。表によると、"n" です。探している文字列 "our" の 1文字目は "u" なのでマッチしません。

13. 7番ノードに対応するビットの右隣のビットを見ます。"1" なので、4番ノードの子ノードにはまだ続きがあるということです。ノード番号は、7番の次なので 8番です。

14. 8番ノードに対応するラベルを調べます。表によると、"u" です。探している文字列 "our" の 2文字目は "u" なのでマッチします。注目するノードを 8番ノードに移します。

15. 8番ノードの最初の子ノードのインデックスを知るため、ビット列を見て、「左から 8個目の "0" の、ひとつ右の位置」のインデックスを調べます。インデックスは 17 です。8番ノードの 1つ目の子ノードのインデックスが 17 だということがわかります。

16. その子ノードのノード番号を知るために、インデックス 17 の位置にある "1" のビットが、左から何個目の "1" であるかを調べます。10個目なので、左から 1つ目の子ノードのノード番号が 10番だということがわかります。

17. 10番ノードに対応するラベルを調べます。表によると、"r" です。探している文字列 "our" の 3文字目は "4" なのでマッチします。探している文字列はそこで終わりなので、検索結果は 10番ノードになります。

今回は、LOUDS のデータに補助データをつけて trie として使う方法について解説しました。

これで、このシリーズは終わりです。

途中、詳しく解説しなかったところがあります。

「ある "1" のビットが左から何個目の "1" なのか調べる」方法や、「左から n 個目の "0" のビットがどこにあるか調べる」方法についてです。

このシリーズでは、わかりやすいように左から 1, 2, 3... と数えていきましたが、この方法では、ノード数が何十万となった時、例えば左から 365205個目の "0" のビットはどこかを探すというのに、その数の分だけ時間がかかってしまいます。それでは、いくらコンピュータが計算が速いといっても、そういった検索を何万回と行うことを考えると実用的ではありません。

実際には、「ある "1" のビットが左から何個目の "1" なのか調べる」ことや、「左から n 個目の "0" のビットがどこにあるか調べる」ことが定数時間で行えるデータ構造があります。それが、「日本語入力を支える技術」でも出てきた、「簡潔ビットベクトル」というものです。

それについては、完備辞書（簡潔ビットベクトル）の解説という記事に書きました。

今回、12回にも分けてこのシリーズを書いたのは、以前書いた情報系修士にもわかるLOUDSが友達（情報系大学院での同級生。このシリーズの対象読者は、元々はその友達ひとりです）にわかってもらえなかった悔しさがあったからです。

私が「日本語入力を支える技術」を読んでダブル配列と LOUDS を理解した時、両方とも難しいとは思ったものの、どちらかがもう片方よりずっと難しいとは思いませんでした。最初に情報系修士にもわかるダブル配列を書いた時、友達にはそれですっと理解してもらえ、ブコメでも「これでダブル配列わかった」というありがたい言葉をいただいたので、同じように LOUDS の記事を書けば友達やネットの読者にわかってもらえると考えていました。

しかし、実際に LOUDS の記事を書いてみると、友達の反応はパッとせず、どうもわかってもらえた気がしない。ブコメも、「これでわかった」という声はあまりありませんでした。Twitter では「よくわかった」と言っていただけたりもしたのですが、そういう人は元々わかる土台がある人だったようです。

それで、一念発起して、名実ともに情報系修士（の友達）にわかってもらえるようなものを書こうと思い、書くたびにその友達に見てもらって、そのフィードバックによってまた内容を更新したりするうち、全 12回にまでなりました。見てもらうたびに、「あぁ、ここで引っかかるのか…」という新しい発見がありました。

そういったいきさつで、このシリーズの解説はそれなりに親切なものになったと自負しています（が、わからなかったところがあればいつでも教えてください）。わかっている人からすると、読者を甘やかしすぎなんじゃないかと思われるかもしれません。しかし私の考えは、できるだけ障壁を低くして、一段一段上がるように理解してもらえたほうが、理解する楽しさをわかってもらえるんじゃないかというものです。世の中に、もっとわかりやすい解説資料が増えればいいと願っています。

ただ実際には、解説資料は技術の発展するスピードになかなか追いつけず、あったとしてもかなり理解力を要求するものであったりします。ただ、そういう資料であっても、書いてあることを素直に読んで、例を手で追ってみるなどすれば、かなりの確率でそのうち理解ができるはずです。

他の解説を読んでも LOUDS が理解できなかったが、このシリーズを読んだらわかった、という人がいれば（いることを願っていますが）、一歩一歩段階を追うことで、難しいと思っていたものがわかるようになるということを実感していただけていると思います。できれば、他のもう少し親切じゃない資料を読んだ時にもそこであきらめず、段階を追って理解して、そしてそうやって理解したものを、元よりもう少し親切な解説資料に書き換えてもらえればと思います。

前回の答えです。

1番ノードの 1個目の子ノードのインデックス: 2
1番ノードの 1個目の子ノードの番号: 2番
1番ノードの 3個目の子ノードの番号: 4番
4番ノードの 1個目の子ノードのインデックス: 9
4番ノードの 1個目の子ノードの番号: 6番
4番ノードの 2個目の子ノードの番号: 7番
7番ノードの 1個目の子ノードのインデックス: 15
7番ノードの 1個目の子ノードの番号: 9番

以上のような手順になります。たどり着いたノードは 9番になります。