１．担当ＰＭ

　鵜飼　文敏　（日本ヒューレット・パッカード株式会社　ヒューレットパッカード研究所　主幹研究員）

２．採択者氏名

３．プロジェクト管理組織

　財団法人京都高度技術研究所

４．委託金支払額

　6,991,505円

５．テーマ名

　共同体的P2P全文検索システムの開発

６．関連Webサイト

　http://hyperestraier.sourceforge.net/

７．テーマ概要

　本プロジェクトでは、ピアツーピア型の分散処理により大規模な全文検索システムの構築を可能にするソフトウェア Hyper Estraierの開発をおこなう。
　Hyper Estraierは、ユーザむけにはコマンドやウェブアプリケーション、そして開発者むけにはライブラリ(API)、この双方を提供し、導入の容易性と高度なカスタマイズ性を両立させる。従来のオープンソースの検索エンジンに比べ、インデックスを構築する処理のパフォーマンスとスケイラビリティの向上をはかる。テキストの解析処理はN-gram法を基礎とすることで完全な再現率を求めつつ、N-gram法に改良を加えることで単なるN-gram法よりも効率的なインデクシングを実現している。
　膨大な量の文書を対象にする場合にはインデックスが巨大になりある程度以上のスケールで性能をだすのが難しくなるが、インデックスをノードごとに分割しノード同士でピア関係を結ぶようにすることで大規模な検索システムの構築ができるようにしている。

８．採択理由

　本提案は単一ノードの検索システムを組み合わせてP2Pな検索システムを作るために必要なコンポーネントの開発であり、HTMLでのハイパーリンクが存在しないドキュメントに対しても、ノードごとの接続関係などを考慮することで、よりよい検索結果を得ることができる分散した検索システムを実現することを目指したものです。提案者はEstraierというフリーソフトウェアな全文検索システムを開発しており、本提案の開発能力はあると判断しました。

９．開発目標

　近年、電子文書の量は増大しており、それらから必要な情報を探しだすための検索システムへの要求は高まってきている。個々の文書につけた属性情報をもとに検索するだけでは不十分であり、文書の本文の全文を対象とした検索システム、すなわち全文検索システムが求められる場合は多い。しかしながら、全文検索にかかる処理は高い計算量をともなうために、大規模な検索システムを構築するにあたっては、高価なハードウェアやソフトウェアおよび専門的な知識が必要となる。
　本プロジェクトの目的は、上記の問題を解決するために、安価なハードウェアでも動作し、検索システムに対する専門的な知識がなくても導入できるシステムを実現することである。
　大規模な検索は、一般的なパーソナルコンピュータを組合せて実現できるようにピアツーピア方式の分散処理により実現できるようにする。検索エンジンライブラリとしての実現に加えて、そのエンジンを利用した典型的な利用目的のための各種ユーティリティを開発することで、ユーザの要求に応じた高度なカスタマイズができるようにしつつ、簡単に導入することもできるようにする。
　成果物はオープンソースソフトウェアとして一般に公開し、この検索システムを利用した検索サービスや、この検索エンジンを使ったアプリケーションなどの開発をうながし、オープンソースソフトウェアにおける検索システムの質・量ともに高めていくことを目指す。

１０．進捗概要

　2005年2月13日、文京グリーンコート産総研オフィスにて、高林哲氏主催で検索システム勉強会が開催された。そこで Hyper Estraierの構想を発表するとともに、検索システムgonzui やnamazuについての発表を聞き、検索システムについて議論した。
　2005年3月には http://hyperestraier.sourceforge.net/ を準備。
　2005年3月26日、文京グリーンコート産総研オフィスにて、再び検索システム勉強会が開催された。Rast、Sennaの開発者と意見をかわし、Hyper Estraierの進捗報告およびデモをおこなった。
　2005年5月頃から、Sourceforge.netから一般配布を開始した。これから後、利用者からのフィードバックを反映しつつ、10回以上リリースを重ねている。
　2005年5月28日、文京グリーンコート産総研オフィスで、中間報告会をおこなった。
　2005年6月3日、Linux Conference 2005の中で開催された検索BOFでHyper Estraierについて発表、他の検索システムRastやNamazu等の開発者と検索システムについて議論した。
　2005年8月19日の未踏成果発表会で、本プロジェクトの成果を発表した。

１１．成果

