Fuzzy Search

Fuzzy search is a search technique tolerant of spelling variations, matching approximate results based on edit distance, n-grams, or phonetic algorithms.

Purpose

Returns relevant results even when user input contains typos or variants, improving the search experience.

Mechanism

Common methods: Levenshtein distance threshold matching, n-gram inverted indexes, BK-tree acceleration, Soundex/Metaphone phonetic matching, and the Bitap algorithm. Implementations are provided by fuse.js, the Elasticsearch fuzzy query, and others.

Use cases

Search engine spelling correction
Command-line autocompletion
Database fuzzy queries
Code search (typo-tolerant)

Examples

Input

recieve → receive

Output

Matches receive (distance 2)

Spelling correction

Common errors

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

Related terms

Levenshtein Distance

The Levenshtein distance is the minimum number of single-character insertions, deletions, and substitutions needed to make two strings identical.

Soundex is a phonetic algorithm that encodes English names by pronunciation as a letter plus three digits, giving similar-sounding names the same code; it is used for fuzzy person-name retrieval.

An N-gram is a sequence of N consecutive units (characters or words) segmented from text, used in language models, similarity, and text analysis.

Edit distance is the minimum number of single-character edit operations (insertion, deletion, substitution) required to transform one string into another; the Levenshtein distance is its most common form.

References