![[Namazu の Webサイト]](namazu-web.png)
最終更新日: 2001-05-29 (公開日: 2001-05-29)
我々は文書の山に囲まれて暮している。なかでも電子メールは身近 な存在である。
とあるシンポジウムでこんな出来事があった。討論の話題が IT (情報技術) 革命におよんだときに、年輩の先生が次のような質問 を投げかけた。「現時点でさえ、私は電子メールの処理に困ってい るのに、これ以上 IT革命が進んだらどうなるのか」
この質問に対し、司会者はすかさず「すでにIT革命に乗り遅れてし まっている先生からの、たいへんいい質問です」と応え、場内は大 いに沸いた。おそらく自分たちも困っているからこそ、多くの人 が笑ってしまったのではないかと思う。
かくいう筆者も電子メールの処理に苦労している人間の 1人である。 筆者のメールボックスには約 5万通、計 200MBのメールが溜まって いる。ほとんどのメールは後から参照することはないが、まれに参 照したくなるときがある。たとえば、この問題の解決策は以前に誰 かがメールで報告していたはずだ、と思い出したときなどである。
そこで、メールの山を検索する必要に迫られるのだが、単純な文字 列検索のプログラムでは歯が立たない。試しに、手元の計算機で UNIXの grep コマンドを使って筆者のメールボックスを検索したと ころ、実に 12分もかかった。これでは短気な筆者などはとても我 慢できない。
一方、高速な全文検索システムを使えば、同様のことが一瞬ででき る。メールの数が倍々に増えていっても、検索に要する時間はほと んど変わらない。実際、筆者は大量のメールを一瞬で検索できる環 境を構築している。
メールの他にも、インターネットから集めてきたニュース記事やソ フトウェアのマニュアルなど、知らず知らずのうちに文書は溜まっ ていく。気をつけていないと、文書の山に生き埋めになってしまい かねない。
増え続ける文書の山を制するには、高速な全文検索システムがもは や不可欠である。全文検索システムというと、ODIN や Google といった WWWの検索エンジンが有名であるが、ここで必要とされて いるのはそのような巨大なシステムではなく、個人で使うための小 規模なものである。Namazu はまさにそのような用途のために作ら れている。[図1]
Namazu は <http://www.namazu.org/> から入手できる。GPL2 (GNU GENERAL PUBLIC LICENSE Version 2) に従ったフリーソフトウェアである。UNIX版と Windows版があるが、 ここでは UNIX版を元に説明する。
Namazu をインストールするためには、あらかじめ次のソフトウェ アをインストールしておく必要がある。
Namazu のインストール方法は一般的なUNIXのフリーソフトウェア と同様である。ソースコード namazu-2.0.x.tar.gz を入手して、 次のように実行すればよい。
% gzip -dc namazu-2.0.x.tar.gz | tar xvf - % cd namazu-2.0.x % ./configure % make % su Password: (root のパスワードを入力) # make install
詳しいインストール方法は Namazuに付属するチュートリアル (tutorial.html) を参照して頂きたい。
Namazu を使って文書を検索するには、まずインデックスを作成す る必要がある。インデックスとは、元の文書の情報を検索しやすい 形で格納したデータ構造である。これについては後ほど詳しく説明 する。
インデックスの作成は mknmz コマンドで行う。たとえば、 ~/Mail/work 以下に保存されているメールを対象とするなら、コマ ンドラインから
% mknmz ~/Mail/work
と実行する。処理が進むにつれて、[図2] のよ うなメッセージが出力される。この例ではたった 9個の文書しか対 象としていないが、実際には数千、数万の単位の文書に対してもイ ンデックスを作成できる。
図2 インデックスの作成の過程
% mknmz ~/Mail/work 9個のファイルがインデックス作成の対象として見つかりました 1/9 - /home/foobar/Mail/work/1 [message/rfc822] 2/9 - /home/foobar/Mail/work/2 [message/rfc822] 3/9 - /home/foobar/Mail/work/3 [message/rfc822] 4/9 - /home/foobar/Mail/work/4 [message/rfc822] 5/9 - /home/foobar/Mail/work/5 [message/rfc822] 6/9 - /home/foobar/Mail/work/6 [message/rfc822] 7/9 - /home/foobar/Mail/work/7 [message/rfc822] 8/9 - /home/foobar/Mail/work/8 [message/rfc822] 9/9 - /home/foobar/Mail/work/9 [message/rfc822] インデックスを書き出しています... [基本] 日付: Sun Aug 27 10:41:33 2000 追加された文書の数: 9 サイズ (bytes): 29,348 合計の文書数: 9 追加キーワード数: 1,233 合計キーワード数: 1,233 わかち書き: module_kakasi -ieuc -oeuc -w 経過時間 (秒): 10 ファイル/秒: 0.90 システム: linux Perl: 5.006 Namazu: 2.0.4
mknmz の実行が終わると、mknmzを実行したディレクトリに NMZ.* ファイルが作られる。Namazuでは、これらのファイルをまとめてイ ンデックスと呼ぶ。[図3]
図3 インデックスを構成するファイル
NMZ.body NMZ.field.to NMZ.result.normal NMZ.body.ja NMZ.field.to.i NMZ.result.normal.ja NMZ.field.date NMZ.field.uri NMZ.result.short NMZ.field.date.i NMZ.field.uri.i NMZ.result.short.ja NMZ.field.from NMZ.foot NMZ.slog NMZ.field.from.i NMZ.foot.ja NMZ.status NMZ.field.message-id NMZ.head NMZ.t NMZ.field.message-id.i NMZ.head.ja NMZ.tips NMZ.field.size NMZ.i NMZ.tips.ja NMZ.field.size.i NMZ.ii NMZ.version NMZ.field.subject NMZ.log NMZ.w NMZ.field.subject.i NMZ.p NMZ.wi NMZ.field.summary NMZ.pi NMZ.field.summary.i NMZ.r
インデックスの大きさは、対象とする文書の量と性質によって決ま る。約2,000通、合計 7MBのメールを対象に作成したインデックス は約 4MB になった。多くの場合、インデックスは対象文書よりも 小さくなるが、文書の量が少ないと、インデックスの方が大きくなっ てしまうことがある。
1つのディレクトリに対して複数のインデックスは置けないので、 新しいインデックスを作るときにはディレクトリを新規に作成する 必要がある。ホームディレクトリに Namazu というディレクトリを 作り、その下にインデックス用のディレクトリをまとめるとよい [図4]。 mknmz に -O オプションを指定すれば、 インデックスの出力先のディレクトリを指定できる。
さきほど作成したインデックスを ~/Namazu/Mail/work に移動する には、 mknmz -p ~/Namazu/Mail/work; mv NMZ.* ~/Namazu/Mail/work と実行する。
図4 インデックスの管理 (ディレクトリ構造)
/
|- home
| |- foobar
| | |- Namazu
| | | |- mydocs ←自分の書いた文書用のインデックス
| | | |- manual ←ソフトウェアのマニュアル用の 〃
| | | |- Mail ←メール用の階層
| | | | |-work ←work メーリングリスト用の 〃
| | | | |-staff ←staffメーリングリスト用の 〃
上の例では ~/Mail/work 以下に保存されているメールを対象にイ ンデックスを作成した。メールを利用しているうちに、新しいメー ルが溜まってきたときは、次のように実行してインデックスを更新 する。インデックスは ~/Namazu/Mail/work に置かれているものと する。
% mknmz --update ~/Namazu/Mail/work
更新の際には新しく追加されたファイルを対象とするため、短時間 で処理できる。もし削除されたファイルや更新されたファイルがあ ればそれらも反映される。
検索は namazu コマンドで行う。さきほど作成したインデックスに 対し、キーワード「コンパイル」で検索するにはコマンドラインか ら次のように実行する。
% namazu 'コンパイル' ~/Namazu/Mail/work
検索結果は [図5] のように表示される。Webサー バと連携すれば [図6] のようにブラウザから検 索できる。
図5 コマンドライン上での検索結果
% namazu 'コンパイル' ~/Namazu/Mail/work 検索結果 参考ヒット数: [ コンパイル: 1 ] 検索式にマッチする 1 個の文書が見つかりました。 1. iconv(3): boundary condition (スコア: 1) 著者: Satoru Takabayashi <satoru-t@is.aist-nara.ac.jp> 日付: Mon, 21 Aug 2000 10:17:37 +0900 以下のプログラムをコンパイルして実行すると、OSによって iconv の挙動が異なります。Linux (glibc 2.1.3) の挙動はおか しくないですか? これは既知の問題でしょうか。 この問題を回 避する方法はありますか? -- /home/foobar/Mail/work/3 (1,954 bytes) 現在のリスト: 1 - 1
図6 Webブラウザ上での検索結果
![[Webブラウザ]](namazu-cgi.png)
上の例では単純に1つのキーワードを指定しただけである。Namazu には、複数のキーワードの指定、正規表現によるキーワードの指定 といった検索方法も用意されている。詳しい使い方は付属するマニュ アル (manual.html) を参照して欲しい。
全文検索システムとは、文書全体に含まれる文字列を検索するシス テムである。ここでは Namazu で採用している手法を例にとって全 文検索システムの仕組みを解説する。
大量の文書を高速に全文検索するためには、検索対象の文書を元に インデックスを作成する必要がある。
インデックスの作成方法には多くの手法があるが、最も一般的なも のは、単語と、その単語を含む文書のIDとの対応表を作る方法であ る。たとえば、computer という単語は文書1と文書3に含まれ、 information という単語は文書3 と文書4に含まれるといった対応 表を作り、単語のアルファベット順に並べる。これを転置ファイル (inverted file) と呼ぶ 。文書IDの代わりにページ数を見立てる と、ちょうど書籍の索引と同じ形になる。 [図7]
図7 転置ファイル
==================================== 単語 |その単語を含む文書のID -------------+---------------------- algorithm | 1, 4, 6, 7 computer | 1, 3 information | 3, 4 java | 4, 7, 8 lisp | 7 processing | 1, 3, 4, 8 scheme | 6, 7 ------------------------------------
検索時には、転置ファイルの単語の表を 2分探索することにより、 与えられたキーワードを含む文書が高速に検索できる。
複数のキーワードを指定して検索するときは、文書IDの集合に対し て集合演算を適用する。たとえば、computer と information の両 方を含む文書を検索 (AND検索) するときは、それぞれの単語で検 索して得られる文書ID の集合 {1, 3}、 {3, 4} の積集合を取ると、 {3} という結果が得られる。
文書IDはソート済の状態で転置ファイルに格納されているため、集 合演算は高速に行える。また、ソート済という特性を活かして文書 IDのデータを圧縮することもできる。Namazu では文書IDを差分で 記録して BER圧縮をかけている。BER圧縮は Perlの pack関数で提 供されている。より高度な圧縮手法としては Elias-γ法などがあ る (文献2)。
上の例では、単語と文書IDを対応させて転置ファイルを作成してい たが、これでは "information processing" のようなフレーズが正 確に検索できない。information と processing を AND検索しただ けでは、"processing of information is ..." といった文を含む 文書までもヒットしてしまう。
フレーズの検索を実現するためには、文書IDとともに単語の出現位 置を記録すればよい。検索時には AND検索で積集合を取るとともに、 出現位置の照合を行う。
単語の出現位置を記録すると、その分、転置ファイルが大きくなる。 Namazu では、ファイルの大きさを抑えるために、ハッシュを用い た手法でフレーズ検索を実現しているが、今にして思えば、たいし てサイズの節約になっていない割に、検索の精度を落とすという弊 害の方が大きいようである。将来のバージョンでは出現位置を記録 する手法に直すつもりでいる。
転置ファイルの作成時に、キーワードにむかない単語を除外する戦 略がある。 a, the, of, to などといった頻出する単語 (ストップ ワードと呼ばれる) を除外すれば、転置ファイルを小さくすること ができる。しかし、弊害として、"to be or not to be" のような フレーズが検索できなくなる。Namazu では弊害の方を重視して、 ストップワードの除外は行っていない。
転置インデックスの手法を日本語の文書に対して適用しようとする と大きな壁につきあたる。英語の場合は語と語の区切りが明白であ るため、単語の表を容易に作れるが、日本語の場合は区切りに曖昧 性があるため同じようにはいかない。
そこで、日本語の区切りの曖昧性を解消し、適切にわかち書きする ためのプログラムが必要となる。Namazu では KAKASIまたは茶筌を 利用している。KAKASI は高橋裕信氏によって開発された、漢字か なまじり文をひらがな文やローマ字文に変換するプログラムである。 わかち書き処理への対応は馬場肇氏によって行われた。茶筌につい ては本特集の記事を参照して頂きたい。
茶筌で「Namazu は手軽に使える全文検索システムである」をわか ち書きすると、「Namazu・は・手軽・に・使える・全文・検索・シ ステム・で・ある」のようになる。
茶筌・KAKASIによるわかち書きの出力が不適切であった場合は、本 来は見つかるはずの文書が見つからないという状況が起きる。一方、 わかち書きを行わない手法としては Suffix Array を用いるものや シグネチャを用いるものなどがある。文献2では転置ファイルの作 成方法も含め、それぞれの手法が詳しく解説されている。
検索結果は、有用な文書が上位となるように表示するのが望ましい。 有用な文書とは利用者が与えた検索質問 (query) に対して最も適 合する文書のことをいう。
検索システムは、検索質問と検索にヒットした文書との適合度を計 算し、それに応じてランキングを行う。ランキングの単純な手法と しては、検索に使われたキーワードをたくさん含む文書ほど優先す る、というものがある。HTMLなどの構造を持った文書に対しては、 タイトルや見出しに含まれる単語に重みをつけることが多い。
複数のキーワードが指定されたときは、ありふれた単語の重みを低 くして全体の適合度を計算する。たとえば、seminumerical, programming, easy と 3つの単語を指定して検索したときに、それ ぞれの単語を等価に扱えば、 easy をたくさん含んだ文書が検索結 果の上位にきてしまうだろう。この例では seminumerical という 希少なキーワードを優先した方がよい結果が得られる。
ありふれたキーワードに低い重みを、希少なものに高い重みをつけ る伝統的な手法として tf idf法がある。キーワードw が与えられ たときの文書d の tf (term frequency) と idf (inverted document frequency) の値は次のように計算する。
tf idf はこれらの積である。
Namazu では、検索質問に含まれる各キーワードごとに tf idf の 値を求め、それらを単純に足し合わせることによって適合度を計算 しているが、一般的にはベクトル空間モデルによって計算されるこ とが多い。ランキング手法については文献3に詳しい。
Namazu は 1997年の夏に生まれた。当時、大学3年だった筆者は、1 つの問題を抱えていた。それは、自分用に作った全文検索システム が遅くて使いものにならない、ということであった。
筆者の手元には、 WWWから集めた約 1,000ファイルの文書があった のだが、それらを検索するのに 30秒もかかった。世界中のWebサイ トを一瞬で検索できる検索エンジンが世の中には存在するというの に、高々 1,000ファイルの検索に 30秒もかかってしまうとは情け ない話である。
そこで、全文検索システムの仕組みについて調べてみると、簡単な システムならすぐに作れそうだと気づいた。さっそく開発に着手し、 1 週間後には動くものができた。
その後は、メーリングリストでの宣伝、Webサイトの開設、一般公 開と、とんとん拍子で進んだ。利用者が増えるにつれて完成度が高 まり、いつのまにか広く使われるフリーソフトウェアになっていた。 バージョン 2.0 からはインターネット上での共同開発が進められ ている。
Namazu という名前の由来は特にない。ふと思い浮かんだだけの名 前である。知人からは「世界を揺るがすから Namazuなんだ、と言っ ておきなさい」と言われているが、どうもこれは大仰な気がするし、 そもそもナマズは地震に反応するだけ (予知するという説もある) であって、地震を起こすものではない。
文献4 に掲載されている、 Namazu を採用した Webサイトの一覧を 見ると、驚くほど多くの組織で Namazu が利用されていることがわ かる。なぜこれほど普及したのか自分でも不思議である。考えられ る理由はこんなところだろうか。
ふり返ってみると、初期のバージョンの完成度は実にひどかった。 しかし、なんとか「動いて」「使える」しろものではあったと思う。 初めから完成されたソフトウェアを開発しようとするより、要求の 半分程度を実現するものをひとまず公開し、それから徐々に改良し て共同開発の体制に持っていく方が成功するようである。この事実 は「デザインの『悪い方がよい』原則」として知られている (文献 5)。以下にその主旨を引用する。
最初に「正しい」方法をとることはしばしば望ましくないという ことである。とりあえず「正しい」ことの半分はできるものを作 り、ウイルスのように広める方がよい。いったん人々がそれに騙 されれば、 「正しい」ことの90％までできるように改善が行わ れるだろう。
Namazu は枯れた技術だけを利用して作られた素朴な全文検索シス テムである。情報検索の分野では、自然言語による検索や概念検索 といった高度な技術の研究が行われているが、 Namazu ではそれら の事情をほとんど考慮に入れていない。それでも結果的に Namazu がこれだけ普及したところをみると、実用的で広く使われるソフト ウェアを作るには、枯れた技術だけでも十分ということらしい。マ イクロカーネルが盛んに研究された時代にあって、伝統的なモノリ シックカーネルの Linux が成功を収めたのも、その 1つの例であ ろう。
Namazu がもっと現代的で高度な検索技術を採用すべきかは悩める ところである。おそらく Namazu に求められているのは、高度な検 索技術よりも、手軽に日常的に使えるソフトウェアであることだろ う。その意味では、使い勝手のよさを追求するべきなのだが、今後 は筆者の勉強も兼ねて、情報検索の現代的な手法を少しづつ取り入 れていこうと思っている。
しかし、新しい手法を取り入れようにも、現在の Namazu は拡張が 難しい状態にある。3年前に Namazu を作り始めたときは、とにか く動けばいい、という一心でプログラミングしていた。そして、機 能が増えるにつれてプログラムの複雑性が増大し、今では手がつけ られない状態になっている。
そこで、筆者は現在 Namazu の再設計に取り組んでいる。Namazu の開発を通じて得られたプログラミングの教訓はたくさんあるが、 最も大きいのは、きちんと設計せよ、というものだ。初期の貧弱な 設計のおかげで、その後、ずっと苦労するはめになった。
新しい設計では、保守がしやすく、自由自在に拡張できるソフトウェ アを目指している。また、使いやすいライブラリの提供も大きな目 標である。全文検索の機能をいろいろなアプリケーションに組み込 めるようにしていきたい。
Namazu は研究プロジェクトではなく、実用を目指すフリーソフト ウェアである。その開発が学問として新たな知見をもたらすことは ないかもしれないが、よりよい計算機環境の追求のために今後も開 発を続けていきたい。ナマズの寿命は 60 年だそうだが、Namazu はこの先何年、使われているだろうか?