1
$\begingroup$

I'm having some trouble understanding part of Skienna's algorithm for edit distance presented in his Algorithm Design Manual. I'm posting the recursive version, prior to when he applies dynamic programming to the problem, but my question still stands in that version too I think.

He provides the following code:

#define MATCH       0
#define INSERT      1
#define DELETE      2

int match(char c, char d)
{
    if (c == d) return(0);
    else return(1);
}

int indel(char c)
{
    return(1);
}

int string_compare(char *s, char *t, int i, int j)
{
        int k;                  /* counter */
        int opt[3];             /* cost of the three options */
        int lowest_cost;        /* lowest cost */

        if (i == 0) return(j * indel(' '));
        if (j == 0) return(i * indel(' '));

        opt[MATCH] = string_compare(s,t,i-1,j-1) + match(s[i],t[j]);
        opt[INSERT] = string_compare(s,t,i,j-1) + indel(t[j]);
        opt[DELETE] = string_compare(s,t,i-1,j) + indel(s[i]);

        lowest_cost = opt[MATCH];
        for (k=INSERT; k<=DELETE; k++)
                if (opt[k] < lowest_cost) lowest_cost = opt[k];

        return( lowest_cost );
}

I am having trouble understanding the logic behind how the indices are decremented when arriving at opt[INSERT] and opt[DELETE]. They seem backwards to me.

How can I prove to myself that they are correct?

$\endgroup$
  • $\begingroup$ The code fragment you've posted doesn't make sense on its own. None of MATCH, INSERT, DELETE, match(), indel() is defined, for example. $\endgroup$ – David Richerby Mar 21 '15 at 17:31
  • $\begingroup$ @DavidRicherby Thanks for the head's up-- the missing code is added. $\endgroup$ – Chris Mar 21 '15 at 17:36
  • 1
    $\begingroup$ Do you understand the underlying recurrence relation, as seen e.g. here? See also this similar question here. (duplicate?) $\endgroup$ – Raphael Mar 21 '15 at 17:57
  • $\begingroup$ @Raphael It's the intuition on the recurrence relationship that I'm missing. How can I gain the intuition that the way the indices are decremented in the recursive calls to string_compare are correct? $\endgroup$ – Chris Mar 21 '15 at 18:31
  • 1
    $\begingroup$ @DavidRicherby I think that the 3 lines of code at the end, including an array, a for loop and a conditional to compute the smallest of three integers is a real achievement. This said, I hate reading code. $\endgroup$ – babou Mar 21 '15 at 22:18
2
$\begingroup$

The two strings s and 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 i and j arguments for that initial call are the length of strings s and t.

It should be noted that s and 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 s[1..i] and t[1..j]. It first compares the two strings at indices i and j, and the recursively at lower indices.

It always tries 3 ways of finding the shortest distance:

  1. by assuming there was a match or a susbstitution edit depending on whether s[i]==t[j];

  2. by assuming there is an insertion edit of t[j];

  3. by assuming there is an deletion edit of s[i];

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.

When 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 s[1..i-1] and t[1..j-1]. A proper match does not increase the distance. Hence dist(s[1..i],t[1..j])= dist(s[1..i-1], t[1..j-1]).

When 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(s[1..i],t[1..j])= dist(s[1..i-1], t[1..j-1])+1.

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 t[j] is due to an insertion edit in the case of the smallest distance. Hence that inserted symbol is ignored by replacing t[1..j] by t[1..j-1], ie by computing the shortest distance of s[1..i] and t[1..j-1], which is string_compare(s,t,i,j-1), and then adding 1 for the insertion edit.

The next and last try is the symmetric one, when one assume that the symbol s[i] was deleted, and thus does not have to appear in t.

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 s[1..i] and t[1..j].

The decrementations of indices is either because the corresponding string elements match, or because they have been taken into account by an edit operation.

$\endgroup$
  • $\begingroup$ That is helpful although I still feel that my understanding is shakey. Do you know of any good resources to accelerate feeling comfortable with problems like this? Or is it instead just a matter of putting in the time studying? $\endgroup$ – Chris Mar 22 '15 at 18:50
  • $\begingroup$ I am not sure what your problem is. Is it this specific problem, before even using dynamic programming. I do not know where there would be any resource to help that, other than working on it or asking more specific questions. The basic idea here is jsut to find the best editing strategy (with smallest number of edits) by exploring all possible editing strategies and computing the cost of each, keeping only the smaller cost. It is simply expressed as a recursive exploration. Regarding dynamic programming, you will find many testbooks on algorithmics. $\endgroup$ – babou Mar 22 '15 at 21:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.