The two strings
t are compared starting from the high index,
down to index
1. This is not visible since the initial call to
string_compare is not provided. The
j arguments for that
initial call are the length of strings
It should be noted that
t could be globals, since they are
the same in all calls.
A call to the function
string_compare(s,t,i,j) is intended to
compute the minimum edit distance of the prefixes
It first compares the two strings at indices
j, and the
recursively at lower indices.
It always tries 3 ways of finding the shortest distance:
by assuming there was a match or a susbstitution edit depending on
by assuming there is an insertion edit of
by assuming there is an deletion edit of
Then it computes recursively the sortest distance for the rest of both
strings, and adds 1 to that result, when there is an edit on this call.
s[i]==t[j] the two strings match on these indices. Hence the
corresponding indices are both decremented, to recursively compute the
shortest distance of the prefixes
proper match does not increase the distance. Hence
s[i]=/=t[j] the two strings do not match, but can be made to
match by a substitution edit. Hence the same recursive call is
possible, but the resulting shortest distance must be incremented by
one for the substitution edit. Hence dist(
That is why the function match returns
0 when there is a match, and
1 when there is none.
Another possibility is not to try for a match, but assume that
is due to an insertion edit in the case of the smallest distance.
Hence that inserted symbol is ignored by replacing
t[1..j-1], ie by computing the shortest distance of
t[1..j-1], which is
string_compare(s,t,i,j-1), and then adding
for the insertion edit.
The next and last try is the symmetric one, when one assume that the
s[i] was deleted, and thus does not have to appear in
The results of the 3 attempts are strored in the array
opt, and the
smallest value of the 3 is kept as shortest distance for
The decrementations of indices is either because the corresponding
string elements match, or because they have been taken into account by
an edit operation.