I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there's an Xmas issue as well — so it's a bit more than monthly). The column is called Theory Workshop and appears in the back of every issue. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so. After all, the PDFs do appear on each issue's DVD after a couple of months. When I buy the current issue, I'll publish the article from the issue a year ago. Since I've now got July's issue, here's July 2008's article.

Although the article is short, the usual two pages, the topic interests me greatly and I wish I could do it more justice. It's about calculating the longest common subsequence (LCS) of two strings and thereby calculate their edit distance and from that, the diffs or the differences between the two strings. Although the diffs between two strings is not that interesting (to a programmer, at least, although I can imagine it's highly meaningful in genetics), the same process can be applied to two text files and the results of that are of great importance. Every version control system out there stores revisions to a file as some kind of diff, for compression, if nothing else.

The standard algorithm I described in the article is pretty simple to understand, but astonishing in that it's so counter-intuitive. I can't imagine how it came about; although, in reality, it's just a dynamic programming problem, when all's said and done. The algorithm is pretty efficient — I even incorporated it into a demo diff program I wrote at Microsoft to show off the new color support in the Console class during the Whidbey cycle (Visual Studio 2005) — but with large files/strings the amount of memory needed can get unwieldy and things slow down. (The algorithm is quadratic in both time and space: O(n*m) essentially.)

There's a version of the algorithm that requires linear space instead, from Dan Hirschberg's 1975 paper A linear space algorithm for computing maximal common subsequences. There are other improvements that deal with special cases, for example in the fields of genetics.

This article first appeared in issue 270, July 2008.

You can download the PDF here.