2010年06月30日

伏字検索の検索方法を改善しました。

従来の伏字検索○○○はメモリ上に展開した巨大なテキストを
頭から比較(grep)するだけのプログラムでした。
検索性能が悪くて1秒を超えることもよくありました。

また検索性能の悪さをごまかすために検索結果を
キャッシュし、2回目以降の検索はキャッシュデータを
利用して早く見せかけていました。

今回採用したのはSuffix Arrayというデータ構造を利用した
saryというツールです。

Suffix Array¤Î´Êñ¤ÊÀâÌÀ
横着プログラミング 第9回: sary: Suffix Array のライブラリとツール

ベンチマークを取ってみたところ大幅に改善できました。
0.1秒を切ることができたので、キャッシュの処理は不要と考え
削除しました。

変更前

山田太郎 0.27338s
山○太郎 0.34138s
山田○郎 0.31219s
山田太○ 0.31457s

変更後

山田太郎 0.00044s
山○太郎 0.00345s
山田○郎 0.01584s
山田太○ 0.00017s

劇的に速くなりました。

今日の教訓:データ構造重要

ご利用くださいまし.

posted by newonone at 23:42| Comment(0) | 伏字検索

2010年06月29日

さくらインターネット(スタンダード)にsary を入れる その2

さくらインターネット(スタンダード)にsary を入れる - newononeが作るネットサービス更新記録

のリベンジ記事です。

2007-12-03 - [foool]丘の上
を参考にしました。
が、自分の環境だとうまくいかないところもあったので
詳細をつらつらと書いておきます。

glib2.xのインストールに躓いて恐ろしく時間を
掛けてしまいました。5時間くらい。

.cshrc編集

setenv PKG_CONFIG_PATH $HOME/local/lib/pkgconfig
setenv LD_LIBRARY_PATH $HOME/local/lib:/usr/lib

libiconvのインストール

%wget http://ftp.gnu.org/pub/gnu/libiconv/libiconv-1.9.1.tar.gz
%cd libiconv-1.9.1
%./configure --prefix=$HOME/local
%make
%make install
%cd $HOME/local/lib/
%ln -s libiconv.so.4.0 libiconv

gettext のインストール

%tar zxvf gettext-0.18.1.1.tar.gz
%cd gettext-0.18.1.1
%./configure --prefix=$HOME/local
%make
%make install

glib2のインストール

%tar zxvf glib-2.25.10.tar.gz
%./configure --with-libiconv=gnu CPPFLAGS="-I$HOME/local/include" LDFLAGS="-L/$HOME/local/lib"
configure: error: *** No iconv() implementation found in C library or libiconv

このエラーがずっと消えない。
いろいろオプションを試してみたけど入れたはずのiconv()が見つからない。

Googleで調べてみた。

RE: No iconv() implementation found in C library or libiconv

以下のオプションで実行したら、configureは通った。

%./configure --with-libiconv=gnu CPPFLAGS="-I/usr/local/include" LDFLAGS="-L/usr/local/lib" --prefix=$HOME/local

ローカルにインストールしたiconv使ってないじゃん...
ひょっとしてgettextも入れなくて良かったのか。

ま、いっか。makeしてみます。

%make
dtrace -C -h -s -o glib_probes.h.tmp
dtrace: failed to open -o: No such file or directory
Error code 1

ダメでした。世の中の人はこれでビルドが通る人が居るのに。
もしかして2.25.10がダメなのか。
古いバージョンも試してみましょう。

  • glib-2.25.10 ... NG (dtrace: failed to open)
  • glib-2.24.1 ... OK

glibのバージョンを少し古いものにしてみたらビルドが通りました。

と言うわけでlibiconv,gettext,glibをアンインストールして最初から
やり直してみます。
blogにはここから書けばよいのですが、備忘録として残しておきます。

.cshrc編集

setenv PKG_CONFIG_PATH $HOME/local/lib/pkgconfig
setenv LD_LIBRARY_PATH $HOME/local/lib:/usr/lib

glib2のインストール

%source ~/.cshrc
%wget http://ftp.gnome.org/pub/gnome/sources/glib/2.24/glib-2.24.1.tar.gz
%tar zxvf glib-2.24.1.tar.gz
%cd glib-2.24.1
%./configure --with-libiconv=gnu CPPFLAGS="-I/usr/local/include" LDFLAGS="-L/usr/local/lib" --prefix=$HOME/local
%make
%make install

やっとsaryのインストールです。

%tar zxvf sary-1.2.0.tar.gz
%cd sary-1.2.0
%./configure CPPFLAGS="-I/home/onone/local/include/glib-2.0" LDFLAGS="-L/ho
me/onone/local/lib/glib-2.0" --prefix=$HOME/local
exact error that occured. This usually means GLIB is incorrectly installed.
configure: error:
GLIB 2.0.0 or better is required. The latest version of GLIB

GLIB 2.0.0以降が必要だよと怒られます。
GLIB のチェックを外してあげると通ります(邪道)

%./configure CPPFLAGS="-I/home/onone/local/include/glib-2.0" LDFLAGS="-L/ho
me/onone/local/lib/glib-2.0" --prefix=$HOME/local --disable-glibtest
%make
%~/local/bin/sary -v
sary 1.2.0

ビルドが通ったので動作を試して見ます。

%cat test.txt
this ia a pen
this ia a ipod
this ia a ipad
%~/local/bin/mksary test.txt
index: 100% |ooooooooooooooooooooooooooooooooooooooooo| Time: 00:00:00
sort: 100% |ooooooooooooooooooooooooooooooooooooooooo| Time: 00:00:00
%ls
test.txt test.txt.ary
%~/local/bin/sary pen test.txt
this is a pen

動きました。

sary-rubyのインストール

%tar zxvf sary-ruby-1.2.0.tar.gz
%ls
ChangeLog README.ja.rd extconf.rb searcher.c
MANIFEST Reference.en.rd init.c
Makefile Reference.ja.rd mkmf.log
README.en.rd builder.c rsary.rb

ノー。setup.rbがない。extconf.rbを使うようです。

%ruby extconf.rb
checking for sary.h... yes
checking for main() in -lsary... no

saryのライブラリを見つけてくれない。
saryライブラリのチェックで弾かれているようなので
チェックをはずして見ます(邪道再び)

%diff -u extconf.rb.org extconf.rb
--- extconf.rb.org      2010-06-28 23:48:29.000000000 +0900
+++ extconf.rb  2010-06-28 23:48:52.000000000 +0900
@@ -18,10 +18,10 @@
 $CFLAGS  += ' ' + `#{pkg_config} sary --cflags`.chomp
 $LDFLAGS += ' ' + `#{pkg_config} sary --libs`.chomp

-if have_header('sary.h') &&
-    have_library('sary')
+#if have_header('sary.h') &&
+#    have_library('sary')
   create_makefile('sary')
-end
+#end

 # Add make targets
 mfile = File.open 'Makefile', 'a'

%ruby extconf.rb
creating Makefile

Makefileができたようです。ビルドしてみましょう。

%make
/usr/bin/ld: cannot find -lintl
Error code 1

saryではなくintlというライブラリがないようです。
/usr/local/libもリンクのパスに追加してみます。

%diff -u Makefile.org Makefile
--- Makefile.org        2010-06-28 23:50:22.000000000 +0900
+++ Makefile    2010-06-28 23:51:07.000000000 +0900
@@ -49,7 +49,7 @@
 DEFS     =
 CPPFLAGS =   $(DEFS) $(cppflags)
 CXXFLAGS = $(CFLAGS)
-ldflags  = -L.  -rdynamic -pthread -L/home/onone/local/lib -lsary -lgthread-2.0 -lglib-2.0 -lintl
+ldflags  = -L.  -rdynamic -pthread -L/usr/local/lib -L/home/onone/local/lib -lsary -lgthread-2.0 -lglib-2.0 -lintl
 dldflags =  -Wl,-soname,$(.TARGET)
 archflag =
 DLDFLAGS = $(ldflags) $(dldflags) $(archflag)

もう1度ビルド。

%make
%make install
%make install
/usr/bin/install -c -o root -g wheel -m 0755 sary.so /home/onone/local/lib/ruby/site_ruby/1.8/i386-freebsd7
install: /home/onone/local/lib/ruby/site_ruby/1.8/i386-freebsd7/sary.so: chown/chgrp: Operation not permitted
Error code 71

できました。
make installするとroot/wheelでインストールしようとします。
これだとうまくいかないので手動で入れます。

/usr/bin/install -c -o onone -g users -m 0755 sary.so /home/onone/local/lib/ruby/site_ruby/1.8/i386-freebsd7

インストール完了。
あとはReference.en.rdを見ながらサンプルを動かしてみます。

test.rb

#!/usr/local/bin/ruby

require 'sary'

pattern = ARGV.shift

ARGV.each {|filename|
searcher = Sary::Searcher.new(filename)
if searcher.search(pattern)
searcher.sort_occurrences
searcher.each_context_line {|text| print text, "\n" }
end
}

%ruby test.rb ip test.txt
this ia a ipod

this ia a ipad

やっと動いたー。

疲れたので今日はココまでにします。

今日の教訓。
ビルドは大変。パッケージングシステムは偉大。

posted by newonone at 20:56| Comment(0) | Webプログラミング

2010年06月28日

さくらインターネット(スタンダード)にsary を入れる

すみません最終的に失敗したという記録です.

参考ページ 横着プログラミング 第9回: sary: Suffix Array のライブラリとツール

環境

筆者のページによるとGLIB2.0だとダメで1.2が必要だそうです。
glib-1.2.10.tar.gzを入手 from ftp://ftp.gtk.org/pub/gtk/v1.2/

glibのビルド。

% tar zxvf glib-1.2.10.tar.gz
% cd glib-1.2.10
% ./configure --prefix=$HOME/local_test
% make
gstrfuncs.c: In function 'g_printf_string_upper_bound':
gstrfuncs.c:870: error: expected ')' before string constant
gstrfuncs.c:1037: error: expected ')' before string constant
(中略)

Error code 1

あららエラーでコケます.

Linux上で同じ症状の人を見つけました。
Glib compile error

intramawebさんの質問に対し、limeric22さんが
gstrfuncs.cを修正して,つけるとうまくいくよと回答しています。

修正前:g_warning (G_GNUC_PRETTY_FUNCTION
修正後: g_warning (G_GNUC_PRETTY_FUNCTION,

これに対しstudiojさんがpatch書いたよコメント

追加 #define G_GNUC_PRETTY_FUNCTION

これに対しbpringlemeirさんがコメント
提供されたパッチはOKだけど、こう直したほうがいいんじゃないの?

削除 g_warning (G_GNUC_PRETTY_FUNCTION
削除 "(): unable to handle positional parameters (%%n$)");
追加 g_warning ("%s(): unable to handle positional parameters (%%n$)", G_GNUC_PRETTY_FUNCTION);

この後ちゃんと動いたよという報告がされている。

何箇所か直さなければならないのが面倒なので

#define G_GNUC_PRETTY_FUNCTION

を追加してみました。

試してみましょう。

%make
(中略)
creating type-test
%make install

glibのビルドに成功しました。

つぎはsaryのビルドです。

% tar zxvf sary-1.2.0.tar.gz
% cd glib-1.2.10
% ./configure --prefix=$HOME/local
checking for GLIB - version >= 2.0.0... gnome-config: not found
gnome-config: not found
gnome-config: not found
gnome-config: not found
gnome-config: not found
gnome-config: not found
no
Could not run GLIB test program, checking why...
The test program failed to compile or link. See the file config.log for the
exact error that occured. This usually means GLIB is incorrectly installed.
configure: error:
GLIB 2.0.0 or better is required. The latest version of GLIB
is always available from ftp://ftp.gtk.org/.

GLIB 2.0.0以上が必要なの?

横着プログラミング 第9回: sary: Suffix Array のライブラリとツール

sary では最新の GLIB 2.0 ではなく一世代前の GLIB 1.2 *7 を利用している。

作って理解するAjax --- No.3インクリメンタル検索を実現 [サーバー編] | 日経 xTECH(クロステック)

saryは,GLibライブラリ(バージョン2.0以降)が導入されているUNIX系OSで動作します。

どっちよー?

saryのChangeLogを見たら

Require GLIB 2.0.0 or later instead of GLIB 1.2.x

あらららら。
今までの苦労はいったい...

教訓としては「最新の情報をちゃんと調べましょう」
というところでしょうか。

と言うわけで今日はあきらめます。

posted by newonone at 22:28| Comment(0) | Webプログラミング