目次


魅力的なPython: Pythonによる全文検索システムの開発

さらに優れた検索への道を開く

Comments

このコラムでは、私のPythonプロジェクトの1つであるindexerモジュールについて説明しますが、もう1つ別の目的があります。それは、私も読者の皆さんと同じように常に多くを学ぼうと心がけていますので、この連載記事に対して皆さんから意見やアイディアをいただきたいのです。皆さんの投稿はこのプロジェクトと今後のコラムに取り入れていくつもりです。このコラムは、単に私自身の関心と知識を提示する場ではなく、皆さんの関心と知識を反映するものにしたいと思っています。では始めましょう。

私は、このindexerモジュールは、たとえこのような初期のバージョンであっても、皆さんにとって役立つものであるよう願っています。この全文検索システムは、独立したユーティリティーとしても、あるいは大規模なプロジェクトのモジュールとしても使用できます。その設計は、全文検索の基礎についてと同様に、再利用可能なオブジェクト指向によるコーディングの原則についても示唆します(非常に精密で、豊富な内容を含んでいます)。「時期尚早の最適化は諸悪の根源である」というKnuthの警告には一理ありますが、索引付けの目的は情報を素早く見つけることがすべてなので、このコラムではパフォーマンスの問題も扱うことにします。

モジュールindexerを開発した直接のきっかけは、膨大なテキストとHTMLのヘルプ・ドキュメントを検索する良い方法を同僚が探していたことです。間接的な動機は、長年ため込んだメール、ニュース、作成アーカイブの使い勝手に自分自身も悩んでいたことです。簡単に言うと、indexerを使えば、正規表現として指定することが困難であったり、不可能であるような検索基準によってドキュメントを検索できます。しかも素早く検索できるのです。同じような機能を果たす市販ツールやフリー・ツールは多数ありますが、その多くはWeb情報検索に重きを置くものです。しかもこうしたツールは(LOCALHOST経由の場合でさえ)CGIインターフェースを必要とし、セットアップしにくく、使いづらいものです。Pythonでは、こうしたツールは(別の点に重きを置くものが)1つしかありません。これに対してindexerは、使いやすさに重きを置いて設計しました。もちろん以前のもっと複雑なツールの中には、多くの機能を果たすものもあります。しかしindexerを設計する際には、その相対的な使いやすさを損なわずに拡張できるような余地を与えてあります。

検索エンジンについて

このコラムで「全文検索」と呼ぶものは、「検索エンジン」というやや幅広いカテゴリーに入ります。通常ほとんどの人が検索エンジンを使用するのは、WWW上のURLを検索するためです。たしかにWWWは人類史上最大の共同ドキュメント保管所ですが、おそらくはその雑然とした編成のため、ドキュメントの山が最も必要としているものは、優れた検索エンジンでしょう。しかしながら、中でもますます大容量になっていくローカル・ディスク上のファイルなど、他のドキュメントの山も検索エンジンの恩恵を受けることができます。たしかに階層ファイル・システムとファイル命名規則は優秀ですが、ただそれだけのことです。特定の情報を含んだドキュメントを探したいだけ、ということだってあるのです。

インターネット検索エンジンの問題の半分は、索引付けされるべき内容を含むドキュメントの位置を特定することにあります。有効なURLの中から多くを見つけ出すための発見的な手法は多数ありますが、そのすべてを列挙するためのアルゴリズムはありません。幸いローカル・ドキュメントを(indexerの現行バージョンが行うように)索引付けするときに、すべてのドキュメントを見つけることは簡単です。どれもみな数えうる既知のロケーションに置かれているからです。しかし一部のディレクトリー・サブツリーだけにインデックスを付け、他には付けたくない場合でも、ドキュメントのリストはすべてを網羅する厳密なものになってしまう可能性があります。

ローカルな検索エンジンの設計に当たっては、2つの違った方針があります。検索するその時に実際のファイルの内容を読込んで条件に一致するかを探ることが出来ますし、事前にどのファイルが何を含んでいるのかをデータベースにし、ファイルそのものよりもデータベースを検索するようにすることも出来ます。1つめのアプローチには、常に精密さを保ち、しかも指示する正確な場所と正確な対象を常に検索するという利点があります。このその場限りの方法の最大の欠点は、スピードがきわめて遅く、多くの検索をこなす場合には高く付くという点です。

