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

2. 原理

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

2.1. 最初は1Gramから

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

 

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

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

  • 文字
  • 出現位置

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

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

文字 出現位置
0
1
2
3
4
5
6
7
8
9
10

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

文字(コード) 出現位置
す (3059) 10
で (3067) 9
に (306B) 4
ば (3070) 7
よ (3088) 5
れ (308C) 6
予 (4E88) 2
報 (5831) 3
天 (5929) 0
気 (6C17) 1
雨 (96E8) 8

1文字を検索する場合

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

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

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

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

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

 

 まず、文字の出現位置を検索し、その結果の1つを px とします

 

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

 ‘気’が(px+1)の位置に出現する
 AND 
 ‘予’が(px+2)の位置に出現する
 AND 
 ‘報’が(px+3)の位置に出現する
 

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

 

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

2.2. 次に 2Gram

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

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

文字出現位置
天気0
気予1
予報2
報に3
によ4
よれ5
れば6
ば雨7
雨で8
です9
10

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

1文字を検索する場合

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

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

2文字を検索する場合

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

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

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

 

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

 “予報”が(px+2)の位置に出現する

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

 “予報”が(px+2)の位置に出現する
 AND
 “によ”が(px+4)の位置に出現する
 AND
 “れば”が(px+6)の位置に出現する

 が、条件になります

 

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

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

 “によ”が(px+2)の位置に出現する
 AND
 “れば”が(px+4)の位置に出現する
 AND
 “ば雨”が(px+5)の位置に出現する

2.3. N-Gram

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

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

文字出現位置
天気予報0
気予報に1
予報によ2
報によれ3
によれば4
よれば雨5
れば雨で6
ば雨です7
雨です8
です9
10

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

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

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

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

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

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

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

 

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

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

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

“によれば”が(px+4)の位置に出現する
AND
“よれば雨”が(px+5)の位置に出現する
PAPER BOWL
NEZEN