The term fuzzy search comes with several meanings, all of which turn on the idea of approximate matching. The most common understanding of the term involves fuzzy string matching, where a search engine matches words that do not match exactly. The classic example is misspellings, where incorrectly spelled queries turn up correctly spelled results. But there’s more to fuzziness than correcting typos, as you’ll see. For example, it could also correct poorly formulated queries, recognize colloquial vocabulary, expand prefixes, or build loose category relationships between a query and the content being searched. 

The fuzzy matching described in this article enables a search engine to apply some (slightly) inexact matching techniques to ensure that it returns all relevant results. In this sense, relevance is not an exact science.

Search relevance, in general

The starting point for search is textual matching, which matches a query’s exact characters, letters, and words to the records in the dataset. Say you search for a “boat”, the search engine will return all records with the word “boat” in it. Not “canoe” or “cruise ship”. 

Textual matching goes a long way. With good data, the query “boat” will return every relevant record, as long as it contains the word “boat”, for example, in titles, descriptions, and categories. With even smarter data, when you search for a “boat”, the search engine could return anything that floats, as well as boating lessons or cruise vacations. 

But what if the word “boat” does not appear in the records, even though the data contains boat-related information? Here’s where synonyms come in. But what if someone wants to find “canoe” and reasonably spells it “canou”? Without typo tolerance, the search engine would return no results.

Fuzzy matching is about enhancing relevance, making the relevance and overall search experience even more intuitive. When done well, fuzzy matching seamlessly integrates closely-related items, where not to do so would be a serious loss of opportunity. Like doing a puzzle, fuzzy search collects similar pieces to help you locate the exact piece. Additionally, because people define what they need as they search, fuzzy search brings up options based on similarity, like taste-testing before ordering the best meal.

Search tools like Algolia (fuzzy search with Typo Tolerance), Elastic (Fuzzy Search), Coveo (Fuzzy Search), and Constructor.io (Fuzzy Search Rules) offer fuzzy matching. They all approach the subject differently. We’ll discuss Algolia’s variety of techniques.

Definitions of fuzzy search & fuzzy matching

What is fuzzy search?

Approximate string matching as opposed to exact string matching. Fuzzy search matches two or more words even if there are typos or misspellings. Fuzzy search resolves clumsy fingers, rushed-for-time and careless typers, mobile users, and the complexities of spelling in every language of the world. Fuzzy search can also play a role in matching user-generated data, which is generally unreliable because users misspell and use alternative or localized spellings for the same words. This can also include matching based on phonetics and sound. 

Other words for fuzzy search: fuzzy or approximate string matching.

Examples:

• Type ”helo”, find records with ”hello”
• Type ”help”, find records with help and hello

See more examples & how this is done, below. 

What is fuzzy matching?

Extends the fuzziness of search to include finding information based on similarities. Fuzzy matching is a broad term, so we’ll speak only about language-based similarities, such as synonyms, grammar (plurals, verb conjugaisons, noun endings, etc.), dictionary-based techniques, and other heuristics or NLP methods. Below, we’ll also include similarities typically used by search engines such as partial word, phrase, or query matching, and the use of filters.  

Examples:

• Type ”pants”, find pants, trousers, slacks (synonyms)
• Type ”be”, find Beatles, bees (prefix search)

See more examples & how this is done, below.

Other usages of “fuzzy”

• Fuzzy sets groups words (and objects) based on shared characteristics. For example, the shape of an American football, rugby ball, and an egg make these items more or less similar (oblong shape), but football and rugby are closer because they also share the qualities of bounce and sport (notwithstanding the egg-in-a-spoon game).
• Fuzzy logic constructs logical relationships based on relative nearness, not binaries like true and false (two objects match based on both being “tall” rather having the same exact height). 

Note that we’ll exclude any fuzzy matching based on semantics, machine learning, or statistical techniques like TF-IDF. 

Fuzzy search using Typo Tolerance

Typo tolerance allows users to make mistakes while typing and still find the records they’re looking for. This is done by matching words that are close in spelling. 

What exactly is a typo?

• A missing letter in a word, “strm” → “storm”
• An extraneous letter, “stoorm” → “storm”
• Inverted letters: “strom” → “storm”
• Substituted letter: “storl” → “storm”

Spelling distance (Damerau–Levenshtein distance) algorithm

Algolia’s typo tolerance algorithm is based on distance, following the Damerau–Levenshtein distance algorithm. Distance refers to the difference in spelling between a typed word and its exact match in the index. Distance has a precise meaning: it’s the minimum number of operations (character additions, deletions, substitutions, or transpositions) required to change one word into another. A perfect match is distance = 0. When there is a perfect match, or the distance is low (one or two letters mistakenly typed), then a match is made and the record is added to the results.

For example, if the engine receives a word like “strm”, this can mean “storm” or “strum” (distance = 1 / one letter incorrect), or “star” or “warm” (distance = 2 / two letters incorrect).

Distance establishes a threshold of tolerance. The threshold is at 2: when a word has a distance of 3 or more mistakes, it’s ‘not tolerated’ (not included in the results).