第2の方法には、少なくともうまく実装すれば、はるかに高速であるという利点があります。検索一回につき、ドキュメントの検索可能な項目についての要約が作成されるため、その後の検索ではこれらのドキュメントを再び読み込む必要がなくなります。このため、検索をはるかに低コストで行うことができます。マイナス面としては、データベースがファイル内容の更新から遅れたものとなるかもしれず、定期的な再検索が必要になって、余分なスペースを占有してしまうことが挙げられます(検索機能と設計の選択によって異なりますが、インデックスされるテキストのサイズの1%?100%)。

その場限りのアプローチとしては、Windowsの「File Find」、Unixライクなオペレーティング・システムのfindおよびgrepユーティリティー(およびKDEでのkfind)、OS/2のPMSeek.exeおよび「Find Object」ユーティリティー、MacOS 7の「Finder」などがあります。データベースのアプローチとしては、Microsoft Officeの「Fast Find」ユーティリティー、類似のものとしてCorel Officeの「QuickFinder」、MacOS 8以上の「Sherlock」、そして非常に限定的な方法であるLinuxlocateユーティリティーなどがあります。BeOS「Find」はハイブリッドですが、属性検索に限定されており、フルテキスト検索はできません。他のオペレーティング・システムでも同様のユーティリティーを提供しています。

検索対象を指定するには、多くの方法があります。その一部を以下に挙げます。

  • 語出現率は、あるドキュメント内で一連の検索語が出現する頻度を示します。ここでは、検索対象項目がより頻繁に出現するドキュメントは、与えられた検索に対して「より良い」合致を見せるという前提に立っています。
  • ブール検索は、語の出現とフレーズの出現の間の複合関係に対応できます。たとえば「(spam AND eggs) OR (ham AND cheese)」は、どちらかの括弧の両方の単語を含んで、他の組からの単語を含まないものと一致するでしょう。
  • 正規表現検索は、(複合の場合もある)パターンを突き合わせます。これは往々にして、概念的なコンテンツを識別するよりも、高度に構造化されたデータを見つける場合に役立ちます。
  • フレーズ検索は、マルチワード項目に対応する簡易検索です。もちろん正規表現検索でもこれを実行できますが、より簡単なシステムでできます。
  • 近似検索は、互いに「近接して」出現する語あるいはフレーズのセットを探します。多くの場合、近似の程度が検索オプションとなります。
  • 実際の語に代わって語幹を使用する場合もあります。「run」、「runner」、「running」、「runs」を関連する語と見なし、各語を個別に突き合わせるのではなく、まとめて見つけることが便利な場合もあります。
  • 概念検索は、意味の類似する語を認識することによって、類似したトピックを扱うドキュメントを見つけ出します。この種の検索では、検索エンジンに何らかの同義語辞典を組み込むことが必要です。
  • Soundex(音索引)検索は、とりわけ英語の変則的なスペルに対応できます。この検索では、それぞれの単語を綴られた通りに扱うのではなく、発音を基にして正規の綴りに変換します。そして変換されたテキストと変換された検索項目とを比較します。

indexerについて

indexerは語出現のデータベースを使用します。バージョン0.1X(アルファ・テスト)では、与えられたセット内のすべての語を含むドキュメントだけを検索できます。この検索ではオプションとして、ドキュメントの長さに対する検索語の占める割合に基づいて、合致するドキュメントを分類できます。indexerはさまざまな方法で拡張できます。いくつかのものは論理的かつ直接的で、他のものはもっと難しいものとなるでしょう。

ブール機能は簡単明瞭なもので、(その機能の組み込みは)予定されています。indexerは、どのファイルがどの語を(何回)含むかを追跡しているので、検索する語が含まれるかどうかに基づいて、そのファイルを除外したり含めたりする論理を追加することがたやすく行えます。実際、現在の機能は原則として各検索語の論理和をとることが標準として設定されています(思うに、実用的な検索の大部分がまさにこの「x AND y AND z」タイプの検索です)。

正規表現をindexerに追加することは、ほとんど不可能です。ですから、どのファイルがどの正規表現と一致するテキストを含むかを示すリストを作成するデータベース検索システムは聞いたことがありません。実際には、正規表現はその場限りの方法で処理する必要があります。そしてgrepはまさにそのためにあるのです。

フレーズおよび近似検索は現在行われていませんが、実装することは難しくないでしょう。基本的に各ファイル内の各語の出現数とともに、各ファイルに対して語が出現するオフセットのリストを収集することが必要になります。そこからフレーズと近似を推論することになります。ただし、これを追加することでデータベースのサイズが増大し、そのため検索時間が長くなるという感じがしています。

概念検索、語幹検索、soundex検索は、現在の一般フレームワーク内で可能ですが、かなりの作業が必要になります。これらによって、データベースは異型を格納せず、基準形のみを格納するので、実際にデータベースのサイズを小さくできる場合もありますが、外部の類義語辞典と語変化の規則パターンという代償が必要になります。

