- #1

- 1,231

- 0

I have a need to compute a "difference" between two strings A and B. The idea is that B is similar to A, except it has had operations of string deletion and string insertion performed on it. An operation of deletion transforms a string xyz into a string xz (x, y, z being strings) and an operation of insertion transforms a string xz into a string xyz.

What I want is an input of A and B, where A is fairly similar to B, and an output which is a series of deletion and insertion operations that transforms A into B. Hopefully this will be a shortest series, but reasonably close is good enough.

Any idea where I should look for information on this before I try to hack something up?

edit: actually I hadn't really done enough looking, 10 more seconds of time brings me to the Levenshtein distance. Though this isn't exactly what I want since I'd rather be able to say "insert the string 'abcdxyzqrstuvqwertyz' at character position 900" than have to give that as 20 different character insertions.

edit2: Perhaps I'm basically looking to implement a custom version of unix's "diff" that goes character-by-character and not line-by-line. Unless "diff" works by treating lines as single symbols, in which case that's not what I need.

edit3: I could be more specific on the criterion I want for "shortest series of insertions and deletions." What I mean is roughly, let an insertion be denoted by a string +n,k,[s1..sk] where n is a number indicating the position of the first character to be inserted, k is the number of characters that follow, and s1..sk are the characters to be inserted. Similarly a deletion can be denoted by a string -n,k where k is the # of characters after position n to be deleted. I want to roughly minimize the total length of the descriptions of all insertions and deletions required to transform A into B. To simplify the problem, you could similarly assume that the cost of an insertion is p + L where L is the length of the inserted string, and p is a small "penalty" constant, and the cost of a deletion is p.

What I want is an input of A and B, where A is fairly similar to B, and an output which is a series of deletion and insertion operations that transforms A into B. Hopefully this will be a shortest series, but reasonably close is good enough.

Any idea where I should look for information on this before I try to hack something up?

edit: actually I hadn't really done enough looking, 10 more seconds of time brings me to the Levenshtein distance. Though this isn't exactly what I want since I'd rather be able to say "insert the string 'abcdxyzqrstuvqwertyz' at character position 900" than have to give that as 20 different character insertions.

edit2: Perhaps I'm basically looking to implement a custom version of unix's "diff" that goes character-by-character and not line-by-line. Unless "diff" works by treating lines as single symbols, in which case that's not what I need.

edit3: I could be more specific on the criterion I want for "shortest series of insertions and deletions." What I mean is roughly, let an insertion be denoted by a string +n,k,[s1..sk] where n is a number indicating the position of the first character to be inserted, k is the number of characters that follow, and s1..sk are the characters to be inserted. Similarly a deletion can be denoted by a string -n,k where k is the # of characters after position n to be deleted. I want to roughly minimize the total length of the descriptions of all insertions and deletions required to transform A into B. To simplify the problem, you could similarly assume that the cost of an insertion is p + L where L is the length of the inserted string, and p is a small "penalty" constant, and the cost of a deletion is p.

Last edited: