RDBで実装するN-Gram全文検索

1. 概要

　N-Gramインデックス方式の全文検索（フルテキスト検索）を、特別なモジュールを使用せず、通常のリレーショナル・データベースだけで実装する方法です。

　SQL の LIKE 演算子を使用した文字列パターン検索よりも、はるかに高速な検索が実現できます。

1.1. 全文検索について

　全文検索とは、対象となるテキストから任意の文字列パターンが出現する位置を見つける、あるいは、テキスト群から文字列パターンを含むテキストを見つけることを言います。

　全文検索の方法は、大きく二種類に分けることが出来ます。一つは、意味を持った単語単位で検索して結果を出すもの。もう一つは、検索語の意味を考慮せず、純粋に文字列パターンが出現するか否かで結果を出すものです。

　SQLのLIKE演算子による検索は、後者に該当します。

　単語単位で検索する方法は、形態素解析などの技術を使用してインデックスを作成するのが一般的です。

　文字列パターンで検索する方法は、検索対象のテキストと検索する文字列パターンを照合することで実現できますが、検索を高速に行うにはインデックスを作成するなどの工夫が必要です。

　N-Gram方式は、この検索方法の一種で、検索対象のテキストを１から数文字で区切り、インデックスを作成する方法です。

　一般的に、インデックスを使用した全文検索は、全文検索エンジンと呼ばれる専用のモジュールを使用して実現します。

1.2. RDBだけで実装する全文検索

　ここでは、N-Gramインデックス方式による全文検索の実装方法をご説明します。

　ただし、特別なモジュール（プログラム）を使用しません。すべて、SQLを使用するリレーショナル・データベース（テーブル型の DB ）上に構築します。

　つまり、N-Gramのインデックスをデータベース上のテーブルとして作成し、そのテーブルを検索することによってSQLだけで高速な全文検索を実現するのです。

　N-Gram方式には、インデックスのサイズが大きくなるという問題があり、インデックス部分を小さくする工夫がなされるのが普通ですが、この方法では、それを行いません。当然、インデックスとして使用するテーブルのサイズは大きくなりますが、データベース製品やハードウェアの能力が許す範囲では、実用的な性能が得られます。