3 ms·

Is there a comprehensive guide that explains the differences between the different libraries for fuzzy/approximate string matching? There is SymSpell, agrep, f

Is there a comprehensive guide that explains the differences between the different libraries for fuzzy/approximate string matching? There is SymSpell, agrep, fuzzywuzzy, closestmatch, fuzzysearch, fuzzyset, SimString, ukkonen and others in Github. The problem is I don't have a clue which one to use for each case, which are the cases and what are the differences between the libraries. A writeup illustrating several cases with a recommendation of a library and a practical example for each one would be very helpful. Btw, if anyone has experience with this type of stuff I would be interested in talking to you (mail is in profile).

deleted 7y ago
[deleted]
dmlittle 7y ago
There's also metaphone[1] for words that might sound similar but are spelled differently for when levenshtein might be too sensitive. For example, someone might have mistyped "berry" as "barry" but you don't want to match it against "terry" (both have a levenshtein distance of 1) [1] https://en.wikipedia.org/wiki/Metaphone https://en.wikipedia.org/wiki/Metaphone
- mjevans 7y ago
  Thanks, I was searching the comments to see if anyone suggested a phonetic variation. The default Linux spelling checker is usually good enough but sometimes I only remember how a word sounds and the close letter variations are clearly wildly incorrect, while asking a search engine or phone is able to figure out exactly the word I mean nearly all of the time.
totalperspectiv 7y ago
It's not exactly what you are looking for, but I did a blog post about the TRE regex engine which does approximate matching and included links to some other good blog posts: http://ducktape.blot.im/tre-a-regex-engine-with-approximate-matching http://ducktape.blot.im/tre-a-regex-engine-with-approximate-... Also, my favorite library for approx matching, which is heavy duty in some cases, is https://github.com/Martinsos/edlib https://github.com/Martinsos/edlib Which has python bindings and Nim binding among others.
anon1253 7y ago
I found the readme of https://github.com/tdebatty/java-string-similarity https://github.com/tdebatty/java-string-similarity particularly helpful, and of course the (Java) lib itself. It's not comprehensive by any means, but it gives a good starting point
taleinat 7y ago
Author of fuzzysearch here. Most of these libraries focus on calculating distance metrics between pairs of strings, or finding the nearest match to a string among many candidates. On the other hand, fuzzysearch is used for finding near matches to a string within much longer strings or texts. Common use cases are fuzzy searches in DNA sequences and long texts such as books and articles.

deleted 7y ago

[deleted]

dmlittle 7y ago

There's also metaphone[1] for words that might sound similar but are spelled differently for when levenshtein might be too sensitive. For example, someone might have mistyped "berry" as "barry" but you don't want to match it against "terry" (both have a levenshtein distance of 1) [1] https://en.wikipedia.org/wiki/Metaphone https://en.wikipedia.org/wiki/Metaphone

mjevans 7y ago
Thanks, I was searching the comments to see if anyone suggested a phonetic variation. The default Linux spelling checker is usually good enough but sometimes I only remember how a word sounds and the close letter variations are clearly wildly incorrect, while asking a search engine or phone is able to figure out exactly the word I mean nearly all of the time.

totalperspectiv 7y ago

It's not exactly what you are looking for, but I did a blog post about the TRE regex engine which does approximate matching and included links to some other good blog posts: http://ducktape.blot.im/tre-a-regex-engine-with-approximate-matching http://ducktape.blot.im/tre-a-regex-engine-with-approximate-... Also, my favorite library for approx matching, which is heavy duty in some cases, is https://github.com/Martinsos/edlib https://github.com/Martinsos/edlib Which has python bindings and Nim binding among others.

anon1253 7y ago

I found the readme of https://github.com/tdebatty/java-string-similarity https://github.com/tdebatty/java-string-similarity particularly helpful, and of course the (Java) lib itself. It's not comprehensive by any means, but it gives a good starting point

taleinat 7y ago

Author of fuzzysearch here. Most of these libraries focus on calculating distance metrics between pairs of strings, or finding the nearest match to a string among many candidates. On the other hand, fuzzysearch is used for finding near matches to a string within much longer strings or texts. Common use cases are fuzzy searches in DNA sequences and long texts such as books and articles.