2011-02-19

Trie が提供すべき操作について検討してみる

nokuno さんの記事「オープンソースのTrieライブラリまとめ」あたりを参考に、まず既存の Trie ライブラリ群がどのような API を提供しているのかを調査し、その上でこれから Trie を実装する場合に、どのような操作・API を提供すべきかを検討した結果のメモです。

記事にあるすべての Trie 実装を確認するのはしんどいので、代表的な感じのものを適当にピックアップしてみました。

  • Tx ... 岡野原さんによる簡潔データ構造を利用した Trie の実装。
    • prefixSearch() ... prefix search。Trie に格納されている文字列の中で、対象文字列の接頭辞としてもっとも長く一致する文字列を探し出す。common prefix search で列挙される文字列のうち、長さが最長のものと同じ。
    • commonPrefixSearch() ... common prefix search。Trie に格納されている文字列より、対象文字列の接頭辞にあたる文字列をすべて列挙する。結果は一括して求められる。
    • predictiveSearch() ... predictive search。Trie に格納されている文字列より、対象文字列が接頭辞となる文字列をすべて列挙する。結果は一括して求められる。
    • expandSearch() ... common prefix search + predictive search。Trie に格納されている文字列より、対象文字列を接頭辞とする文字列、または対象文字列の接頭辞にあたる文字列を列挙する。結果は一括して求められる。
  • UX ... Tx と同じく岡野原さんによるプロダクト。さらに簡潔。だいたい Tx と同じ API 構成。この命名は、"Tx" の1つ先(t -> u)を行く、という意味が込められているのかな?
    • prefixSearch() ... prefix search。
    • commonPrefixSearch() ... common prefix search。
    • predictiveSearch() ... predictive search。
  • sumire-tries ... やたさんによる、簡潔データ構造を含む各種 Trie の実装。Trie 木構造のノードレベルでの走査(traversal)ができるのが特徴。
    • TrieBase#find() ... exact match。Trie に格納されている文字列より、対象文字列に完全一致する文字列を探し出す。
    • TrieBase#follow() ... Trie・ノードの走査。指定されたノードから始まり、対象文字列に合致する Trie 上の経路(ノード)を辿る。
    • TrieBase#find_child() ... Trie・ノードの走査。あるノードより指定された文字を辿った先にある子ノードを求める。
    • TrieBase#child() ... Trie・ノードの走査。指定のノードの先にある子ノードのうち、最初の子ノードを求める。
    • TrieBase#sibling() ... Trie・ノードの走査。指定のノードの、次の兄弟ノードを求める。
    • class CompleterBase ... predictive search。Iterator パターンで、文字列を順次列挙する。
  • marisa-trie ... やたさんによる、簡潔データ構造を利用した Trie の実装。UX の手法をさらに発展させたものっぽい。
    • lookup() ... exact match。sumire-tries では find() でしたが、marisa-trie では同名メソッドは別の機能を提供しているようです。
    • find() ... common prefix search。一括して列挙する。
    • find_first()/find_last() ... prefix search。
    • find_callback() ... common prefix search。1つずつ、コールバック関数を呼び出して列挙する。
    • predict() ... predictive search。一括して列挙する。
    • predict_callback() ... predictive search。1つずつ、コールバック関数を呼び出して列挙する。
  • Darts ... MeCab 開発者の工藤さんによる Double Array Trie の実装。MeCab でも利用されています。
    • exactMatchSearch() ... exact match。
    • commonPrefixSearch() ... common prefix search。一括して列挙する。
  • Doar ... Igo/Gomoku の開発者 sile さんによる Double Array Trie の C++ 実装。
    • Searcher#search() ... exact match かな?
    • Searcher#common_prefix_search() ... common prefix search。1つずつ、コールバック関数を呼び出して列挙する。
    • Searcher#children() ... Trie・ノードの走査。子ノードを1つずつ、コールバック関数を呼び出して列挙する。
  • jada ... sile さんによる Double Array Trie の Java 実装。
    • Trie#search() ... exact match。
    • Trie#commonPrefixSearch() ... common prefix search。同メソッドを繰り返し呼び出して、1つずつ列挙する。

こんなところでしょうか。以上より「Trie を使った操作」は、
  • exact match
  • common prefix search
  • predictive search
  • prefix search
の4つが用意できるとよさそうです。少なくとも、上から3つは必須となりそうですね。

「Trie の走査を実現する走査」としては、ピックアップした実装ではあまり提供されていませんでしたが、
  • あるノードの直下の子ノードを列挙する
操作は必須となりそうです。

この結果を参考に、汎用的に使えそうな Trie の Java 実装について検討を進めてみます。
1:59No comments

2010-12-11

