# Length of an Edit Script and the Number of Deletions

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?

• 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....) – D.W. Apr 27 '16 at 19:42
• I've linked to the paper. You're right: only inserts and deletes. – sam.bishop Apr 27 '16 at 19:45

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.

• 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. – sam.bishop Apr 27 '16 at 20:16