Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search
 

[REBOL] Re: Edit Distance Function?

From: greggirwin:mindspring at: 17-Jul-2002 14:44

Hi Gary, << Has anyone out there written an edit distance function in Rebol they would be willing to share. >> I just hacked this up, and tested it only very lightly. You can use it, in trade for testing it for me. :) I could write a much better version given some time, but going off the references I found, this came together quickly. It's going to be slow though, and has high space complexity. A better version will take a little more time, which I don't have much of at the moment. If you can verify that this works correctly, then I can use it as a reference for future development of an improved version. edit-distance: func [s1 s2 /local x y z] [ c: array/initial reduce [1 + length? s1 1 + length? s2] 0 x: y: z: 0 repeat i 1 + length? s1 [c/:i/1: i] repeat j 1 + length? s2 [poke c/1 j j] for i 2 1 + length? s1 1 [ for j 2 1 + length? s2 1 [ x: 1 + pick pick c i - 1 j y: 1 + pick pick c i j - 1 either s1/:i = s2/:j [ z: pick pick c i - 1 j - 1 ][ z: 1 + pick pick c i - 1 j - 1 ] poke c/:i j min min x y z ] ] subtract last last c 1 ] edit-distance "Gregg" "Greg" edit-distance "Gregg" "Gary" edit-distance "Gregg" "Hirschberg" --Gregg