はじめに
この記事は株式会社うるる（ULURU）Advent Calendar 2024 の17日目の記事です。
私はこれまで全文検索エンジン（SolrやOpenSearch）を利用したシステムにいくつか携わってきました。全文検索エンジンで使用するngramには、これまでbi-gram(バイグラム)を使用してきましたが、昨年tri-gram(トリグラム)を使用しているシステムに携わり、それが有効なケースもあるとわかったのでそれを記事にしたいと思います。
全文検索を実装するための基本的な方法
全文検索エンジンで使用するインデックスの作成方法は形態素解析とngramの2種類あります。そして検索時には両方を併用するという方法を採用していることが多いかと思います。
形態素解析やngramとは何か、また両方を併用するにはどうすればよいのかという点については、「Elasticsearchで日本語の全文検索の機能を実装する」の記事がとてもわかり易いので参考にしてください。
ngramの設定の選択肢
ngramはN文字ずつに文章を区切る方法で、このN文字を具体的に何文字にするのかを決める必要があります。
bi-gram
一般的には2文字とするbi-gramが採用されます。ただしその場合、検索語が1文字のものは検索できないという欠点があります。この欠点を補う方法として、1文字づつで作成するuni-gram作成しておき、検索語が1文字のときはuni-gramを、2文字以上のときはbi-gramを使用するという方法があります。
形態素解析も併用している場合は、1文字の検索語は形態素解析にまかせてngramでヒットしなくてもよいとする方法がとれます。私の携わったシステムでは主にこの方法が採用されていました。
bi-gramを使用する際の注意点としては、検索する際に語順の一致も条件とするフレーズ検索にする必要がある点です。「バイク」という検索語の場合、「バイ」と「イク」で検索するので、フレーズ検索を使用しないと、バイクという単語がなくても「バイキング」と「イクラ」を含む文章でもヒットしてしまうためです。
tri-gram
tri-gramを利用する場合の実現方法は、uni-gram、bi-gram、tri-gramを作成しておき、検索語に合わせて使用するインデックスを切り替えるという方法があります。
1文字ならuni-gram、2文字ならbi-gram、3文字以上ならtri-gramを使用します。この場合、語順の一致も条件とするフレーズ検索を利用する必要は、ほとんどのシステムではないと思います。検索語が「バイキング」の場合、「バイキ」「イキン」「キング」の3語が、「バイキング」を含まない文章でたまたまヒットすることはほとんどないためです。
検索性能
2000万件ぐらいのデータで実際に計測してみた結果は以下のとおりです。
参考までにuni-gramの計測結果ものせています。
検索ワードが2文字（水道）
| 方法 | 性能 |
|---|---|
| uni-gram + フレーズクエリ | 10ms |
| bi-gram + フレーズクエリ | 2ms |
| tri-gram | 2ms |
検索ワードが4文字（水道工事）
| 方法 | 性能 |
|---|---|
| uni-gram + フレーズクエリ | 27ms |
| bi-gram + フレーズクエリ | 12ms |
| tri-gram | 3ms |
検索ワードが2文字で2つ（水道、工事）
| 方法 | 性能 |
|---|---|
| uni-gram + フレーズクエリ | 23ms |
| bi-gram + フレーズクエリ | 8ms |
| tri-gram | 8ms |
2文字以下の検索では差は出ませんが、3文字以上（3文字での比較結果が残っておらず上記の結果は4文字ですが）の検索ではtri-gramの性能がよいようです。
もう一つの選択肢？
OpenSearchのngramの設定では、複数のインデックスを同時に作成する設定が可能です。「min_gram: 1、max_gram: 3」とするだけで、uni-gram、bi-gram、tri-gramが全て作成されて検索時にはそれらを併用して検索する機能になります。これはよい方法のように思えるのですが、実際には3つのインデックスを同時に検索する挙動になるので性能的には良くありませんでした。「bi-gram+フレーズクエリ」と比較した場合の結果は以下のとおりです。
検索ワードが3文字（バイク）
| 方法 | 性能 |
|---|---|
| bi-gram + フレーズクエリ | 8ms |
| ngram(1〜3)複合 | 9ms |
検索ワードが7文字（コールセンター）
| 方法 | 性能 |
|---|---|
| bi-gram + フレーズクエリ | 11ms |
| ngram(1〜3)複合 | 19ms |
どの方法がよいか？
性能的にtri-gramはよいのですが、以下のデメリットがあります。
- bi-gramだけに比べて、インデックスのサイズが大きくなる
- 検索語により使用するインデックスを切り替えるのは実装が煩雑になる
- OpenSearchのフィルターで、文字数が変わるような変換をしているときには対応ができない
- 実際、tri-gramを採用しているシステムではこのフィルターの変換を行っているため、特定の検索語では不正確な結果となる課題がありました
以上のことから基本的にはbi-gramを採用するのが無難で、性能に特化させたいケースだけtri-gramの採用を検討するのがよいと考えています。はじめに紹介した「Elasticsearchで日本語の全文検索の機能を実装する」の記事では以下の記述がありますが、その通りだなと思いました。
日本語では、一般的にはバイグラムが使われます。ただし、バイグラムの場合、細かく分割されすぎることがあり、パフォーマンスとして良くない場合もあります。パフォーマンス重視の場合、特定のフィールドに対し、tri-gram（トリグラム）を利用するといった使い分けも考えられます。
おわりに
明日は、眞島さん(@shin_majima)の記事です！
ご覧いただきありがとうございまいた！