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

全文検索の勉強会の復習です。

転置インデックスとは

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

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

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

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

インデックスのイメージ

日本語を辞書を用いて前後の文脈を加味してキーワードを抽出する仕組み
辞書を用いてキーワードを抽出する際に何パターンかに区切って一番適当と判断されたものが利用される
例)
渋谷/で/カレー/が/食べ/たい
渋谷で/カレーが/食べたい
辞書にはメタデータが登録されていてメタデータにある情報でどれが適当かを判断している
例)
渋谷,名詞,・・・
で,助詞,先頭には来ない
など
検索する文書によって何が適当かは異なるためどの辞書を使うかなどチューニングが必要
例)検索対象
・新聞
・tweet:省略されることが多い
・女子高生の会話:新しい情報が多い
辞書を変更したらインデックスを作り直す必要がある
辞書は最新のものに変えたくなるものなので、そのメンテナンスをどうするかも運用で問題になる →新しいキーワードを追加する場合などに更新作業が発生する。 →対応策として事前に切り替え用のインデックスを作成しておいてから切り替える事でダウンタイムを最小限に抑えられる。 CPUやディスクなどのリソースに余裕がある場合に実施できる。

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

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

こんにちは

こん
んに
にち

など

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

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

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

日本語の場合、複数のキーワードで検索することも多く、検索の際に検索したキーワードは同じ文書にあって、隣り合っていなければならない。隣り合っている事を確認するための方法が完全転置インデックスとそれ以外の場合の２種類がある。

キー、対象のURL、文書の中の位置を保存し差が1だったら隣り合っているものと判定し検索結果を返す
下記のような例だと「全文」「検索」で検索した場合 * 「検索」の位置と「全文」の位置の差分が1(3-2=1)になっているので http://Aがマッチした文書として返却される