前回は形態素解析を使う検索エンジンのしくみについて説明しました。今回は，FINDSPOTで使用しているN-gramという検索エンジンのしくみについて説明します。

N-gramによる見出し語の切り出し

前回は，形態素解析による検索エンジンでは，検索可能な最小単位が分かち書きの切り分け単位となる点を説明しました。

一方，N-gramを使った検索エンジンでは，単純に文字の並びを見出し語としてインデックスを作成します。1文字を元にインデックスを作成する方法をユニグラム，2文字の並びを元にインデックスを作成する方法をバイグラム，3文字の並びを元にインデックスを作成する方法をトリグラムと呼んでいます。

1文字：ユニグラム

2文字：バイグラム

3文字：トリグラム

N-gramによる見出し語の切り出しは，形態素解析のための文法解析を伴わないため，特定の自然言語に依存しないという特徴があります。

FINDSPOTでは，1文字の文字列を見出し語として用いるユニグラムと，2文字の文字列を見出し語として用いるバイグラムの手法を併用して，インデックスを作成しています。このうち，ユニグラムは専ら1文字の文字列検索に使用しており，2文字以上の文字列についてはバイグラムを用いて検索を行っています。

具体例を用いて説明しましょう。「今日は良い天気です。」という文字列をバイグラムのインデックスを作成してみます。この文書のIDを1番とすると，次のような索引情報が生成できます。

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

別の「今日は大雨です。」という文書ID 2番の文書をバイグラム情報は，次のようになります。

今日    2
日は    2
は大    2
大雨    2
雨で    2
です    2
す。    2
。　    2

文書ID 1番と2番の文書を合算した索引情報は，次のようになります。

今日    1, 2
日は    1, 2
は良    1
良い    1
い天    1
天気    1
気で    1
です    1, 2
す。    1, 2
。　    1, 2
は大    2
大雨    2
雨で    2

これがバイグラムによる転置インデックスです。

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

では，バイグラムの単位より長い文字列の検索についてはどうでしょうか。長い文字列をバイグラムで検索するには，検索文字列をバイグラムの単位に分解します。そして，それぞれの2文字の文字列片による検索を行い，結果を合成します。

「⁠良い天気」という文字列を検索するには，「⁠良い」と「天気」という文字列に検索文字列を分解します。次にそれぞれの文字列片で検索を行います。「⁠良い」という文字列が含まれる文書IDは1，「⁠天気」という文字列が含まれる文書IDは1なので，結果をANDで演算して文書ID 1が検索結果となります。

では「今日は大雨」という文書についてはどうでしょうか。こちらは5文字の奇数長の文字列なので，文字列の終わりの1文字を重複させ，「今日」「⁠は大」「⁠大雨」という文字列に分解します。それぞれの文字列片で検索を行うと，「⁠今日」は文書IDが1と2，「⁠は大」は文書IDが2，「⁠大雨」は文書IDが2となります。結果をANDで演算すると文書ID 2が検索結果となります。