Edit distance

In order to transform one source string of text x[1 ? m] to a target string y[1 ? n], we can perform various transformation operations. Our goal is, given x and y, to produce a series of transformations that change x to y. We use an array z—assumed to be large enough to hold all the characters it will need—to hold the intermediate results. Initially, z is empty, and at termination, we should have z[j] = y[j] for j = 1, 2, ..., n. We maintain current indices i into x and j into z, and the operations are allowed to alter z and these indices. Initially, i = j = 1. We are required to examine every character in x during the transformation, which means that at the end of the sequence of transformation operations, we must have i = m + 1.

There are six transformation operations:

• Copy a character from x to z by setting z[j] ← x[i] and then incrementing both i and j. This operation examines x[i].

• Replace a character from x by another character c, by setting z[j] ← c, and then incrementing both i and j. This operation examines x[i].

• Delete a character from x by incrementing i but leaving j alone. This operation examines x[i].

• Insert the character c into z by setting z[j] ← c and then incrementing j, but leaving I alone. This operation examines no characters of x.

• Twiddle (i.e., exchange) the next two characters by copying them from x to z but in the opposite order; we do so by setting z[j] ← x[i + 1] and z[j + 1] ← x[i] and then setting i ← i + 2 and j ← j + 2. This operation examines x[i] and x[i + 1].

• Kill the remainder of x by setting i ← m + 1. This operation examines all characters inx that have not yet been examined. If this operation is performed, it must be the final operation.