More examples of fuzzy search based on typo tolerance

Below are a few examples of how Algolia counts the operations needed to transform a word to find records with “Michael”:

michael	0 typos
mickael	1 typo (substitution: h → k)
micael	1 typo (deletion: h)
mickhael	1 typo (addition: k)
micheal	1 typo (transposition: a ⇄ e)
mickaell	2 typos (substitution: h → k, addition: l)
tichael	2 typos (substitution: m → T, first letter)
tickael	3 typos (substitution: m → T, first letter, substitution h → k)

Ranking and typo tolerance

In terms of relevance: all fuzzy matches based on spelling differences are considered less relevant than exact matches. Thus, records that have a 0 distance – that is, which match exactly – are ranked (ordered) higher than records with typos. Likewise, records with 1 typo are ranked higher than records with 2 typos.  

Fuzzy matching with Synonyms

Fuzzy matching should enable users to write as they speak and allow them to use their own vocabulary. One way to accomplish this is with synonyms. 

Synonyms tell the engine which words and expressions to consider equal – for example, pants = trousers. Thus, a search for “trousers” will return “trousers” and “pants”, and a search for “pants” will also return “trousers” and “pants”.

Synonyms can be dictionary-driven. You can use a thesaurus. However, a thesaurus-based search algorithm is unusable, because it will bring back too many similar results. Every word has multiple synonyms in a thesaurus, which is useful for writers but not for querying a very specific set of data. For example, “slacks” could have several meanings (laziness, loose, low activity), and for each, several synonyms. But in a clothing store’s index, the only relevant synonyms for “slacks” are “pants” and “trousers”.

Finally, search engines can detect common synonyms over time using machine learning, thus building up a dynamic list of relevant synonyms. 

Other methods for fuzzy matching

Partial word matching with Prefix Search

Prefix matching is central to Algolia’s as-you-type search experience. It enables the engine to start matching records based on partial words.

For example, records containing “apricot” are returned as soon as a user types “a”, “ap”, “apr”. There’s no need for the engine to wait for a full-word match before displaying results. 

Flexible string matching by searching in middle of the word (“contains”)

A query can be setup to match and rank records based on the word position with the attriibute of the record. In other words, a match can start in the middle of an attribute. 

• Query “hiking” matches record: “Backpacks used for hiking and traveling”.

Partial phrase matching with Optional Words

Normally, in order for a record to match it must match all words in the query. By creating a list of optional words, you can match records that match only some of the words. 

• Query “backpacks hiking” matches records in a store that sells only backpacks. The store might want to remove the word “backpacks” from the query (thus, making it an optional word), because they won’t use “backpack” in the product name – but they also don’t want to miss out on good results if someone happens to include it in the query. 

Removing words if no results

A search engine can start removing words if the full phrase returns no results.

• Query “hiking backpacks heavy clothing”, no records match (too many words), so the engine removes “heavy clothing” and finds backpacks used for hiking.

Fuzzy grouping based on robust filtering & faceting

Filtering is basic to all search engines, as well as faceting, the front-end face of filtering. Adding characteristics to your data (like brand, genre) is crucial to any search, browse, and discovery experience. Tagging records with user-generated categories and with your own robust understanding of your data creates a richer combination of results, based on fuzzy grouping as described above. 

Additionally, the filter syntax of “AND” and “OR” expands the grouping of content, allowing the engine to combine records with multiple similarities as well as dissimilarities.

Optional filters & filter scoring

Optional filtering behaves like normal filters, meaning that it returns records that match both the query and the filters. However, it also returns records that do not match the filters. The effect is on the ranking: records matching the filters are ranked higher than records that do not match the filters. If you use negative filters, items that match your filter are ranked lower than other records.

Filter scoring allows you to bring in more records, but controls the ranking so that the fuzzy matches are ranked lower than the exact matches.

So .. How do you contain the multitude of all these fuzzy searches and matching

Adding fuzzy logic, while powerful, comes with some risk. It may return too many results for a user to sift through, or it may return unexpected results that may break, in the users mind, the relevance of the results. 

It’s the job of the search engine to limit the impact of this expansion of information. For example, by giving higher priority to exact matches, ensuring that exact matches show up at the top of the results, above the fuzzy ones:

• In the case of misspellings, exact matches are considered more relevant than inexact matches (even if the typo is obvious to the user). 
• With synonyms, exact matches are more relevant than synonym matches (even if the word in the query has multiple meanings and the synonym would be the better choice). 

Essentially, engines hedge the bet on the fuzzy algorithm by displaying the fuzzy matches after the exact matches. 

There are also many UI patterns to manage this. For example, Google and other search engines add “suggested spellings” just below the search bar. Or they offer an Autocomplete or Query-Suggestion feature, where the user is given suggested queries (and categories) in a dropdown list as they type, which they can choose from as their query.  

But the proper solution is the one below the surface, completely transparent to the user, where the search engine returns results that create an intuitive feeling in the user that the displayed items are the best and most relevant results – even if not exactly matching the text of the query.