転置インデックスで日本語を検索する際の仕組み

転置インデックスとは

速く全文検索するための仕組み
文書全体を頭から検索していると時間がかかるため
事前にインデックスを作成して高速に検索できるようにする。

今回の例はネット上にある文書を全文検索の対象とする。
大まかな流れは以下のようになる

検索キーワードをパース→転置インデックスから文書を検索→文書を返す

転置インデックスの作り方

文書に含まれる文字列をキー、キーが含まれる文書を登録したインデックスを作成する。
インデックス作成時のキーの分け方に形態素解析やN-gramがある

インデックスのイメージ

キー	文書
こんにちは	http://A,http://B
全文	http://A,http://B
検索	http://A
したい	http://A

形態素解析とは

日本語を辞書を用いて良い感じにを分ける仕組み

全文検索したい！
→全文　検索　したい　！

N-gram

N文字ごとに文字列を区切る仕組み

1文字ごとに区切る：ユニグラム
2文字ごとに区切る：バイグラム
3文字ごとに区切る：トリグラム

こんにちは

こん
んに
にち
など

形態素解析早いが漏れがある
N-gramは遅いが漏れが無い

京都を探したい時
東京都が出てほしくない：形態素解析使う
出て欲しい：N-gramを使う

キワードをパースする際と転置インデックスを作成するときに同じロジックでを分ける必要がある、ロジックが違うと正しい物がヒットしなくなってしまう。

「全文検索」をキーにしてインデックスを作成してもキーワードをパースする際に「全文」で分けてしまうと対象の文書を返却できない。

その他メモ

GroongaはMeCabも利用できる
Groongaにはパトリシアトライというツリー構造にして絞込を行える仕組みもある。
→オートコンプリート機能などで
「と」を入力した際に「東京」を候補として出すような場合に使える。
MySQL5.7日本語対応しているがバイグラムなので1文字を検索できない。
Mroongaはパトリシアトライを利用して1文字検索も可能
MariaDBにはデフォルトでMroongaがインストールされている
転置インデックスには要素が増えても検索スピードが落ちない仕組みがある。

1.0〜9の配列を用意
2.キーをハッシュ化した数値を取得
3.数値を10で割ったあまりの配列にデータを格納
4.アクセスする際には2.,3.で取得した値をキーに格納されているデータから対象のデータを検索する

上記によって用意する配列の数を増やせば、各配列に格納されているデータの量が減るため高速に検索できる。

辞書を変えると転置インデックスを作る時もキーワードをパースする際も更新が必要だが更新作業は大変
→新しいキーワードを追加する場合などに更新作業が発生する。
→対応策として事前に切り替え用のインデックスを作成しておいてから切り替える事でダウンタイムを最小限に抑えられる。
CPUやディスクなどのリソースに余裕がある場合に実施できる。
日本語の場合、複数のキーワードで検索することも多く、検索の際に検索したキーワードは同じ文書にあって、隣り合っていなければならない。隣り合っている事を確認するための方法が完全転置インデックスとそれ以外の場合の２種類がある。

完全転置インデックス

転置インデックスはキーと存在する文書を格納したもの

キー、対象のURL、文書の中の位置を保存し
差が1だったら隣り合っているものと判定し検索結果を返す
下記のような例だと「全文」「検索」で検索した場合

「検索」の位置と「全文」の位置の差分が1(3-2=1)になっているので
http://Aがマッチした文書として返却される

キー	文書	位置
こんにちは	http://A	1
全文	http://A	2
検索	http://A	3
したい	http://A	4

完全ではない転置インデックス

位置を保存しないで、対象の文書だけをしぼりこみその文書の中身を検索する
PostgreSQLなどで採用されている。
入れる情報が少なくなるのでメモリ上に載りやすくなり、少ないリソースでも動きやすくなるが検索時に遅くなりがち
タグ検索など位置情報が必要ないものにも使える