Anonymous user
User:Mwn3d/Levenshtein distance: Difference between revisions
Assumptions are wrong I think
m (rm debugging line) |
(Assumptions are wrong I think) |
||
Line 80:
}
}</lang>
: Part of the problem is that you're not actually computing the distance function correctly. For example, the Levenshtein distance between “stop” and “tops” is 2 (delete the “s” at the front and add an “s” at the end). Because you have to consider inserts and deletes even when the length is the same, you've got a much larger explosion of possibilities. OTOH, there's a <math>O(n^2)</math> algorithm that only has a linear amount of state; see the Tcl solution of the problem for how to do it. –[[User:Dkf|Donal Fellows]] 16:26, 13 January 2011 (UTC)
| |||