kousu
commented
2 years ago The matches would be improved, too, in our case by doing them case insensitively. So, e.g., rewrite difflib.get_close_matches to
--- /tmp/a 2021-10-16 19:36:44.887957974 -0400
+++ /tmp/b 2021-10-16 19:36:54.873261759 -0400
@@ -33,9 +33,9 @@
raise ValueError("cutoff must be in [0.0, 1.0]: %r" % (cutoff,))
result = []
s = SequenceMatcher()
- s.set_seq2(word)
+ s.set_seq2(word.lower())
for x in possibilities:
- s.set_seq1(x)
+ s.set_seq1(x.lower())
if s.real_quick_ratio() >= cutoff and \
s.quick_ratio() >= cutoff and \
s.ratio() >= cutoff:or if not using get_close_matches() directly but instead, say, using linear_sum_assignment(), at least make sure to call .lower() before computing the ratios. And another optimization -- effective for us but maybe not for every situation? -- is to write ratio() something like
def ratio(a,b):
if a == b: return 1.0
return SequenceMatcher(None, a, b).ratio()because we have a lot of exact matches and == is faster than SequenceMatcher
Another optimization might be to clamp pairs below a threshold to 0.0? Maybe that doesn't save any time though.
jcohenadad
I went down a rabbit hole and want to pin this idea in case someone wants to take it up later: optimal fuzzy matches between the gsheet and CCV databases (or potentially any other database formats we support in the future).
find_matching_ref()does a basic JOIN then uses a simple heuristic to handle rare conflicts:https://github.com/jcohenadad/bibeasy/blob/637635b5e14ccc30bf71a9af491a1e8484393864/bibeasy/utils.py#L163-L177
replace_ref_in_text()goes its own way and usesisin()to give a degree of toleration:https://github.com/jcohenadad/bibeasy/blob/637635b5e14ccc30bf71a9af491a1e8484393864/bibeasy/utils.py#L403-L405
Both work well enough because the data is fairly accurate, and
find_matching_refwarns about any data it doesn't understand so they can be manually corrected.As the database grows and time to maintain it shortens though this gets harder.
There's a generic solution to this in the literature: use
difflib.SequenceMatcher.ratio()(or another kind of fuzzy matcher; there's other metrics available infuzzywuzzy) to get a score for every pair of titles and pick the best. For example, you could directly replace the line infind_matching_refwith:which would then be able to tolerate misspellings, changes in capitalization, abbreviations, and punctuation variations. The current code will warn that all of these situations are "MISSED".
We can even match on multiple fields using this trick: average their scores:
sum(ratio(df_ccv[row,field],row[field]) for field in fields))/len(fields)(you could also play with using a weighted average, so that say the Publisher is worth half as much as the Year which is three-quarters as much as the Title. But to get that feature you need to rewritedifflib.get_close_matches().And we can do even better than that. So far what I've described allows for collisions; they are rare, but they can happen if the same article was published in multiple venues with small title variations. Optimally, we want a best guess for the complete database of what goes to what, with no redundant matchings. This is the Assignment Problem, and there's a solution here available as
scipy.optimize.linear_sum_assignment().