20

Disclaimer: I know nothing about diff algorithms. If what we have now is the best there is, I apologize in advance.

Sometimes (read: oftentimes) the diff highlighting in the revision history is really weird. For example:

Now in order to save one : the system interprets the entire link as having been removed and replaced, instead of the understanding that all that was added was "available here:"

Or how about this one, from one of SO's all time favorites:

enter image description here

Now, it could have realized that what was really important was the sentence underlined in blue. Instead, it chose to take (seemingly random) chunks from different parts of the paragraph. (You could possibly argue that it took the wrong HTML and is not a because it looked for the first occurrence of that string, but that reason fails to explain why it selected things after the actual target sentence.)

One more:

enter image description here

Not knowing anything about diffs, if it was possible to have a word match together with the punctuation following it, without the punctuation being necessary for the match, that would solve most of the punctuation problems. For the example in the question that Jeff brought), the : would be considered an optional part of the previous word ("get"). Right now it seems like it deliberately ignores an immediately following punctuation mark and goes for the next available one.

In order to better see and understand what was changed in revision history, is it possible to get a better diff algorithm implemented? If not, could someone at least explain to me why it works like this?

Improve this question
14
  • 2
    see meta.stackexchange.com/questions/111252/…
    – Jeff Atwood
    May 17, 2012 at 4:30
  • 2
    Ahh, thanks! That does explain some things. I searched for related problems, but missed that one, which is easily the most relevant. Hmm, sounds like another feature-request. :)
    – Hod - Monica's Army
    May 17, 2012 at 4:48
  • 4
    Note that switching to side-by-side source diffs (this icon) can often make a dramatic difference in the results. If you're having trouble understanding an edit visually in the default rendered diffs, try switching to source.
    – Shog9
    May 17, 2012 at 5:16
  • 1
    @Shog9 That does help some, but just check out the source diff for the regex answer. Same problem, albeit less extreme.
    – Hod - Monica's Army
    May 17, 2012 at 5:19
  • 1
    Another nice read from balpha at Suggested edit diff shows different results depending upon mode: "If, on the other hand, you change not just a typo, but the whole text, this means D=N and hence O(N²) performance – so between a 50-word post and a 2000-word post, the difference is suddenly 1600-fold. [...] A few weeks ago, this became painfully obvious [...] that diff took 35-40 seconds" and then explains some details about implemented solutions.
    – Arjan
    May 17, 2012 at 12:53
  • 1
    Relevant: Differences between plain-text diff and formatted diff
    – Hod - Monica's Army
    May 17, 2012 at 13:07
  • 1
    Re your edit: Nothing has changed (and it still looks like your screenshot to me)
    – balpha StaffMod
    May 30, 2012 at 15:51
  • @balpha Sorry, I don't know what I was looking at there. Rolling back. Since I've got you here anyway, any comment on the question as a whole?
    – Hod - Monica's Army
    May 30, 2012 at 15:53
  • 1
    The post you found yourself, and others mentioned in the comments and answer, pretty much answer the question -- there will always be cases were you looking at a computer generated diff will think "that's stupid, doing it such and such way would be much better." We have to optimize for the usual case (example: Usually a change to a link means there's a link in the previous version, and there's a link in following version; in that case, the weirdness you notice wouldn't be there. Usually a colon that appears neither in code or in a link is normal punctuation).
    – balpha StaffMod
    May 30, 2012 at 16:04
  • 2
    That said, I make tweaks to the diff engine once in a while to improve it, and reports like yours are a good basis for finding possible areas of improvement. Be aware however that I don't consider this a huge issue -- after all, the diffs are correct, and your examples are extreme edge cases.
    – balpha StaffMod
    May 30, 2012 at 16:04
  • 1
    @balpha I understand that it's not possible to make it always work, but the examples I bring are far from edge cases. I see things like this all the time. But I understand that it's not a huge priority. If you have the time, though, I'm dying to know what on earth is going on in the regex example.
    – Hod - Monica's Army
    May 30, 2012 at 16:10
  • 1
    It's the (or at least one) shortest edit script to go from the old to the new version. For that particular case, the answer is really identical to meta.superuser.com/a/3849, which you found already.
    – balpha StaffMod
    May 30, 2012 at 16:14
  • 1
    And the question "is it an edge case" is not "how often do you see it", but "how often do you not see it".
    – balpha StaffMod
    May 30, 2012 at 16:15
  • @balpha To which the answer would inevitably be, "as often as I don't look at revision histories". ;)
    – Hod - Monica's Army
    May 30, 2012 at 16:18

3 Answers 3

Reset to default
6

You have already found Differences between plain-text diff and formatted diff yourself, which applies to your examples as well. Short of having an actual human being look at the text and creating the diff by hand, we'll never reach a 100% satisfaction rate.

