2. 原理

　文字が出現する位置の情報をインデックスとして保持し、それを利用して検索します。

2.1. 最初は1Gramから

　N-Gram方式でNを１とした場合です。つまり、検索対象のテキストに対して１文字単位にインデックスを作成します。

　まず、ある程度の大きさを持ったテキストがあるとしましょう。このテキストの各文字について、インデックスを作成します。

　インデックスの要素は次のようになります。

• 文字
• 出現位置

　このインデックスは、任意の文字の出現位置を、素早く得られるものとします。

　“天気予報によれば雨です”という検索対象のテキストに対して、インデックスの要素は以下のとおりです。

　仮に、これらの要素が文字をキーにソートされるとすれば以下のようになり、バイナリサーチ等の方法で検索できます。

１文字を検索する場合

　１文字を検索するのはとても簡単です。各文字の出現位置を見つけ出すことと同等なので、検索結果を保持しているようなものです。

　“雨”という文字を検索するには、インデックスから文字‘雨’をキーとして出現位置を検索することにより、結果が得られます。

２文字以上を検索する場合

　２文字以上を検索する場合は次のようにします。

　“天気予報”という文字列を検索するものしましょう。

　まず、文字‘天’の出現位置を検索し、その結果の１つを px とします。

　この px に対して、次の条件が成立すれかどうかを調べます。

　文字‘天’の全ての出現位置、p0,p1,p2...px...に対して、上記の条件が成立する場合が、“天気予報”という文字列パターンの出現する位置です。

　このようにして、1Gram のインデックスにより、任意の文字列パターンを検索することが出来ます。

2.2. 次に 2Gram

　次に、N を 2 としてインデックスを作成して場合について考えます。このインデックスは次のように作成します。

　“天気予報によれば雨です”が、検索対象のテキストであれば、以下のようになります。

　最後の“す”は、１文字になってしまいますので、２文字目にはシステムで取り決めた適当なコードを埋めておくことにします。

１文字を検索する場合

　２文字のインデックスから１文字を検索するので、このインデックスは、前方一致で検索した結果も高速に得られる必要があります。

　“雨”を検索する場合、SQL の LIKE 演算子で表せば、LIKE '雨%' または、LIKE '雨_' で検索した結果です。

２文字を検索する場合

　２文字のインデックスから２文字の文字列パターンを検索するので、１文字のインデックスから１文字の文字列パターンを検索する場合と同様、簡単に結果を得られます。

３文字以上を検索する場合

　検索結果が３文字以上の場合には、1Gram インデックスで２文字以上を検索する場合と同じように条件を加えます。

　“天気予報”という文字列を検索するには、まず、文字列“天気”の出現位置を検索します。その結果の１つを px として、次の条件が成立すれかどうかを調べます。

　同様に、“天気予報によれば”を検索するには、

　が、条件になります。

　検索する文字列パターンの長さが２の倍数ではない場合には、最後の条件を変えることで対応できます。

　“予報によれば雨”という７文字のパターンを検索するには、“予報”の出現位置 px に対して次の条件になります。

2.3. N-Gram

　検索対象のテキストを、任意の N 文字に区切ってインデックスを作成します。

　“天気予報によれば雨です”に対する４文字のインデックスは以下のようになります。

N未満の文字数を検索する場合

　2Gram の場合と同様、前方一致で検索します。

N文字の文字列を検索する場合

　これも 2Gram と同様に検索します。

N+1文字以上の文字列を検索する場合

　文字数が、N の倍数の場合は、問題ないでしょう。

　出現位置 px に対して、px+N,px+2N,px+3N,,, の位置に検索文字列が出現するという条件を加えます。

　文字数が、N で割り切れない場合には、最後の条件で調整します。

　（文字数-N）の位置に出現する文字列を条件とします。

　“天気予報によれば雨”を 4Gram のインデックスで検索する場合には次のようになります。