第2章では、Hyper Estraierの概要を開発者自身が説明します。設計や実装に関する技術解説も行います。
まず最初に、Hyper Estraier（以下H.E.）とは何か簡単に説明します。
H.E.は誰でも簡単に全文検索システムを作るためのツールキットです。H.E.を使えば、第3章で説明するようなデスクトップ検索も容易に行なえますし、第4章で説明するようなWebサイト検索機能も手軽に実現できます。全文検索システムというのは非常に高度な処理を行うものなのですが、典型的なユースケースでは難しいことを考えずに利用できるのがH.E.の特徴です。管理用コマンドを数回叩くだけでインデックスが生成され、付属の検索用CGIスクリプトを設置すれば、もう全文検索を楽しむことが可能となります。
まずは以下のデモサイトにアクセスしてみてください。Wikipedia日本語版の約32万件の記事を対象にした全文検索システムです。これを使うと全文検索の便利さとH.E.の性能を実感していただけると思います。
H.E.は汎用の全文検索システムです。検索対象となるレコードのことを「文書」と呼ぶことにしますが、最も典型的な文書はローカルファイルシステム上にあるファイルでしょう。H.E.はそれだけでなく、リモートのファイルサーバにあるファイルや、Web上のページや、メールボックス内のメールデータや、リレーショナルデータベース内の各行を文書として扱うこともできます。H.E.は文書のリポジトリ（格納場所）に依存しないだけでなく、文書の形式にも依存しません。典型的な文書形式と言えばプレーンテキストですが、HTML、PDF、Microsoft-Wordなどの文書を扱うこともできます。管理用コマンドのオプションや検索用CGIスクリプトの設定ファイルをいじると、H.E.の挙動をかなり自由にカスタマイズすることができます。また、外部プログラムと連携することもでき、任意のクローラと連携することで様々なリポジトリに対応させることができますし、任意のテキストフィルタと連携することで任意の文書形式に対応させることができます。さらに、ライブラリとして実装されているので、任意のアプリケーションに全文検索機能をつけるために利用することができます。ライブラリのAPIについては第5章を御覧ください。
一般的に全文検索システムというのは対象データの規模に応じて検索速度が遅くなるので、非常に高価なマシンを用意したり、システムのチューニングに専門的なノウハウが必要になったりするのですが、H.E.は普通のPCで何も考えずに動かしてもそれなりの性能が出るように設計されています。また、ライセンス費用だけで100万円以上にもなるシステムが市販されていますが、H.E.はGNU LGPLで基づくフリーソフトウェアなので、無償で利用でき、かつ自由に改造したり再配布したりできます。全文検索というとYahoo!やGoogleやMicrosoftのような巨人達にしか扱えない技術というイメージがあるかもしれませんが、実はそうでもないのです※。全文検索という技術を我々のような一般人にも「自分のものとして」操れるようにするためにH.E.は生まれました。本稿では、読者の皆さんがH.E.自体を改造したり、H.E.を越える新たな全文検索システムを作ったりしてもらうために、H.E.の設計方針や実装について詳しく説明します。
なぜH.E.を作ったのか。H.E.の開発に至った経緯をお話ししましょう。
時は前世紀末に遡ります。学生だった筆者はとある研究プロジェクトで全文検索システムを構築することになり、Namazu※というソフトウェアをいじり始めました。リレーショナルデータベース内のレコードを検索対象にしたいとか、スニペット※を表示したいとか、様々な要求があっていろいろ改造が必要だったのですが、Perlが苦手だったこともあって途中で挫折してしまいました。そこで、どうせなら全部Cで書き直しちゃえと半ばヤケクソで思い立ち、全文検索システムSnatcherを作ったのが全ての始まりです。ただし、これは自分のホームページで公開して、Vector※に登録するなどの普及活動も行いましたが、正直言って全く流行りませんでした。
いつの間にやら卒業、就職してSE※になっていた筆者ですが、全文検索システムの野望は捨てきれずに、ひっそり夜鍋して研究開発活動を行ない、2003年に全文検索システムEstraier※を公開しました。また、Estraierの開発に先行して、新たにデータベースエンジンQDBM※を書き起こしました。前作SnatcherはデータベースエンジンとしてGDBM※を使っていたのですが、その性能と品質に限界を感じたからです。EstraierとQDBMについては世界進出すべく英語のマニュアルも書いて、SourceForge.net※に登録し、Freshmeat.net※でアナウンスしました。100万レコード以上の規模の検索システムのエンジンとしてEstraierを使ってくれるユーザもいたりして、この時点でかなり実用的な検索システムになっていたと思います。ユーザ数も増えて少しずつ注目されるようになっていきました。
気をよくした筆者はさらに開発を続けました。そして、2004年にIPAの未踏ソフトウェア創造事業※というものを知り、Estraierをさらに改良したものを作るという企画でそれに応募したのです。Estraierは分かち書き方式のインデックスを使っていたので検索漏れが発生するという欠点がありましたが、N-gram方式に変更することによってそれを克服しました。また、ほとんどの機能をライブラリとして実装して、他のプログラムに簡単に組み込めるようにするとともに、PerlやRuby等のスクリプト言語からも利用できるようにしました。さらに、P2P型の分散処理を可能にして、インターネット環境においてEstraierよりさらに大規模な全文検索システムを構築できるようにしました。そうして作られたのがHyper Estraierです。H.E.の開発は現在でも続けられています。今後の開発予定については本特集のAppendixを御覧ください。
H.E.のコンセプトは、高性能・高機能・簡単の三拍子そろった検索システムということです。
H.E.の最も大きな特徴は、検索性能がきわめて高いことにあるでしょう。あらかじめ対象文書のテキストを抜き出してインデックスを作っておくことによって高速に検索できるのです。このインデックスは、「文書のID → それが含むトークン※のリスト」という順番で参照する通常のリポジトリの構造を転置して、「トークン → それを含む文書のIDのリスト」という構造のデータベースとして作られるので、「転置インデックス」と呼ばれます。
転置インデックスを作成する処理を「インデクシング」と呼びますが、大規模な文書群のインデクシングには多くの時間がかかり、作られた転置インデックスのサイズも大きくなります。実運用上の問題として、インデクシングにかけられる時間と転置インデックスを置けるディスクスペースには限りがあるので、できるだけ早く、できるだけ小さいインデックスを作れるようにすることが、できるだけ大規模な検索システムを作るのには必要になります。H.E.はこのような時間効率や空間効率の要請にもきちんと応えています。筆者の開発環境（Pentium4/1.7GHz、メインメモリ1GBのノートPC）の環境では、27万件（合計1.5GB）の文書群のインデクシングが99分で完了し、転置インデックスのサイズは1.4GBになりました。
検索時の応答速度は検索条件によって大きく左右されますが、デモサイトを御覧いただくと、ほとんどの場合に0.1秒以内に結果が出ることがお分かりいただけると思います。
転置インデックスのサイズがギガバイト単位になり、個々のマシンのメインメモリの容量を大幅に越えるような規模になった場合、実用的な応答速度を出すためには分散処理を検討することになります。H.E.は転置インデックスを複数に分割して別々のマシンに配置し、それらをP2P的に連携させて統合的に検索する機能を備えています。それによって超大規模な検索システムを構築することができます。詳しくは第6章を御覧ください。
H.E.は筆者にとっての理想的な全文検索システムとなるべく、筆者が欲しいと思った様々な機能を取り込んで作られています。N-gram方式による漏れのない検索ができるのはもちろん、分かち書きを併用して検索速度と検索精度を高めることもできます。AND、OR、NOTといった論理式はもちろん、フレーズ検索や正規表現検索や類似検索もサポートします。分かち書きのための解析器としてはMeCab※が利用できるほか、任意の解析エンジンを組み込むことも可能です。
文書に属性（メタデータ）を付与しておくことで属性検索を行うこともできます。文書のタイトルや更新日時を属性として付与すると便利でしょう。属性検索条件と全文検索条件を併用することもできます。例えばファイルサーバの文書群を対象とした検索では、「本文にSoftware Designを含む」という全文検索条件と、「2006年11月23日以降に更新された」という属性条件と、「PDF形式の」という属性条件の全てに当てはまる文書を検索できると、多くのユーザのニーズを満たせると思います。
H.E.はUnicode（UCS2）の全ての文字を扱えるので、日本語や英語はもちろん、中国語、韓国語、ロシア語、フランス語、ドイツ語、スペイン語など、現在世界で使われているほぼ全ての言語の文書を検索対象にすることができます。ひとつの文書の中に複数の言語が混在していてもかまいません。登録文書の文字コードはUTF-8を基本としますが、文字コードを自動判定して正規化するユーティリティも備えています。
Web上の文書を収集してインデクシングするために、H.E.にはWebクローラが付属しています。巡回の入り口となるURLをいくつか指定しておくだけで、そこからリンクを辿って、指定した数の文書を収集して登録することができます。Webを巡回する際には巡回の順番が重要になり、深さ優先や幅優先といったアルゴリズムを使うことになるのですが、H.E.のクローラはそれらに加えて類似度優先のアルゴリズムを選択することができます。これは、種となる文書を指定して、その内容に近い文書のリンクから優先的に辿るというものです。このクローラを使うと特定の内容に特化したWeb検索エンジンを手軽に構築することができます。
H.E.は、それ自身にHTMLとMIME（電子メール）のデータからテキストや属性を抽出するためのテキストフィルタがついています。また、H.E.のソースパッケージには、UNIX上でPDF/Word/Excel/PowerPointを扱うためのテキストフィルタが付属しています。H.E.のWindows版バイナリパッケージには、PDF/RTF/Word/Excel/PowerPoint/一太郎/MHTなどに対応したテキストフィルタ※が付属しています。これらによって典型的なファイル検索システムを手軽に構築することができます。
既に述べたように、H.E.のパッケージには、管理用コマンドをはじめとして、たくさんのユーティリティプログラムが付属しています。それらを使えば、プログラミングのスキルのない人にでも、簡単に全文検索システムを構築し、柔軟なカスタマイズを施すことができます。Slashdot日本版※をはじめ、H.E.を使った検索機能をつけているWebサイトもだんだんと増えてきています。読者の皆さんもだまされたと思ってぜひぜひ使ってみてください。
ライブラリを使ってプログラムを書けば、さらに強力で多機能なアプリケーションを実装することができます。H.E.のライブラリを組み込んだアプリケーションが既に数多く発表されています。代表的なものを以下に挙げます。
それでは、Hyper Estraierの技術的な解説に入っていきます。
H.E.のアーキテクチャを図XXに示します。H.E.の本体はデータベースマネージャの部分で、それにアクセスするための手段やその他のユーティリティがコアライブラリとして提供されます。データベースには転置インデックスや文書のデータそのものが格納されます。
H.E.のアプリケーションは大きく分けてギャザラとサーチャという2つの機能からなります。ギャザラは、検索対象の文書が格納されたリポジトリをクロールして文書のデータを取り出して、それにテキストフィルタをかけて本文と属性を取り出して「文書オブジェクト」というデータ構造を作ってから、それをデータベースに登録します。サーチャは、ユーザからの入力を受け取ってクエリを生成してから、それをデータベースに問い合わせて、該当する文書の一覧を検索し、それに含まれる文書オブジェクトを取得して表示します。
H.E.のパッケージに含まれている管理コマンドは、上記のギャザラとサーチャの両方の機能を実装したアプリケーションです。また、付属のCGIスクリプトは、サーチャの機能を実装したアプリケーションです。
H.E.は、対象文書のテキストをN-gram法で解析して抽出したトークンを検索キーにした転置インデックスを構築します。N-gram法とは、一定の文字数の部分文字列をトークンとみなし、1文字ずつずらしながら選択していく手法です。例えば、「技術評論社」を2文字ずつのN-gram法（2-gram法）で解析すると、「技術」「術評」「評論」「論社」というトークンが得られるわけです。ここからわかる通り、N-gram法によって抽出されるトークンの数は文字数とほぼ等しくなります。したがって、文書規模の増大に比例して、莫大な数のトークンを転置インデックス内に記録しなければなりません。素直に実装した転置インデックスのサイズは元の文書の数倍にもなってしまうので、データを圧縮して保持するとともに、データの読み書きを効率的に行うデータベースが必要となります。
H.E.では、データベースマネージャとしてQDBMの圧縮B+ツリーという機構を利用することによって、その要請に応えています。圧縮B+ツリーとは、似たパターンのトークンをページという単位にまとめて、圧縮して記録する手法です。個々のページにはBツリーというインデックスが張られるので、個々のレコードを高速に参照することができます。
さらに、H.E.では、N-gram法をベースとしたN.M-gram法という手法を用いることによって、転置インデックスの空間効率を改善しています。通常のN-gram法では、N文字以上のクエリを検索する際には、トークン同士が隣り合っているか判定する「連接判定」の処理が必要となります。例えば「評論社」というクエリに該当する文書を検索する場合、「評論」の1つ後の位置に「論社」があることを判定しなければなりません。そのために、N-gram法の転置インデックスには、各トークンにその文書内の出現位置を関連づけて記録する必要があります。この文書内位置情報のオーバーヘッドがバカにならないのです。
N.M-gram法では、文書内位置情報の代わりに後続のトークンのハッシュ値を用いることによって連接判定を行います。例えば「ファイル」というテキストを解析した場合、「ファ」「ァイ」「イル」というトークンが抽出されますが、「ファ」は「ァイ」と「イル」のハッシュ値と関連づけて記録されます。2-gramで処理したトークンの各々に、後続2つのトークンのハッシュ値を関連付けて記録するので、これを2.2-gram法と呼ぶことにします。このようにして作られた転置インデックスを使って検索を行う際の処理を図XXに示します。
N-gram法においても位置情報を差分列に変換した上でBER圧縮※をかけるといった空間効率の改善手法が知られていますが、それを考慮しても、1バイトないし2バイトのハッシュ値を記録するだけのN.M-gram法の空間効率の方が優れていると言えます。Wikipedia日本語版から無作為に抽出した10000件の記事を対象にN-gramとN.M-gramの空間効率を比較した結果を表XXおよび図XXに示します。
| 方式 | 2.2-gram | 2-gram | 3-gram | 4-gram |
|---|---|---|---|---|
| 異なり語数 | 560149 | 560149 | 3596486 | 8370344 |
| 論理的なレコードサイズ | 91.72MB | 91.92MB | 140.83MB | 212.95MB |
| 実際のデータベースサイズ | 60.44MB | 65.85MB | 108.08MB | 166.91MB |
| 圧縮率 | 0.659 | 0.716 | 0.767 | 0.783 |
| 構築時間 | 158秒 | 165秒 | 1551秒 | 7510秒 |
N.M-gram法は、空間効率だけでなく、検索時の時間効率も優れています。N-gram法においては、「ファイル」という文字列の存在を確認するには、転置インデックスから「ファ」を調べて位置情報を取得し、さらに「イル」も調べて位置情報を取得し、その差が2であることを調べねばなりません。クエリの文字数をトークンの文字数Nで割った値の回数だけ転置インデックスを操作する必要があるので、すなわち2-gramの転置インデックスで4文字のクエリを処理すると 4 / 2 = 2回の操作が必要となります。一方で、N.M-gram法では、「ファ」を調べると「ァイ」と「イル」のハッシュ値が取得できるので、その時点で「ファイル」の存在がわかります。クエリの文字数N+Mで割った値の回数だけの操作で済むので、すなわち2.2-gramの転置インデックスで4文字のクエリを処理する場合は 4 / (2 + 2) = 1回の操作となります。つまり、2.2-gram法の転置インデックスは4-gram法の転置インデックスに匹敵する検索性能を持っていると言えます。
N-gram法の欠点として、トークンの文字数Nを大きくするとインデクシングにかかる時間が非常に大きくなることが挙げられます。また、Nより短いクエリの検索の処理効率が非常に悪化してしまいます。例えば4-gramの場合は3文字以下のクエリで検索した場合に応答速度が非常に遅くなってしまうのです。したがって、Nを大きくすれば検索性能を上がるとは言い切れません。N.M-gram法でも同じ欠点はあるのですが、Nを小さくしてMを大きくすることができるので、検索効率の悪化を最小限に抑えて、平均的な処理速度を向上させることができるのです。N-gramとN.M-gramの検索性能をクエリの長さに応じて計測した結果を表XXおよび図XXに示します。検索語の候補は上述したデモサイトのログから取りました。
| 方式 | 4文字以上平均 | 全検索語平均 |
| 2-gram | 82.3ミリ秒 | 59.3ミリ秒 |
|---|---|---|
| 2.1-gram | 31.3ミリ秒 | 24.8ミリ秒 |
| 2.2-gram | 32.3ミリ秒 | 27.7ミリ秒 |
| 2.3-gram | 36.8ミリ秒 | 30.3ミリ秒 |
| 3-gram | 26.7ミリ秒 | 22.5ミリ秒 |
| 3.1-gram | 5.7ミリ秒 | 15.5ミリ秒 |
| 3.2-gram | 6.0ミリ秒 | 17.8ミリ秒 |
| 3.3-gram | 6.5ミリ秒 | 20.8ミリ秒 |
以上のことから、N.M-gram法は、空間効率においてN-gram法よりも優れているとともに、インデクシングの性能と検索性能のバランスがとれた手法であることがおわかりいただけるかと思います。弱点として、ハッシュ値が衝突した場合やN+M文字以上のクエリを使った場合に検索精度が下がることが挙げられますが、その確率はそれほど高くありませんし、スニペットを作る際に不必要な文書をふるい落とせるので、実用上問題になることはまずないでしょう。2.2-gram法におけるクエリの長さ毎の検索精度は表XXのようになります。
| 文字数 | 精度 |
| 2文字 | 100.0% |
| 3文字 | 97.2% |
| 4文字 | 99.6% |
| 5文字 | 96.5% |
| 6文字 | 97.8% |
| 7文字 | 96.6% |
| 8文字 | 96.1% |
| 9文字 | 95.6% |
| 10文字 | 98.5% |
「京都」で検索すると「東京都」がヒットしてしまうという、N-gram転置インデックスの伝統的な問題があります。「うに」で「そのように」がヒットするとか、「テロ」で「ステロイド」がヒットするとか、類例は枚挙に暇がありません。適切な言語処理に基づいて分かち書きを行なってトークンを抽出した場合はそのような問題は起きないのですが、逆に解析ミスがあった場合に検索漏れになるという問題があります。
N-gram方式と分かち書き方式の双方の欠点を補うために、H.E.では双方を併用するアプローチをとっています。N-gramで抽出した語からなるメインインデックスとは別に、分かち書きで抽出した重要語だけからなる補助インデックスを管理します。そうすると、検索語が適切に分かち書きできた場合は、補助インデックスを見て、高速で高精度な検索を行うことができます。分かち書きがうまく行えなかった場合も、メインインデックスを見れば、検索漏れのない結果を提示することができます。
抽出した重要語は、頻度と関連付けた「キーワードベクトル」として、登録文書とも関連づけて保存されます。キーワードベクトルを使うと、ベクトル空間モデルという手法に基づいて文書間の類似度を計算することができるので、それを用いて類似検索が実装されています。元となる文書の重要語のリストでOR検索した結果を、類似度の降順で並べ変える検索手法です（図XX）。また、通常の検索結果の該当文書の中で類似度が高いものを折り畳んで表示する類似文書隠蔽という機能も実装されています（図XX）。
属性検索は属性データベースにおける全てのレコードを検査するために多くの時間がかかります。H.E.は属性検索を高速化するために属性インデックスをサポートしています。属性インデックスを作成すると、検査するレコードをインデックスで絞り込むことによって属性検索を高速化することができます。
属性インデックスには3つの型があります。シーケンシャル型の属性インデックスは、文書IDをキーにして属性値を値に持つ構造です。検索時には全てのレコードが検査されますが、属性データベースよりは高速に属性検索が行えるようになります。また、型に依存しないという利点と、ソートも高速になるという利点があります。
文字列型の属性インデックスは、昇順（辞書順）の文字列をキーとして文書IDを値に持つ構造です。文字列型の演算子の一部がとても高速化されます。それ以外の文字列型の演算子もやや高速化されます。数値型の属性インデックスは、昇順の数値をキーとして文書IDを値に持つ構造です。数値型の演算子の一部がとても高速化されます。それ以外の数値型の演算子もやや高速化されます。ひとつの属性に指定できるインデックスはひとつだけです。なお、属性インデックスを張ると文書の更新や削除の処理は少し遅くなります。
特定の文書が頻繁に更新される場合、そのたびに転置インデックスも更新するのは効率がよくありません。そのような場合のために、更新は早いが検索は遅いという特性を持つ疑似インデックスという機構が提供されています。文書オブジェクトのファイル化して特定のフォルダに入れておくと、そのフォルダを疑似的なインデックスとして扱い、その中にある文書ドラフトを検索対象に含めることができます。疑似インデックスの検索はgrepと同様の逐次探索で行なわれるので、本当のインデックスに比べてかなり遅くなってしまいますが、インデックスを作る必要がないというのが便利なところです。疑似インデックスを検索対象に加えた場合、本当のインデックスと疑似インデックスのメタ検索が行なわれます。
本当の転置インデックスに文書を登録する際には、各文書を別個のコネクションで登録するよりも、たくさんの文書を1回のコネクションで登録した方が効率的です。したがって、登録すべき文書がある程度の量になるまでは疑似インデックスに入れておき、ある程度の量になったら疑似インデックスの中の文書ドラフトを本当のインデックスに登録して、疑似インデックスを空にすると効率的です。
最後にH.E.を活用するアイデアについて述べ、本稿のまとめとします。
H.E.の典型的な使い方がWebサイト検索やファイルサーバ検索やメールボックス検索であることは既に述べましたが、他にも使い道はいろいろ考えられます。テキストが抽出できるデータのまとまりは何でも文書として扱えるので、論文データベースや判例データベースや特許データベースの検索システムとして利用することも容易です。その際には属性検索や類似検索機能も役に立つでしょう。英文の用例検索に使ったり、図書館の蔵書検索に使うといったことも考えられます。
ブログやWikiなどのCMS※的なシステムが隆盛している昨今ですが、そういったシステムの検索機能としてH.E.を活用している人も多くいます。TracというバグトラッキングシステムとH.E.を連携させることもできるようです。さらに言えば、H.E.自体をリポジトリとしてCMSを作ることも可能です。筆者のブログは自作のシステムを利用して運営しているのですが、近い内にH.E.を使った検索ベースのブログシステムとしてリニューアルしたいと考えています。
H.E.の概要説明と技術解説をざっとしてきましたが、いかがでしたでしょうか。なんだか難しい用語がたくさん出てきましたが、要は、パターンマッチングを高速化させるためのインデックスを管理するライブラリに便利なオマケをつけまくったものです。しかし、筆者が欲する機能はあらかた実装されていますので、少なくとも筆者にとっては世界最高の全文検索システムに仕上がっています。とはいえ、読者の皆さんが使ってみた際にはいろいろと注文をつけたくなる点も多いかと思います。そのような場合は遠慮無くメーリングリストに意見を投げていただけると、その1週間後くらいに筆者か他の誰かが実装してくれるかもしれません。ユーザのみなさんとともに今後もH.E.を育てていきたいと思っているので、どうぞおつきあいくださいませ。
H.E.に関する質問や要望はメーリングリスト※にて受け付けています。初心者からハッカーまで、忌憚なくご発言いただければと思います。