Top >文字成分表によるLIKEの高速化

2. 原理

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

  

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

  

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

2.1. 文字成分表

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

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

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

  

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

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

‘あ’→ 0000 0000 0000 0001
‘い’→ 0000 0000 0000 0010
‘う’→ 0000 0000 0000 0100
‘え’→ 0000 0000 0000 1000
‘お’→ 0000 0000 0001 0000
        :
        :

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

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

“あい”→ 0000 0000 0000 0011 
“いえ”→ 0000 0000 0000 1010
 

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

2.2. 文字成分表との比較

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

  

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

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

  

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

( T OR S ) = T

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

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

“あいうえお”→ 0000 0000 0001 1111 

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

“あか”→ 0000 0000 0010 0001 

 ORを取ると

11111 OR 100001 = 111111 

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

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

“あい”→ 0000 0000 0000 0011 

 ORを取れば、

11111 OR 11 = 11111

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

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

PAPER BOWL
NEZEN