株式会社クリアコード > ククログ

ククログ


groongaの全文検索処理の流れ

groongaにデータを登録して、インデックスを更新すると全文検索をすることができます。ここでは、groongaが内部でどのような処理をして全文検索をしているかを説明します。

前提

まず、以下のように「Yes good」と「Hey good」という文書が登録されているとします。

登録されている文書と転置インデックス

このとき、「Yes good」で検索したらどうなるかを説明します。

トークナイズ

まず、入力の「Yes good」をトークナイズします。このとき使用するトークナイザーは使用する転置インデックスと同じものです。転置インデックスが使用するトークナイザーは語彙表(lexcion)を見ればわかります。今回はTokenDelimitトークナイザーですね。

TokenDlimitトークナイザー

TokenDlimitは空白区切りでトークナイズするトークナイザーなので「Yes good」は「Yes」と「good」にトークナイズされます。

転置インデックスの参照

トークナイズしたら、それぞれの単語について転置インデックスを参照します。転置インデックスの参照は2段階あります。

まず、単語をキーとしてlexiconを検索し、単語ID(= lexiconのレコードID)を取得します。「Yes」の場合は単語IDは「1」です。

「Yes」の単語IDを検索

次に、単語IDを使って単語に対応する転置インデックスの値を取得します。単語ID「1」に対応する転置インデックスの値は文書ID「1」です。つまり、「Yes」という単語を含む文書は文書IDが「1」の文書だということです。

単語ID「1」の転置インデックスの値を取得

続いて、単語「good」の転置インデックスを参照します。「Yes」のときと同様にまずはlexiconを検索します。「good」の単語IDは「2」です。

「good」の単語IDを検索

「Yes」の時と同様に、単語IDを使って単語に対応する転置インデックスの値を取得します。単語ID「2」に対応する転置インデックスの値は文書ID「1」と「2」です。つまり、「good」という単語を含む文書は文書IDが「1」の文書と「2」の文書だということです。

単語ID「2」の転置インデックスの値を取得

元の入力は「Yes good」だったので、「Yes」の転置インデックスにも「good」の転置インデックスにも両方含まれている文書ID「1」だけがヒットした文書になります*1。文書ID「2」は「good」の転置インデックスに含まれていますが、「Yes」の転置インデックスには文書ID「2」が含まれていないので「Yes good」ではヒットしません。

ヒットした文書

部分文字列での全文検索

このケースでは「ood」など部分文字列ではヒットしません。どうしてヒットしないかを説明します。

まず、「ood」をトークナイズすると空白がないので「ood」という1単語にトークナイズされます。次に、「ood」という単語でlexiconを検索するとそのような単語は登録されていないので、単語IDを取得できません。そのため、この時点でヒットする文書がないと判断し、転置インデックスは参照しません。

それでは、部分文字列でも検索できるようにするにはどうすればよいかというと、トークナイザーを変更します。どうしてトークナイザーがでてくるかというのは、先に説明した転置インデックスを参照する処理の流れを考えるとわかります。

転置インデックスを参照する処理は以下の2つの処理にわけられます。

  1. lexiconから単語IDを取得する。
  2. 単語IDを使って転置インデックスの値を取得する。

「ood」で検索する例で確認した通り、「lexiconから単語IDを取得する」ことができないために部分文字列で検索できていません。よって、部分文字列でも「lexiconから単語IDを取得する」ことができるようにすれば、部分文字列でも検索できるようになります。

ここでトークナイザーの出番です。lexiconに登録される単語は文書をトークナイズして得られた単語です。そのため、トークナイズするときに部分文字列も単語としてトークナイズすればlexiconに単語の部分文字列も登録されます。すると、検索時に部分文字列でlexiconを参照しても単語IDを取得することができます。

groongaにはいくつか組み込みのトークナイザーがあります*2。部分文字列でも検索できるようにするには空白区切りで単語にトークナイズするTokenDelimitではなく、2文字単位で単語にトークナイズするTokenBigramを使います*3

トークナイザーとしてTokenBigramを使うと「Yes good」は「Ye」・「es」・「s 」・「 g」・「go」・「oo」・「od」・「d」にトークナイズされます。

TokenBigramを利用

