Plain-text diff and formatted diff produce different results in what they consider was added.


I wondered about the following editing diff in a recent post of mine:

enter image description here

I clearly added a sentence to the end of the paragraph, but the diff thinks I added something between the three final words.


The plain-text diff shows a saner result: The edit is clearly a sentence added to the end:

enter image description here

share
1  
Also, the left-side version is shown to have a space before the final full stop. The site claims I'm plenking, which is a ridiculous accusation! –  Daniel Beck Dec 10 '11 at 20:15
    
Oh dear, you wouldn't ! –  slhck Dec 11 '11 at 10:15
    
For what it's worth, this recent change actually causes the expected diff for this example now (but as I said; it's a question of chance). –  balpha Feb 21 '13 at 14:10
    
@balpha Clearly, status-completed. Great answer on MSO btw. –  Daniel Beck Feb 21 '13 at 18:13

1 Answer 1

up vote 4 down vote accepted

To you and me, it's obvious that the diff engine didn't find the optimal solution here; however, to the computer it's not. Let's break this down to the simplest example. Consider you wrote this:

A B

and later edited it to be this:

A B A C B

(essentially, "A" is the word "Finder" and "B" is the word "running" in your case). Obviously, what we'd like to see the diff engine show is this, where the highlight means "this letter was added":

A B A C B

But what the diff engine gives us is this:

A B A C B

Both solutions are correct, and both solutions – as far as the diff engine is concerned – are equally good, since they both consist of "adding three letters" (in technical terms, they are both shortest edit scripts).

The diff algorithm guarantees to find one such shortest edit script, but it doesn't guarantee which one. It's pretty much a question of chance1.

Fixing this would pretty much mean using a different algorithm, which also (in some way) considers subsequent additions to be better than separated additions. This would have some drawbacks, though:

  1. It's guaranteed to have other edge cases. There will always be examples where a human being actually looking at the text will find a better diff than an algorithm. So we may fix this very example, but may just as well break another one.

  2. It will probably be slower. The diff algorithm we use has pretty good performance characteristics (if you're interested, here's the description of the algorithm; we're using a slightly modified version of this implementation), and we wouldn't like to give that up.

  3. Even setting 1. and 2. aside, this would mean quite some effort for something that works well in the 99% case. We're quite happy with the diff engine's work, especially after our recent improvements, and even though there are edge cases like the one you found, the diff is almost always good.

  4. The diff in your example is not an uncomprehensible mess. Sure, it's not what you'd expect, but it's a result we can live with. Not to forget that despite looking weird, it's actually correct2, and that you also have the choice of another diff view.

With those reasons in mind, I'll have to make this wontfix – it's just not worth it, sorry.


1 The algorithm is deterministic, so it's not truly random. But which of the solutions is found depends on many things, including what comes before and what comes after the content in question. If you actually run the diff engine over the ABACB example, for instance, it realy does find the "better" solution; if you run it over "ABC -> ABCBDC", it finds the "worse" solution.
2 The additional space before the period (you mention this in a comment) is somewhat related to this; the diff engine is set to be a bit lenient about whitespace, since this in most cases makes the diff more readable.

share
    
Almost expected that. Only thought we might have a leg to stand on since the plain text algorithm clearly gets it right. Thanks for the great response! –  Daniel Beck Dec 12 '11 at 13:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .