全文検索システム Namazu Version 1.2.0.1 説明書

Last Modified: 06/22/1998


はじめに

このファイルは主にプログラムの使い方をまとめたマニュアルです。 ソフトウェアの概要に関するドキュメントは intro.html の方を参照してください。 このプログラムは GPL2 (日本語訳) に従ったフリーソフトウェアです。 著作権は高林哲が保有します。 完全に無保証ですので運用は個人の責任で行って下さい。 バグの発見や Namazu をこんな風に使っています、というような報告を頂けるとありがたいです。

目次

Namazu の最新情報を得るには

http://saturn.aichi-u.ac.jp/~ccsatoru/Namazu/ に Namazu のページがあります。 私が在学している間 (1999 年 3 月までの予定) はここにあると思われます。

ヴァージョンの違いについて

v1.2.0 では

といった大きな変更が行われています。フレーズ検索用のインデック スを作成するためにメモリの使用量が多くなっています。また、処理にか かる時間もそれにともなって増えました。ご注意ください。フレーズ検索 が不要な方は mknmz を -P オプションつきで実行してください。

また、多言語を意識して NMZ.(head|foot|body|msg) に日本語ならば `.ja' 英語ならば `.en' というように言語別のサフィックスをつけるこ とにしました。従来の NMZ.(head|foot|body|msg) は単純に末尾に .ja と付け加えればそのまま使えます。自動的に処理するには

% ls NMZ.{head,foot,body,msg} |perl -nle 'rename($_,"$_.ja")'
% ls NMZ.{head,foot,body,msg}-e |perl -nle 's/-e$//;rename("$_-e","$_.en")'

のように実行すると良いでしょう。

その他の変更点については ChangeLog.ja を参照してください。

動作環境

動作に必要なソフトウェア

あると便利なソフトウェア

KAKASI, nkf, httpdown は
http://saturn.aichi-u.ac.jp/~ccsatoru/Download/
にも置いてあります。

KAKASI/ChaSen について

日本語を扱うために KAKASI または ChaSen を必要とします。 KAKASI を用いる場合は、京都大学の馬場肇さんが作成された「わかち書きパッチ」をあてた KAKASI でなければなりません。 FreeBSD の ports に収録されている KAKASI は FreeBSD 2.2.5-RELEASE から「わかち書きパッチ」が当たっているようです。 このパッチは元々 freeWAIS-sf を日本語化するために作成されたもので、馬場さんの freeWAIS-sf japanization information から情報が手に入ります。

このパッチは 09/02/1997 付けで更新され、 kakasi -Ea -w と実行したときの小さなバグが取れました。 Namazu ではこのバグを吸収するルーチンをいれてありますが、 KAKASI 自身を新しくしたほうが良いでしょう。

KAKASI (with wakatigaki mode) を作成するには kakasi-2.2.5.tar.gz (約 47 KB), kakasi-ext.tar.gz (約 7 KB), kakasidict.940620.gz (約 870 KB) の 3 つのファイルを get してソースにパッチをあてた後で make をします。 実際の手順については KAKASI のドキュメントを参照してください。

ChaSen は奈良先端科学技術大学院大学で開発された本格的な日本語の形態素解析を行うソフトウェアです。 単純にわかち書き出力をさせる分には KAKASI と比べて品質にそれほど差はないようですが、品詞情報の抽出を行えるためきめの細かい日本語処理を行うことができます。 ChaSen を使用するには必要なファイルを http://cactus.aist-nara.ac.jp/lab/nlt/chasen.html から取得してドキュメントに従って make してください。

両者を比べると、処理速度は KAKASI の方が高速です。 また、展開後の辞書のサイズは ChaSen が 約 7 MB, KAKASI が約 2 MB になります。 ディフォルトでは KAKASI を用いるものとして設定してあるため、 ChaSen を用いるにはいくつかの注意が必要です。 ドキュメントをよく読むようにしてください。 ChaSen による品詞情報を利用した処理を行う効果については ChaSen による品詞情報の利用を参照してください。 現在はまだ実験段階です。

日本語のインデックス処理の品質は用いる辞書に依存します。 KAKASI の標準の辞書は 10 万語以上の単語が登録されているので、ごく標準的な文章ならば特に不満もなく使えると思われますが、人名、地名、専門用語などについてはどうしても弱くなります。 この欠点を補うために KAKASI では辞書の強化が比較的容易に行えるようになっており、フリーの専門用語辞書なども出回っているようですから、それらを用いることをお勧めします。 この辺りの問題点については馬場さんの freeWAIS-sf japanization information日本語化パッチの問題点の章に詳しいです。

フリーの辞書のポインタ集

中には条件によって使用制限があるものもあるかもしれません。 よくドキュメントを読んでから使用した方が良いでしょう。

動作の確認されている環境

過去に一度でも Namazu の動いたことのある環境です。 もしかしたら Namazu の新しい版では動かないかもしれません…。

OS

C コンパイラ

Perl

httpd

上記以外の環境で動作に成功された方はの方までぜひ御連絡ください。

Win32 での動作について

Win32 で make するのは結構大変です。わざわざ make しなくても Win32 用のバイナリ・パッケージ を使えば比較的容易に動かすことができます。 その場合についてはWin32 用のバイナリ・パッケージを用いるの項を参照してください。

ソースから自分で make するにはまず、

といったソフトウェアを集めてきてインストールする必要があります。 Perl for Win32 は CPAN の ports/win32/ActiveWare/Release/Pw32i315.exe で動作確認しました。 さらにこれらとは別に日本語 EUC, JIS コード対応のエディタ (Mule for Win32 や秀丸) もあった方が良いでしょう。 Web Server としては Apache-1.3b3-win32, OMNI HTTPD, fnord 1.0.0.23, ANhttpd あたりが使えるようです。

OS/2 での動作について

OS/2 への移植は清水@住友林業さんが行ってくれました。動作には

が必要になります。 Makefile は専用の Makefile.OS2 が用意されていますのでこちらをご利用下さい。 OS/2 での動作については清水さんのウェブ・ページ に情報があります。

インストールの方法

ソースからインストールする

アーカイヴの展開

まずはアーカイヴを展開します。GNU 版の tar なら

tar xzvf namazu-xxx.tar.gz

そうでなければ

gunzip -c namazu-xxx.tar.gz| tar xvf -
zcat namazu-xxx.tar.gz | tar xvf -

のようにしてファイルを展開してます。

configure の実行

v1.2.0 からは configure が添付されました。まず最初に

./configure

のように実行して Makefile を作成します。 Perl, KAKASI/ChaSen, nkf のパスは自動検出します。

通常は configure の作成した Makefile がそのまま使えますから何も修正しないで make を実行して構いません。編集したい場合は次の項を参照してください。もっとも単純な Namazu のインストール方法は以下の通りです。

./configure
make
(必要に応じて root になって)
make install

大抵はこれでうまくいくと思います。何か問題が発生した場合はお使いの 環境やエラーメッセージなどの詳しいレポートを私の方まで送ってもらえ れば対応できるかもしれません。

Makefile の編集

v1.1.0 からは Makefile を編集してインストールします (原型は佐藤文優@cij.co.jp さんが作ってくださいました Thanks!)。必要に応じて

BASEDIR = /usr/local
CGIDIR = $(BASEDIR)/etc/httpd/cgi-bin
NAMAZUDIR = $(BASEDIR)/namazu
BINDIR_SYS = $(BASEDIR)/bin
BINDIR = $(NAMAZUDIR)/bin
INDEXDIR = $(NAMAZUDIR)/index
DOCDIR = $(NAMAZUDIR)/doc
LIBDIR = $(NAMAZUDIR)/lib
OPT_NAMAZU_CONF = $LIBDIR/namazu.conf
OPT_URL_CGIBIN = /cgi-bin
OPT_ADMIN_EMAIL = webmaster@foo.bar.jp

OPT_PATH_PERL = /usr/bin/perl
OPT_PATH_NKF = /usr/local/bin/nkf
OPT_PATH_KAKASI = /usr/local/bin/kakasi
OPT_PATH_CHASEN = /usr/local/bin/chasen
WAKATI = KAKASI
LANG = ja

あたりを自分のサイトに合わせて変更します。それぞれ

CGIDIR = $(BASEDIR)/etc/httpd/cgi-bin
namazu.cgi をインストールするディレクトリ。
NAMAZUDIR = $(BASEDIR)/namazu
Namazu をインストールするディレクトリ。
BINDIR_SYS = $(BASEDIR)/bin
Namazu の検索コマンド namazu をインストールするディレクトリ。
(検索コマンドだけは /usr/local/bin などにも入れて欲しいです)
BINDIR = $(NAMAZUDIR)/bin
Namazu の実行ファイル (namazu, mknmz, wdnmz) をインストールするディレクトリ。
INDEXDIR = $(NAMAZUDIR)/index
mknmz によって作成され、namazu.cgi が参照するインデックスを格納するディレクトリ。
DOCDIR = $(NAMAZUDIR)/doc
Namazu ドキュメント類 (このファイルなど) を格納するディレクトリ
LIBDIR = $(NAMAZUDIR)/lib
Namazu のライブラリなどを格納するディレクトリ
CONTRIBDIR = $(NAMAZUDIR)/contrib
contribute して頂いたプログラム類を格納するディレクトリ
OPT_NAMAZU_CONF = $(LIBDIR)/namazu.conf
namazu.conf (設定ファイル) のパスを指定します。
URL_CGIBIN = /cgi-bin
namazu.cgi をアクセスするための相対 URL。この URL に `/namazu.cgi' が付加されて使用される。
OPT_ADMIN_EMAIL = ccsatoru@vega.aichi-u.ac.jp
検索エンジン管理者のメールアドレスを設定します
OPT_PATH_*
それぞれのプログラムの場所の指定 (KAKASI と ChaSen はどちらか片方あれば OK です)
WAKATI = KAKASI
日本語の処理に KAKASI を使うという意味です。
LANG = ja
表示メッセージの言語を ja or en で指定します。

となっています。 Makefile 自体にコメントをいれているのでそちらも参照してください。 Makefile で指定できない細かい設定をする場合は直接ソースを修正することになります。

make

make には sed が必要です。また、 Win32 の場合は \bin に GNU-Win32 の sh.exe を置いておく必要があります。 Namazu の make は基本的には

1.ゴミ掃除をする
make clean
2.Namazu を作る
make
4.Namazu をインストール
make install

の手順になります。 make が成功するとそれぞれ mknmz, wdnmz, namazu* が作成されます。 make install でインストールされます。 CGIは make install_cgi でインストールします。

バイナリ・パッケージの場合

Win32 用のバイナリ・パッケージを用いる

Namazu のWin32用のパッケージを広瀬@NECエンジニアリングさんが用意してくださいました。 また、全文検索システム Namazu for Win32のホームページも作って頂きました。 Win32版に関する詳しい情報はそちらを参照してください。

Namazu の Win32 用バイナリ・パッケージに含まれる namazu.exe および kakasi.exe は GNU-Win32 の gcc で make されています。実行には cygwin.dll が必要ですので、注意してください。 mknmz の方は

perl mknmz

のように perl に実行させます。 基本的にこのマニュアルの内容は UNIX用に書かれていますが、 Win32 でもほぼ同じような使い方ができるかと思います。 ただ、プログラムの性質からして初心者向けではないでしょうから、 ある程度の知識がある方じゃないと難しいかも知れません。

NMZ.head.ja, NMZ.foot.ja を編集するために JIS コード対応のエディ タ (Mule for Win32 や秀丸) が必要になります。これらも用意しておい てください。

Win32の対応についてはどの程度需要があるのか良く分かっていませんので、 動作報告やご意見などを頂けると助かります。

使い方

基本編

インデックスを作成するには mknmz の引数にインデックスを作成する元となるファイルのあるディレクトリ名を与えます。 つまり /home/foo/public_html を対象とするならば

% mknmz /home/foo/public_html

と実行すれば /home/foo/public_html 以下の *.html *.txt といったファイル (Makefile の OPT_TARGET_FILE に定義されています) をすべてインデックスして、 mknmz を実行したカレントディレクトリに NMZ.* というファイルを作成します。 mknmz にはいくつかのオプションがあります。 それらについては mknmz のコマンドライン・オプション の項で述べます。

二度目以降のインデックス作成の際は、前回以降に追加されたファイルのみを抽出して追加する仕組みになっています。 一度インデックスしたファイルに関しては登録ファイル・リスト (NMZ.r) に名前が記録されるので消してしまっても構いません。 インデックスは追加のみ可能という仕様になっています。

make で作成された namazu が検索プログラムです。

% namazu /home/quux/namazu/index "bar"

のように実行すれば、 /home/quux/namazu/index (これは Makefile の INDEXDIR で設定したディレクトリの場合は省略できます) にある NMZ.* をもとにキーワード bar を検索します。 namazu のコマンドライン・オプションは別の項で説明します。 ディフォルトではコマンドラインから実行した際はプレインなテキストで出力します。 HTML で出力したい場合には -h オプションを指定します。

また、

% namazu /home/quux/namazu/index/hoge1 /home/quux/namazu/index/hoge2 "bar"

のように複数のインデックス (hoge1, hoge2) を指定することもできます。

CGI として使う

CGI として動作させる場合は検索対象となるインデックス・ファイルを Makefie の INDEXDIR で指定したディレクトリ、 または namazu.conf ファイルで設定した場所にに置く必要があります。 そうでないと CGI プログラムから参照できないので注意してください。

ディフォルトでは mknmz によって作成されるインデックスには <A HREF="/home/quux/public_html/index.html"> のように URL が展開されています。

ローカルのディスクを対象としたときはこれで良いと思いますが、 WWW 用の検索エンジンを作るときは困ります。

CGI として用いるために http:// から始まる URL を作成するにはいくつかの方法があります。 一つは

namazu.conf

REPLACE /home/foo/public_html/ http://foo.bar.jp/%7Efoo/

のように指定しておくことで (各項目は TAB で区切ってください)、 検索結果の出力時に /home/foo/public_html/ の部分を http://foo.bar.jp/%7Efoo/ に動的に置き換えて出力することができます。この方法ではひとつのインデックスをローカル用と CGI 用と共用できるのが利点です。 コマンドラインから検索するときには -R オプションを指定することでこの置き換えを行わないようにすることができます。

別の手法としては

mknmz "http://foo.bar.jp/~quux/" "/home/foo/public_html"

のように引数に自分の URL を指定する方法もあります。 これは mknmz がインデックス作成を行う際に対象ディレクトリへ移動し、 &find() を実行して得られる

./index.html

というファイル名の頭に http://foo.bar.jp/~quux/ をくっつけて URL を作り出します。 毎回これを入力するのが面倒という場合は、 mknmz のソースの頭の方にある

$URL_PREFIX = "\t";

の部分を修正して任意の URL を書いておくことです。 例えば

$URL_PREFIX = "http://foo.bar.jp/~quux/";

のように設定します。

三つ目の方法は httpdown で取得されたファイルのように URL をそのまま示すようなディレクトリ構造を作ってしまう方法です。 これはシンボリック・リンクを使うと無駄が無くて良いでしょう。 具体的には /home/quux/hogehoge/foo.bar.jp というディレクトリを作成してその下に "~quux" という名前で /home/quux/public_html をシンボリック・リンクしておくのです。 これで mknmz でインデックス作成を行う際に /home/quux/hogehoge を指定することによって期待通りの URL に展開できるはずです。 ややこしいと思うかもしれませんが、ちょっと考えてみれば単純なことだと思います。 このようにシンボリック・リンクを張る方法を用いれば、サーヴァにアカウントを持っているすべてのユーザの public_html をまとめてうまく処理することができます。

インデックス作成時には

mknmz "http://" "/home/quux/hogehoge"

のようにします。

末尾がディレクトリで終わる URL の表記をしたい場合もあります。 普通は index.html は省略できるように設定されているものです。 これは Makefile の OPT_DEFAULT_FILE で指定できます

_default などという名前がディフォルトなのかというと、これは httpdown でファイルを取得したときに末尾がディレクトリの URL のファイルは _default という名前で保存されるからです。

相対パスの URL を作りたい場合は

mknmz "" "/home/foo/public_html"

のように URL の指定を "" と null で指定します。 相対パスで URL を作成した場合は検索結果表示に <BASE HREF="..."> を出力するようにします。 namazu.confBASE の設定をしてください。

検索プログラムは (日本語ならば) NMZ.head.ja と NMZ.foot.ja というヘッダとフッタのファイルを参照します。 これらは mknmz を実行した際にサンプルが作成されますが、必要に応じてタイトルとメッセージを自分用に書き直しておきましょう。 この NMZ.head.ja と NMZ.foot.ja にあるファイル数やキーワード数の記 述されている部分はインデックスを更新した際に、自動的に更新されるよ うになっているので、 <!-- FILE --> といったダミー のタグを消さないでください (そんな情報は必要ないというのなら削除し ても構いません) 。

一通りの設定が終わったらブラウザから CGI としてアクセスしてみてください。 NMZ.head.ja, NMZ.body.ja, NMZ.foot.ja を元にした表示を行います。 メッセージは自分のサイトに合わせて書き替えてください。 その際は文字コードを必ず ISO-2022-JP で保存します。

…というように、書かれたことを読むだけだと難しく感じるかもしれませんが、実際に試してみれば、単純な仕組みであることが理解できるかと思います。

mknmz のコマンドライン・オプション

これらのオプションは -am のようにつなげて指定しても -a -m のように別々に指定しても構いません。 ただし、 -I オプションの後ろにはひとつ空白をあけて次の引数でファイルを指定するようにしてください。 -k -c -m のいずれかのオプションを省略した場合は Makefile の WAKATI で指定したものが使われます。

-I オプションに続けてファイルを指定すると、 mknmz 実行時にそのファイルをインクルード (require) します。 これは主に変数を上書きするのに役立ちます。

-R と -Pオプションはそれぞれ正規表現用インデックスとフレーズ検 索用インデックスを作成したくないときに指定します。

Perl 版の検索クライアントを使う

contrib ディレクトリに収録されている Perl版の検索クライアントを使うことによって C のソースをコンパイルすることなしに、検索が行えます。 コマンドラインからの使い方は C言語版とほぼ同じで、また、 CGI としても動作しますから、 プロバイダなどで C コンパイラが使えない環境などで役立つと思います。

KAKASI を用いずに日本語を分解する機能を持っているので、巨大な辞書を用意する必要がないのも特徴です。 検索にかかる時間は C言語版に比べてほとんど遜色ありません。

namazu のコマンドライン・オプション

$namazu [-nwsvhHela] "key string" [index dir(s)]

のように実行する形になっています。 [index dir(s)] は検索対象となるインデックスの置いてあるディレクトリの指定ですが、 Makefile の INDEXDIR で設定したディレクトリの場合は省略することができます。オプションは以下の通りです。

これらのオプションは必ず -ahs のようにまとめて指定することができます v1.1.2.3。

コマンドラインから実行したときはディフォルトでプレインなテキストとして検索結果の表示を行います。 HTML で出力する場合には -h オプションを使います。 CGI から検索したときは結果が一度に表示できないと下の方に [1] [2] [3] のように先の検索結果へ進むためのリンクが作られますが、 コマンドラインから実行したときにはこれらの表示は無意味なので、表示しないようになっています。 この余分な表示を何らかの理由によって強制的に表示させるには -H オプションを使います。 また、コマンドラインから実行したときはディフォルトで <FORM> ... </FORM> を表示させないようになっていますが、 -F をつけると強制的に表示させることができます。

-a オプションは検索結果をすべて表示させます。 これはコマンドラインから実行したときだけの特別なオプションです。 CGI として使う場合はすべてを表示することは敢えてできないようにしています。

検索結果の 21 件目から 40 件目までを表示させたいという場合には -n 20 -w 20 のように指定します。 -w の値が 21 でないところに注意してください。 これはちょっと変ですが、今更変更するのもあれなので仕様ということにします:-)。

-U オプションはコマンドラインから実行して plain text で結果出力する際に URL encode のデコードを行わないためのオプションです。ディフォルトでは行われるようになっています。

namazu.conf での設定について

namazu.conf および .namazurc ではいくつかの設定が行えます。 namazu は

  1. namazu を実行したディレクトリにある .namazurc (CGIのときに便利でしょう)
  2. ユーザのホームディレクトリにある .namazurc
  3. Makefile で LIBDIR に指定したディレクトリにある namazu.conf (通常は /usr/local/namazu/lib/namazu.conf)

の順で探して見つかればこれをリソースファイルとして読み込みます。

オリジナルは namazu.conf-dist という名前になっているので、 これを namazu.conf または .namazurc という名前にコピーして使います。 オリジナルは残しておいた方が良いでしょう。 これは主に make 時の設定とは違う環境に合わせるときに用います。

各項目と値は TAB で区切ります。これは仕様ですので注意してください。設定の意味は以下の通りです。

必要な設定は make 時に行っているので、 特に変わったことをしようとしない限り、 namazu.conf で設定をする必要はありません。 make 時に -DNOCONF を指定することでこのファイルの参照を抑制することができます。

実際の検索に役立てる

コマンドラインから検索する

namazu をコマンドラインから実行した場合、その出力をパイプで less に渡して眺めることができますが、 せっかくの検索結果を元にリンクを辿っていくことができないのであまり便利ではありません。

namazu -h "keyword" > kekka.html

のように出力を HTML でファイルに書き出してそれをブラウザで読み込めば検索結果のリンクをたどることができます。

これはちょっと面倒だぞ、という方のために上の処理を自動化してくれるコマンドライン用検索クライアントを馬場肇@京大さんが作ってくださいました。 これは

bnamazu -b "browser" -d "database" "keyword"

のように実行することで、 keyword を検索し、その結果をテンポラリ・ファイルに保存してそれを自動的に browser で指定したブラウザに渡して読み込ませるというツールです。 -b browser を省略するとディフォルトでは Netscape Navigator が呼び出されるようになっています。

-d database は検索対象とするインデックスのあるディレクトリを指定します。これを省略した場合は namazuDEFAULT_DIR が対象となります。

これはなかなかセコイようでいて、結構便利なツールです。 Namazu のパッケージを展開したときにできる contrib ディレクトリに入っています。ぜひお試し下さい。

コマンドラインから使うのもなんだかなあという方は Mule や X, Win32 から使えるそれぞれの検索フロントエンドを使うと便利でしょう。 または Lynx の lynxcgi の機能を使って http を通さずにローカルの CGI として namazu を実行して検索することもできます。 以下の説明を参照してください。

http を通して CGI として検索する

CGI として動作させることで WWW 全文検索エンジンになります。 インターネットを通して広く公開しても良いですし、イントラネットとして内輪だけで共有する使い方も考えられます。 普段使い慣れたブラウザで閲覧できるところも利点ですね。

http を通さず Lynx から検索する

Lynx をお使いの方は lynxcgi の機能を使って http を通さずに CGI を実行して検索することができます。これは NMZ.head の

<FORM> の部分を

<FORM METHOD="POST" ACTION="lynxcgi://localhost/home/foo/cgi-bin/namazu">

のように METHOD を POST にして ACTION の部分を lynxcgi://localhost/ の後に namazu の実行ファイルのフルパスを指定しておくことで実現します。同じように lynxcgi.html の ACTION の指定も確認してください。

以上の準備が整った後は Lynx から lynxcgi.html を読み込むことで検索することができるようになります。 Lynx は WWW ブラウザですから検索結果のリンクをたどっていくことも容易にできます。これはなかなか便利な使い方だと思います。

なお、 lynxcgi の機能を使ったときは一度に表示し切れなかった分の検索結果を見ることはできません。これは仕様です。

Mule から検索する

Mule から検索できるインタフェース (namazu.el) を パッケージに同梱させてもらうことになりました。 namazu.el を作成してくださった まつもとゆきひろさん、やまだあきらさん、馬場肇さんに感謝します。

Namazu の contrib ディレクトリに入っている namazu.el-xxxxxxxx.xx.gz をどこか適当な場所へ namazu.el という名前で置きます。例えば /home/foo/elisp に置いた場合は .emacs

(setq load-path (cons (expand-file-name "/home/foo/elisp") load-path))
(autoload 'namazu "namazu" nil t)

のように記述することで Mule から M-x namazu で namazu-mode を呼び出すことができるようになります。詳しい説明は namazu.el の上の方のコメントを読んでください。とても便利です。

X Window System から検索する

広瀬@NECエンジニアリングさんが Tcl/Tk による GUI な検索クライアント Tknamazuを作ってくださいました。 contrib ディレクトリに tknamazu-XXX.tar.gz という名前でファイルがあります。 使用するには lynx が必要になります。 v2.6 などの古いヴァージョンの lynx では問題があるので新しいものを用意する必要があります。

このツールは非常によくできていて、

といった特徴があります。 詳しくは Tknamazu 付属のドキュメントを参照してください。 また、 広瀬さんによる Tcl/Tk Namazu client のページがあるので、こちらを参照すると最新版の情報が手に入ります。

Windows 95/NT から検索する

私の先輩の山下誠二さんが "Search-S for Namazu" という名前の Win32 用の GUI な検索ツールを作ってくださいました。

実行ファイルのサイズが大きいため Namazu の配布パッケージには含まれていません。 最新版は 山下さんのウェブサイト から取ってくることができます。

このツールは Delphi で記述されており、ソースも付属しています。 検索結果は Netscape Navigator および Internet Explorer に渡して表示させることができる他、内部ブラウザで表示することもできます。 この場合はファイルの中身の表示も含めて単体で動作します。

広瀬@NECエンジアリングさんによる Namazu for Win32 と組み合わせることによってWin32 環境での手軽な全文検索ツールとして使えると思います。

Java 版検索クライアントを使う

まつむらのぞみさんによる Java版の検索クライアントが contrib ディレクトリに収録されています。 こちらも GUI な検索ツールとして動作します。 Java の実行環境を持っている方はぜひお試しください。

雑多な情報

NMZ.* ファイルの説明

上から六つのファイルは変更禁止です。 これらの NMZ.* のファイルは httpd から参照されない場所に置いておいた方が良いでしょう。 NMZ.head.[a-z]{2} と NMZ.foot.[a-z]{2} は検索プログラムが表示に用 いるヘッダとフッタのファイルです。日本語なら `.ja' 、英語なら `.en' のようなサフィックスがつきます。

NMZ.log はインデックス作成のログを保存します。 処理した日付、ファイルの数、サイズ、追加されたキーワードの数、処理に要した時間が記録されます。

NMZ.slog は検索されたキーワードのログを取るファイルです。 これは mknmz 実行時にサイズ 0 のファイルが作成され、ファイルのパーミッションは -rw-rw-rw- のように設定されます。 このままだと他のユーザに消されてしまう可能性もあるので、 root 権限を持っている人は chown nobody (httpd のユーザ) のようにしておくと良いかもしれません (普通はそんなに気にする必要はないとは思いますが)。

NMZ.lock は検索にロックをかけるときのファイルです。 このファイルがあると検索プログラムは NMZ.msg を出力し、検索は行いません。

NMZ.msg は検索にロックがかかっているときのメッセージ用のファイルです。 ディフォルトでは「現在、メンテナンス作業を行っています」のようなメッセージが作成されます。

NMZ.h は通常約 256 Kbytes になります

Namazu では二度目以降の検索の際に前回に入力されたキーワードと表示件数および出力フォーマットの設定が残るような仕組みを実現しています。 これは NMZ.head の

<INPUT TYPE="TEXT" NAME="key" SIZE="40">
<OPTION VALUE="10">10
<OPTION VALUE="short">OFF

などの行を見張って適宜書き換えるので、あまりこの辺りはいじらない方が良いです。

検索されたキーワードのログ

NMZ.slog は検索されたキーワードのログを保存します。 ログは

検索されたキーワード TAB ヒット数 TAB ホスト名(or IP アドレス) TAB 日時

のような書式で保存されます。 日本語 EUC で保存され、 TAB で区切っているので、後々テキスト処理を施すのも容易でしょう。 例えば

% awk '-F\t' '{ print $1 }' NMZ.slog | sort | uniq -c | sort -nr

のようにコマンドラインから実行すれば検索されたキーワードをそれぞれカウントして数字の大きい順に出力することができます。 同時に検索されたキーワードを比較・分析して ODIN のような 同義語辞書を作成するのも面白いかもしれませんね。

作成されるインデックスのサイズ

RFC の 1 - 2200 までの約 75 MB 分の英文のテキストファイルをインデックス化した場合、作成される NMZ.* の合計は約 29 MB になりました。 日本語の文書の場合は英文のみの場合とくらべて大きめになります。

インデックスの更新最中の検索

インデックスを更新している最中に検索をかけてもまず大丈夫ですが、更新処理の最後にファイルのリネームを行っているほんの一瞬の間は検索処理が行われないように NMZ.lock を置いてロックをかけています。

インデックスの作成・更新に混乱したら

普通に行っていれば特に問題は起こらないはずですが、 NMZ.* ファイルを下手にいじってしまうと更新がうまくいかなくなります。 また、インデックス作成の途中で強制終了などをして中途半端な NMZ.* ファイルの残骸が残っていたりすると次にインデックス作成を行う際におかしな動作をする可能性があります。 そのようなときはすみやかに NMZ.* をすべて削除して最初からインデックス作成をやり直してください。

インデックスに登録されているキーワードを調べるには

NMZ.i に登録されているキーワードを一覧表示する専用のツールを添付しているのでこれを使います。 具体的には

% wdnmz NMZ.i

のよう実行すれば (先頭の行の #!/usr/bin/perl を確認しておいてください)、

単語 TAB その単語が含まれるファイルの数

の書式で標準出力に出力されます。 文字コードは日本語 EUC です。 例えば

% wdnmz NMZ.i | wc -l

のように実行すれば登録されている単語の数を確認できますね。

バイトオーダの違いについて

v1.1.2 からは別のマシンで作ったバイトオーダの異なるインデックスを扱うことができるようになりました。 通常に検索するだけならば特にインデックスのバイトオーダの違いを気にする必要はありませんが、 インデックスを更新する際には問題になります。 バイトオーダを変換するツールが用意されているのでそれを使います (通常はほとんど使う必要はないでしょう)。

% rvnmz Go

と実行するとカレントディレクトリにあるインデックスのバイトオーダを変換することができます。

little-endian のインデックスの場合は NMZ.le、 big-endian のインデックスの場合は NMZ.be というファイルが目印として置かれています。

英語でメッセージを表示させたい

英語でメッセージを表示させるにはいくつかの方法があります。

  1. Makefile の LANG の指定を ENGLISH にするとディフォルトの言語が英語になります。
  2. % namazu -L en
    のようにコマンドライン引数を渡して実行する
  3. namazu.confで設定する
  4. CGI 変数で lang=ENGLISH として渡す
    <INPUT TYPE="HIDDEN" NAME="lang" VALUE="en"> とでも指定すれば良いでしょう。 <SELECT> ... </SELECT> で選択させることもできます。

英語のメッセージは NMZ.*-e に保存されています。 適宜修正して使ってください。 また、作者の英語の力は極めてアヤシイのでおかしな表現があったらこっそり報告してくださると助かります :-)。

カスタマイズ

Makefile で設定できない細かいカスタマイズについてはソースを直接編集することになります。

カスタマイズが容易にできるように重要な定数・メッセージの定義をソースの頭の方で行っています。 それぞれコメントがついているので、好みに応じて変更してください。 取り返しの付かない変更を行って後悔しないようにオリジナルは保存しておいた方が良いでしょう。

インデックス作成を速く行うには Makefile の OPT_ON_MEMORY_MAX の値を大きくして make と効果的です。 これは一度にオン・メモリで処理するファイルの合計サイズの値ですので、メモリをたくさん積んでいるマシンの場合はそれに合わせて増やすと良いでしょう。 ディフォルトでは 5 MB 分のファイルをオン・メモリで処理するように設定しています。

メーリングリスト/Newsのアーカイヴの全文検索システムを作成するには

メーリングリストや NetNews のアーカイヴをインデックス化する際には MHonArc といった HTML 変換コンヴァータを利用してからインデックス作成することをお勧めします。 これらのコンヴァータを使えば議論のスレッド単位での相互リンクを張ってくれるので文書のクロスリファレンス性も高まりますし、 HTML のタグ付けをすることによってスコアリングの品質も向上します。 このように、素のままのテキストファイルと比べて断然データベースとしての価値が高まるわけです。

Namazu では Mail/News を意識した行頭・行末の処理Mail/News の要約作成を行っています。 これとは別にインデックス作成時にオプションを指定することで uuencode の部分を無視することもできます。 詳しくはmknmz のコマンドライン・オプションを参照してください。

Mail や News の plain なファイルを処理する際は mknmz 実行時に -h とつけると不必要なヘッダを取り除いたり要約に From: と Date: をつけたりといった処理を行うことができます。 (v1.0.4) また、 MIME の Mutipart で添付されたファイルについては text/plain 以外のものを捨てる処理をしています。 (v1.1.1)

また、 MHonArc (v2.1.0) に特化したインデックス処理を行うこともできます (2.1.0 より古い MHonArc は対応していません)。 MHonArc で作成される HTML ファイルに特有の不必要な部分を削除したり、要約に From: と Date: をつけたりといったことをしています。 また、 maillist.html や threads.html といった MHonArc の作成するインデックスをスキップします。 (v1.0.4) この処理は自動的に行われますが、 mknmz 実行時に -M と指定することにより抑制することもできます。(v1.1.1)

メーリングリストや News のようにファイル名に数字の連番がつくものについては (MH 形式や MHonArc の msg00000.html のようなもの) 検索時に「新しい順」「古い順」のソートを行うことができます。 これはデータベースに日付を記録しているわけではなくて、単に番号順に処理した並びを利用しているだけです。 この機能を利用するには NMZ.head に下のように <FORM> の項目を入れておきます。 UNIX の Netscape Navigator ではフォームの日本語表示がうまくできないものがあるのでアルファベットで表記した方が親切ですね。

<STRONG>ソート:</STRONG>
<SELECT NAME="sort">
<OPTION SELECTED VALUE="score">score
<OPTION VALUE="later">in late order
<OPTION VALUE="earlier">in early order
</SELECT>

man の全文検索システムを作成するには

mknmz 実行時に -r オプションをつけると Makefile の

OPT_HELPER_MAN		= /usr/bin/jgroff -man -Tnippon

で指定したフィルタを通して man のファイルを扱います。 mknmz 内でもフィルタ処理が行われますが、この処理は割といい加減です。

httpdown 3.13 について

httpdown は東北大学のくまがいまさあきさんの作成されたフリーソフトウェアです。 このプログラムを用いることによって任意の URL のディレクトリ以下のファイルをリンクから辿れる限りごっそりと取ってくることができます。 ただし、注意して使わないと相手のサーヴァに迷惑をかけることになります。あまり大量のファイルを一気に取ってくるのはマナーが悪いといえるでしょう。 取得されたファイルは URL から http:// を取った形でそのままのディレクトリ構造で保存してくれるのでとても便利です。
例えば

http://foo.bar.jp/~quux/index.html

を指定してファイルを取得するとローカルのハードディスクに

./foo.bar.jp/~quux/index.html

という形で保存されます。 このように保存されたファイルならば頭に http:// とくっつけるだけで簡単に URL を復元できるというわけです。

この全文検索エンジンはテキスト専用ですので取得するファイルもテキストだけで十分です。 そういうときは httpdown の定義ファイルに

start http://foo.bar.jp/~quux/
allow http://foo.bar.jp/~quux*/
allow http://foo.bar.jp/~quux/*.htm*
allow http://foo.bar.jp/~quux/*.txt
allow http://foo.bar.jp/~quux/*.HTM*
allow http://foo.bar.jp/~quux/*.TXT

のように設定すれば http://foo.bar.jp/~quux/ を起点にそのディレクトリ以下からテキストファイルだけを取得してくることができるでしょう。 *.cgi などはあまり意味がないので取得しません。 末尾がディレクトリで終っている URL のファイルは _default という名前で保存されるので大丈夫です。

なお、インデクシングの処理が終わった後はローカルに集めてきたファイルは削除してしまっても構いません。

Namazu の用いる <FORM>の形式

なぜ GET なのか

Namazu では

<FORM METHOD="GET" ACTION="/cgi-bin/namazu.cgi">

のように GET メソッドを使って入力データを渡しています。 基本的に GET よりも POST の方が信頼性が高く、広く用いられているのですが、検索結果のページ単位での表示を実現するために GET を使うことにしました。 実際のところ、検索システムという性質からしてブラウザから巨大なデータが送られてくることはまずないので、問題はないと思われます。

結果表示の件数と出力フォーマット

