Anonymous user
User:Mwn3d/Levenshtein distance: Difference between revisions
no edit summary
(Assumptions are wrong I think) |
No edit summary |
||
Line 82:
: 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)
: There's also a far greater number of insertion possibilities than what you have here. You could insert any character from "b" at any position in "a" (including before the start of "a"). --[[User:Paul.miner|Paul.miner]] 16:59, 13 January 2011 (UTC)
| |||