indexerのプログラム方法

indexerのソースをダウンロードすることを皆さんにお勧めします(この記事の最後の参考文献を参照してください)。わずか1つのファイルで構成され、非常に詳しく、ほとんど修辞的プログラミングと呼んでもよいほどにまで、コメント付けされています。

プログラム構造についていくつかの注意を次に示します。ファイルは番号付けされており、各ファイルはインテジャー変数、「fileid」に関連付けられています。

indexerは、検索キーが単語であり、値それ自身がまた、キーが「field」で、「field」で指定されたファイルにその単語が出現した回数を値とする辞書である、Pythonの辞書モジュールをを管理しています。Python辞書のルックアップは非常に効率的なので、実際のファイル名に「fileid」を接続する際に比較的わずかな作業を追加するだけですみます。

indexerは、そのメインにGenericIndexerという名前の抽象クラスを含みます。GenericIndexerで定義されている最も重要なメソッドは、add_files()find()です。save_index()メソッドも、記憶機構がファイナライズを必要とする場合(たいていは必要)には、重要になることがあります。

GenericIndexerを抽象クラスにしているのは、自らをインスタンス化できないという事実です。特定の義務をさらに果たす限りにおいて、その子クラスだけがインスタンス化を行うことができます。「抽象」という用語はC++から引き継いだもので、C++ではクラスの形式宣言の一部をなすことができます。Pythonでは、そのような形式宣言はなく、クラスの「抽象」性は、クラスの開発者によるユーザーへの単なる推奨にすぎません。それがPythonのやり方で、データの隠蔽、メンバーの可視性、継承の要件などを強制することなく、これらの事項が行われるべきタイミングに関して穏当な規則に従うだけです。ただしGenericIndexerは、そのメソッドのいくつかが「raise NotImplementedError」の行で構成されているので、その推奨を強制する作業をうまくやってのけます。特に__init__()load_index()を呼び出しますが、これはこうした「NotImplemented」メソッドの1つです。

GenericIndexerの派生クラスは、実際にインデックスを格納するのに異なる方法を実装します。中でも最も実用的なものはZPickleIndexerですが、これはzlibcPickleを組み合わせ、圧縮され蓄積された辞書を格納します。おもしろ半分な気持ちと、驚くべきパフォーマンス結果に引かれて(モジュールのベンチマークを参照)、私はSomethingIndexerクラスを他に多数作成しました。お気に召すなら、shelve、XML、フラットファイル、cPickleのクラスが利用できます。意味がないともいえますが、すべてのインデックスを/dev/nullに効果的にダンプして、毎回検索の開始時に再検索を要求するNullIndexer派生を作成することもできます。

load_index()save_index()の実装を提供することに加え、具象(「抽象」の反意語)SomethingIndexerクラスは「ミックスイン・クラス」SomethingSplitterから継承します。現在のところ、そのようなクラスはTextSplitterだけですが、他にも追随するものが出てきそうです。SomethingSplitterは、テキスト・ストリングを取り込んで構成単位語に分解する非常に重要なsplitter()メソッドを提供します。しかしこのことは、想像よりもはるかに困難だと分かります。語であるものと語でないものを区別するのは、ほんの微妙な相違なのです。将来私はXMLSplitterTeXSplitterPDFSplitterなどのようなTextSplitterの派生を作成するつもりです。さしあたって今は、ほどほどに愚直な方法でテキスト語を見つけようと試みているところです。

「ミックスイン・クラス」は興味深い概念であり、多くの場合優れた設計の選択肢になります。TextSplitter(あるいはその将来の派生)のようなクラスは、多くの具象派生にとって役立つ機能を含んでいることがあります。抽象クラスと同様に、ミックスインは直接にインスタンス化されることはほとんどありません(これは禁止の問題というよりも、むしろ便利さの問題です。私はミックスインの中でNotImplementedErrorが投げられるようにはしません)。ただし抽象クラスとは異なり、ミックスインは子クラスのためのフレームワークを含めようとはしません。TextSplitter.splitter()は、基本的にグローバル・ユーティリティー関数と似ていますが、若干有効スコープの制御に優れています。

indexerにおける未解決の問題

indexerには解決したい特有の問題がいくつかあります。そうした問題は最終的にはパフォーマンスに行き着きます。