ディフォルトで作成される NMZ.head には

<P>
<STRONG>一度に表示する件数:</STRONG>
<SELECT NAME="max">
<OPTION VALUE="10">10
<OPTION SELECTED VALUE="20">20
<OPTION VALUE="30">30
<OPTION VALUE="50">50
<OPTION VALUE="100">100
</SELECT>
<STRONG>文書の要約表示:</STRONG>
<SELECT NAME="format">
<OPTION SELECTED VALUE="long">ON
<OPTION VALUE="short">OFF
</SELECT>
</P>

のように記述され、ブラウザ側から結果表示の件数と出力フォーマットを指定できるようになっていますが、このようにブラウザ側から設定をいじれるようにしておくと検索システムを利用する一般の人には複雑に感じられてしまうかもしれません。 また、ごたごたしているのが嫌いという人もいるでしょうから、この部分は消してしまっても構いません。

ブラウザからインデックスを指定する方法

ブラウザから複数のインデックスの中からひとつを選べるように設定することもできます。 ただし、割とややこしいので仕組みをよく理解している人でないと難しいかもしれません。 まず初回アクセス用の index.html などを作成します。 その <FORM></FORM> の中に

<STRONG>検索対象:</STRONG>
<SELECT NAME="dbname">
<OPTION SELECTED VALUE="foo">foo
<OPTION VALUE="bar">bar
<OPTION VALUE="baz">baz
</SELECT>

のような記述をいれておくことで、 foo, bar, baz の中からデータベースの指定ができるようになります。 この選択の要素はいくつあっても構いません。 foo が選ばれた時は Makefile の INDEXDIR で定義されたディレクトリの下にある foo というディレクトリにある NMZ.* を元に検索することになります。 INDEXDIR/usr/local/namazu/index の場合は下のようなディレクトリ構造になります。

        /
        + usr/
          + local/
            + namazu/
              + index/
                + foo/
                + bar/
                + baz/

また、その foo, bar, baz にある各 NMZ.head にもそれぞれ上のような記述をいれておかなければなりません (SELECTED はつけなくても良いです)。 ACTION の指定についてもすべての NMZ.head で同じ物を指定しておきます。 ディフォルトで作成される NMZ.head にはこのデータベース指定の設定は記述されていないので、必要のある人は各自で追加してください。

<INPUT TYPE="HIDDEN" NAME="dbname" VALUE="foo">

のように INPUT を HIDDEN 属性にしてこっそり指定しておくこともできます。

なお、実にダサイ仕様なのですが、この各ディレクトリの名前は short, long, score, later, earlier, 数字以外の名前をつけてください (理由は…分かるでしょう)。

また、おかしな人が "../../../etc" などのように上位のディレクトリを指定してきた場合を考えて、 dbname に渡される文字列に '/' が含まれる場合には無効にするようにしました (実際にはどうせ NMZ.* しかプログラムは参照できないわけですが)。

複数のインデックスに検索をかける方法

v1.1.2 からは複数のインデックスに検索をかけて結果をマージして出力することができるようになりました。 <FORM> ... </FORM> の中に下のような記述を入れてください。 注意点は上のブラウザからインデックスを指定する方法で述べたものと同じです。

<STRONG>対象インデックス</STRONG><BR>
<UL>
<LI><INPUT TYPE="CHECKBOX" NAME="dbname" VALUE="foo" CHECKED>foo
<LI><INPUT TYPE="CHECKBOX" NAME="dbname" VALUE="bar" CHECKED>bar
<LI><INPUT TYPE="CHECKBOX" NAME="dbname" VALUE="baz" CHECKED>baz
</UL>

このように記述しておくことで foo, bar, baz から複数選択して検索することができます。 検索結果に使われる NMZ.head, NMZ.foot は Makefile で INDEXDIR で指定したところにあるものが使われます (または namazu.conf, .namazurc の中で INDEX の項目で指定したディレクトリにあるもの)。 インデックスの指定がひとつだった場合には個々の NMZ.head, NMZ.foot が使われる点に注意してください。 これを回避したい場合にはすべての NMZ.head, NMZ.foot を共通にしてしまうことです。

Namazu の設計・実装

検索式

大文字、小文字の区別はありません。foo* のように末尾にアスタリスクを指定することで前方一致検索が可能です。また、単語をスペース区切りで並べて書くとアンド検索になります。日本語は KAKASI/ChaSen によって分解され、「日本語情報処理」なら 「日本語」 「情報処理」 のように 2 つの単語に分かれてアンド検索されます。日本語の単語の分解は完全ではありません。品質は辞書によって決定されます。

全角 (2 bytes) アルファベット・記号はすべて 1 byte として処理されます。記号を含む検索も可能で TCP/IP というような単語の検索も可能です。ただし、記号の処理は完全ではないので TCP IP のように分けてアンド検索をかけた方が取りこぼしがありません (その代わり余計なファイルまでヒットしてしまう可能性もありますが)。

括弧を含めたアンド検索とオア検索およびノット検索が可能になっており検索式に & | ! ( ) を用います。記号の代わりに and/or/not で指定することも可能です。 検索式はひとつづつスペース区切りで入力しなければなりません。 たとえば

のように指定します。

といった検索をすることができます。 これは「 sed または awk が含まれ、perl は含まれない、そして regexp が含まれる」文書を検索するという意味になります。 括弧のネストもできるので、さらに複雑な検索式で検索することも可能です。

フレーズをダブルクォーテーションまたは中括弧 '{' '}' で囲むこと でフレーズ検索ができます。ただし、精度は 100%ではありません。とき どきはずれます。たとえば

のように指定します。

正規表現および中間一致/後方一致の検索も可能です。ただしちょっと 遅いです。これは日本語も使えます。

のように指定します。

HTML タグによる文書の要約の作成

コンピュータによって文書の要約を作成する技術は自然言語処理の分野でも広く研究されている分野です。 北陸先端科学技術大学院大学の佐藤理史先生が行っているネットニュースのダイジェスティングや、ジャストシステムの一太郎に搭載された文書要約機能など、本格的なシステムの例もあります。 本来、文書の要約を作成する作業は人間でもなかなか難しいものですから、コンピュータに処理させることは相当に大変であろうことが容易に想像できます。

HTML は元々 SGML の一アプリケーションであり、文書の構造を定義する言語ですから、<H[1-6]> タグによって定義される文書のヘディング (見出し) の情報を利用することによって簡単に要約らしきものを作成することができます。 要約はディフォルトでは 200 文字に設定されていますから、ヘディングだけを集めて足りない部分は文書の先頭から補うようにします。 また、対象が単なるテキストファイルだった場合には文書の先頭から 200 文字をそのまま使います。 Namazu ではこのように単純なアプローチを取っています。

このヘディングの情報を元に要約を作成するという手法は対象となる HTML ファイルに正しく文書の論理構造が定義されていなければ効果を発揮しません。 <H[1-6]> を文字サイズの指定に使っているようなページではほとんど意味のない要約が作成されてしまうことになります。 HTML によって文書の論理構造を定義することの意義が広く浸透すればこの状態も改善されることと思われます。

HTML タグによるスコアの重みづけルール

ディフォルトでは

