Fuzzy Search

ファジーサーチ（Fuzzy Search）は、綴りの揺れに耐性を持つ検索技術であり、編集距離、n-gram、音声アルゴリズムなどに基づいて近似した結果を照合する。

目的

ユーザー入力に誤字や変種が含まれていても関連する結果を返し、検索体験を向上させる。

メカニズム

一般的な手法は、レーベンシュタイン距離のしきい値照合、n-gram 転置インデックス、BK-tree による高速化、Soundex/Metaphone による音声照合、Bitap アルゴリズムなどである。fuse.js、Elasticsearch の fuzzy クエリなどが実装を提供する。

ユースケース

検索エンジンのスペル訂正
コマンドラインのオートコンプリート
データベースのあいまいクエリ
コード検索（誤字許容）

例

入力

recieve → receive

Output

Matches receive (distance 2)

Spelling correction

よくあるエラー

Overly loose thresholds cause too many false matches: Adjust thresholds dynamically based on word length

関連用語

Levenshtein Distance

レーベンシュタイン距離は、二つの文字列を同一にするために必要な単一文字の挿入・削除・置換の最小回数である。

Soundex は英語の名前を発音に基づいて 1 文字＋3 桁の数字に符号化する音韻アルゴリズムで、よく似た発音の名前に同じコードを与える。人名のあいまい検索に使われる。

N-gram（エヌグラム）はテキストから切り出したN個の連続した単位（文字または単語）の列であり、言語モデルや類似度、テキスト解析に使われる。

編集距離は、ある文字列を別の文字列に変換するのに必要な単一文字編集操作（挿入・削除・置換）の最小回数である。レーベンシュタイン距離が最も一般的な形である。

References