Diff - Solaris, Linux and Ruby Tuesday, December 15, 2009

I am looking for diff functionality with Ruby for a project I am involved in. There seems to be a few available. The one I liked is differ. It allows you to do comparisons line by line, word by word, or character by character.

This got me thinking about the diff(1) command. With a little searching, I found that GNU diff and Solaris diff implement two different diff algorithms.

Solaris diff is based off some old code from ATT&T (cfront?) and uses the algorithm described in Hunt, J.W. and McIlroy, M.D. ‘‘An Algorithm for Differential File Comparison.’’ Computing Science Techn- ical Report 41, Bell Laboratories (1975).

The GNU diff (the one used by Linux) utility uses the algorithmn described in An O(ND) Difference Algorithm and Its Variations - Eugene Myers, Algorithmica Vol. 1 No. 2, 1986. This is a faster algorithm than the one used in Solaris, although it can be a slower for cases where the input is large and the differences are many.

Very interesting. I plan to read more about this.

0 comments: