Posted at

Groongaで学ぶ全文検索 2015-11-20

More than 3 years have passed since last update.


日本語の検索


全文検索おさらい

全文検索は下記のようにキーワードにマッチした文書を出力として返す仕組み

マッチした文書を探す際に単純に頭から検索していると時間がかかるためインデックスを作成して

インデックスから対象の文書を検索する。

入力(キーワードなど)→全文検索→出力(マッチした文書)


インデックス

インデックスは下記のようにキーと値を持っていて、キーに入っているものだけが検索可能

キー

Groonga
[文書A,文書C]

Mroonga
[文書A,文書B]

英語は空白で区切られているのでキーの決め方が簡単だが

日本語の場合下記の例のように区切りが曖昧なのでキーの決め方が難しい。

例)

「東京都」を検索したい場合に

東京都、東京どちらも使う可能性がある。


日本語検索には大きく分けて2種類のアプローチがある


1.単語をキーにするアプローチ:形態素解析


  • 意味のある単語に区切りキーに登録する

    例)

    花が咲いた

    「花」

    「が」

    「咲いた」


  • 日本語は区切りが曖昧なので難しい

    例)

    ここではきものをぬいでを区切る場合

    ここで/はきものを/ぬいで

    ここでは/きものを/ぬいで


  • 検索の際に手数が少なくすむ


  • 代表的なソフトウェアにMeCabがあり文書を解析する際に文書が長くなるとリソースが足りなくてエラーになる。

    Groongaでは長くなり過ぎたら切ってMeCabに渡すオプションがある。



2.なんでもキーにするアプローチ:N-gram


  • 意味を考えずに区切る

    例)

    花が咲いた

    「花が」

    「が咲」

    「咲い」

    「いた」


  • 2文字で区切る2gram(バイグラム)、3文字で区切る3gram(トリグラムなどがある


  • 検索するときにもキーワードを区切る


  • キーワードを見つけてからandを取る必要があり、さらに隣り合っているかを見つける必要がある。


  • 隣り合っているかを判断するためにインデックスの中に順序の情報を入れる


  • キーワードが連続しているかどうかをチェックをする検索のフレーズ検索が必須。

    例)

    下記のA,Bの文書から「咲いた」を2gramで検索する場合

    「咲い」「いた」でキーワード区切る

    A.もB.もキーは存在するがB.は位置が隣り合っていないので目的の文書では無い。

    文書A.花が咲いた

    文書B.花が咲いていた、いた。


キー
文書と位置

花が
A[1],B[1]

が咲
A[2],B[2]

咲い
A[3],B[3]

いて
B[4]

いた
A[4],B[5,6]

※実際にはサイズを抑えるために格納方法を工夫している