The Design of Software (CLOSED)

A public forum for discussing the design of software, from the user interface to the code architecture. Now closed.

The "Design of Software" discussion group has been merged with the main Joel on Software discussion group.

The archives will remain online indefinitely.

Wiki Page Diff Algorithms

Can anyone tell me what algorithms are used to show the changes between multiple edits of a page in applications like Wikipedia? Or perhaps give a general outline of how this sort of thing works, because I really wouldn't know where to start.

Algorithmically Challenged
Wednesday, October 26, 2005
I would guess that the source for the Unix command diff (or a Linux equivalent) is freely available on the web for you to look at.
Andy Brice Send private email
Wednesday, October 26, 2005
Wikipedia's technology seems to be more sophisticated than diff; it can highlight differences on a word-by-word basis, while diff only works in terms of lines.

That said, MediaWiki is also open-source software, so there's nothing stopping anyone looking there instead.  :P
Wednesday, October 26, 2005
Python also has a difflib written in pure python in the standard library.  It accepts arbitraty "symbols" so you could pump it words instead of lines.  Probably as good a reference implementation as anything.
Wednesday, October 26, 2005
>  Python also has a difflib

There's also one for java that's a pretty straight port of the gnu diff code. Not pretty, but it worked.
son of parnas
Wednesday, October 26, 2005
The docs for the Perl module Algorithm::Diff are excellent, originally written by the author of the book Higher Order Perl (strongly recommended):
Chris Winters Send private email
Wednesday, October 26, 2005
The one I use for JDiff ( is pretty general purpose. I tried it with lines and then finally used it to compare sentences. The diff algorithm is interesting in itself, the same as finding the shortest distance between two points.

Matt Doar Send private email
Wednesday, October 26, 2005

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
Powered by FogBugz