[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