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

全文検索の方式

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

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

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

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

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

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

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

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

見出し語の切り出し

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