　Hyper Estraierは転置インデックスと呼ばれるデータ構造のデータベースを用いて高速な検索を実現している。以下このデータベースを単にインデックスと呼ぶ。一般的に、インデックス型の検索システムは、インデックスを構築する機能とインデックスの検索をおこなう機能を主体とし、その周辺にユーザの要求に応じた機能をくみあわせて構成される。Hyper Estraierもその構成を踏襲している。Hyper Estraierでは検索対象の文書を収集してインデックスに登録する機能を「ギャザラ(gatherer)」と呼び、インデックスに対して検索をおこないその結果をユーザに提示する機能を「サーチャ(searcher)」と呼んでいる。
　Hyper Estraierは、ギャザラやサーチャを簡単に実装するためのライブラリと、それを実際に実装したアプリケーションを提供している。周辺機能として以下のものも実装している。
　・ファイラ: 対象文書のリポジトリを走査し、対象文書のデータをぬきだす
　・フィルタ: 対象文書のデータを解析し、本文や属性情報をぬきだす
　・アナライザ: 対象文書の本文を解析し、検索キーを抽出する
　Hyper Estraierのライブラリは複数のAPI層からできている。
　・コアAPI: インデックスに対する最低水準の操作を実装したもの
　・スレッドAPI: コアAPIをスレッドセーフにしたもの
　・ノードAPI: インデックスを内包するサーバプロセスに対する操作を実装したもの
　・言語バインディング: コアAPIとノードAPIを各種スクリプト言語から利用できるようにしたもの

　Hyper Estraierは、これらのライブラリを用いて実装したユーザ用アプリケーションを提供している。ひとつはコアAPIを使ったギャザラで、ローカルファイルシステムを走査し対象文書をインデックスに登録するためのコマンドラインインターフェースプログラムである。もうひとつはコアAPIを使ったサーチャで、CGIスクリプトとして動作するプログラムで、Webブラウザでリモートから検索できるようにするために利用できる。最も典型的なWebサイトの全文検索システムはこれらの二つのプログラムを利用すれば、一切プログラミングすることなく構築することが可能である。そのほかにノードAPIを使ったギャザラ兼サーチャも提供している。ノードサーバは単体でWebインタフェースのサーチャを内蔵しているので、ノードAPIを使った検索システムも簡単なものであれば一切プログラミングせずに構築することができる。
　インデックスを構築する際に、検索語をとりだすためにもとのテキストを解析する必要がある。テキスト解析手法としては、N-gram法を改良した方法を採用している。
　一般に大規模な検索システムでは分かち書き方式と呼ばれる方法でテキストを解析している。これはテキストを、語彙の辞書や文法を考慮して人間が識別できる単語もしくは形態素ごとに分割・抽出する手法である。この方式では、辞書にない語彙を含んだり、くだけた表現がなされていたりする場合に、本来意図されていた通りに単語もしくは形態素に分割されず、思ったとおり検索できない場合があるという問題がある。このような検索漏れは、アプリケーションによっては大きな問題となることがある。また言語に強く依存しがちなため、多言語化が難しい。
　一方、N-gram法はテキストを単純にN文字単位で区切っていくために、いかなる言語のいかなる語彙をもつテキストでも漏れのない検索ができるようなインデックスを構築することができる。しかし、単語として検索するような場合でも検索キー同士の隣接判定をおこなう必要があるために、どの検索キーがどの位置に出現したかという位置情報もインデックスに持つ必要がでてくるために、インデックスのサイズが非常に大きくなってしまうという問題がある。インデックスのサイズの増大はインデックスの構築速度の低下と検索速度の低下をまねき、実用上のスケイラビリティを低下させる。
　Hyper Estraierでは、位置情報を持たなくてもN-gramのキーの連接が判定できる仕組みを考案し、実装した。簡単に説明すると、各検索キーに後続のキーのハッシュ値をもたせてインデックスに格納する方式である。通常の位置情報を使う方式では、インデックスのサイズが対象文書のサイズの数倍にならざるを得ないが、Hyper Estraierの方式では、インデックスサイズを対象文書のサイズの半分以下に抑えることができる。これにより、普通のパソコンクラスのリソースがあれば100万件(10GB)以上の文書を対象とした検索システムが実用的に使えるようになった。N-gram法の実装でこのようなスケイラビリティを有するシステムは他に類を見ない。
　大規模な検索システムを構築できるようにするために、Hyper Estraierでは複数のノードサーバが相互に通信することによるP2P方式の分散処理を実現している。ノードサーバ同士は対等の関係であるため、クライアントはどのノードサーバにアクセスしてもサービスを享受することができる。どれかのノードサーバがダウンしてもシステム全体が停止することはない。ノードはそれぞれ独自のインデックスを管理することができ、別のノードに対して自由にリンクをはっていくことでノードのネットワークをひろげていくことができる。
　Hyper Estraierでは、単一のプロセスおよび単一のポートで複数のインデックスを管轄できるノードマスターというプログラムを提供している。ノードマスター内の個々のインデックスごとに独立したサービスを提供するので、ノードマスターは複数のサーバの集合体とみなすこともできる。個々のインデックスごとの独立したサービスを提供する仮想的なサーバをノードサーバと呼ぶ。
　各ノードサーバには独立したURLがわりあてられ、そのURLによってどのノードサーバかが一意に特定できる。ノードサーバは別のノードサーバに対して一方的にリンクを張ることができる。クライアントがノードサーバに検索要求を出した場合、依頼をうけたノードサーバは自分がリンクをはっているノードサーバにもクエリを中継し、返された結果を自分のインデックスの結果とマージしてクライアントにかえす。いわゆるメタ検索機能を全てのノードサーバがもつことによって、P2P型の分散処理を実現している。
　Hyper EstraierのP2P機構は単にスケイラビリティを増大させるだけではなく、検索精度の向上にも寄与する。検索結果は各ノードが保持しているインデックスおよびそのノードから他のノードへのリンクの状況によって変化するため、接続するノードごとに検索結果に特徴がでてくることになる。ノードが収集する文書のジャンルにかたよりを持たせ、ノード間のリンクを適切に管理すれば、ノードを選択するという行為を検索範囲やスコアリングに影響がでるようなシステムにすることができる。ノード間の各リンクには、信頼度という数値を設定できる。ノードがメタ検索の結果をマージする際には、スコアの重みづけにこの信頼度も利用する。信頼度が高いとそのノードからかえされてきた結果はスコアがよくなり、上位にきやすくなる。
　HyperEstraier は、SourceForgeのホスティングサービス http://hyperestraier.sourceforge.net/ を利用してGNU Lesser General Public Licenseのもとに一般に公開されている。
　また、Hyper Estraierを利用したアプリケーションもいくつか開発されリリースされている。
　・mod_estraier http://modestraier.sourceforge.net/
　・gdestraier http://www.mitsuki.no-ip.com/~seagull/software-archives/hyperestraier/gdestraier.html
　・PgEstraier http://pgestraier.projects.postgresql.org/

