What Is Fuzzy Search?

Fuzzy search is search engine technology that looks for near matches instead of exact matches to the input search term. Users searching for information may make spelling errors or use colloquial terms for technical words. Fuzzy search looks for search results that are "close enough" to the search terms, giving relevant results the user needs even if they don't exactly know what they are looking for. It broadens the search scope and improves knowledge retrieval workflows. However, fuzzy search is challenging to implement as it finds and sorts a practically infinite set of close-match options instead of a finite set of exactly matching data.

Fuzzy search and the matching logic that powers it are useful in various fields. Below are some examples.

Machine translation

Different countries and regions may have distinct vernaculars, even when speaking the same language. When a business wants to translate a text for its audience, it needs to create an accurate final product that reflects these subtle changes in vocabulary or language use.

Fuzzy search and fuzzy matching assist this process by searching for a close resemblance to an original text in the target language. After consulting a database of options through fuzzy matching, a translator selects the best one for the scenario.

Fuzzy matching techniques speed up machine translation, allowing more accurate and precise translations.

Research and exploration

Users searching for information may not know the exact name of an article or concept they're looking for. Fuzzy search returns relevant results to the customer, displaying close category results when searching.

Similarly, the search engine's ability to produce a range of related options streamlines the exploration process in scenarios where users don't know exactly what they want. Organizations such as academic research institutes, enterprise knowledge centers, and customer-facing agencies all employ fuzzy search to enhance research and exploration.

Ecommerce

If a user isn't familiar with the exact name of a product, they may type in a close approximation of what they think the product is called. Fuzzy search identifies these potentially misspelled items and suggests the item or category most likely to be correct.

In an eCommerce situation, fuzzy approximate string matching ensures that users do not need to spell correctly or precisely understand what product they want before browsing the store. This function streamlines the customer experience and helps connect users with the products they seek.

Fuzzy matching mathematically calculates the similarity or "distance" between two text strings. Two identical strings have a "distance" of zero, but character and word changes increase this distance. This allows the system to mathematically assess approximate matching. Below are some of the fuzzy matching algorithms.

Levenshtein distance

The Levenshtein distance (LD) measures the distance between two strings, expressing this distance with a numerical figure. A higher number suggests a greater difference between two strings. By identifying other strings that have a small Levenshtein Distance from the original search query, the fuzzy search suggests similar strings.

The subtraction, addition, or substitution of one character always has a distance of one in this fuzzy matching algorithm. For example, when typing the word 'Londoon,' there is a distance of 1 from the string 'London.' Another example is 'Seing' to 'Seeing,' an addition of one letter, which would also have a distance of 1.

Alternatively, in the change from 'Klokwork' to 'Clockwork,' the substitution of 'K' to 'C' and adding another 'C' results in a Levenshtein Distance of 2.

Hamming distance

The Hamming distance or Fuzzy Hamming Distance (FDH) uses a similar strategy to LD fuzzy string matching but only functions on strings of equal lengths. In both LD and FDH, the difference between 'Clear' and 'Cleay' would be 1.

FDH is most commonly used in healthcare and bioinformatics to compare genetic sequences. With known data sets, it identifies minor variations in the expected and actual string outputs.

Damerau-Levenshtein distance

The Damerau-Levenshtein distance (DLD) takes the Levenshtein Distance fuzzy search one step further by incorporating transpositions of adjacent characters as a distance of one. For example, it would give 'Scuot' and 'Scout' a distance of one, as 'O' and 'U' were swapped in the first example.

Detecting these adjacent changes is helpful because they are pervasive typographical errors. Users may accidentally press one key before another when browsing the internet or another search bar, causing errors that DLD detects and understands.

Jaro-Winkler distance

The Jaro-Winkler distance is a more precise form of statistical modeling that examines two strings and determines their similarity. Instead of identifying distances based on missing or additional letters, it uses two alternative criteria.

• Number of characters matching across the two strings, including any letters not in the right order.
• Whether or not the words begin with the same few characters.

Based on these two factors, it calculates string similarity and expresses this as a probability out of 1. Similar words, such as 'Amazon' and 'Amazen,' receive a higher percentage rating closer to 1, while 'Amazon' and 'BestBuy' score lower than 0.5.

Jaccard Similarity

The Jaccard Similarity compares entire phrases as it determines how many elements in a string a search has in common with another. For example, if you searched for 'Cloud data enterprise protection,' approximate string matching may also suggest results for 'Cloud data enterprise security.'

This form of fuzzy searching is helpful for longer search terms. It also handles word order to suggest similar results.

Phonetic algorithms

Several phonetic algorithms also index words based on their verbal pronunciation. These algorithms detect words with similar pronunciation using the International Phonetic Alphabet (IPA). For example, in the name 'Clare,' a similar spelling, 'Clair,' would have the same pronunciation, grouping these two strings together.

Fuzzy search, exact text search, wildcard search, and open search are all forms of search methods that help deliver accurate results in reply to misspelled search queries.

Exact text search vs. fuzzy search

Fuzzy search generates results through a fuzzy matching algorithm, the specific logic of which depends on the use case a business needs. In contrast, an exact text search produces only exact matches to a search query. If a user writes 'Londen,' the search results only reflect that exact search rather than understanding that they probably mean 'London.'

Wildcard search vs. fuzzy search

Wildcard search is an alternative search engine function that allows users to replace letters with either '*' or '?' depending on their intention. Replacing a letter with '*' produces results for any word that follows the asterisk. For example, 'Emplo*' produces results like 'Employee,' 'Employment,' 'Employer,' and so on.

Similarly, a '?' in a wildcard search is replaced with any letter that fits that character. For example, you can use this when including search engine results from both UK and US writing styles, like in the word 'Gr?y' (Grey/Gray).

Wildcard search puts the onus on the user to find close matches. Fuzzy search determines the various combinations without the user stating any rules.

OpenSearch vs. fuzzy search

OpenSearch is a distributed, community-driven, Apache 2.0-licensed, 100% open-source search and analytics suite. It is a specific search solution that combines NLP and fuzzy logic to provide results, developing a contextual understanding of what a user may be searching for. Fuzzy search references the underlying algorithms within OpenSearch.

Amazon Kendra is a highly accurate and easy-to-use enterprise search service that helps users discover information stored in the organization's vast content. It uses a deep learning semantic search model that is far more sophisticated than the fuzzy search algorithms mentioned above. As a result, you get a richer search experience that presents specific answers and related content to explore if you need more information.

With Amazon Kendra, you can:

• Create a unified search experience across multiple unstructured and structured content repositories.
• Utilize NLP to provide highly accurate answers.
• Deliver customized search results at lightning speeds, fine-tuned based on user behavior and more.

Amazon Kendra GenAI Index is a new index in Kendra designed for retrieval-augmented generation (RAG) to help enterprises build digital assistants and AI applications. This index offers high retrieval accuracy, leveraging advanced semantic models and the latest information retrieval technologies.

Get started with fuzzy search on AWS by creating a free account today.