2. 原理

　文字列中から特定の文字列を探す処理よりも、数値に対する演算、比較の方が、圧倒的に処理が速いということを利用します。

　プログラムミングの出来る方には説明するまでも無いことですが、文字列中から文字列を探すには、for文などの繰り返し構文を二重に使用しなければなりません。一方、数値の演算、比較は１行で済みます。

　検索対象となるレコードに対し、数値の演算、比較で、該当するレコードの数を絞り込み、文字列を探索する処理の実行回数を減らすことによって、全体の検索処理を高速化します。

2.1. 文字成分表

　検索対象のレコードを絞り込むために、文字成分表を使用します。

　文字成分表とは、文字列中に出現する文字の一覧です。使用する文字コードのすべての文字について、出現するか否かをビットの位置として情報化します。

　完全な表を作るには、文字種と同数のビット数が必要ですが、ここでは、任意のビット数に制限した不完全な表を使用します。

　例として、16 ビットの表で考えてみます。

　すべての文字に、16 ビット中の、どこかの位置の 1 ビットを割り当てます。

　当然、すべての文字に違うビットを割り当てることは出来ません。複数の文字に同じビットが割り当てられることになります。

　この割り当てにしたがって、文字列中に出現する文字のビットのORを取ります。

　 このようにして作成した任意のビット数の整数を文字成分表として使用します。文字成分表を参照することによって、任意の文字が文字列中に出現している可能性があるかどうかが分かります。

2.2. 文字成分表との比較

　検索対象とするテーブルの列（テキスト型）に対応する整数型の列を追加し、そこに、文字成分表である数値を格納します。

　検索を行うには、検索文字列に対しても文字成分表を作成します。

　検索対象の文字成分と検索文字列の文字成分を比較することにより、検索対象に検索文字列が含まれている可能性があるかどうかが分かります。この比較では、必ず含まれているかどうかは分かりませんが、含まれている可能性が無い場合を除外できるので、時間のかかる文字列探索の処理回数を減らすことが出来ます。

　検索対象文字列の文字成分を T とし、検索文字列の文字成分を S とすると、以下の式が成り立てば、検索文字列がヒットする可能性があります。ここで、OR はビット演算の OR です。

　検索対象の文字列が長い場合には、T が 1111...1111 に近くなり、式が真になるケースが多くなりますが、ある程度の長さであれば、文字列探索を実行する対象レコードを絞り込むことが出来ます。

　例として、文字列“あいうえお”の文字成分表が次のようであるとします。

　検索文字列が“あか”であって、文字成分表が次のようであるとします。

　ORを取ると

　ですから、“あか”は“あいうえお”に含まれていないことが分かります。

　次に、検索文字列が“あい”であって、文字成分表が次のようであるとします。

　ORを取れば、

　となりますから、“あい”は“あいうえお”に含まれている可能性があります。

　検索文字列が“いあ”であっても同じ結果になり、“いあ”が“あいうえお”に含まれる可能性があるということになりますから、実際に含まれるかどうかは、文字列を探索して確定しなければなりません。