Problem
This code is meant to solve the problem in this software engineering question. To summarize the issue: given a set of strings that are sort of similar, but not similar enough to use regex upon, how would one get out a set of those "similar strings" amongst the "nonsimilar" strings? This is apparently called fuzzy matching strings, which I personally think is a fabulous name, but moving on. I looked around and hit upon the Jaro similarity as what seemed like a decently simple way to solve the problem. I'm particularly interested in seeing how the functions can be improved. It is written in Python 3.
Approach
First, in the match function, I convert each string into sets and find the intersection of the sets. Then, in the technical_match() function, I calculate the maximum distance to satisfy the requirements of the Jaro similarity, and then find the index of each item in the set of matches in each string, and subtract the two indices to find the distance. If this distance is less than the maximum distance, then it is a "true match" and is appended to a list of these.
Then, I calculate the number of transpositions necessary, i.e., given hello and jello, there are none necessary, because the strings produced when non-matches are stripped out are 'ello' and 'ello'. However, if I have 'cello' and 'ecllo', then it requires a transposition to switch c and e. I calculate this by producing a string from the match letters ordered as per their position in the actual string and then compare each for differences using diff_letters().
With these calculations in hand, I can then calculate the actual Jaro similarity, which is a pretty simple formula.
Finally, I created a fake file, foobar.txt, with some words, and open it, read it, split it by line breaks, and go through each and match to a pattern. If the Jaro similarity is greater than a certain constant, in this case 0.5 (the max, if both strings are the same, being 1, I believe), than that value is added to a list, and the list is printed at the end.
Code
import math
def match(s1, s2):
set_of_matches = set.intersection(set(s1), set(s2))
return set_of_matches
def technical_match(s1, s2):
matches = match(s1, s2)
max_distance = math.floor(max(len(s1), len(s2)/2)) - 1
true_list = []
for i in matches:
distance = abs(s1.index(i) - s2.index(i))
if distance <= max_distance:
true_list.append(i)
return true_list
def diff_letters(seq1, seq2):
return sum(1 for a, b in zip(seq1, seq2) if a != b)
def transpositions(s1, s2):
t = list(technical_match(s1, s2))
s1_list = []
s2_list = []
for i in s1:
if i in t:
s1_list.append(i)
for i in s2:
if i in t:
s2_list.append(i)
s1 = ''.join(s1_list)
s2 = ''.join(s2_list)
return diff_letters(s1, s2)
def jaro_similarity(s1, s2):
matches = len(technical_match(s1, s2))
if matches == 0:
return 0
else:
return 1/3*(matches/len(s1) + matches/len(s2) + (matches + transpositions(s1, s2))/matches)
match_text = open('foobar.txt', 'r').read().splitlines()
pattern = 'hat'
constant = .5
results = []
for i in match_text:
if jaro_similarity(i, pattern) > constant:
results.append(i)
print(results)
Fake text file and output
I used a file called foobar.text which contained
cheat
chat
choose
hat
hot
and ran the code on it (see here if you wish to run it) and received the output ['cheat', 'chat', 'hat', 'hot']
.
Review
I'd be glad to accept all comments, as I need all the improvement I can get in my coding style. I am fairly sure this works, as I've tested it on a variety of inputs, but if there's a bug that's slipped through, I apologize; I did my best implementing the Jaro similarity, but the wikipedia article was a tad bit confusing in places.
fuzzywuzzy
, could it suit your needs somehow? \$\endgroup\$fuzzywuzzy
package looks pretty nice (thank you for linking to it!) but I would prefer a review on my own code, I think. I'm also unsure which is the best algorithm here - is Jaro similarity sufficient? Is Levenshtein distance better? I don't know. \$\endgroup\$fuzzywuzzy
once or twice. \$\endgroup\$