Groongaで学ぶ全文検索の勉強会に参加した際のメモです。
https://groonga.doorkeeper.jp/events/31604

全文検索とは

複数文書にまたがって、文書の全文を対象とした検索

入力（クエリー、キーワードなど）→全文検索→出力(マッチした文書)

上記の様に複数の文書の中からクエリやキーワードなどの入力にマッチした文書を出力として返す
※何かを考えるときは入力と出力を考えるとよい

全文検索の仕組み

複数の文書の中の文字列を毎回頭から検索していると時間がかかるため
辞書の索引の様に、事前にどの文書にマッチする文字列が存在しているかという情報を保持するインデックス作る。
全文検索の際には作成したインデックスからマッチする文書を検索する。

どうやって見つけるかによって作成の仕方が異なる。
前方一致で検索させる事が多いためA-Zなど決まった順に並んだリストとして作成する事が多い。
下記の例の様に「He」で検索したい場合などに周辺のデータを探しやすい。

index0 Hello 文書3
index1 Hey   文書2 
index2 World 文書3

関連するものを取る必要がないタグなどの場合にはハッシュ値などを利用してデータを一意に特定することもある

インデックスの作り方には
1.随時処理
2.バッチ処理
の２種類があるが
Groongaの場合には随時逐次処理を利用する事ができ、インデックスの作成時間を遅く感じさせない事ができる

作成したインデックスを検索する際には二分探索を使う事が多い。
これにより文書数が増えても線形的に検索時間が増えることを防いでいる。

二分探索の検索の仕方

1.データを昇順、または降順に並べたリスト作る
2.リストの中央値をとる
3.検索したいものが中央値と同じであれば終了
4.検索したいものが中央値よりも前半にある場合検索の対象範囲前半として、後半にあれば対象範囲を後半として2.に戻り、3.になるまで検索を続ける。

例)下記のリストからHを検索する場合
中央値はリストの最初と最後の値を足して2で割ったものとする(小数点以下は切り捨て)

1.(1+10)/2 =5が中央値でEを取得
2.HはEより後ろなので中央値より後ろを検索範囲とする
3.(6+10)/2 =8が中央値でHを取得し検索終了

index1  A 
index2  B
index3  C
index4  D
index5  E　☆1.最初の中央値
index6  F
index7  G
index8  H  ☆2.次の中央値
index9  I
index10 J

→条件がゆるすぎると検索結果が多すぎてしまい、きつすぎると欲しいものが見つからなくなってしまう。

例)「ネジ」でも「ねじ」でも検索させたい。

例)通常の検索では記号を無視するが
下記などリファレンスなどの場合には記号も検索対象とするなど

→効率的に処理できるように近いものは同じ領域に確保するなどの工夫をしている