2012/04/13

Trie4J - Java Patricia Trie Implementation

ちょこちょことまとめているパトリシアトライのJava実装ですが、現状のソースをGitHubにあげました。

https://github.com/takawitter/trie4j

記事では簡単のためラベルをString, 子ノードをList<String>で管理しているものを紹介していますが、この実装では
  • ラベルをchar[]、子ノードをNode[]で管理する、org.trie4j.patricia.simple.PatriciaTrie
  • ノードの状態(終端かどうか、子ノードを持つかどうかなど)に応じてクラスを変更し、かつ多層トライによるサイズ圧縮に対応する、org.trie4j.patricia.multilayer.MultilayerPatriciaTrie
の2つが含まれています(もう一つありますが、あまり効果無いのでそのうち消します)。 詳しい解説はまた後ほど(predictive search書けてから)。
コメントを投稿