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.
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 UX 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.
Fuzzy search is approximate string matching as opposed to exact string matching. It 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.
Examples:
See more examples & how this is done, below.
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:
See more examples & how this is done, below.
Note that we’ll exclude any fuzzy matching based on semantics, machine learning, or statistical techniques like TF-IDF.
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.
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).
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) |
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 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.
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.
A query can be set up to match and rank records based on the word position with the attribute of the record. In other words, a match can start in the middle of an attribute.
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.
A search engine can start removing words if the full phrase returns no results.
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 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.
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:
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.
Peter Villani
Sr. Tech & Business WriterPowered by Algolia AI Recommendations
Diego Salinas Gardón
Freelance Writer at Authors CollectiveJosh Dzielak
Catherine Dee
Search and Discovery writer