のように HTML タグに応じてスコアに重みづけがされています。 これらの値は mknmz.pl の %TAGW という連想配列に設定されており、ソースの頭の方で定義されています。 <FONT> などの見栄えを指定する物理タグは論理的な意味をもたないためスコアに重みづけをしていません。 これは Namazu に限った話ではありませんが、論理タグを使わずにいくら <FONT> などのタグを使って見栄えのする (それもすべてのブラウザで通用するわけでもない) ページを作ったとしても、検索システムのインデクサから見ると、まったく文書の論理構造のない HTML であるので、まともなスコアリング処理はできません。 また、ダイジェスト化の処理を行う検索システムでは一切情報が残らないということも起こり得ます。 私が言うことでもありませんが、 HTML 自体は論理構造を記述し、文書の見栄えを指定するにはスタイルシートを用いるのがスマートな方法だと思います。

実際にウェブ・ページを収集して調べてみたところ、想像以上に <H[1-6]> を文字サイズの指定に使っている人 (本文全体を <H1> で囲んだり) が多いことが判明したので、タグにはさまれる文字列の長さが 128 文字を越える場合は重みづけをするのをやめることとしました。 この制限は $INVALIDLENG に定義されています。

また <META NAME="keywords" CONTENT="foo bar">foo bar に対しては 32 のスコアがつきます。 これは $METAKEYW という変数に設定されています。

その他 HTML タグの処理

Namazu ではインデックス作成の際に &quot;, &amp;, &lt;, &gt; および &#9-10, &#32-126 の named entity と numbered entity を復号しています。 &lt &gt; のようにホワイトスペース区切りで複数指定して最後にセミコロンを打った形式でも大丈夫です。 内部処理を日本語 EUC で行うため ISO-8859-1 の右半分 (0x80-0xff) の記号は処理できません。 同じ理由により I18N 拡張された UCS-4 な numbered entity にも対応不可能です。 また、インデックス作成の際には <IMG> タグの ALT 要素の取り出しを行っています。

インデックス作成の処理は最終的には HTML タグをすべて捨てるのですが、その際、タグによっては単に削除すべきものと空白に変換すべきものとがあります。 例えば、「これは<STRONG>重要</STRONG>です」などというように用いられるタグは削除しますが、「This is foo.<BR>That is bar.」のような用いられ方のタグは単純に削除してしまうと foo.That と単語が繋がってしまうため、空白に変換しておきます。 この設定は mknmz.pl の $NON_SEPARATION_TAGS に定義されています。

行頭・行末の処理

行頭・行末の空白・タブ、行頭の > | # : を削除します。 また、行末が日本語で終わる場合は改行コードを無視します (日本語の単語が行末で分断されてしまうのを防ぐ) 。 これら処理は特にメールのファイルをなどを扱う際に効果を発揮します。 これらのルーチンのアイディアとコードは古川@ヤマハさんがくださいました。 また、英文ハイフォネーションの復元も行います。

Mail/News の要約作成

Mail/News のファイルを扱う際は「◯◯@△△と申します」のように自分の名前を名乗る行や、 引用時の「◯◯さんは△△の記事において□□時頃書きました」のような情報、 > などで表される引用部分をできるだけ要約に含ませないように処理をしています。 これらのメッセージは要約には含まれませんが、 検索対象には入るようになっています。 このアイディアはやまだあきらさんから頂きました。 実際にどのように処理しているか興味のある方はソースで確認してください。

文字コードの扱い

内部処理を ASCII + 日本語 EUC 、出力を ISO-2022-JP で行っています。 JIS X 0201 の右半分 (いわゆる半角カナ) の文字は扱えません。 また、多言語の処理も行えません。

出力する HTML について

HTML 4.0 Strict DTD に従った HTML を出力します。 文法については石川雅康@慶應 W3C さんの作成された jweblint で検証済みです。 出力する HTML を修正する際には正しい HTML を考慮するようにしましょう。 あくまでも検索エンジンなのですから、変に装飾にこだわる必要はないように思われます。 HTML を記述する上で参考になるものを参考文献に挙げているので、それらを参照されることをお勧めします。

アンド・オア検索時のスコア計算

tf idf法によるスコアの計算

v1.1.2.2からはtf idf法によるスコア計算を実装しました。 これは与えられたキーワードが2つ以上あるときに用いられます。

計算式は

のようになっています。 これにより多くの文書に含まれるキーワードには低いスコアがつき、 そのキーワードを含む文書が少ない場合には高いスコアがつくことになります。

従来のスコアの計算

A という単語と B という単語をアンドまたはオア検索した場合、それぞれの単語のスコアを元にスコアの再計算を行います。 具体的には、アンドのときは A と B を比べてスコアの小さい方を、 オアのときは A と B の大きい方を新しいスコアとして採用します。 例えば "THE BEATLES" というキーワードでアンド検索をかけた場合、 "THE" の方のスコアはほとんど意味がないため、小さい方のスコアを重視する方針にしました。 オア検索はその反対の理由によります。

ChaSen による品詞情報の利用

ChaSen は文章の形態素解析を行い、形態素単位での品詞情報を抽出することができます。 Namazu ではこれによって得られた品詞から名詞のみを有効とし、他をすべて切り捨てる動作をオプションで行えるようになっています。 これによって無駄な単語をインデックスに含むことなく、スリムなインデックスを作成することができます。 また、検索のキーに与えられた文字列にも同じ処理を施します。

この辺りの処理はまだ暫定的なもので、 ChaSen の形態素解析を最大限に発揮できる処理を考えている最中なのですが、現段階でも検索のキーに「 Linux で使えるメール用のソフトウェア」のようなセンテンスが与えられた時には "Linux", "メール", "ソフトウェア" のように不要な品詞を省いて名詞のみを取り出してくれますから、それなりに実用的な処理は実現していると思います。 しかし、例えば「ソフト」を名詞ではなく形容詞として判断するなど微妙な問題があるので、品詞情報を利用するのもなかなか難しいものがあります。 とりあえずは、現在は実験段階ということで、後々対策を考えていきたいと思います。

記号を含む単語のインデックス処理

記号の処理はなかなか難しい問題です。 例えば (foo is bar.) のような文があったときに単純にスペース区切りでインデックス化してしまうと "(foo", "is", "bar.)" のように登録されてしまい、これでは foo や bar で検索できなくて困ります ("bar*" とすることで前方一致は引っかかりますが、アルゴリズムの性質上、前方一致以外の部分一致は不可能です) 。

この問題を回避するためには記号をすべて取り払ってしまえば最も楽なのですが、 .emacs, TCP/IP といった記号混じりの単語で検索したい場合もあります。 Namazu ではインデックス化しようとするファイルに tcp/ip のような文があった場合、 "tcp/ip", "tcp", "ip" のように 3 つに分解してインデックスに登録します。 tcp/ip から tcp, ip と取り出して登録してもあまり意味がないように思えるかも知れませんが、 s.takabayashi という文に対して s.takabayashi だけでなく takabayashi や s & takabayashi でも検索できるようにとの配慮です。

また、 (tcp/ip) という文があった場合には "(tcp/ip)", "tcp/ip", "tcp", "ip" のように 4 つに分解します。 <s.takabayashi>, e-mail: のようなものでも同じです。 さすがに ((tcp/ip)) のように入れ子構造になっている場合の処理は行っていないので "((tcp/ip))", "(tcp/ip)", "tcp", "ip" のように処理されます。 最初の例の場合は "(foo", "foo", "is", "bar.)", "bar.", "bar" のように登録されるため foo でも bar でも検索することができます。

この手法でもまだ単語の取りこぼしが発生するという点で完全というわけではないのですが (例えば e-mail:ccsatoru@vega.aichi-u.ac.jp という文から ccsatoru@vega.aichi-u.ac.jp を取り出すことはできない) 、そんなに悪くないのではないかと思っています。 欠点としてはインデックスのサイズが結構大きくなってしまうことですね。 検索の柔軟性を高めようとするとどうしてもゴミが増えてしまいます。