１２．プロジェクト評価

　当初の目標通り、P2P的に連携可能な高性能・高機能な全文検索システムを開発することができた。N-gram方式を改良した方法により、N-gramでの再現率をおとすことなく、効率的にインデックスを作成できるようになった。
　プロジェクト期間途中から一般公開し、ユーザからのフィードバックを反映しつつ改良を加えリリースを重なっていった点も評価できる。高性能・高機能な検索システムを容易に構築するためのソフトウェアが開発・配布できており、フリーなオペレーティングシステム・ディストリビューション用のパッケージも作成されている。既にいくつかのWebサイトの検索システムとして利用されはじめている。さらに、Hyper Estraierを利用したアプリケーションも第三者によっていくつか開発がはじまっている点もすばらしい。

１３．今後の課題

　全文検索システムとしての基本的な機能は実装できたが、典型的なシステムであるWeb検索エンジンとして構築しようとするとWebから文書を収集してくる部分などまだ若干欠けている部分があるので、そのような機能を実装していき、より広範囲に利用できる全文検索システムのプラットホームとしての拡充を期待したい。Web検索エンジンだけでなく他のアプリケーション、例えばメールの検索やデスクトップ検索などといったアプリケーションなどもできるといいだろう。
　プロジェクト期間内ではP2P機能の実装はできたが、これを実際にどのように運用していけば、よりよい分散検索システムとして動作するのかがまだ未知数であるので、Hyper Estraierを普及しノードサーバのネットワークを広げていき実証を重ねていって、正しい運用ガイドラインなどをととのえていく必要がある。