Anonymous user
User:Mwn3d/Levenshtein distance: Difference between revisions
m
no edit summary
m (rm debugging line) |
mNo edit summary |
||
| (5 intermediate revisions by 3 users not shown) | |||
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)
::I realize this isn't the best algorithm. I was doing this more as an exercise. Thanks for your hints about stop/tops, though. That will be a helpful test case (maybe it should be added ot the task page). --[[User:Mwn3d|Mwn3d]] 18:15, 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)
::Thinking about it before i fell asleep last night I realized that I forgot inserting at the start. I guess I will have to re-work some things. Also, I bet the D recursive solution is wrong just like this one is. Thanks for your help. --[[User:Mwn3d|Mwn3d]] 18:15, 13 January 2011 (UTC)
{{tag|subproperty}}
{{tag|property}}
{{#show: User:Mwn3d/Levenshtein distance | tag}}
| |||