このとき、「ood」で検索したらどうなるかを説明します。

まず、転置インデックスが使っているのと同じトークナイザーTokenBigramでトークナイズします。「ood」は「oo」・「od」にトークナイズされます。lexiconを検索すると「oo」の単語IDは6で「od」の単語IDは7です。どちらも登録されている単語なのでヒットする文書がありそうです。

「oo」と「od」の単語IDを検索

次に、単語ID「6」と単語ID「7」の転置インデックスを参照します。「oo」も「od」もどちらも文書ID「1」に含まれていることがわかります。よって、文書ID「1」の文書は「ood」という文字列を含んでいることがわかります*4

単語ID「1」と「2」の転置インデックスの値を取得

検索時はこのように動作するため、トークナイザーによって検索結果が異なります。

トークナイザーの使い分け

では、トークナイザーはどのような基準で選ぶとよいのでしょうか。一見すると、部分文字列でも検索できるトークナイザーの方がよさそうに見えます。しかし、必ずしもそうとは限りません。部分文字列でもヒットするということは、望んでいない文書もヒットする可能性が増えるということです。

例えば、「cat」で「category」もヒットするようになります。「cat」で検索しているときに「category」に関する文書もヒットすると、それはノイズとなります。ノイズが多いと目的の文書を見つけづらくなってしまうため、使い勝手が悪くなります*5。よって、部分検索もできるようにしたほうがよいかどうかはアプリケーションに依る、ということになります。

なお、groongaは1つの全文検索で複数の転置インデックスを使うことにより、「完全一致した文書はスコアを高めにつけて、部分一致した文書はスコアを低めにつける」ということもできます。これは、転置インデックス毎*6に異なるトークナイザーを利用できるためです。

タグ検索

転置インデックスを用いると全文検索と同じ方法でタグ検索も実現できます。

実は、上記のTokenDelimitを使った全文検索の説明はタグ検索の動作そのものになっています。「Yes」や「good」をタグだと考えてもう一度読みなおしてみてください。

まとめ

groongaでの(簡略化した)全文検索処理の流れを説明しました。思ったように検索ができない場合は、全文検索の処理の流れを考えながら挙動を確認していくと、どこが問題かをみつけやすくなるはずです。

*1 実際は「両方含まれている」だけではなく「入力と同じ順序で両方含まれている」文書だけを選びます。そのため、転置インデックスには単語が文書中のどこで現れたのかを記録しておく必要があります。groongaでは位置情報も含めるかどうかはカラム定義時のオプションで指定することが可能です。なお、位置情報も含んだ転置インデックスを完全転置インデックスと呼びます。

*2 ここでgroongaのドキュメントにトークナイザー一覧ページを作ってリンクを貼れると嬉しい。

*3 KEY_NORMALIZEを指定すると必ずしも2文字単位ではなくなるので注意すること、ということはここでは省略する。

*4 実際は「両方含まれている」だけではなく「入力と同じ順序で両方含まれている」ことも確認します。つまり、「oo」の次に「od」が出現していることも確認します。

*5 キーワードは「適合率」と「再現率」。

*6 実際は転置インデックス毎ではなくてlexicon毎。

タグ: Groonga

この記事の続き

2011-10-20

«前の記事: Debian GNU/LinuxでWindows用バイナリをビルドする方法 最新記事 次の記事: どうして開発者がドキュメントを書くべきか»
タグ:
年・日ごとに見る
2008|05|06|07|08|09|10|11|12|
2009|01|02|03|04|05|06|07|08|09|10|11|12|
2010|01|02|03|04|05|06|07|08|09|10|11|12|
2011|01|02|03|04|05|06|07|08|09|10|11|12|
2012|01|02|03|04|05|06|07|08|09|10|11|12|
2013|01|02|03|04|05|06|07|08|09|10|11|12|
2014|01|02|03|04|05|06|07|08|09|10|11|12|
2015|01|02|03|04|05|06|07|08|09|10|11|12|
2016|01|02|03|04|05|06|07|08|09|10|11|12|
2017|01|02|03|04|05|06|07|08|09|10|11|12|
2018|01|02|03|04|05|06|07|08|09|10|11|12|
2019|01|02|03|