ファジーマッチングは、目的の項目と正確に一致しないものを識別することができます。 これは多くの検索エンジンのフレームワークの基礎となっており、クエリにタイプミスがあったり、言葉の時制が異なっていたりしても、関連する検索結果を得ることができる主な理由の 1 つです。
ご想像のとおり、テキストのファジー検索に使用できるアルゴリズムは多数ありますが、bleve を含む事実上すべての検索エンジン フレームワークでは、ファジー文字列マッチングにレーベンシュタイン距離を主に使用しています。 例えば、ターゲット用語が「book」でソースが「back」の場合、最初の「o」を「a」に、2番目の「o」を「c」に変更する必要があり、レーベンシュタイン距離は2となります。編集距離は非常に簡単に実装でき、コードインタビューの際に人気のある課題です（JavaScript、Kotlin、Java、その他多くのレーベンシュタイン実装は、こちらで見つけることができます）。
さらに、いくつかのフレームワークでは Damerau-Levenshtein 距離もサポートしています:
Damerau-Levenshtein 距離
これは Levenshtein 距離の拡張で、1 つの追加操作を許可します。
例: TSARからSTAR
Damerau-Levenshtein distance = 1 (SとTの位置を入れ替えるのに、1回の操作で済む)
Levenshtein distance = 2 (S からT、TからSに入れ替える)
ファジーマッチと関連性
ファジーマッチには大きな副作用がある、関連性を台無しにするのである。 Damerau-Levenshtein は一般ユーザーのスペルミスのほとんどを考慮するアルゴリズムですが、特に英語のように1単語あたり平均5文字しかない言語を使用している場合は、かなりの数の誤検出も含まれることがあります。 そのため、検索エンジンのフレームワークの多くは、レーベンシュタイン距離にこだわることを好んでいます。 実際の例を見てみましょう。
まず、この映画カタログのデータセットを使用することにします。 全文検索で遊びたいなら、ぜひおすすめです。 そして、タイトルに「book」が含まれる映画を検索してみましょう。 簡単なコードは以下のようなものです。
|
1
23
4
5
6
|
String indexName = “movies_index”;
MatchQuery query = SearchQuery.match(“book”).field(“title”);
SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, query).highlight();
searchQuery(indexName).highlight().fullname;
searchQuery.result = data(“”).fullname;
#3540limit(6)); printResults(movies);
|
上記のコードで、以下の結果が得られるでしょう。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
1）ブックシーフ
スコア。 4.826942606027416
ヒットした場所。
field:title
term:book
fragment.BlackBook(ブラックブック)
がヒットしました。
—————————–
2) エリ書
score: 4.8269426027416
Hit Locations:
field:title
term:book
fragment:
—————————–
3) The Book of Life
score: 4.8269426027416
Hit Locations:
field:title
term:book
fragment:
—————————–
4) Black Book
score: 4.826942606027416
Hit Locations:
field:title
term:book
fragment:
—————————–
5) The Jungle Book
score: 4.8269426027416
Hit Locations:
field:title
term:book
fragment:
—————————–
6) ジャングルブック2
score: 3.9411821308689627
Hit Locations: The Jungle Book 2
。
field:title
term:book
fragment:
—————————–
|
デフォルトでは、結果は大文字小文字を区別しませんが、異なる分析器を使用して新しいインデックスを作成すれば、この動作を簡単に変更できます。
ここで、ファジー性を 1 (Levenshtein distance 1) として、クエリーにファジーマッチ機能を追加しましょう。これは “book” と “look” は同じ関連性を持つことを意味します。
|
1
2
3
4
5
6
|
String indexName = “movies_index”;
MatchQuery query = SearchQuery.match(“book”).field(“title”).fuzziness(1);
SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, query).highlight().LR.Match(“”,””);
New SearchQuery(indexName, query).highlight().limit(6));
printResults(movies);
|
そしてファジー検索結果がこちらです。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
1）フック
のスコア。 1.1012248063242538
ヒットした場所。
field:title
term:hook
fragment:
—————————–
2) Here Comes the Boom
score: 0.7786835148361213
Hit Locations.Of The Boom
—————————–
ヒットの場所は？
field:title
term:boom
fragment:
—————————–
3) Look Who’s Talking Too
score: 0.7047266634351538
Hit Locations:
field:title
term:look
fragment:
—————————–
4) Look Who’s Talking
score: 0.7047266634351538
Hit Locations:
field:title
term:look
fragment:
—————————–
5) 本泥棒
score: 0.52288117537184
Hit Locations.Of The Book Thief (本泥棒) —————————–
5) The Book Thief —————————–
Hit Locations:
field:title
term:book
fragment:
—————————–
6）エリの書
score: 0.52288117537184
Hit Locations:
field:title
term:book
fragment:
—————————–
|
今、「Hook」という映画が最初の検索結果ですが、これは「Book」の検索でユーザーが期待しているものとは異なるかもしれません。
How to minimize false positives during fuzzy lookups
理想の世界では、ユーザーが何かを検索中にタイプミスすることは絶対にないはずです。 したがって、真の問題は、関連性の損失を最小限に抑えながら、ファジーな文字列マッチングを行うにはどうすればよいかです。 編集距離が低い一致は、通常、より高いスコアを得ます。 この特性により、異なるファジーレベルを持つこれら 2 つのクエリを 1 つにまとめることができます。
|
1
2
34
5
6
7
8
|
String indexName = “movies_index”;
String word = “Book”;
MatchQuery titleFuzzy = SearchQuery.SearchQuery.Fuzzy。match(word).fuzziness(1).field(“title”);
MatchQuery titleSimple = SearchQuery.match(word).field(“title”);
DisjunctionQuery ftsQuery = SearchQuery.disjuncts(titleSimple, titleFuzzy);
SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, ftsQuery).highlight().MatchSimple;
New SearchQuery(indexName).MatchSimple(titleSimple, titleFuzzy);
#3540limit(20)); printResults(result); |
上のファジーなクエリの結果は以下のとおりです。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
1）ブックシーフ
スコア。 2.398890092610849
ヒットした場所。
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
2) エリ書
score: 2.398890092610849
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
3) The Book of Life
score: 2.398890092610849
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
4) Black Book
score: 2.398890092610849
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
5) ジャングルブック
score: 2.398890092610849
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
6) ジャングルブック2
score: 1.958685557004688
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
7) National Treasure: Book of Secrets
score: 1.6962714808368062
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
8) American Pie Presents: ザ・ブック・オブ・ラブ
score: 1.517191317611584
Hit Locations:
field:title
term:book
fragment:
—————————–
field:title
term:book
fragment:
—————————–
9) フック
score: 0.5052232518679681
Hit Locations: 0.5052232518679681 (スコア:0)
ヒットロケーション。
field:title
term:hook
fragment:
—————————–
10) ヒア・カムズ・ザ・ブーム
score: 0.3572467812941
ヒットした場所。
field:title
term:tree
fragment:
—————————–
11) Look Who’s Talking Too
score: 0.32331663301992025
Hit Locations:
field:title
term:look
fragment:
—————————–
12) Look Who’s Talking
score: 0.32331663301992025
Hit Locations:
field:title
term:look
fragment:
——————————-
|
ご覧のように、この結果はユーザーが期待するものにかなり近くなっています。 現在、DisjunctionQuery というクラスを使っていることに注意してください。ディスジャンクションは、SQL の「OR」演算子と同等です。
ファジー マッチング アルゴリズムの負の副作用を減らすために、他にどのような改良が可能でしょう。
私たちはすでに、ファジー検索が予期しない結果 (たとえば、Book -> Look、Hook) を生成することがあることを知っています。 しかし、単一用語検索は通常ひどいクエリで、ユーザーが正確に何を達成しようとしているかのヒントをほとんど与えてくれません。
間違いなく使用中の最も高度なファジー検索アルゴリズムを持つ Google でさえ、私が「テーブル」を検索するときに何を探しているのか正確にわかりません:
では、検索クエリのキーワードは平均どのくらいなのでしょうか? この問いに答えるために、Rand Fishkin氏の2016年のプレゼンテーションからグラフを紹介します。 (彼はSEO界で最も有名な達人の一人です）
上のグラフによると、検索クエリの~80%は2つ以上のキーワードを持っているので、ファジー1を使って映画「ブラックブック」を検索してみてみましょう。
|
1
2
3
4
5
6
|
String indexName = “movies_index”;
MatchQuery query = SearchQuery.match(“Black Book”).field(“title”).fuzziness(1);
SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, query).highlight().limit(12));
printResults(movies);
|
Result:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
1）ブラックブック
スコアの場合です。 0.6946442424065404
ヒットした場所。
field:title
term:book
fragment.BlackBook(ブラックブック)
がヒットしました。
—————————–
field:title
term:black
fragment:
—————————–
2) フック
score: 0.40139742528039857
Hit Locations:
field:title
term:hook
fragment:
—————————–
3) ブロックを攻撃
score: 0.2838308365090324
Hit Locations: 0.2838308365090324
3) ブロックを攻撃。
field:title
term:block
fragment.Image:ブロック
のようになります。
—————————–
4) Here Comes the Boom
score: 0.2838308365090324
Hit Locations.Of The Boom
ヒットした場所:
field:title
term:boom
fragment:
—————————–
5) Look Who’s Talking Too
score: 0.25687349813115684
Hit Locations:
field:title
term:look
fragment:
—————————–
6) Look Who’s Talking
score: 0.25687349813115684
Hit Locations:
field:title
term:look
fragment:
—————————–
7) Grosse Pointe Blank
score: 0.2317469073782136
Hit Locations.Of.Pirates
ヒットした場所。
field:title
term:blank
fragment:
—————————–
8) 本泥棒
score: 0.19059065534780495
Hit Locations.Of The Book Thief (本泥棒)
ヒットした場所。
field:title
term:book
fragment:
—————————–
9) エリ書
score: 0.19059065534780495
Hit Locations:
field:title
term:book
fragment:
—————————–
10) The Book of Life
score: 0.19059065534780495
Hit Locations:
field:title
term:book
fragment:
—————————–
11) The Jungle Book
score: 0.19059065534780495
Hit Locations:
field:title
term:book
fragment:
—————————–
12) Back to the Future
score: 0.17061000968368
Hit Locations.Of the Future
ヒットした場所。
field:title
term:back
fragment:
——————————-
|
悪くないな。 検索していた映画を最初の結果として得ることができました。 3984>
しかし、ここで新しい良い特性があるように見えます。キーワードの数が増えると、あいまいマッチングの副作用がわずかに減少します。 ファジィネス 1 で “Black Book” を検索すると、back look や lack cook (編集距離 1 の組み合わせ) のような結果が得られますが、これらは実際の映画のタイトルである可能性は低いでしょう。
「book eli」をあいまい度2で検索しても、3番目に表示されるでしょう。
|
1
2
3
4
5
6
|
String indexName = “movies_index”;
MatchQuery query = SearchQuery.match(“book eli”).field(“title”).fuzziness(2);
SearchQueryResult result = movieRepository.getCouchbaseOperations().getCouchbaseBucket().query(
new SearchQuery(indexName, query).highlight().match(“indexName”).title(“title”).fuzziness(2);
SearchQueryResult = searchQuery(indexName, query).highlight().fuzziness(2);
＜3540limit(12)); printResults(movies);
|
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
|
1）エド・ウッド
点数。 0.030723793900031805
ヒットした場所。
field:title
term:wood
fragment:
—————————–
field:title
term:ed
fragment:
—————————–
2) Man of Tai Chi
score: 0.0271042761982626
Hit Locations:
field:title
term:chi
fragment:
—————————–
field:title
term:tai
fragment:
—————————–
3) エリの書
score: 0.02608335441670756
Hit Locations:
field:title
term:eli
fragment:
—————————–
field:title
term:book
fragment:
。
—————————–
4) The Good Lie
score: 0.02439822770591834
Hit Locations: The Good Lie
4:
field:title
term:lie
fragment:
—————————–
field:title
term:good
fragment:
——————————-
|
ただし、英語の平均単語は 5 文字なので、たとえば “Schwarzenegger” などスペルを間違えやすい長い単語（少なくともドイツ人またはオーストリア人以外）でもユーザーが検索するのでなければ、編集距離を 2 よりも長くすることはおすすめしません。
結論
この記事では、ファジーネス マッチングと、その関連性を台無しにすることなくその主な副作用を克服する方法について説明しました。 ファジーマッチングは、関連性が高くユーザーフレンドリーな検索を実装する際に利用すべき多くの機能の 1 つに過ぎないことに留意してください。 このシリーズでは、そのうちのいくつかについて説明します。 Nグラム、ストップワード、Steeming、Shingle、Elision。
Check out also the Part 1 and Part 2 of this series.
In the meantime, if you have any questions, tweet me at @deniswsrosa.
Author
- Denis Rosa, Developer Advocate, Couchbase –