[メモ]MinGW/MSYS 環境で Kyoto Cabinet Core & Java バインディングをビルドする

本家から Windows 版がでた今となっては全く不要な記事となりましたが、せっかく書いたので残しておきます。

対象バージョン


1. 準備

Kyoto Cabinet のビルドを始める前に、依存ライブラリ regex と zlib をビルド&インストールする必要があります。

1.1 regex のビルド・インストール

上記 URL からダウンロードした regex の tarball を展開し、展開先ディレクトリにて
$ ./configure
$ make
 を実行します。make が終わったら、スタティックな libregex.a を作るため、
$ rm libregex.a
$ ar rcs libregex.a regex.o
 とします。その後、
$ make install
を実行し、regex のビルド・インストールは完了です。

1.2 zlib のビルド・インストール

zlib の tarball を展開した先のディレクトリにて、
$ make -f win32/Makefile.gcc
とし、Windows/gcc 環境用の Makefile を用いて make します。インストールの際は以下のように、事前に INCLUDE_PATH、LIBRARY_PATH の環境変数を定義する必要があります。
$ export INCLUDE_PATH=/usr/local/include
$ export LIBRARY_PATH=/usr/local/lib
$ make -f win32/Makefile.gcc install
以上で準備は完了です。

2. Kyoto Cabinet core library のビルド・インストール

g++ に渡すオプションを、以下のとおり定義します。
$ export CPPFLAGS=-D_WIN32_WINNT=0x0501
あとは、kyotocabinet の tarball 展開先ディレクトリにて、
$ ./configure
$ make
$ make check
$ make install
として、ビルド&インストールが完了します。

3. Kyoto Cabinet Java バインディングのビルド・インストール

3.1 準備

Kyoto Cabinet Java バインディングをビルドする前に、JDK をインストールした先のディレクトリの情報を MSYS の fstab ファイルに追記する必要があります。

fstab ファイルは、(MinGW のインストールルート)\msys\1.0\etc ディレクトリに配置されています。以下は、"C:\Program Files\Java" ディレクトリに JDK をインストールした場合の追記内容の例です。
C:\Progra~1\Java\jdk1.6.0_18 /java
上記のように、JDK をインストールした先のパスの途中に空白を含むディレクトリが存在する場合、チルダ ~ を使ってそのディレクトリ名を表記する必要があるようです(ダブルクォーテーションで括っても、MSYS は認識してくれません)。

3.2 ビルド&インストール

./configure を実行する前に、環境変数 JAVA_HOME を定義し (直し) ます。
$ export JAVA_HOME=/java
JAVA_HOME を定義したら kyotocabinet-java の tarball 展開先で
$ ./configure
とします。./configure が完了したら、出力された Makefile を一部修正します。以下のようにターゲット libjkyotocabinet.so.$(LIBVER).$(LIBREV).0 の内容に、jkyotocabinet.dll を生成するためのコマンドを追記します。
libjkyotocabinet.so.$(LIBVER).$(LIBREV).0 : $(LIBOBJFILES)
 $(CXX) $(CXXFLAGS) -shared -Wl,-soname,libjkyotocabinet.so.$(LIBVER) -o $@ \
   $(LIBOBJFILES) $(LDFLAGS) $(LIBS)
 ##### 以下の2行を追記する #####
 $(CXX) $(CXXFLAGS) -shared -Wl,--kill-at -Wl,-soname,jkyotocabinet.dll -o jkyotocabinet.dll \
   $(LIBOBJFILES) $(LDFLAGS) $(LIBS)
本来なら CPPFLAGS などの環境変数で解決したい内容なのですが、何故か kyotocabinet-java の ./configure では環境変数が反映されないようなので、やむを得ずこのような work around をしています。さて、Makefile の編集が終わったところで、
$ make
$ make check
とします。なお、make check は
make DBNAME="*" RNUM="10000" check-each
のテストの実行時にエラーになってしまうようです。この問題はまだ解消できていませんが、普通に利用する分には支障はないのかな、と思います。

後は、生成された jkyotocabinet.dll と kyotocabinet.jar を利用すれば、Windows 上でも Java から Kyoto Cabinet が使えるようになることでしょう(試していません…)。
2:26No comments

2010-11-21

「第8回 データマイニング+WEB 勉強会@東京」で発表してきました

11/14(日)に開催された「第8回 データマイニング+WEB 勉強会@東京」で、「協調フィルタリングにおける希薄問題の解決法 - Random walk」という題目で発表してきました。以下はその発表に使ったスライドです。


現在、本発表内容に関連した、もう一歩踏み込んで説明した補足資料を作成しています。11/23(火)までに作り終えられるといいなあ。

12/1 追記

補足資料を slideshare で公開しました。

23:34No comments