[REBOL] Re: Edit Distance Function?
From: greggirwin:mindspring at: 24-Jul-2002 14:30
Hi Gary,
This version should work correctly, but I don't like the solution. The block
of count values is offset, by -1, from the index of the elements you're
comparing. Since REBOL is good for humans, and doesn't use 0 to n-1 series
indexes, I started checking the series at element 2, so the first char was
skipped. By adding a dummy element to the head of each series, we can trick
it. Not a great solution, but until I have more time...
--Gregg
REBOL []
edit-distance: func [s1 s2 /local x y z] [
; Insert matching dummy elements at the head of each series
s1: head insert copy s1 " "
s2: head insert copy s2 " "
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
]
if not system/script/args [
;edit-distance "Gregg" "Greg"
;edit-distance "Gregg" "Gary"
;edit-distance "Gregg" "Hirschberg"
;edit-distance "abcdefghijkl" "bcdeffghixkl"
etest: func [arg1 arg2] [
print [arg1 " / " arg2 " / " (edit-distance arg1 arg2)]
]
print now/time
etest "a" "b"
etest "am" "at"
etest "I" "I"
etest "i" "I"
etest "Gregg" "Greg"
etest "Gregg" "Gary"
etest "Gregg" "Hirschberg"
etest "Do you enjoy fishing" "Do you like to fish"
etest "Do you enjoy fishing" "Do you like to hunt"
etest "how are you" "how are you today"
etest "how have you been" "how've you been"
etest "how much was it" "how much did it cost"
etest "how much was it" "how much did you pay for it"
etest "how old are you" "how old're you now"
etest "I'm broke" "I'm busted"
etest "I'm broke" "I'm out of money"
etest "I'm trying to quit" "I am trying to quit!"
etest "I'm trying to quit" "I'm attempting to quit"
etest "I'm trying to quit" "I'd like to quit"
etest "I'm trying to quit" "I want to stop"
etest "Let's take a break" "Let's take a breather"
etest "Let's take a walk" "Let's go for a walk"
etest "That's good!" "That's bad!"
etest "That's good!" "That fantastic"
etest "That's stupid" "That sucks!"
etest "the" "teh"
etest "what're you having for lunch today" "what are you eating for
lunch"
etest "what're you having for lunch today" "what're you going to have
for lunch today"
etest "what day is it" "hat day is it"
etest "what is you name" "what's your name"
etest "what time is it" "what is the time"
etest "what time is it" "what time is it now"
etest "what time is it" "whattimeisit"
etest "what time is it" "what time was it"
etest "where do you live?" "Where do yo reside"
etest "you're crazy" "you are crazy"
etest "you're crazy" "you must be crazy"
etest "abcdefghijkl" "bcdeffghixkl"
print now/time
halt
]