プロダクト

Elasticsearchであいまい検索を使用する方法

By
Andrew Cholakian

更新：この記事は、かつてFoundと呼ばれていたマネージドElasticsearchサービスについて説明しています。Foundは現在、Elastic Cloudとして知られていることにご注意ください。

Elasticsearchのファジークエリは、多くの状況で役立つ強力なツールです。ユーザー名の検索やスペルミス、その他の問題は、この型にはまらないクエリで解決できることがよくあります。この記事では、時にわかりにくいファジー検索のオプションを明確にし、LuceneのFuzzyQueryの内部構造についても詳しく解説します。

はじめに

自然言語の検索は本質的に不正確です。コンピューターは自然言語を理解できないため、検索方法には多くのアプローチがあり、それぞれに長所と短所があります。Elasticsearchの基盤技術であるLuceneは、多くのテキスト処理ツールを備えた万能のスイスアーミーナイフのような存在です。各ツールはヒューリスティックであり、真の言語理解の代わりとなるアルゴリズムの近道です。SnowballステマーやMetaphone音声解析器のように高度なものもあれば、単語の先頭文字を単純に照合するプレフィックスクエリのような基本的なものもあります。ファジークエリは洗練度の点で中間に位置し、クエリに一致させるために最大で一定数の文字修正（「編集」と呼ばれる）を必要とする単語を検索します。例えば、「ax」のファジー検索は「axe」と一致します。これは「e」を1文字削除するだけで両者が一致するためです。

シンプルなファジーマッチ

ファジークエリは、以下の例のようにマッチクエリタイプに引数を追加することで最も簡単に実行できます。この例では、余分なAが含まれる「vaacuum」を検索しても、「Vacuum」製品が結果に表示されます。fuzziness引数は、最大編集距離2で一致することを指定しています。fuzzinessは1または2の値でのみ使用すべきであり、クエリと文書内の用語間の編集は最大2回まで許可されます。より大きな差異は計算コストが高くLuceneでは処理されません。公式ドキュメントではまだ0.5などの浮動小数点値の設定が言及されていますが、これらは非推奨であり理解が難しいため避けるべきです。

# インデックスの作成
PUT /fuzzy_products
# 製品マッピングの作成
PUT /fuzzy_products/product/_mapping
{
  "product": {
    "properties": {
      "name": {
        "type": "string",
        "analyzer": "simple"
      }
    }
  }
}
# ドキュメントのアップロード
PUT /fuzzy_products/product/1
{"name": "Vacuum Cleaner"}
PUT /fuzzy_products/product/2
{"name": "Turkey Baster"}
# ファジー検索の実行
POST /fuzzy_products/product/_search
{
  "query": {
    "match": {
      "name": {
        "query": "Vacuummm",
        "fuzziness": 2,
        "prefix_length": 1
      }
    }
  }
}

編集距離の決定

ファジークエリで一致を判断する指標はDamerau-Levenshtein距離の公式です。簡単に言えば、2つのテキスト間のDamerau-Levenshtein距離は、一方の文字列をもう一方に一致させるために必要な挿入、削除、置換、転置の回数です。例えば、「ax」と「axe」のLevenshtein距離は1で、1文字の削除が必要です。

Damerau-Levenshtein距離は従来のLevenshtein距離を修正し、転置を有効な操作として加えたものです。両方の公式がサポートされており、デフォルトはDamerau-Levenshteinで、クエリでtranspositionsをfalseに設定すると従来のLevenshteinを選択できます。転置の有用性は「aex」と「axe」を比較した場合に明らかで、従来のLevenshteinでは2回の編集が必要ですが、Damerau-Levenshteinでは1回の転置操作で済みます。これにより、Damerau-Levenshteinの方が直感的に理解しやすいことがわかります。

ファジー検索を扱う際は、Elasticsearchではテキストが検索可能になる前にアナライザーを通過することを理解することが重要です。データはインデックス化される際に「用語」と呼ばれる検索単位に処理されます。検索されるのは分析済みの用語（用語の定義については

ゼロからのElasticsearchで紹介しています）であり、実際の保存ドキュメントではありません。したがって、ファジークエリでは分析結果により予期しない用語と比較され、混乱を招くことがあります。また、同義語が有効なフィールドでは、ソーステキストにない単語の同義語が一致することもあります。例えば、ngram分析されたフィールドにファジークエリを使うと、結果が奇妙になることがあります。ngramsは単語を多くの小さな文字列に分割し、多くが1～2回の編集で一致しますが、実際の単語は異なります。Snowballアナライザーを使う場合、「running」のファジー検索は「run」にステミングされますが、スペルミスの「runninga」には一致しません。これは「run」と「runninga」の編集距離が2以上だからです。このため、ファジークエリ用のテキストにはシンプルアナライザーを使い、同義語は無効にすることが推奨されます。以下にSnowballアナライザーを使ったファジークエリの図を示します。

A fuzzy query using a snowball analyzer

