Stackoverflow's text diff [duplicate]

Question

When I go to (for example) review section here, I see these beautifully formatted text diffs:

Or the combined one:

Now, just how the hell is this done? I'd love to include this to my site, but I can't really figure out the algorithm. Is this documented somewhere? Is there an open-source implementation for this, preferably in PHP?

Thanks for any help.

Answer 1

From the images that you posted, and my own (albeit little experience) it seems that the website uses a modification of the longest common sub sequence algorithm. This explains why it never shows rearrangement / shuffling of words.

The first modification is that instead of thinking of alphabets as atomic units, they consider words as atomic units. (also punctuation)

Secondly, the algorithm is relatively naive, it points out that you crossed out "work" when you actually just inserted a to there. It seems to just mark discontinuities of any kind (insertions, deletions, modifications) and crosses out one word or the whole discontinuation portion.

Thirdly, everything in the second list not a part of the first list is marked in green.

Seems relatively easy to implement. Check out some tutorial on dynamic programming.