読者です 読者をやめる 読者になる 読者になる

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

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

転置インデックスとは

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

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

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

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

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

インデックスのイメージ

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

形態素解析とは

  • 日本語を辞書を用いて前後の文脈を加味してキーワードを抽出する仕組み

  • 辞書を用いてキーワードを抽出する際に何パターンかに区切って一番適当と判断されたものが利用される
    例)
    渋谷/で/カレー/が/食べ/たい
    渋谷で/カレーが/食べたい

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

N-gram

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

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

こんにちは

こん
んに
にち

など

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

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

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

その他メモ

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

完全転置インデックス

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

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

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

  • タグ検索など位置情報が必要ないものにも使える