Fuzzy String Matching – A Hands-on Guide

Introduction

Fuzzy string matching, also known as fuzzy matching, is the technique of finding strings that match with a given string partially and not exactly. When a user misspells a word or enters a word partially, fuzzy string matching helps in finding the right word – as we see in search engines.

The algorithm behind fuzzy string matching does not simply look at the equivalency of two strings but rather quantifies how close two strings are to one another. This is usually done using a distance metric known as ‘edit distance’. This determines the closeness of two strings by identifying the minimum alterations needed to be done to convert one string into another. There are different types of edit distances that can be used like Levenshtein distance, Hamming distance, Jaro distance, etc.

In this article, you will explore fuzzy matching in Python, focusing on fuzzy string matching techniques. We will discuss libraries like FuzzyWuzzy, which simplify the process of identifying approximate string matches, making data handling more efficient. You’ll learn practical applications and examples to enhance your programming skills.

This article was published as a part of the Data Science Blogathon

What is Fuzzy String Matching?

Fuzzy string matching is like finding similar things, even if they aren’t exactly the same. It’s used to find misspelled words, similar names, or even close matches in DNA sequences. It’s like saying, “These things are close enough!

Let us illustrate how the Levenshtein distance is calculated.

Example 1:

String 1 = ‘Put’

String 2 = ’Pat’

Levenshtein distance would be 1 as we can convert string 1 to string 2 by replacing  ‘u’ with ‘a’.

Example 2:

String 1 = ‘Sun’

String 2 = ‘Saturn’

Levenshtein distance would be 3 as we can convert string 1 to string 2 by 3 insertions – ‘a’, ’t’ and ‘r’.

Fuzzy String Matching in Python:

Comparing Strings in Python

To compare two strings in python, we can run the following code:

Str1 = "Back"
Str2 = "Book"
Result = Str1 == Str2
print(Result)

The above code will give an output as ‘False’ as the two strings are not the same.

Levenshtein distance in Python

Levenshtein distance in Python using the ‘Levenshtein’ python package.

import Levenshtein as lev
Str1 = "Back"
Str2 = "Book"
lev.distance(Str1.lower(),Str2.lower())

The above code will give an output of 2 we can convert string 1 to string 2 by 2 replacements.

FuzzyWuzzy in Python

FuzzyWuzzy is a python package that can be used for string matching. We can run the following command to install the package –

pip install fuzzywuzzy

Just like the Levenshtein package, FuzzyWuzzy has a ratio function that calculates the standard Levenshtein distance similarity ratio between two sequences.

from fuzzywuzzy import fuzz
Str1 = "Back"
Str2 = "Book"
Ratio = fuzz.ratio(Str1.lower(),Str2.lower())
print(Ratio)

The output of the following code gives 50 as the Levehshtein ratio is calculated by dividing the Levenshtein distance by the maximum of the length of the string1 and string 2.

Let us calculate the ratio for another set of strings.

from fuzzywuzzy import fuzz
Str1 = "My name is Ali"
Str2 = "Ali is my name"
Ratio = fuzz.ratio(Str1.lower(),Str2.lower())
print(Ratio)

The output of the code gives 50 indicating that even though the words are the same, the order of the words matters while calculating the ratio.

Partial Ratio using FuzzyWuzzy

The partial ratio helps us to perform substring matching. This takes the shortest string and compares it with all the substrings of the same length.

Str1 = "My name is Ali"
Str2 = "My name is Ali Abdaal"
print(fuzz.partial_ratio(Str1.lower(),Str2.lower()))

The output of the code gives 100 as partial_ratio() just checks if either string is a substring of the other.

This ratio could be very useful if, for example, we are trying to match a person’s name between two datasets. In the first dataset, the string has the person’s first and last name, and in the second dataset, the string has the person’s first, middle, and last name. The ratio would be 100 because the first string is a substring in the second string.

Token Sort Ratio using FuzzyWuzzy

In token sort ratio, a method used in fuzzy string matching, the strings are tokenized and pre-processed by converting to lower case and getting rid of punctuation. The strings are then sorted alphabetically and joined together. Post this, the Levenshtein distance similarity ratio is calculated between the strings.

Str1 = "My name is Ali"
Str2 = "Ali is my name"
print(fuzz.token_sort_ratio(Str1,Str2))

The output of the code gives 100 as the token sort ratio is found after sorting the strings alphabetically and hence the original order of words doesn’t matter.

Token Set Ratio using FuzzyWuzzy

Token set ratio performs a set operation that takes out the common tokens instead of just tokenizing the strings, sorting, and then pasting the tokens back together. Extra or same repeated words do not matter.

Str1 = "My name is Ali"
Str2 = "Ali is my name name"
print(fuzz.token_sort_ratio(Str1,Str2))
print(fuzz.token_set_ratio(Str1,Str2))

The output of the token sort ratio comes to be 85 while that of the token set ratio comes to be 100 as the token set ratio doesn’t take into account the repeated words.

Let us illustrate another example for the token set ratio for a deeper explanation.

Str_A = 'Read the sentence - My name is Ali' 
Str_B = 'My name is Ali'
ratio = fuzz.token_set_ratio(Str_A, Str_B)
print(ratio)

The output of the above code gives us 100. This is because, under the hood, the token set ratio has a more flexible approach. After it takes out the common strings (‘My name is Ali’), it finds out the fuzz ratio for the following pairs and then returns the maximum value amongst the three:

• common string and the common string with the remainder of string one
• common string and the common string with the remainder of string two
• common string with the remainder of one and common string with the remainder of two

Process Module using FuzzyWuzzy

If we have a list of strings and we want to find the closest matching string from the list with a given string, we can leverage the ‘process’ module.

from fuzzywuzzy import process
query = 'My name is Ali'
choices = ['My name Ali', 'My name is Ali', 'My Ali']  
# Get a list of matches ordered by score, default limit to 5
process.extract(query, choices)

If we want to extract out the top match, we can run the following code:

process.extractOne(query, choices)

About Author

Nibedita Dutta

Nibedita completed her master’s in Chemical Engineering from IIT Kharagpur in 2014 and is currently working as a Senior Consultant at AbsolutData Analytics. In her current capacity, she works on building AI/ML-based solutions for clients from an array of industries.

Nibedita Dutta

Nibedita completed her master’s in Chemical Engineering from IIT Kharagpur in 2014 and is currently working as a Senior Data Scientist. In her current capacity, she works on building intelligent ML-based solutions to improve business processes.