### What does fuzzy mean?

Fuzzy means some thing that is not clear, usually because of other unwanted noises. Typos while searching can be termed as fuzzy too. But wouldn’t it be great if the computer could correct you mistakes or perhaps present you result that you might have wanted to type in?

Yes, such technology exists, and we use it every day, for e.g. all search engines like Google, Bing etc. With Elasticsearch, we can now include these features into our own application for better user experience. In Elasticsearch there is something called fuzzy search, which is the topic of the discussion.

##### What is fuzzy search?

Elasticsearch’s Fuzzy query is a powerful tool for a multitude of situations. Username searches, misspellings, and other funky problems can often be solved with this unconventional query.

Lucene, the technology underlying Elasticsearch, is a swiss-army knife composed of many text processing tools. Some of these tools, like the Snowball stemmer and the Metaphone phonetic analyzer, are quite sophisticated. Other tools are very basic, like the prefix query type. Fuzzy queries sit somewhere in the middle of this toolchest in terms of sophistication; they find words that need at most a certain number of character modifications, known as ‘edits’, to match the query. For instance, a fuzzy search for ‘ax’ would match the word ‘axe’, since only a single deletion, removing the ‘e’, is required to match the two words.

Let us dive into the internals of Lucene’s FuzzyQuery.

##### Determining Edit Distance

The metric used by fuzzy queries to determine a match is the Damerau-Levenshtein distance formula. Simply put, the Damerau-Levenshtein distance between two pieces of text is the number of insertions, deletions, substitutions, and transpositions needed to make one string match the other. As an example, the Levenshtein distance between the words “ax” and “axe” is 1 due to the single deletion required.

The Damerau-Levenshtein distance formula is a modification of the classic Levenshtein distance formula, altering it by adding transposition as a valid operation. Both formulas are supported, with Damerau-Levenshtein being the default, and classic Levenshtein being selectable by setting transpositions to false in the query. The utility of transpositions can be seen in the case of comparing the strings ‘aex’ and ‘axe’. When using the classic Levenshtein distance formula, ‘aex’ is not one, but two edits away; the ‘e’ must be deleted, after which a new ‘e’ is inserted in the proper place, while in Damerau-Levenshtein, a single operation, swapping the ‘e’ and the ‘x’, suffices. Extrapolating out from this, using classic Levenshtein would mean that ‘aex’ is as far away from ‘axe’ as ‘faxes’ is; an example showing why Damerau-Levenshtein makes greater intuitive sense in most cases.

When dealing with fuzzy searches, it is vital to understand that in elasticsearch text is first run through an analyzer before being made available for search. When data is indexed it is processed into what are known as ‘terms’, the actual searchable units in the database. It is the analyzed terms, not the actual stored documents that are searched. That means that when performing fuzzy queries, the query text may be compared to an unanticipated term value as a result of analysis, leading to sometimes confusing results. This also means that if synonyms are enabled on a field the synonyms may be matched, even if that word does not appear at all in the source text. This can cause quite a bit of confusion, and for this reason, it often makes sense only to use the simple analyzer on text intended for use with fuzzy queries, possibly disabling synonyms as well.

##### The Different Types of Fuzzy Searches

match query + fuzziness option:
{
“query”: {
“match”: {
“name”: {
“query”: “Vacuummm”,
“fuzziness”: 2,
“prefix_length”: 1,
“max_expansions”: 100,
“transpositions”:true
}
}
}
}

fuzziness: The value of fuzziness can be 0, 1, 2, AUTO
prefix_length: The number of initial characters which will not be “fuzzified”. This helps to reduce the number of terms which must be examined. Defaults to 0. If the value is greater then 0 then the typos in the prefix will be ignored. This value must be set to users requirements as 0 prefix_length might cause performance issues.
max_expansions: The maximum number of terms that the fuzzy query will expand to. Defaults to 50. This simply means that only 50 terms will be fuzzied and rest will be ignored.
Using a higher number might cause slowness, using a lower number might not produce desired results. It is to be tuned to users requirements.
transpositions: Whether fuzzy transpositions (ab → ba) are supported. Default is false.

This type of query is highy preferred instead of other fuzzy query. However users are not restricted tu use other fuzzy query.
fuzzy query:
{ “query”: {
“fuzzy” : { “user” : “ki” }
}
}

This type of query is generally not preferred.
fuzzy_like_this/fuzzy_like_this_field:
A more_like_this query, but supports fuzziness, and has a tuned scoring algorithm that better handles the characteristics of fuzzy matched results.
In the latest versions of elastic search is this is removed, instead it is recommended to use fuzziness parameter in a more like this query.
suggesters: Suggesters are not an actual query type, but rather a separate type of operation (internally built on top of fuzzy queries) that can be run either alongside a query, or independently. Suggesters are great for ‘did you mean’ style functionality. Please check elastic search documentation for further understanding.

##### Performance Considerations

Even though Lucene’s Levenshtein distance implementation is state of the art, and quite fast, it is still much slower than a plain match query. The runtime of the query grows with the number of unique terms in the index. That is to say, when performing a fuzzy search the main criteria is not how many documents will be returned, but how many unique terms across the cluster there are for the fields being searched. If there are 100 documents with 10,000 unique words apiece, searching that index will be slower than searching 10,000 documents where the field being searched only has 100 unique words.