As I commented on your question, we tweak the algorithms regularly for improvement, taking reports like yours as hints for possible areas that could use tweaking. However, it's an illusion to assume there will ever be a perfect solution. And – just as I say in that post – do not forget that despiting looking curious, the diffs in all three of your examples are correct.

Let me address a few things you said, though.

Sometimes (read: oftentimes) the diff highlighting in the revision history is really weird

and in comments you say

but the examples I bring are far from edge cases. I see things like this all the time.

and

[I do not see these issues] "as often as I don't look at revision histories". ;)

The latter is of course ridiculous, since it would mean that all diffs look like this. But even the claim that these are not edge cases is something you should reconsider. I argue that you think "I see this all the time" because you only notice when something looks weird, but you don't notice when it does not. Just like you think "everytime I want to pass this traffic light, it's red", because in the instances that it's green, this fact doesn't even cross your mind; you just drive on.

Go ahead and look at 1000 randomly chosen revision diffs, and count how many of them are just fine.

Given my assumption that not 100% can be perfect, we obviously care more about the diffs looking good in the usual case, while living with the fact that they may look weird in the edge case.

Now in order to save one : the system interprets the entire link as having been removed and replaced, instead of the understanding that all that was added was "available here:"

This isn't true. It is (more or less) true of the Markdown source, and when you look at the Markdown diff, it will show just that. However, you're complaining about the diff of the rendered version. And in the rendered version of revision 2 there is a link, but in revision 1, there is not. That is a pretty huge difference (and a rare one at that -- you usually do not have a URL that is not linked).

Not knowing anything about diffs, if it was possible to have a word match together with the punctuation following it, without the punctuation being necessary for the match, that would solve most of the punctuation problems.

Sure, that's possible. But it would not solve most of the punctuation problems. Quite the contrary. Compare:

two diffs showing an example of how attaching puncuation to the previous word makes the diff worse

I hope you agree with me that a) the left diff is the better one, and b) that this kind of edit is much more common than your example.

Improve this answer
2
  • Thank you for answering! FWIW, I find that if I'm looking at a post's revisions, it's probably because there's been some heavy editing, so it's much more likely to have problems in the diff. Also, what I meant about punctuation is that punctuation should optionally match together with the immediately proceeding word; that is, it should match whenever doing so doesn't cause the pair to be seen as removed (as in your example above). In other words, match punctuation to include, but not exclude. I don't know if that's feasible, though.
    – Hod - Monica's Army
    May 31, 2012 at 14:29
  • 1
    No, that's not really feasible, since the diffing happens after the tokenizing, but your idea would make the tokenization dependent on the diff. And then imagine multiple instances of this test in one post -- this would add an O(n^2) factor, in other words a performance nightmare.
    – balpha StaffMod
    May 31, 2012 at 17:42
7

Reference balpha's answer to Q 111252.

It seems like your first example could easily be improved by having the lexer consider each of the following as "words" (case-insensitive):

http:
https:
file:
data:
ftp:
imap:
ldap:
telnet:
about:
chrome:

et cetera.
Optionally, an entire URL could be considered a word, but I've personally modified the middle of URL's before, so that might be suboptimal.

I'm not sure there is a good way to fix the second example without potentially breaking something else.

Improve this answer
2
  • +1 Just to add: *.com could also be considered one word, as it seems (from other revision histories I've seen) that is also a problem.
    – Hod - Monica's Army
    May 17, 2012 at 5:38
  • Not knowing anything about diffs, if it was possible to have a word match together with the punctuation following it, without the punctuation being necessary for the match, that would solve most of the punctuation problems. For the example in the Q Jeff brought, the : would be considered an optional part of the previous word. Right now it seems like it deliberately ignores an immediately following punctuation mark and goes for the next one.
    – Hod - Monica's Army
    May 17, 2012 at 5:47
2

In the first example, it looks a lot like the tokenizer is breaking the original string "(http://raphael.eu.pn/gematriel/)" into the tokens "(http", ":" and "//raphael.eu.pn/gematriel/)". This is just my somewhat educated guess, and I'd appreciate it if someone who knows the tokenizing algorithm could confirm or deny it, but that's the only way I can see the diff algorithm producing that particular set of "smallest changes" on that input.

If so, besides Brock Adams' suggestion of treating "http:" as a single token, it would also help if parentheses were not considered part of the adjacent words.

I guess this might have originally been intended as a deliberate feature, to better handle the Markdown [link](URL) syntax. Even if so, though, I suspect that removing it would improve the output in several reasonably common cases (like the example above), leave others mostly unchanged, and only cause very minor regressions in a few hopefully rare cases such as "(at http://example.com)" → "(at [this page](http://example.com))" (where it might affect the choice of which ")" to mark as new). Even those regression could be avoided by making the tokenizer better at telling the difference between valid Markdown link syntax and random URLs that just happen to be inside parentheses.

Improve this answer

You must log in to answer this question.

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