rxを読んだメモ
rxはGoogle日本語入力（Mozc）でも使われているTrieのライブラリである。LOUDSというツリーを表す簡潔データ構造を使ってTrieを実現している。第2回自然言語処理勉強会@東京に行ってきて、そういえばrxは読んでなかったなと思ったので、ちょっとだけ読んでみた。あくまでもメモ書きである。絵があると100倍ぐらいわかりやすくなる気がするけどメモなので絵は描きません。
- 読んだのは現在公開されている最新版であるrx-1.0rc4。
- rxというのとrbxという2つの機能がある。rxが実現しているのはあくまでもtrieで、値的なものとしてはノードIDしか取れない。rbxはノードIDのような整数から、任意の長さのバイト列を引っ張ってくるためのライブラリ。普通の配列は当たり前だが要素が固定長であるので、要素が可変長であるというところがrbxの大きな特徴である。
- rxでのエッジに対する文字割り当てはどうやって処理しているか→Txと同様、別の配列に保存してある。エッジの要素サイズは1byte固定のライブラリが多いが、rxでは1byte以下にすることもできる。
- rbxは任意のバイト長でデータを保存できる。
- 例えば、3byte, 2byte, 4byteのデータを突っ込んだ場合、データ本体は本体用の配列に書き込まれる。特にデリミタなどはない。その他に、添字から実際の場所へと変換するためのビットベクターを構築する。このビットベクターでは、各データのサイズ分だけ1を並べて0を置く、ということを繰り返したもので、rank,select操作付きである。3byte, 2byte, 4byteのデータを突っ込んだら、ビットベクターは0111011011110となる（検索の都合上、先頭に0を付与した）。2番目のデータ(2byteのやつ)にアクセスする際には、まずbv.select0(2-1)をすると4という数値が得られる。0はビットベクター側でのデリミタなので、データ本体の配列へアクセスする際には1の数だけを数えたい。そこで、bv.rank1(4)とすると、データ本体で何バイト目にアクセスすればいいのかがわかる。データの長さもビットベクターを見ればわかる。
- rbxではデータのサイズ分だけ1を並べる。LOUDSのノードの持つ子要素の数だけ1を並べるという手法と、やり口がよく似ている。
- 実際のrbxでは要素の最小サイズが決められたり、任意のバイト長ではなくもっと大きな単位でデータを保存できたりと、ビットベクターを小さくするためにいくつか工夫がある。
- 上の説明ではbv.select0(2-1)とか書いてるけど、rxはC言語で書かれているので実際のソースコードはこんなメソッド呼び出しの形にはなっていない。読みやすいように勝手にC++風に書いた。
作るのは絶対にrxの方が大変だったと思うのだが、どちらかというとrbxの仕様の方に感心した。よく考えられている。
それにしても、なぜTrie系のライブラリはぐぐりにくい名前が多いのか。Dartsあたりから連綿とぐぐりにくい名前がつけられている気がする。
