はじめてのQiitaです。
先月のことになりますが、Groongaで学ぶ全文検索 2015-11-20に参加しましたのでそのことを書きます。
この回のテーマは 「日本語検索のしくみ」でした。
そもそもGroongaの全文検索の仕組みはどうなってるのか？
データがDBに入っていてそれを検索したい！という時、大量の検索対象に対して検索するのは大変なので、インデックスをつくっておいて、それを利用して検索します。 インデックスに登録されているものだけ検索可能です。ここ重要！
インデックス
インデックスはキーとバリューで構成されています。
- キー : 検索キーワード
- バリュー : データを特定できる情報(IDリストとイメージすればOK)
例えばユーザーが「Groonga」で検索したら、インデックスのキーに対して「Groonga」を探しに行き、ヒットしたらバリューを返す、という仕組みです。「Groongaで学ぶ全文検索」という文字を含むデータを探すために「Groonga」で検索したけど、インデックスキーには「Groongaで学ぶ全文検索」と登録されていた場合、検索したいデータを取得することはできません。つまり、検索の精度を上げるために重要なのは、ユーザーが検索するキーワードをどれだけインデックスに登録できるかということになります。
では、Groongaではどういう風にインデックスを登録しているのかというと・・・
- 英語の場合
例えば「this is a pen」という文をインデックスに登録する場合、インデックスのキーは以下のようになります。（4レコードになる）
this
is
a
pen
英語の文章は半角スペースで区切られるので単語の区切りが明確です。また、検索するときも同じことが言えます。（「pen」を検索したいときに「pe」など中途半端な文字で検索しないはず。）そのためインデックスのキーには単語を登録すればOKだし、単語を登録することが簡単！というわけで上記のようなキーになっています。
- 日本語の場合
日本語の場合は2種類の方法が用意されています。
1.単語をキーワードにする(形態素解析)
2.なんでもキーワードにする(N-gram)
1.単語をキーワードにする(形態素解析)
１つ目は単語をキーワドにする形態素解析と呼ばれる方法です。例えば「花が咲いた」をインデックスに登録する場合、キーは以下のようになります。（3レコードになる。「咲いた」をこの例では1単語とする。）
花
が
咲いた
単語をキーワードにするってのは英語の場合と一緒です。
これの難しいとこは日本語は単語の区切りが判断しにくい(>_<)ってところです。日本語は句読点がなくても意味が通じるし、「すもももももももものうち」という文章があった場合、「すもも」で区切るのか「す」で区切るのか・・・単語の区切りが不明瞭なのです。そこでその問題に対応できる2つ目の方法もあります。
2.なんでもキーワードにする(N-gram)
２つ目の方法は、単語の区切りは考えず、ある文字数で区切ってキーにしてしまうというものです。これは「N-gram」と呼ばれる方法で、2文字で区切る場合は「2gram(バイグラム)」、3文字で区切る場合は「3gram(トリグラム)」と呼ばれます。
先ほどの「花が咲いた」を2gramでインデックスに登録すると以下のようなキーになります。（4レコードになる。）
花が
が咲
咲い
いた
これだと１つ目の方法よりちょっと検索処理が複雑になります。
こんな感じ。
検索キーワードに「咲いた」が指定された場合の検索処理
1.検索キーワード分割する
咲い
いた
2.検索キーワードを全て含むものを検索する
インデックスのキーで「咲い」にヒットするものと「いた」にヒットするものを探す。
例えば
キー：バリュー（[データを示すID,...]）
咲い：[1,2,3]
いた：[1,4]
これだと1がヒットする。
3.2でヒットしたものを対象に、キーワードが隣り合ってるかを検索(フレーズ検索)する
「咲い」と「いた」が含まれていても「咲いていた」のように隣り合っていなければ
それは検索結果として相応しくないので、「咲い」と「いた」が隣り合っているかを検索します。
これをフレーズ検索と言います。このフレーズ検索も2つの方法が準備されています。
▼フレーズ検索（2種類ある）
A.インデックスのバリューに、キーの文字がデータ中の何番目の文字かをいれといて、検索時にとなりあっているかをみる方法。
例えばこんなイメージ。
キー：バリュー（[データを示すID[キーの文字がデータ中の何文字目か],...]）
咲い：[1[1],2[1],3[6]]
いた：[1[2],4[4]]
この場合、文書1の「咲い」と「いた」は隣り合っているので「咲いた」の検索結果として適切なものと判断される。
B.インデックスをみに行く時点では怪しいものをピックアップしておくまで（上記の2まで）。
その後怪しいものを対象に分割前の検索キーワードで検索する。
キー：バリュー（[データを示すID,...]）
咲い：[1,2,3]
いた：[1,4]
この例でいうと、1のデータに対して「咲いた」で検索をかけるということになります。
このN-gramの嬉しいことは形態素解析に比べて 検索漏れがないということ。
難しいことは形態素解析より検索処理がちょっと大変ということです。
まとめ
- 先輩に
はめられて誘われて急に参加した勉強会でした。私、Groonga初心者でかなり緊張していたのですが、初心者にもわかるようにすっごく丁寧に説明してくださいました！質問もしやすくて優しさに感激しました！ - 日頃仕組みもよくわからず利用しているものって多いのですが、仕組みを知るって面白いなーって感じました。もっと知りたい！という気持ちになりました。
- こういった勉強会参加するの初めてだったのですが、行ってみるもんだなと思いました。先輩にも須藤さんにも参加者の皆さんにも感謝です。 とにかく皆さんにありがとうございました！という気持ちです。今後も参加させていただきたいなと思っています。