海風に揺れる一輪のTRIEライブラリ erikaを作ってみたよ
注意：この記事の内容は古いものです。
最新版のerika-trieは
erika-trie(実用版)とキーワード抽出ツールerika_extractを作ったよ - EchizenBlog-Zwei
うっかり手が滑って自分で☆つけてしまいましたが自画自賛してるわけではないです・・・。
をご参照ください。
最近TRIE(トライ)に対する興味が高まってきたので勉強のためにライブラリを作っていた。一応完成したので公開しておく。普通のTRIEとLOUDSによるTRIEの二つを実装した。
名前はerika。もしくはerika-trie。以前作ったCompressed Suffix Arrayのライブラリがtsubomiだったので、今回はerikaにした。コードはGoogleCodeのtsubomiと同じところにおいてある。というかtsubomiの付属品状態。開発はlinuxで行ったが特に環境に依存したコードはないのでどんな環境でも動く(はず)。
参考:
もっともTRIEに関しては世の中にはtxやらmarisa-trieやら優れたライブラリがたくさんあるので、erika_trieはあくまで勉強用。凝ったことはしていないのでコードを読むのも楽だと思われる。今後勉強を兼ねて色々と手を入れていく予定。
以下、使い方と簡単な評価など。
まずコードを入手。make erikaする。
$$ svn checkout http://tsubomi.googlecode.com/svn/trunk/ tsubomi $$ cd tsubomi $$ make erika
するとerika_mktrie, erika_searchというツールができる。このツールは適当に書いたサンプルコード的なものなのであまり洗練されていない。使い方を以下で説明。
まず1行1エントリなファイルを用意。今回はtsubomiの時と同様、住所データを使う。
$$ mkdir var $$ cd var $$ wget http://jusyo.jp/downloads/new/csv/csv_zenkoku.zip $$ unzip csv_zenkoku.zip $$ nkf -w zenkoku.txt > zenkoku.txt.utf8 $$ perl -ne '@a=split(/\t/);$s="$a[7]$a[9]$a[11]";$s=~s/"//g;print "$s\n"' zenkoku.txt.utf8 > zenkoku.key $$ sort -u zenkoku.key -o zenkoku.key $$ cd ..
次にerika_mktrieをすると普通のTRIE、LOUDS版TRIEができる。
$$ ./erika_mktrie var/zenkoku.key $$ ls -la var/zenkoku.key* -rw-rw-r--. 1 xxxx xxxx 3869373 2010-09-04 10:10 zenkoku.key -rw-rw-r--. 1 xxxx xxxx 6069182 2011-05-24 10:24 zenkoku.key.bt -rw-rw-r--. 1 xxxx xxxx 3057650 2011-05-24 10:24 zenkoku.key.lt
これでvar/zenkoku.key.bt, var/zenkoku.key.ltというファイルができた。前者が通常のTRIEで後者がLOUDS版。LOUDS版のほうがサイズが小さいのがわかる。すばらしい。(一般に通常のTRIEの空間計算量がO(NlogN)なのに対してLOUDSはO(N)になる。)
さて次に検索を実行してみる。キーを先頭部分として含むものを見つけてくるようになっている(marisa-trieのpredictと同じ)。
$$ wc -l var/zenkoku.key 117957 $$ time ./erika_search var/zenkoku.key.bt < var/zenkoku.key > hoge real 0m7.313s user 0m3.132s sys 0m2.909s $$ time ./erika_search var/zenkoku.key.lt < var/zenkoku.key > hoge real 0m7.532s user 0m3.647s sys 0m2.791s
どちらのTRIEもそんなに大きく差は出なかった。LOUDSすごい。もっと大きいデータだと差が出るのかも。あと本当はSTL::mapとかと比較もしたら良かった気がしたが眠いので別の機会に。
以上。説明終わり。簡単に実装できる割には性能が良かったんじゃないかと思う。久々にまともなコードを書いたので楽しかった。手抜きした部分が多いので改善の余地は色々ある。今後手を入れていくかも。
