Anonymous user
User talk:Dingowolf: Difference between revisions
→Levenshtein distance, recursive D solution: Thanks
(→Levenshtein distance, recursive D solution: new section) |
|||
| (One intermediate revision by one other user not shown) | |||
Line 10:
Did you test it with both of the test cases I listed in the broken Java version? Did you change the algorithm at all? What did i do wrong? --[[User:Mwn3d|Mwn3d]] 01:18, 13 January 2011 (UTC)
:I test the recursive version with D library Levenshtein distance function, it pass some short random string samples. I think my algorithm is almost the same as yours, except :
:#I don't use the hash/dict '''mem''', it seems not need;
:#The insertion should be from both left and right direction, and each direction should have '''1 plus length of shorter string''' numbers of insertions/candidates, eg. if input are "'''ab'''", "'''12345'''",
:::*the left-insert candifates are : '''1'''ab, a'''2'''b, ab'''3''',
:::*the right-insert candifates are : ab'''5''', a'''4'''b, '''3'''ab.
:But I can't test long strings input, it cost a lot of time.
:bye :) [[User:Dingowolf|dingowolf]] 04:00, 13 January 2011 (UTC)
::Good thoughts. The "mem" thing was leftover from me trying to memoize it. It also helped debug some earlier problems. I'll try out your suggestions eventually and see what happens. Thanks. --[[User:Mwn3d|Mwn3d]] 04:22, 13 January 2011 (UTC)
| |||