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.
This article was published as a part of the Data Science Blogathon
Let us illustrate how the Levenshtein distance is calculated.
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’.
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’.
To compare two strings in python, we can run the following code:
The above code will give an output as ‘False’ as the two strings are not the same.
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 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.
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.
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 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:
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)
A. Fuzzy matching in regex Python is a technique used to match patterns in text data that are similar or partially match the target pattern. Fuzzy matching allows for variations in spelling, punctuation, and spacing in the text data. In Python, fuzzy matching can be achieved by using regular expressions and string distance functions like Levenshtein distance, Jaro-Winkler distance, or fuzzywuzzy library. The fuzzywuzzy library provides a set of functions for fuzzy string matching and can be used to find the best match among a set of possible matches.
A. Fuzzy matching and stemming are both techniques used in natural language processing, but they serve different purposes. Fuzzy matching allows for variations in spelling, punctuation, and spacing in the text data, while stemming is used to reduce words to their root or base form. Fuzzy matching is useful for matching similar or partially matching patterns, while stemming is useful for grouping words with the same root or meaning.
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.
Lorem ipsum dolor sit amet, consectetur adipiscing elit,