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).
[ Parent
| on HN ]
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:
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...