[English | Japanese]

Namazuの豆知識

目次

• インデックス作成の高速化
• メモリを節約したインデックス作成
• HTML要素によるスコアの重みづけ
• HTMLの処理
• 行頭行末の処理
• HTML文書の要約作成
• Mail/News の要約作成
• 記号を含む単語のインデックス処理
• (あやしげな)フレイズ検索の実現
• 文書の更新・削除に対応インデック スの更新

インデックス作成の高速化

• Perlモジュールを利用する
  NKF, KAKASI (または ChaSen) をそれぞれコマンドとして呼び出し たときと較べて 1.5倍 - 2倍くらい速くなります。
  • NKF
  • Text::Kakasi
  • Text::ChaSen1
  • MeCab
• --media-type=mtype オプションを指定する
  mknmz は File-MMagic モジュールを使って文書形式の自動判別を 行います。対象ファイルの文書形式があらかじめわかっているなら-- media-type=mtype を指定することで自動判別の処理を停止できま す。1,2割くらい速くなります。
  対象ファイルが Mail/News なら --media-type=message/rfc822 を 指定する代わりに --mailnews を指定できます。同じく MHonArc なら --media-type='text/html; x-type=mhonarc' の代わりに --mhonarc で指定できます。
• mknmzrc の $ON_MEMORY_MAX の値を大き くする
  標準では 5 MBに設定されています。mknmz はこの値に従って、メ モリ上で処理する文書ファイルの量を制限しています。メモリを 1 GBくらい積んだ計算機を使っているなら、この値に 100 MB を設定 しても大丈夫でしょう。作業ファイルへの書き出し回数が減ります。
• 高速な計算機を使う
  高速な CPU + 大量のメモリ + 高速 な HDDを積んだ計算機を使うと効果的です。$ON_MEMORY_MAX の変 更をお忘れなく。

メモリを節約したインデックス作成

インデックス作成にはたくさんメモリを必要とします。mknmz の実 行時に Out of memory! というエラーが発生する場合には、次の対 策が考えられます。

• mknmz に --checkpoint オプションを指定する
  mknmz は mknmzrc の $ON_MEMORY_MAX の値で、一度にメモリに読 み込む文書ファイルの量を制限しています。そして、読み込んだ文 書ファイルの量が $ON_MEMORY_MAX に達するたびに、作業ファイル を書き出します。 --checkpoint を指定すると、mknmz はこのときに自分自身を exec し直します。結果として mknmz のプロセスはぐっと小さくなりま す。興味のある方は挙動を top で眺めてください。
• mknmzrc の $ON_MEMORY_MAX の値を小さくする
  標準では、mknmz は 5 MB に設定されています。この値はおおよそ メモリを 64 MB 程度積んだ計算機を想定しています。 64 MB より 少ないメモリしか持たない計算機で mknmz を実行する場合は mknmzrc の $ON_MEMORY_MAX の値を小さくするといいでしょう。

HTML要素によるスコアの重みづけ

標準では次の規則に従って重みづけを行います。この値は経験的に 求めたものです。理論的な根拠はありません。

• <title> 16
• <h1> 8
• <h2> 7
• <h3> 6
• <h4> 5
• <h5> 4
• <h6> 3
• <a> 4
• <strong>, <em>, <code>, <kbd>, <samp>, <cite>, <var> 2

また、 <meta name="keywords" content="foo bar"> の foo bar に対しては 32 のスコアがつきます。

HTMLの処理

Namazu ではインデックス作成の際に ", &, <, > および &#9-10, &#32-126 の named entity と numbered entity を復号しています。内部処理を日本語 EUC で行うため ISO-8859-1 の右半分 (0x80-0xff) の記号は処理 できません。同じ理由により UCS-4 の numbered entity にも対応 不可能です。

行頭行末の処理

行頭・行末の空白・タブ、行頭の > | # : を削除します。また、 行末が日本語で終わる場合は改行コードを無視します (日本語の単 語が行末で分断されてしまうのを防ぐ) 。これら処理は特にメイル のファイルをなどを扱う際に効果を発揮します。また、英文 hyphenation の復元も行います。

HTML文書の要約作成

HTML は文書の構造を定義します。<h[1-6]> によって定義さ れる文書の見出しの情報を利用すれば、簡単に要約のようなものを 作成できます。要約は標準では 200 文字に設定されています。見 出しだけを集めて足りない部分は文書の先頭から補います。また、 対象が単なるテキストファイルだった場合には文書の先頭から 200 文字をそのまま使います。

Mail/News の要約作成

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

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

記号の処理は難しい問題です。例えば (foo is bar.) のような文があったときに単純に空白区切りでイン デックスを作ると "(foo", "is", "bar.)" のように 登録されてしまい、これでは foo や bar で検索できなくて困りま す 。

この問題を回避するためには記号をすべて取り払ってしまえば最も 楽なのですが、 .emacs, TCP/IP といった記号混じ りの単語で検索したい場合もあります。そこで、Namazu では tcp/ip のような文があった場合、 "tcp/ip", "tcp", "ip" と 3 つに分解してインデックスに登録します。

また、 (tcp/ip) という文があった場合には "(tcp/ip)", "tcp/ip", "tcp", "ip" と 4 つに分解 します。しかし、入れ子の処理は行っていないので、 ((tcp/ip)) は "((tcp/ip))", "(tcp/ip)", "tcp", "ip" と処理されます。最初の例では "(foo", "foo", "is", "bar.)", "bar.", "bar" と 登録されるため foo でも bar でも検索できます。

(あやしげな)フレイズ検索の実現

フレイズ検索を素朴に実装すると、インデックスのサイズが巨大に なってしまいます。そこで、 Namazu では単語をハッシュ値に変換 する方法により、インデックスのサイズを小さくしています。

フレイズ "foo bar" が検索式として与えられると、 Namazu は foo, bar についてアンド検索を行い、次にフレイズ情報を用いて 結果を絞り込みます。

フレイズの情報は 2語単位で 16 bitのハッシュ値に変換して記録 しているため、 3語以上のフレイズは正確に検索できません。たと えば "foo bar baz" というフレイズで検索すると、

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

のように "foo bar" と "bar baz" の含まれる文書に誤ってヒット してしまいます。また、ハッシュ値の衝突が起きたときも誤った検 索結果を引き起こします。しかし、誤ってヒットしてしまった文書 についても、少なくとも単語 foo, bar, baz はすべて含まれてい ます。

文書の更新・削除に対応インデック スの更新

この仕組みは実際にインデックスから登録済の文書を更新・削除す るのではなく、欠番情報を記録することによって実現されています。 つまり、インデックスに記録された元の情報はそのままで、単にそ の文書の IDが欠番になったという情報を記録するだけです。

文書の更新/削除を含むインデックスの更新を繰り返していくと欠 番が増えてインデックスの記録効率が悪くなっていきます。そのと きは gcnmz を使ってゴミ掃除をします。

Namazu Homepage