Snowballアナライザーを使ったファジークエリ

ファジー検索の種類

Elasticsearchは複数のファジー検索タイプをサポートしており、違いがわかりにくいことがあります。以下にそれらを明確にします。

  • matchクエリ + fuzzinessオプション：fuzzinessパラメータを追加すると、通常のmatchクエリがファジークエリになります。検索前にクエリテキストを分析します。
  • fuzzyクエリ：elasticsearch のfuzzyタイプクエリは一般的に避けるべきで、termクエリのように動作し、クエリテキストを分析しません。
  • fuzzy_like_this/fuzzy_like_this_field：more_like_thisクエリの一種で、fuzzinessをサポートし、ファジー一致結果の特性をより適切に処理するスコアリングアルゴリズムを持ちます。
  • サジェスター：実際のクエリタイプではなく、ファジークエリを内部的に利用した操作で、クエリと併用または単独で実行可能です。ユーザーの入力ミスに対する「もしかして：」機能に優れています。

fuzzinessパラメータ付きのmatchクエリは最も汎用的なファジークエリです。fuzzyクエリは同じ動作をサポートしますが、クエリテキストの分析ができず、matchクエリの機能のサブセットであるため、混乱を招きやすいです。

fuzzy_like_this（FLT）クエリは、編集距離で区切られたスペルミスや不正確さを含む大きなテキストに基づくレコメンデーションに役立ちます。fuzzy_like_thisとfuzzy_like_this_fieldの2種類があり、後者は単一フィールド用に構文が簡略化されています。like_textパラメータに記事本文などの大きなテキストを指定し、それに似た文書を検索します。記事内のテキストをチェックし、like_text内の頻度に基づいてクエリ用語に重み付けを行います。FLTクエリはスペルミスが多いコーパスに最適で、そうでなければ標準のmore_like_thisクエリの方が性能が良いです。詳細はFuzzy More Like Thisの公式ドキュメントを参照してください。

サジェスターは、ユーザーが「New Yrok」と入力した場合に「New York」と提案するなどの機能に優れています。アプリケーションはサジェスターを使って、UI上に「もしかして」というボックスを表示し、修正候補を提示することができます。タイプアヘッド検索の場合は、遅延に敏感なため、completion APIの方が性能が良いことに注意してください。詳細は検索サジェスターのページを参照してください。

パフォーマンスに関する考慮事項

LuceneのLevenshtein距離実装は最先端で高速ですが、通常のmatchクエリよりはるかに遅いです。クエリの実行時間はインデックス内のユニーク用語数に比例します。例えば、10,000語のユニーク単語を含む100文書のインデックスは、100語のユニーク単語を含む10,000文書のインデックスより遅くなります。

この遅さの主な理由は、標準のmatchクエリがLuceneの内部データ構造であるタームインデックスをバイナリ検索で高速にチェックできるためです。一方、ファジークエリは多数の用語を処理するDFAを使うため、常に遅くなります。例として、英語版Wikipediaデータセットでmin_similarity=2の「history」検索は約320msかかりますが、通常のmatch検索は35msです。min_similarity=1では150msです。これらのテストは統計的に厳密ではなく、アプリケーションによって異なります。

パフォーマンスは、クエリと完全に一致するプレフィックスを要求することで大幅に向上します。これにより検索範囲が狭まり、前方のスペルミス単語は見つかりにくくなります。prefix_length=1で320msが104msに短縮され、さらに増やすと速度が向上します。大規模データセットではプレフィックス指定が推奨されます。

max_expansions設定は、検索を停止する前にファジークエリが一致させる最大用語数を定義し、パフォーマンスに大きく影響します。ただし、用語数を減らすと有効な結果が見つからない可能性があります。max_expansionsはシャード単位で動作し、1に設定しても複数の用語が異なるシャードから返されることがあります。これによりmax_expansionsが効いていないように見えることがあるため、返されたユニーク用語数で判断しないでください。

ファジーマッチングの代替手段

ファジーマッチングは常に最適な手法ではなく、他の技術で不正確な一致を見つけることもあります。発音分析プラグインには、メタフォンアナライザーなど、音声的に似た単語を見つける魅力的なツールが含まれています。例えば、runとranを同等とみなす場合は、Snowballアナライザーのようなスマートアナライザーが適しています。また、データセットによっては、n-gram分析がクエリ時に高速に動作します。ただし、n-gramはストレージやメモリ使用量が増え、インデックス処理が増加し、誤検出が多くなる欠点があります。

追加のリソース

  • Elasticsearchのファジークエリのパフォーマンスについて詳しく知りたい場合は、LuceneのコアコントリビューターMike McCandlessによる興味深いブログ記事があります。また、Dawid WeissによるLuceneとSolrの有限状態オートマトンに関するプレゼンテーション動画もあります。
  • Levenshtein Automataについてさらに学びたい場合は、Nick Johnsonによる素晴らしい記事「Damn Cool Algorithms: Levenshtein Automata」があります。