darts-clone の Java 移植

矢田さんのdarts-cloneをJavaに単純に移植したので、GitHubに上げました。

https://github.com/hiroshi-manabe/darts-clone-java

darts-clone については、矢田さんの日記に詳しい解説があります。

これを移植したときは、仕事で使えるかと思ってやってみたのですが、結局そのときは容量の小ささを重視して takawitter さんのtrie4jを改造して使うことになりました。

せっかくなので置いておきます。

これはいろいろな事情があり、かなり Java 的でないものになっています。

その背景には、上記の trie4j の存在もあります。

trie4j はダブル配列も含むため、通常であればそちらを使うのが簡単でいいと思いますが、darts-clone はいろいろと変態的な工夫（1ノードあたり 4 バイトしか消費しないとか、値が同じであれば DAWG という仕組みでかなり容量が節約できるとか）があるので、そういうのを求める場合に使うのがいいと思います。

darts-clone-java では、キーは byte で渡すようにしています。

移植元の darts-clone では、テンプレートでキーの文字型を指定できるようになっているのですが、あいにく Java のジェネリクスでは基本型は使えないので、byte か String（UTF-16）かを選ぶ必要がありました。

しかし、darts-clone を UTF-16 で使っても「辞書サイズは大きくなるし，構築時間は長くなるし，隙間だらけだしと良いところが見つかりません」ということになるので（矢田さんの日記より）、byte にしました。

最初、String のラッパーメソッドも用意して、内部で UTF-8 に変換して処理することを考えていたのですが、結局やめました。

それにはいくつか理由があります。

まず、ビルド時にはキーをソートして与える必要があるのですが、このソート順が String と byte では違うものになります。

Java の String をソートするとき、Unicode のコードポイント順ではなく、UTF-16 の符号単位ベースでソートしているので、UTF-8 に変換したときのソート順と変わってしまいます。

これはわかりにくいので、最初から String は渡せないようにしました。

また、共通接頭辞検索のひとつの典型的な使い方は、長い文字列に対して開始位置をずらしながら何度も呼ぶというものです。

String のメソッドを用意してしまうと、長い文字列が何度も何度も UTF-8 に変換されるという悲劇が起こりかねません。

そのため、byte[] と開始位置のオフセットで検索するようにしました。

そもそも、darts-clone をわざわざ Java に移植するようなことがなければいいのですが…。

どうも Java では、いろいろな事情から C++ のライブラリを使うということをあまりせず（JNI というものはあるのですが）、何でも Java で済ませるということが多いようです。

これには、Java のパフォーマンスの高さがあると思います。

C のように Java を書くと、C に近いパフォーマンスが得られるので、それなら Java で書いたほうが扱いやすいということでしょうか。

しかし、darts-clone を Java に移植するにあたって、ネイティブ型のみをメンバに持つオーバーヘッドのないクラスというものが作れないため、結構面倒なことになりました。

C++ から JVM バイトコードにコンパイルできたら、Java からも扱いやすくていいと思うのですが。

trie を使うとき、速さ重視ならダブル配列、容量重視なら LOUDS を使うのが定番です。

上で挙げた trie4j は LOUDS も含んでいます。

ただ、現在のバージョンではキーと値を関連付ける方法がありません。

仕事では、速度はボトルネックになっていなかったので、上で書いたように結局 darts-clone-java は使わず、trie4j を改造して、キーとユニークな id を関連付けられるようにして使いました。

欲を言えば、marisa-trie（同じく矢田さんによる、LOUDS とパトリシアトライを組み合わせた実装）も Java に移植できればいいのですが、あまりにも複雑すぎて、手が出ませんでした。

ちなみに、あまり情報はないのですが、pinarell...@gmail.com さんによる marisa-javaという Java バインディングはあるようです。