Elasticsearchに限らずですが、検索エンジン案件ぽい話の際に、SQL/RDB界隈の部分一致検索のメタファーでN-Gramでの検索を語ることになりつつも、
結果、「部分一致」の先入観からかえってわかりにくくなる面もあって悩ましいということもなくはない...ので、このようなケースの
語り部記事を投稿いたします。
mapping
前提とするmapping設定はこちらです。
mappingおよび以下の検索確認は、Elasticsearch 6.8で行なっていますが、7系でも稼働するようなものになっていると思います。
PUT xgram
{
"settings": {
"analysis": {
"tokenizer": {
"2g": {
"type": "ngram",
"min_gram":2,
"max_gram":2,
"token_chars": [
"letter",
"digit"
]
},
"3g": {
"type": "ngram",
"min_gram":3,
"max_gram":3,
"token_chars": [
"letter",
"digit"
]
},
"23g": {
"type": "ngram",
"min_gram":2,
"max_gram":3,
"token_chars": [
"letter",
"digit"
]
}
},
"analyzer": {
"2g": {
"type": "custom",
"tokenizer": "2g",
"filter":["ja_stop"]
},
"3g": {
"type": "custom",
"tokenizer": "3g",
"filter":["ja_stop"]
},
"23g":{
"type": "custom",
"tokenizer": "23g",
"filter":["ja_stop"]
}
}
}
},
"mappings": {
"_doc": {
"dynamic_templates": [
{
"g": {
"match_mapping_type": "string",
"mapping": {
"fields":{
"2g":{
"type":"text",
"analyzer":"2g"
},
"3g":{
"type":"text",
"analyzer":"3g"
},
"23g":{
"type":"text",
"analyzer":"23g"
}
}
}
}
}
]
}
}
}
※雑に解説すると、2-Gram、3-Gram、2,3-Gramです。whitespaceで強制トークン分割を期待する設定(token_charsのところです。whitespaceという単語は出てきませんが、消去法です。)です。
サンプルデータ(1件だけ!)
ここにひとまず、ベンチマーク(というには件数が少ないですが)として次の1件のドキュメントをインポートします。
POST xgram/_doc
{ "t":"東京は昨日は晴れで今日は雨だが、埼玉は昨日も雨だ"}
以下では、このドキュメントが、それぞれの検索語・match系検索方法で当たるのか当たらないのかの事例をなぞって温度感を探ってみたいと思います。
(それとなく結論や主張は匂わせていますが、厳密な議論は筆者のパワーの問題もあって難しいので、雰囲気説明です。ご了承ください。)
なお、このドキュメント-フィールドのanalyze例は次のとおり。適宜ご参照ください。
2-Gram
GET xgram/_analyze
{ "analyzer": "2g",
"text":"東京は昨日は晴れで今日は雨だが、埼玉は昨日も雨だ"
}
{
"tokens" : [
{
"token" : "東京",
"start_offset" : 0,
"end_offset" : 2,
"type" : "word",
"position" : 0
},
{
"token" : "京は",
"start_offset" : 1,
"end_offset" : 3,
"type" : "word",
"position" : 1
},
{
"token" : "は昨",
"start_offset" : 2,
"end_offset" : 4,
"type" : "word",
"position" : 2
},
{
"token" : "昨日",
"start_offset" : 3,
"end_offset" : 5,
"type" : "word",
"position" : 3
},
{
"token" : "日は",
"start_offset" : 4,
"end_offset" : 6,
"type" : "word",
"position" : 4
},
{
"token" : "は晴",
"start_offset" : 5,
"end_offset" : 7,
"type" : "word",
"position" : 5
},
{
"token" : "晴れ",
"start_offset" : 6,
"end_offset" : 8,
"type" : "word",
"position" : 6
},
{
"token" : "れで",
"start_offset" : 7,
"end_offset" : 9,
"type" : "word",
"position" : 7
},
{
"token" : "で今",
"start_offset" : 8,
"end_offset" : 10,
"type" : "word",
"position" : 8
},
{
"token" : "今日",
"start_offset" : 9,
"end_offset" : 11,
"type" : "word",
"position" : 9
},
{
"token" : "日は",
"start_offset" : 10,
"end_offset" : 12,
"type" : "word",
"position" : 10
},
{
"token" : "は雨",
"start_offset" : 11,
"end_offset" : 13,
"type" : "word",
"position" : 11
},
{
"token" : "雨だ",
"start_offset" : 12,
"end_offset" : 14,
"type" : "word",
"position" : 12
},
{
"token" : "だが",
"start_offset" : 13,
"end_offset" : 15,
"type" : "word",
"position" : 13
},
{
"token" : "埼玉",
"start_offset" : 16,
"end_offset" : 18,
"type" : "word",
"position" : 14
},
{
"token" : "玉は",
"start_offset" : 17,
"end_offset" : 19,
"type" : "word",
"position" : 15
},
{
"token" : "は昨",
"start_offset" : 18,
"end_offset" : 20,
"type" : "word",
"position" : 16
},
{
"token" : "昨日",
"start_offset" : 19,
"end_offset" : 21,
"type" : "word",
"position" : 17
},
{
"token" : "日も",
"start_offset" : 20,
"end_offset" : 22,
"type" : "word",
"position" : 18
},
{
"token" : "も雨",
"start_offset" : 21,
"end_offset" : 23,
"type" : "word",
"position" : 19
},
{
"token" : "雨だ",
"start_offset" : 22,
"end_offset" : 24,
"type" : "word",
"position" : 20
}
]
}
3-Gram
GET xgram/_analyze
{ "analyzer": "3g",
"text":"東京は昨日は晴れで今日は雨だが、埼玉は昨日も雨だ"
}
{
"tokens" : [
{
"token" : "東京は",
"start_offset" : 0,
"end_offset" : 3,
"type" : "word",
"position" : 0
},
{
"token" : "京は昨",
"start_offset" : 1,
"end_offset" : 4,
"type" : "word",
"position" : 1
},
{
"token" : "は昨日",
"start_offset" : 2,
"end_offset" : 5,
"type" : "word",
"position" : 2
},
{
"token" : "昨日は",
"start_offset" : 3,
"end_offset" : 6,
"type" : "word",
"position" : 3
},
{
"token" : "日は晴",
"start_offset" : 4,
"end_offset" : 7,
"type" : "word",
"position" : 4
},
{
"token" : "は晴れ",
"start_offset" : 5,
"end_offset" : 8,
"type" : "word",
"position" : 5
},
{
"token" : "晴れで",
"start_offset" : 6,
"end_offset" : 9,
"type" : "word",
"position" : 6
},
{
"token" : "れで今",
"start_offset" : 7,
"end_offset" : 10,
"type" : "word",
"position" : 7
},
{
"token" : "で今日",
"start_offset" : 8,
"end_offset" : 11,
"type" : "word",
"position" : 8
},
{
"token" : "今日は",
"start_offset" : 9,
"end_offset" : 12,
"type" : "word",
"position" : 9
},
{
"token" : "日は雨",
"start_offset" : 10,
"end_offset" : 13,
"type" : "word",
"position" : 10
},
{
"token" : "は雨だ",
"start_offset" : 11,
"end_offset" : 14,
"type" : "word",
"position" : 11
},
{
"token" : "雨だが",
"start_offset" : 12,
"end_offset" : 15,
"type" : "word",
"position" : 12
},
{
"token" : "埼玉は",
"start_offset" : 16,
"end_offset" : 19,
"type" : "word",
"position" : 13
},
{
"token" : "玉は昨",
"start_offset" : 17,
"end_offset" : 20,
"type" : "word",
"position" : 14
},
{
"token" : "は昨日",
"start_offset" : 18,
"end_offset" : 21,
"type" : "word",
"position" : 15
},
{
"token" : "昨日も",
"start_offset" : 19,
"end_offset" : 22,
"type" : "word",
"position" : 16
},
{
"token" : "日も雨",
"start_offset" : 20,
"end_offset" : 23,
"type" : "word",
"position" : 17
},
{
"token" : "も雨だ",
"start_offset" : 21,
"end_offset" : 24,
"type" : "word",
"position" : 18
}
]
}
2,3 Gram
GET xgram/_analyze
{ "analyzer": "23g",
"text":"東京は昨日は晴れで今日は雨だが、埼玉は昨日も雨だ"
}
{
"tokens" : [
{
"token" : "東京",
"start_offset" : 0,
"end_offset" : 2,
"type" : "word",
"position" : 0
},
{
"token" : "東京は",
"start_offset" : 0,
"end_offset" : 3,
"type" : "word",
"position" : 1
},
{
"token" : "京は",
"start_offset" : 1,
"end_offset" : 3,
"type" : "word",
"position" : 2
},
{
"token" : "京は昨",
"start_offset" : 1,
"end_offset" : 4,
"type" : "word",
"position" : 3
},
{
"token" : "は昨",
"start_offset" : 2,
"end_offset" : 4,
"type" : "word",
"position" : 4
},
{
"token" : "は昨日",
"start_offset" : 2,
"end_offset" : 5,
"type" : "word",
"position" : 5
},
{
"token" : "昨日",
"start_offset" : 3,
"end_offset" : 5,
"type" : "word",
"position" : 6
},
{
"token" : "昨日は",
"start_offset" : 3,
"end_offset" : 6,
"type" : "word",
"position" : 7
},
{
"token" : "日は",
"start_offset" : 4,
"end_offset" : 6,
"type" : "word",
"position" : 8
},
{
"token" : "日は晴",
"start_offset" : 4,
"end_offset" : 7,
"type" : "word",
"position" : 9
},
{
"token" : "は晴",
"start_offset" : 5,
"end_offset" : 7,
"type" : "word",
"position" : 10
},
{
"token" : "は晴れ",
"start_offset" : 5,
"end_offset" : 8,
"type" : "word",
"position" : 11
},
{
"token" : "晴れ",
"start_offset" : 6,
"end_offset" : 8,
"type" : "word",
"position" : 12
},
{
"token" : "晴れで",
"start_offset" : 6,
"end_offset" : 9,
"type" : "word",
"position" : 13
},
{
"token" : "れで",
"start_offset" : 7,
"end_offset" : 9,
"type" : "word",
"position" : 14
},
{
"token" : "れで今",
"start_offset" : 7,
"end_offset" : 10,
"type" : "word",
"position" : 15
},
{
"token" : "で今",
"start_offset" : 8,
"end_offset" : 10,
"type" : "word",
"position" : 16
},
{
"token" : "で今日",
"start_offset" : 8,
"end_offset" : 11,
"type" : "word",
"position" : 17
},
{
"token" : "今日",
"start_offset" : 9,
"end_offset" : 11,
"type" : "word",
"position" : 18
},
{
"token" : "今日は",
"start_offset" : 9,
"end_offset" : 12,
"type" : "word",
"position" : 19
},
{
"token" : "日は",
"start_offset" : 10,
"end_offset" : 12,
"type" : "word",
"position" : 20
},
{
"token" : "日は雨",
"start_offset" : 10,
"end_offset" : 13,
"type" : "word",
"position" : 21
},
{
"token" : "は雨",
"start_offset" : 11,
"end_offset" : 13,
"type" : "word",
"position" : 22
},
{
"token" : "は雨だ",
"start_offset" : 11,
"end_offset" : 14,
"type" : "word",
"position" : 23
},
{
"token" : "雨だ",
"start_offset" : 12,
"end_offset" : 14,
"type" : "word",
"position" : 24
},
{
"token" : "雨だが",
"start_offset" : 12,
"end_offset" : 15,
"type" : "word",
"position" : 25
},
{
"token" : "だが",
"start_offset" : 13,
"end_offset" : 15,
"type" : "word",
"position" : 26
},
{
"token" : "埼玉",
"start_offset" : 16,
"end_offset" : 18,
"type" : "word",
"position" : 27
},
{
"token" : "埼玉は",
"start_offset" : 16,
"end_offset" : 19,
"type" : "word",
"position" : 28
},
{
"token" : "玉は",
"start_offset" : 17,
"end_offset" : 19,
"type" : "word",
"position" : 29
},
{
"token" : "玉は昨",
"start_offset" : 17,
"end_offset" : 20,
"type" : "word",
"position" : 30
},
{
"token" : "は昨",
"start_offset" : 18,
"end_offset" : 20,
"type" : "word",
"position" : 31
},
{
"token" : "は昨日",
"start_offset" : 18,
"end_offset" : 21,
"type" : "word",
"position" : 32
},
{
"token" : "昨日",
"start_offset" : 19,
"end_offset" : 21,
"type" : "word",
"position" : 33
},
{
"token" : "昨日も",
"start_offset" : 19,
"end_offset" : 22,
"type" : "word",
"position" : 34
},
{
"token" : "日も",
"start_offset" : 20,
"end_offset" : 22,
"type" : "word",
"position" : 35
},
{
"token" : "日も雨",
"start_offset" : 20,
"end_offset" : 23,
"type" : "word",
"position" : 36
},
{
"token" : "も雨",
"start_offset" : 21,
"end_offset" : 23,
"type" : "word",
"position" : 37
},
{
"token" : "も雨だ",
"start_offset" : 21,
"end_offset" : 24,
"type" : "word",
"position" : 38
},
{
"token" : "雨だ",
"start_offset" : 22,
"end_offset" : 24,
"type" : "word",
"position" : 39
}
]
}
では、当たり具合、当たらな具合を見ていきます。
(1) これはヒットしてしかるべきでヒットするよねの例
対象ドキュメント(再掲): "東京は昨日は晴れで今日は雨だが、埼玉は昨日も雨だ"
■ex.①A
GET xgram/_search
{"query": {
"match": {
"t.2g": { "query": "東京",
"operator":"and",
"analyzer":"2g"
}}}}
↓
ヒットする
■ex.①B
GET xgram/_search
{"query": {
"match": {
"t.2g": { "query": "埼玉",
"operator":"and",
"analyzer":"2g"
}}}}
↓
ヒットする
(2) こいつはどうでしょう(検索語(文)そのままはありませんが...)の例
対象ドキュメント(再掲): "東京は昨日は晴れで今日は雨だが、埼玉は昨日も雨だ"
よく見るとそのままのセンテンスではないのにヒットする例です。
■ex.②A
GET xgram/_search
{"query": {
"match": {
"t.2g": { "query": "東京は昨日も雨だ",
"operator":"and",
"analyzer":"2g"
}}}}
↓
ヒットする
■ex.②B
GET xgram/_search
{"query": {
"match": {
"t.2g": { "query": "埼玉は昨日は晴れ",
"operator":"and",
"analyzer":"2g"
}}}}
↓
②Aはヒットしたくせに、こちらはヒットしない
これらは、当たって欲しくない派閥から見ると嫌な例(ヒットしてしまう)ですね。
ただし、これは上記のようなそれっぽいセンテンスに対して、本当にそんな検索ニーズあるんかなという例で検索したからこその事例というところもあります。
長文のフリーテキストフィールドを検索するならまだしも、お店の名前や小説・映画のタイトルといったフィールドに対して、少し気の聞いた部分一致検索をしたいというシーンでは、
この長さの検索語であれば、「こんなの部分一致じゃねーっ!」というところまで及ばない(実害はない)ケースも多々あるように思われます。
(3) ちょっと寄り道しますの例(Gramの刻み違い)
対象ドキュメント(再掲): "東京は昨日は晴れで今日は雨だが、埼玉は昨日も雨だ"
2Gramの検索アナライズと3Gramのインデックスアナライズをぶつけてみます。
文字面だけ見るとヒットしそうですが、噛み合わせが悪くヒットしません。
■ex.③A
GET xgram/_search
{"query": {
"match": {
"t.3g": { "query": "埼玉は",
"operator":"and",
"analyzer":"2g"
}}}}
↓
ヒットしません。
■ex.③B
今度は反対。
GET xgram/_search
{"query": {
"match": {
"t.2g": { "query": "埼玉",
"operator":"and",
"analyzer":"3g"
}}}}
↓
ヒットしません。
深く考える必要はありませんが、この仕組みの本質のひとつでもあるので頭の片隅においておきましょう。
(4) 本題に戻ってきて、アナライザーを同じものにする、もしくは 小刻みな方で併用アナライザー(筆者の造語)のインデックスデータにぶつける
対象ドキュメント(再掲): "東京は昨日は晴れで今日は雨だが、埼玉は昨日も雨だ"
■ex.④A
GET xgram/_search
{"query": {
"match": {
"t.23g": { "query": "埼玉は",
"operator":"and",
"analyzer":"23g"
}}}}
↓
(いくつか前の方の例でヒットしなかった例と同じ検索語ですが、こちらは)ヒットします。
■ex.④B
GET xgram/_search
{"query": {
"match": {
"t.23g": { "query": "埼玉",
"operator":"and",
"analyzer":"23g"
}}}}
↓
ヒットします。
■ex.④C
GET xgram/_search
{"query": {
"match": {
"t.23g": { "query": "埼玉は",
"operator":"and",
"analyzer":"2g"
}}}}
↓
ヒットします。
■ex.④D
GET xgram/_search
{"query": {
"match": {
"t.23g": { "query": "埼玉",
"operator":"and",
"analyzer":"2g"
}}}}
↓
ヒットします。
なんとなく、肌感覚を掴めてきたでしょうか。
(5) 当たらない方が正統派と思われますが、ひょっとしたらヒットするかも...いやこの例は実際はヒットしない例(間違い探し的にヒットする例)
対象ドキュメント(再掲): "東京は昨日は晴れで今日は雨だが、埼玉は昨日も雨だ"
■ex.⑤A
GET xgram/_search
{"query": {
"match": {
"t.23g": { "query": "埼玉は今日も雨",
"operator":"and",
"analyzer":"23g"
}}}}
↓
懸念がありましたが、無事(?)ヒットしませんね。
(余談ですが、多分事実としては正しいのですが...)
■ex.⑤B
では、さすがに、これは、当たって欲しいわけではないがあたっちゃうんじゃないの?の例
GET xgram/_search
{"query": {
"match": {
"t.23g": { "query": "東京も昨日も雨だ",
"operator":"and",
"analyzer":"23g"
}}}}
↓
ヒットせず。
タネ明かし:「京も昨」がドキュメント中に存在しないので、この例はヒットせず。
■ex.⑤C
GET xgram/_search
{"query": {
"match": {
"t.23g": { "query": "東京は昨日も雨だ",
"operator":"and",
"analyzer":"23g"
}}}}
↓
ついに敗北? ヒットしてしまいました。
流石に、今度はヒットしてしまいますね。
(東京の昨日の天気には触れていないにも関わらず...「東京は」「は昨日」「昨日も」「も雨だ」あたりが存在するため。)
(6) 定番ですがphrase型の検索にシフトチェンジします(部分一致に近づけるには...の例)
前項あたりの例(特に最後の例)を見せると、やはりこの類の挙動(実際はからくりはありますが)を不安定に感じて嫌がる人も多いですかね。
私などは、最後の例で善戦したところまでで十分ではと思う要件もなくはないという感想ですが...
いや許せん!
そんなあなたにオススメなのが、phrase型の検索です。 phrase型の検索の場合、検索語・検索センテンスの検索対象ドキュメントでの登場順と一致するかを考慮してくれます。
対象ドキュメント(再掲): "東京は昨日は晴れで今日は雨だが、埼玉は昨日も雨だ"
■ex.⑥A
GET xgram/_search
{"query": {
"match_phrase": {
"t.23g": { "query": "東京は昨日も雨だ",
"analyzer":"23g",
"slop":0
}}}}
↓
ヒットしなくなりましたね。
(当たって欲しくないし、実際に)当たらなくなった。
ここまで随分前置きが長くなったが、match_phraseのslop=0だとクラシカルな「部分一致」になると言えるでしょう。
※ヒットしない方の例を出しましたが、もちろん、「東京は昨日は晴れ」などであればヒットします。
ちなみに、slopを大きくしていくと...
■ex.⑥B
GET xgram/_search
{"query": {
"match_phrase": {
"t.23g": { "query": "東京は昨日も雨だ",
"analyzer":"23g",
"slop":30
}}}}
↓
ヒットします。
再び当たるようになった! (が、やっぱり流石に気持ち悪いか...)
(7) スペース区切りのキーワード複数(はどんな部分一致を期待?)
ここまではセンテンス風の検索語でしたが、スペース区切りのキーワード複数の検索ってWeb検索で見慣れてみんなやるよねの話です。
具体的には、"東京 昨日 雨だ"などと検索された場合の利用者の意図は? ・・・分かりません。
UIやそのサービスでどうしたいかのUX設計次第。
ただ、「東京」「昨日」「雨だ」を同時に含むものというところを大まかに期待しており、何かヒットすると嬉しいというところまでで、「東京は昨日雨だった...」というところまでは求めてないような気がしますね。
スペース区切りのワードごとの部分一致のAND検索となって欲しいのではと思い込むことにしましょう。
とした場合に、N-Gramというよりは、その前段で強制トークン分割する条件として、whitespaceをひとつの条件とする設定としてあるからこそですが、以下のとおり、多数派がそうなって欲しいという挙動になるかな...と筆者は感じました。
■⑦A
GET xgram/_search
{"query": {
"match": {
"t.23g": { "query": "東京 昨日 雨だ",
"operator":"and",
"analyzer":"23g"
}}}}
↓
ヒットする。
■⑦B
GET xgram/_search
{"query": {
"match": {
"t.23g": { "query": "東京 昨日 晴れ",
"operator":"and",
"analyzer":"23g"
}}}}
↓
ヒットする。
■⑦C
GET xgram/_search
{"query": {
"match": {
"t.23g": { "query": "東京 昨日 晴れだ",
"analyzer":"23g",
"operator":"and"
}}}}
↓
ヒットしない。「晴れだ」がマッチしないため。前の2つの例に比べて、「晴れ」よりも「晴れだ」で利用者の気持ちが入った検索なので、今回の例だとヒットしない(残念ながらあなたのお探しの例はありません)でも、そんなに悪くないと言えませんかね?
まとめ(ズルして上の方ではっきりと触れていない事項も含む):
- 部分一致という言い回し先行の要件を望むなら、Elasticsearchのmatch句系のoperatorはデフォルトではORであるため、ANDを明示指定する。
- AND指定しても、N-Gramはなんとなく使うと、大半のケースは素直に部分一致しているように見えるがそうでもないパターンが発生する。
- 部分一致しているように見えるがそうでもないパターンは、筆者自身は、RDBのワイルドカード挟みのLIKE検索に比べほど良い忖度があって、実のところキライではない。
- 厳格な部分一致に近づけるなら、min_gramとmax_gramを違う値にしたN-Gramを設定する。max_gramを大きくすると当然、厳格になる。といいつつ、イビデンスは英語圏だけかもしれないが、minは2、maxは3で十分うまく行くらしい。
- N-Gram関係の検索は、search側で別のアナライズを行うことで、空間効率を高めることや当たり方の厳格度やユル度の微調整に近い効果が得られる場合がある。ただし、インデックス側のmax_gramより大きいNを検索側のアナライズに適用すると絶対にヒットしないので注意。ちなみに、この考え方で、あえてmin、maxを大きめにすることで、アソビのある部分一致とそこそこの厳密な部分一致を両立させることもできる(し、定性的に仕様を宣言(例. 検索語が4文字以上でないと部分一致させません!)できる。まあ、当たり前だが。)
- さらにより厳格な部分一致を極めていくなら、matchではなく、match_phraseを使う。特にslopを0にすると「隙間」無しとなるので、本当に「部分一致」になる。もちろん、今度は遊びがなくなるので、slopを0より大きな値にして文中で多少離れていてもその語順になってさえいれば良いという許容範囲に応じて微調整する、....あるいは、検索の意図の深読みはやめて、●項のような、アソビを残すのは手でしょう。
その他
上記で例にあげたものは、辞書によく出てくるような未知語も少なく、単語分割がはっきりしている例(晴れ、東京、埼玉...)でした。
このような例はそもそもN-Gramではなく、使える辞書を使って(つまり形態素解析の分かち書きで)頑張れば上記のようなまどろっこしい例とはなりにくいことを今更ですが補足しておきます。
なお、「部分一致」じゃないかもというところからスタートしたコラムなので、大前提としてAND推しでしたが、全文検索の華は、OR検索のような気もしますので、
次のしかけ等をうまく使って検索体験を向上させるようなトリックとしていろいろ打つ手はありそうです! というところだけそれとなくご紹介して終わりにします。
- minimum_should_match: AND検索に適度に近づけつつ、残念ながらそのワードではヒットしませんよというワードをほどほどに無視する。
- shingle(トークンフィルター): 無印のmatch検索で、phrase検索を擬似実現。
- トーカナイザーでN-Gramを使って、トークンフィルターでもN-Gram系を使う:
参考リンク
勉強させてもらいました↓
gihyo.jp