現在の設計では、索引が格納されるのは、起動時にメモリーに読み込まれる単一のデータベースです(実際にはShelveIndexerは3つの「棚(シェルフ)」を使用しますが、WORDシェルフが唯一の大型のもので、それは十分問題となる大きさです)。3?4 MBのデータベースを読み込み、語の一致を見つけ、結果を生成するには、96 MBの333 Mhz Linuxマシンでほんの5秒ほどしかかかりません。これはきわめて妥当なもので、その場限りの検索ツールに比べてはるかに高速です。しかしデータベースが大きくなるにつれて、パフォーマンスは劇的な非線形を示します。データベースが12 MBになると、読み取り?ロード?検索の時間は1分を優に超えてしまいます。これは実に受け入れがたいもので、データベース・サイズの4倍の増加に見合うものではありません。何らかのキャッシュ・ミスの影響が考えられますが、システムの実際のメモリーを考慮すれば、私には納得できるものではありません。

大規模データベースの問題に対するきわめて簡単なソリューションは、データベースを細かく分割することでしょう。たとえば、異なる文字で始まるインデックス付きの語には、異なるファイルを使用します。ほとんどの検索がほんの数語に対して行われ、わずかな最初の文字でヒットするので、こうしたファイルのサブセットだけが、与えられた検索に対してロードされることになります。頭文字が不均一に分布している場合でも、これは読み取りを大幅に縮小します。もちろん各データベース・ファイルを読み込んだ後にメモリー内の辞書を結合するために若干余分な処理が必要になりますが、それでもファイル全体を読み込むことに比べれば安く収まるはずです。

データベースを読み込むコストに対するさらに優れたソリューションは、その作業をまとめて回避してしまうことです。これには、shelveを使用するのが1つの方法でしょう。ディスク・ファイルをメモリーに読み込まずに辞書として利用できるからです。しかし2台のテスト・マシンでは、インストールされたdbmdumbdbmdbhashだと判明しました。これらはともに、途方もなく膨張したデータベースを生成します(ZPickleIndexerの10倍の大きさです)。私にはこれは受け入れがたく、またユーザーがgdbmbsddbのようなより優れたdbmをインストールすると決めてかかる気にはなれません。

しかしながら、データベースのサイズに関する問題は、さらに基本的な問題に帰着します。理想的には、検索されるファイルが増えるにつれて、辞書の増大が漸近的になることが期待されます。結局のところ、あるところまでいくと、殆ど可能性のある全ての単語が追加されたようになるのではないでしょうか。残念ながら、このような理想的な状況は現実のものになりそうもありませんが。

現実の語を識別するということは、きわめて困難だと分かります。こうした語の多くは簡単な英語辞書で見つかるようなものではなく、わけの分からない言葉と区別するのは至難の技です。1つには、ドキュメントは別の人間が使用する言葉類でもで記述されています。商標、ユーザー名、URL、会社名、オープン・ソース・プロジェクト、その他多くのソースが、indexerが明らかに「語」と認識するような言葉を使用しています。テキスト以外のデータを含むファイルでは、base64やアンエンコーディングのようなセミバイナリー・エンコーディングによって、さらにはバイナリー・エンコーディングによってでさえ、偶然に擬似語が生成されます。TextSplitterはいくつかのヒューリスティックを使用して、かなり多くのこの手のわけの分からない言葉を排除しますが、改善されたスプリッター・クラスならば、おそらくインデクシングはさらに望ましい漸近的な作業になるでしょう。語を文字のストリングに限定すれば、多くのノイズを削減できますが、純粋な文字/数字の組み合わせはあまりに多すぎます(「P2P」、「Win95」、「4DOM」など)。提案があれば、どうぞお寄せください。

結論

このコラムではindexerモジュールと、全文検索という少し範囲の広い話題について、ほんの概略を説明したにすぎません。時とともにモジュールが改善を重ね、読者とユーザーの皆さんから提案が寄せられたあかつきには、将来のコラムでこのモジュールを再度取り上げ、その背後にある理論についてさらに詳しく触れることにします。


ダウンロード可能なリソース


関連トピック

  • indexer.pyユーティリティー/モジュールをダウンロードします。
  • dtSearch Corporationでは各種の状況において高機能フルテキスト検索を行う市販製品のファミリーを提供します。
  • 定評ある強力な全文検索・エンジンはht://Digです。
  • Perlfect SearchはPerlで作成された多用途検索エンジンです。

コメント

コメントを登録するにはサインインあるいは登録してください。

static.content.url=http://www.ibm.com/developerworks/js/artrating/
SITE_ID=60
Zone=Linux
ArticleID=230152
ArticleTitle=魅力的なPython: Pythonによる全文検索システムの開発
publish-date=05012001