/darts-java

Java porting of Darts (Double ARray Trie System)

Primary LanguageJava

darts-java: Double-ARray Trie System Java implementation.

概要

Taku Kudo さんの Double Array Trie の C++ 実装 (*1) を MURAWAKI Yugo さんが Java ポーティングしたバージョン (*2) に対して、 より Java らしいインタフェースに変更し、また性能面も改善した Darts の Java 実装です。

元実装 (Java ポーティング版) からの改善点

  • インタフェースの改善
  • 文字列の char[] 表現や配列の多用を改め、より Java らしいインタフェースで、かつ手軽に利用できるインタフェースとしました。
  • 入力データによってエラーとなるケースへの対処
  • ヒープ消費量の改善
  • Trie 構築時、および構築後のヒープ消費量が少なくなるようにしました (元実装の約 26% のヒープ消費量)。
  • 実行速度の改善
  • Trie の構築 (約 2.6 倍) や exact match での検索 (約 1.7 倍)、common prefix での検索 (約 1.2 倍) それぞれについて処理性能を向上しました。

使い方

DoubleArrayTrie.java を単品でご利用ください(実装はこのファイル一つで完結しています)。

Benchmark

テストデータ

Ubuntu 12 の /usr/share/dict/words (916 KB、99171 語) をテストデータとして利用しています。

測定方法

  • ヒープ消費量
  • DoubleArrayTrie#build() の呼び出し前後それぞれにおいて、ヒープ消費量を Runtime#totalMemory() / Runtime#freeMemory() にて計測し、その差分をとることで 構築後のヒープ消費量を算出しています。
  • build() 処理時間
  • ファイルから読み込んだテストデータを build() で 50 回処理し、その平均と標準偏差を算出しています。
  • exactMatchSearch() 処理時間
  • テストデータをもとに構築された Trie に対して、テストデータの語句すべてを 順に exact match 検索する処理を 50 回実施し、その平均と標準偏差を算出しています。
  • commonPrefixSearch() 処理時間
  • exactMatchSearch() と同様に、テストデータをもとに構築された Trie に対して、 テストデータの語句すべてを順に common prefix 検索する処理を 50 回実施し、その平均と標準偏差を算出しています。
  • 元実装では、commonPrefixSearch() の結果を同メソッドに渡した int 配列で受け取るインタフェースと なっているため、検索結果の個数を求めるためと、実際の結果を受け取るためのそれぞれ1回ずつ (合計2回)、commonPrefixSearch() を呼び出しています。

測定結果

                              original     imploved
====================================================
ヒープ消費量 [byte]         62,287,864   16,780,160
----------------------------------------------------
build() [msec]                  165.68        64.26
  (標準偏差)                    (82.87)       (6.74)
----------------------------------------------------
exactMatchSearch() [msec]        10.88         6.24
  (標準偏差)                     (7.21)       (7.73)
----------------------------------------------------
commonPrefixSearch() [msec]      17.18        14.04
  (標準偏差)                     (4.68)       (4.75)
----------------------------------------------------

License

LGPL と修正 BSD のデュアルライセンスです。 各ライセンスの詳細は LGPL ファイル、BSD ファイルをご覧ください。

TODO

  • Javadoc を記述する。