Fuzzy matching treats two words that are “fuzzily” similar as if they were the same word. First, we need to define what we mean by fuzziness.
In 1965, Vladimir Levenshtein developed the Levenshtein distance, which measures the number of single-character edits required to transform one word into the other. He proposed three types of one-character edits:
- Substitution of one character for another: _f_ox → _b_ox
- Insertion of a new character: sic → sic_k_
- Deletion of a character: b_l_ack → back
Frederick Damerau later expanded these operations to include one more:
- Transposition of two adjacent characters: _st_ar → _ts_ar
For example, to convert the word
beaver requires the
b: bie_b_er → bie_v_er
i: b_i_ever → b_a_ever
e: b_ae_ver → b_ea_ver
These three steps represent a Damerau-Levenshtein edit distance of 3.
bieber is a long way from
beaver—they are too far apart to be
considered a simple misspelling. Damerau observed that 80% of human
misspellings have an edit distance of 1. In other words, 80% of misspellings
could be corrected with a single edit to the original string.
Elasticsearch supports a maximum edit distance, specified with the
parameter, of 2.
Of course, the impact that a single edit has on a string depends on the
length of the string. Two edits to the word
hat can produce
allowing two edits on a string of length 3 is overkill. The
parameter can be set to
AUTO, which results in the following maximum edit distances:
0for strings of one or two characters
1for strings of three, four, or five characters
2for strings of more than five characters
Of course, you may find that an edit distance of
2 is still overkill, and
returns results that don’t appear to be related. You may get better results,
and better performance, with a maximum