4 ms·
On the other hand, computing Levenshtein distance is O(n^2), while the cosine approach is O(n).
by xyzzyz 11y ago
On the other hand, computing Levenshtein distance is O(n^2), while the cosine approach is O(n).
- nl 11y agoHmm 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 http://www.mit.edu/~andoni/papers/compEdit.pdf [2] https://en.wikipedia.org/wiki/Edit_distance#Improved_algorithms https://en.wikipedia.org/wiki/Edit_distance#Improved_algorit...
- danieldk 11y agoThis 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 https://github.com/danieldk/dictomaton