News for hackers. Stuff that matters.
Re:Fuzzy string matching using cosine similarity by nl on Monday September 21, 2015 @05:35AM (#10251228)
This is nice, but a better measure of string similarly is an edit count based measure. See Levenshtein distance for example: https://en.m.wikipedia.org/wiki/Levenshtein_distance
Re:Fuzzy string matching using cosine similarity by xyzzyz on Monday September 21, 2015 @07:58AM (#10251619)
On the other hand, computing Levenshtein distance is O(n^2), while the cosine approach is O(n).
Re:Fuzzy string matching using cosine similarity by danieldk on Monday September 21, 2015 @09:50AM (#10252223)
This very topic was discussed yesterday. For a given word, you can construct an automaton that matches that word within a certain edit distance in O(n) where n is the length of the word. Since the result is a DFSA, you can also see if a string matches in O(n). (See the work of Schulz & Mihov.)

Moreover, rather than going over each word in a dictionary to find out whether that word is within a certain distance, you can compute the intersection language of the Levenshtein automaton and the dictionary automaton (which is generally faster, intersection is O(mn) in the number of states of the two automata).

For an implementation of this and more, see:

https://github.com/danieldk/dictomaton

Re:Fuzzy string matching using cosine similarity by nl on Monday September 21, 2015 @08:13AM (#10251657)
Hmm true - very good point.

Worth noting that for short strings this is unlikely to matter.

There is [1], titled APPROXIMATING EDIT DISTANCE IN NEAR-LINEAR TIME. Wikipedia also has a reference[2] for better time complexity versions.

I haven't explored these though.

[1] http://www.mit.edu/~andoni/papers/compEdit.pdf

[2] https://en.wikipedia.org/wiki/Edit_distance#Improved_algorit...