An Introduction to Fuzzy Matching

As mentioned above, fuzzy matching is an approximate string-matching technique to programatically match similar data. Instead of simply looking at equivalency between two strings to determine if they are the same, fuzzy matching algorithms work to quantify exactly how close two strings are to one another. In doing so, they can help determine the likelihood that two different strings were actually meant to be equivalent. This is often done by incorporating edit distance.

Edit distance is a string metric. This metric provides a manner for detecting the closeness of two strings to one another by identifying the minimum number of alterations that must occur to transform one string into the other. Given the example at the beginning of this piece, “New York City” vs. “New Yolk City”, one can easily tell that simply switching a single letter in the second string (the “l” to an “r”) results in these two strings being the same. Meaning the edit distance is relatively low, and these two strings are very close to one another. In other words, there is a high likelihood that these strings were meant to be the same.

Fuzzy matching has multiple use cases, many of which we encounter on a regular basis. Type “New Yolk” into a GPS app, for example, and it’ll likely yield the suggestion “New York.” Slightly misspell a search term in your favorite search engine, and you’ll likely be provided with results for the term for which you actually meant to perform the search. In other words, implementations leveraging some form of fuzzy matching are all around us, and many times they mean the difference between a positive user experience and a negative one.

Now, let’s take a look at implementing fuzzy matching in Python, using the open source library FuzzyWuzzy.

Fuzzy Matching with Python FuzzyWuzzy

FuzzyWuzzy, an open source string matching library for Python developers, was first developed by SeatGeek to help decipher whether or not two similarly named ticket listings were for the same event. FuzzyWuzzy evaluates the Levenshtein distance (a version of edit distance that accounts for character insertions, deletions and substitutions) to make this possible. In addition, FuzzyWuzzy contains functionality for evaluating string similarity in other circumstances that we’ll touch on below.

Evaluating string similarity with the fuzz.ratio function

To evaluate two different strings using edit distance, we’ll use the fuzz.ratio function within FuzzyWuzzy’s fuzz module. This function returns a similarity score as a value between 0 and 100. The closer the value is to 100, the more similar the two strings are. For example, let’s compare two strings that are identical to one another:

from fuzzywuzzy import fuzz
value = fuzz.ratio('New York', 'New York')
print('value: ' + str(value))

Executing this script results in the following output:

value: 100

Now, let’s take a look at ‘New Yolk’ vs. ‘New York’ and see what is returned by the ‘ratio’ function:

value = fuzz.ratio('New Yolk', 'New York')
print('value: ' + str(value))

And here is the output:

value: 88

With just one difference in the relatively short strings of “New York” and “New Yolk”, the returned value falls from 100 to 88. Still, this value indicates that the two strings are highly similar to one another. As a final test, let’s replace ‘New Yolk’ with ‘New Zealand’. And compare this string to ‘New York’.

value = fuzz.ratio('New Zealand', 'New York')
print('value: ' + str(value))

This results in the following output:

value: 42

This lower value indicates a more significant difference between the two strings.

With that said, while fuzz.ratio works well in many situations, it may not be the best option for evaluating similarity between strings with partial matches. For this, FuzzyWuzzy contains the function partial_ratio that may be more applicable.

Ignoring token order in your evaluation

Now, let’s consider the situation in which two strings are provided in differing order. With FuzzyWuzzy, these can be evaluated to return a useful similarity score using the token_sort_ratio function.

value = fuzz.token_sort_ratio('To be or not to be', 'To be not or to be')

The above code returns a value of 100. Essentially, the two strings are tokenized, re-ordered in the same fashion, and evaluated using the fuzz.ratio function. This can prove useful in a variety of cases, including:

• Searching for a famous quote that has been accidentally typed in an incorrect order
• The case of SeatGeek, who were trying to aggregate tickets offered by multiple vendors whose description of the sporting event varied widely. 

Consider the following code snippet that also returns a value of 100:

value = fuzz.token_sort_ratio('Chiefs vs. Raiders', 'Raiders vs. Chiefs')

Wrapping up

The above functionality represents just a small subset of what FuzzyWuzzy has to offer. To further evaluate its functionality, check out the README, and give it a chance to see how it can help bolster your fuzzy matching implementation.

Although fuzzy matching is far from a perfect science, it can provide application developers with a starting point for cleansing cluttered datasets and developing a more resilient, versatile and intuitive user experience. Fine-tuning a fuzzy matching implementation will almost always require some serious thought, as well as a mixture of different fuzzy matching techniques. But, for any application that must evaluate user text input, or for a dataset in which duplicate entries are an ever-present problem, the juice is certainly worth the squeeze.

• To get started building your own fuzzy matching solution, sign up for a free ActiveState Platform account so you can download our Fuzzy Matching runtime environment and get started faster.

Related Reads

BERT vs ERNIE: The Natural Language Processing Revolution

Natural Language Processing: NLTK vs spaCy