前回までで、現在のFINDSPOTに至る一通りの開発の流れを説明しました。今回からFINDSPOTの内部構造について解説していきます。FINDSPOTはN-gramというしくみを使ったシステムですが、今回は検索エンジンの内部構造としてN-gramと並び利用例の多い、形態素解析を使ったシステムの構造について説明します。

全文検索の方式

全文検索を行うにはさまざまな方法があります。大きく分けると、全文照合方式と索引方式に分けられます。

全文照合方式は、検索対象の文書をすべて走査して、一致する文字列を含む文書を探す方法です。UNIXのgrepはこの方法の代表格です。また、ワープロやテキストエディタでの検索や置換機能は、検索対象のデータがメモリ上に置かれていますが、検索文字列とメモリ内のテキストデータと照合して一致する箇所を見つけるという意味では、基本的に同じ方法といえます。

全文照合方式は、文字列パターンと対象のテキストデータを突き合わせて一致する箇所を高速に見つけ出す、全文照合のアルゴリズムを利用するのが一般的です。KMP(Knuth-Morris-Pratt)法やBM(Boyer-Moore)法は、全文照合アルゴリズムの代表格です。egrepでは検索パターンから有限オートマトンを作成して検索を行うという方法を使っています。

索引方式では、あらかじめ検索対象の文書をいったんメモリ上に読み込み、検索語に対応する索引データを作成する前処理を行います。検索時には、あらかじめ作成されている索引を元に、合致した文書を見つけ出す方法です。索引といってもピンとこない方もいると思いますが、書籍の索引を思い浮かべると理解しやすいと思います。書籍の索引には次のように、見出し語と、見出し語が使われているページ番号が記載されています。

ソフトウェア的な索引では見出し語に対して、その見出し語が使われている文書（ファイル名、文書ID等）のリストを保存します。検索時は索引から見出し語を見つけ、その見出し語が使われている文書のリストを取得するだけなので、高速に検索が行えます。

全文照合方式と索引方式には、それぞれメリットとデメリットがあります。全文照合方式は、検索のたびに対象のテキストデータをメモリ上に読み込んで照合処理を行うため、大量の検索対象の場合、どうしても検索時間がかかるという欠点があります。

索引方式は、高速に検索が行える反面、あらかじめ索引を作成しておかなければなりません。索引の作成処理は、かなり負荷の高い処理になってしまいます。

このため、全文照合方式と索引方式には、それぞれ向き、不向きがあります。利用する場面に応じて使い分けるのがポイントです。検索対象が少量で検索回数も少ないなら全文照合方式、検索対象が大量で頻繁に検索されるようなら索引方式が向いています。

見出し語の切り出し

高速に大量の文書を検索するのに向いた索引方式にも、さまざまな手法があります。よく利用されている手法は、形態素解析方式とN-gram方式です。形態素解析方式の代表格は、フリーソフトの検索エンジンであるNamazuが挙げられます。FINDSPOTでは後者のN-gram方式を採用しています。基本的に、見出し語をどのように作成して検索を行うかが大きな違いです。

分かち書きと形態素解析

英語は単語と単語の間がスペースで区切られますが、日本語ではテキストの中から正しく単語を切り出すという処理が意外と大変です。この単語を切り出す操作を分かち書きと呼んでいます。テキストを分かち書きするには、原文の自然言語を構文解析する手法が一般的です。この操作を形態素解析と呼びます。先に名前の挙がったNamazuでは、日本語の形態素解析機能としてKAKASIやChaSen(茶筌)というシステムを利用しています。NamazuはKAKASIを前提に作られていますが、ChaSenという別の形態素解析のシステムで代用も可能です。機能的にはChaSenの方が高度な分析が行えますが、スピード的にはKAKASIの方が高速と言われています。

では、実際の形態素解析を使った検索方法について説明していきましょう。「⁠今日は良い天気です。」という文書を分かち書きしてみます。結果は次のようになります(/は区切り位置を示します)。

今日/は/良い/天気/です。

この文書のIDを1番とすると、次のような索引情報が生成できます。

別の「今日は大雨です。」という文書IDが2番の文書を分かち書きすると、「今日/は/大雨/です。」となります。索引にこの情報を追加すると、次のようになります。

検索エンジンでは、この索引を格納するデータベースやファイルのことを、「⁠転置インデックス」とか「転置ファイル」と呼んでいます。また、文書情報から、転置インデックスを作成する処理を「転置インデックス作成」あるいは略して「インデックス作成」と呼びます。

このようにして作られた索引情報を使って、「⁠天気」という文字列を検索すると、文書IDが1番の文書が該当することがわかります。また「今日」という文字列を検索すると、文書IDが1番と2番の文書が見つかります。さらに「今日」と「大雨」という2つの文字列を含む文書を探す場合には、「⁠今日」の検索結果と「大雨」の検索結果をAND条件で合成すると、文書IDが2番という結果が得られます。これが形態素解析で作成した索引を使った検索ロジックです。

形態素解析の問題点

では、別の「天気予報通りです。」という文書ID3番の文書を追加してみましょう。分かち書きの処理を行って「天気予報/通り/です。」という結果が得られたとします。この情報を索引に追加します。索引情報は次のようになります。

この索引情報を使って、再度「天気」という文字列を検索してみましょう。先ほどと同じように文書IDが1番の文書が該当することがわかります。ここで注目すべき点は、文書IDが3番の文書には「天気」という文字列が含まれているにもかかわらず、検索結果として3番の文書が検索できなかったことです。これは、分かち書きで「天気予報」の部分が1語として処理されたためです。形態素解析用の辞書に「天気予報」という単語が登録されており、この部分が1語として扱われたのが原因です。「⁠天気予報」という単語を辞書から削るなどの辞書の保守を行うか、あるいは合成語をさらに分解するしくみを持った形態素解析システムを利用するなどの工夫が必要です。

次に「雨で」という文字列を検索してみましょう。今度は、見出し語に「雨で」という文字列が存在しないので、検索結果は0個の文書になります。「⁠今日は大雨です。」という文字列には「雨で」という部分文字列が含まれていますが、「⁠雨で」という単位で分かち書きされなかったため、検索できないのです。形態素解析による処理では、見出し語の切り分け単位が検索の最小単位となるため、このような状況が生まれてしまいます。前者は辞書の改良などである程度対応できますが、後者は形態素解析による検索エンジンの限界とも言えます。

検索対象に特殊な用語や人名、新語が数多く含まれる場合や、完全一致での検索が確実に求められる場合などでは、形態素解析を使った検索システムは不得意です。また、形態素解析は日本語や英語などの特定の言語を対象に解析を行うため、他の言語の文書は正しく索引を作成できません。複数の言語が混ざっている文書の集合体を検索するのは、複数言語の形態素解析エンジンを併用しなければならないため、かなり難しい処理となります。形態素解析を使う検索エンジンを利用する場合には、以上のような限界点が運用上の問題にならないかをよく吟味して利用すると良いでしょう。