一般的なアプローチとして、記号や数字を一切無視する、検索する意味のない単語を無視する (助詞などの品詞を捨てる)、ひらがなを無視する、短い単語を無視する、頻度の異常に高い単語を無視する、 などといった手法によってゴミを減らすことも考えられますが、 Namazu では小中規模の全文検索エンジンということでできるだけ多くの単語をインデックスに含めるように実装しています。 …ですが、 mknmz 実行時に -H, -K といったオプションを指定することでひらがなのみからなる単語を無視したり記号をすべて削除したりといったこともできます。 -m オプションを指定すると ChaSen による品詞情報を利用して名詞のみを登録といった処理も行えます。

Namazu の検索アルゴリズム

Namazu の検索アルゴリズムは実に稚拙なものなので、あまり堂々と公表できるものでもないのですが、内部の仕組みがどうなっているのか知りたいという人もいるかもしれないので、簡単に検索アルゴリズムについて説明します。 興味のない方は読み飛ばしてください。 アルゴリズムの専門家の方も読まない方が良いでしょう (読んでも笑わないように)。

英和辞書はページをめくる側に A-Z まで各アルファベットから始まる単語のそれぞれの範囲が分かるように階段状に印がつけられています。 ですから stupid という単語を調べるときは s から始まる単語の範囲の中だけを調べれば良いことになります。

Namazu では先頭の 2 オクテット分の範囲をあらかじめ調べてありますから、 st から始まる単語の範囲だけを調べれば良いわけです。 2 オクテット = 16 bit の組み合わせの種類は 65536 あるのですが、 Namazu で扱う実際に有り得る ASCII + 日本語 EUC の 2 オクテットの文字コードの並びは約 15,000 です。 仮に 10 万語の単語のインデックスがあったとして、理想的に単語が分布しているとすれば 100,000 / 15,000 = 約 6 となり、たった 6 つの中から単語を調べれば良いことになります。

実際には単語の分布には相当のばらつきがあるので、そうはうまくいかないのですが、悪くても数百程度には範囲を絞ることができると思われます。 うまくいけばたった 1 つに絞ることもあり得ます。 多くの場合はその中間くらいでしょう。 その絞られた範囲の中で二分探索法を用いて検索します。

元々、二分探索法は少ない比較回数で検索が可能なアルゴリズムですから、 10 万語から検索する場合でも最悪 17 回の比較で検索が可能なのですが、その数をもう少し減らそうというのが Namazu のせこいアプローチです。

本当は正統的なハッシュ法を用いれば、さらに高速な検索も可能なはずなのですが、プログラミング技術と実装との折り合いで、今の手法で妥協しています。 自分では実用的な速度は達成できたと思っています。

正規表現/後方一致/中間一致検索の実装

ひとつ上の項で説明したように Namazuは二分探索を実装しています。 二分探索ではアルゴリズムの性質上、中間一致や後方一致は不可能ですから、 別の方法を採るしかありません。

そこで、古川@ヤマハさんが中間一致、後方一致を実現するためのイ ンデックスを考案して pnamazu に実装してくださいました。

C版の namazuでもこれを真似して実装を試みましたが、途中で、ある ことに気付いて中止しました。それは「最近のマシンは速いから登録単語 を全数 grep しても十分実用になるだろう」ということです。

この方法ならば正規表現が使えるし、実装もシンプルになるというわ けでさっそく試してみたところ、事実、十分実用的な (私のところでは 2,3秒くらいです) 速度で検索が可能なことが分かりました。

正規表現は Ruby の コードを使わせていただいているので (まつもとゆきひろさん Thanks!)、 日本語も扱えます。たとえば /インター?フェ[ーイ]ス/ と いった指定が可能になっています。

なお、中間一致/後方一致は内部的に正規表現に変換して実現されていま す。これらの機能が不要な場合は NMZ.w を削除してください。

(あやしげな)フレーズ検索の実装

フレーズ検索の実装はかねてからの目標でした。最も問題だったのは 単純に現状のインデックスの構造の延長上に実装するとインデックスのサ イズが巨大になるということでした。良い方法が思いつかずに悩んでいる と、古川@ヤマハさんから次のような助言をいただきました。

「フレーズを構成する個々の単語はすべて AND検索でそのファイルに 存在することが分かっているのだから、調べる必要があるのは単語の並び だけである。精度を多少犠牲にして単語をハッシュ値に変換すればサイズ は小さくなる。」

なるほど、これはいける、ということで実装したのが Namazu のフレー ズ検索です (古川さん Thanks!)。「あやしげな」というのは精度 が 100% ではないことを意味します。

フレーズは 2語単位で 16 bitのハッシュ値に変換して記録しているの で、たとえば "foo bar baz" というフレーズで検索すると

...
foo bar ...
... bar baz

のように "foo bar" と "bar baz" の含まれるファイルもヒットして しまいます。これはちょっと困ったことですが、少なくとも foo & bar & baz で検索するよりは候補を絞れます。

理想的には "foo bar baz" を確実に検索できた方が望ましいのですが、 インデックスのサイズとの兼ね合いもあるので難しいところです。もっと 良い方法が見つかれば置き換えたいと思っています。

フレーズ用のインデックス NMZ.p のサイズは転置ファイル NMZ.i よ りは小さくなります。また、これの補助インデックスとして 256KB (int = 32bitで計算) を必要とします。

なお、フレーズ検索用インデックスの作成にはメモリを割と消費する ので注意が必要です。FAQmknmz で Out of memory! がでてしまいま すを参照してみてください。

プログラムの問題点

Namazu の仕様

主な技術仕様

プログラムの主な仕様

出力する HTML の仕様

今後の予定

ToDoファイルにまとめました。

将来的には HTML タグを利用したスコアの重みづけ、要約の作成の処理を応用して SGML 文書を対象とした検索システムを作るのも面白そうだと思っています。

謝辞

初期の段階から開発に協力して頂き、数々の助言をくださった馬場肇@京大さん、 やまだあきらさん、 たくさんの素敵なコードを追加してくださった古川@ヤマハさん、 HTML およびテキスト処理に関していろいろと教えてくださった石川雅康@慶應W3Cさん、 QKC のコードを引用または参考にすることを承諾してくださった佐藤公彦@東大さん、 全文検索システムの開発のきっかけとなった httpdown の作者くまがいまさあき@東北大さん、 Win32 対応用のコードをくださった林卓司@エフエフシーさん、 広瀬@日本電気エンジニアリングさん、 Makefile を作成してくださった佐藤文優@cij.co.jp さん、 Ruby の正規表現のコードを使わせてくださったまつもとゆきひろさん、 バグ報告・動作報告をしてくださったみなさん、 Namazu mailing list のみなさん、 日頃お世話になっている愛知大学名古屋情報処理センターのみなさん。 改めて感謝を述べさせて頂きたいと思います。

最後に

プログラムに改良すべき点を見つけた方はお知らせ頂けるとありがたいです。 特にバグに関してはできる限り対処していきたいと思っています。 このささやかな検索システムが情報検索の場面で少しでもお役にたてれば幸いです。

参考文献

プログラムの履歴

ChangeLog を参照してください。

作者


email: ccsatoru@vega.aichi-u.ac.jp
Namazuのホームページへ

ccsatoru@vega.aichi-u.ac.jp