1
$\begingroup$

I am reading the 1989 paper called "An O(NP) Sequence Comparison Algorithm" by Wu, Manber, Myers, and Miller. The algorithm sounds like a good fit for a project I'm doing at work. I have found some implementations in my target language that I could reuse, but I want to make sure that I understand the algorithm (and the code) because it is so crucial to my project.

I am a ways into the paper, and seem to be understanding it, but there's something important in the abstract that still doesn't make sense to me. This is the relevant portion:

Let $A$ and $B$ be two sequences of length $M$ and $N$ respectively, where without loss of generality $N \ge M$, and let $D$ be the length of a shortest edit script between them. A parameter related to $D$ is the number of deletions in such a script, $P = D/2 - (N - M)/2$. We present an algorithm...

This relationship between $P$, $D$, $N$, and $M$ is not proven in the paper. And when a try using it with a simple example (turning "xy" into "x", for instance), I get a nonsensical answer. Can someone please explain the relationship?

Improve this question
$\endgroup$
2
  • $\begingroup$ Do you have a link to a free PDF of the paper? What kinds of operations do they allow in an edit script? insert, delete, and substitute? or only insert & delete? (I'd be inclined to suspect the latter....) $\endgroup$
    – D.W. ♦
    Commented Apr 27, 2016 at 19:42
  • $\begingroup$ I've linked to the paper. You're right: only inserts and deletes. $\endgroup$
    – sam.bishop
    Commented Apr 27, 2016 at 19:45

1 Answer 1

Reset to default
0
$\begingroup$

This is a straightforward consequence of the fact that the edit script only contains insert and delete operations. It follows from a little bit of basic arithmetic -- it's nothing especially deep.

Consider a script that contains $I$ insert operations and $P$ delete operations. Then the total number of operations in the edit script is $I+P$. If we're given that the total number of operations is $D$, we know $D=I+P$. Also we know $M+I-P=N$ (since each insert operation increases the length of the document, and each delete decreases it). Solving these two simultaneous equations yields the relationship you list.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you! I also think I understand why I was confused. You can only get from $M$ to $N$ with a simple non-zero $P$, zero $I$ example (such as "xy" -> "x") if $M$ is greater than $N$. But the authors have assumed that $N$ is larger than $M$, so that's impossible. It's unfortunate that the paper was written that way. $\endgroup$
    – sam.bishop
    Commented Apr 27, 2016 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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