Diff Algorithm
(April 2006)

Introduction

The Matrix

• keep the letter (when no change is needed) - a diagonal line is drawn
• insert a letter - a vertical line
• remove a letter - a horizontal line

1. At the beginning, 4 letters are the same and need not be changed.
2. At this point there are two possibilities: delete the 'C' or insert a 'W'.
3. 'W' and 'O' have been inserted.
4. 'C' and 'A' have been removed.
5. At this point the next character (a space) is a space and need not be changed.
6. -
7. This is the end: the source string has been transformed in the destination string.
8. On the blue path, 'CALL OF THE' is removed.
9. 'WOLF IS' is inserted.

The Simpliest Path

= THE
- CALL
=   (space)
+ W
= O
+ L
= F
- THE
+ IS
=  WILD

A PHP implementation

<?
// implementation of a diff between 2 strings

// example of behaviour
// source = "abcdefghiZ..."
// dest =   "abcdXefghi..."
// this function returns an array of this sort :
// '=', "abcd"
// '+', "X"
// '=', "efghi"
// '-', "Z"
// '=', "..."
function diff($source, $dest) {
	$source_len = strlen($source);
	$dest_len = strlen($dest);

	// matrix of Levenshtein distance
	// build the matrix
	$d = array();
	for ($i=0; $i<$source_len+1; $i++) $d[] = array_fill(0, $dest_len, 0);

	// initialize the matrix
	for ($i=0; $i<$source_len+1; $i++) $d[$i][0] = $i;

	for ($j=0; $j<$dest_len+1; $j++) $d[0][$j] = $j;

	// compute the matrix
	for ($i=0; $i<$source_len; $i++) {
		for ($j=0; $j<$dest_len; $j++) {
			if ($source[$i] == $dest[$j]) $d[$i+1][$j+1] = $d[$i][$j];
			else $d[$i+1][$j+1] = min($d[$i][$j+1], $d[$i+1][$j])+1;
		}
	}

	// follow the path starting from the end
	// in order to find the optimized path
	$stack = array();
	$j = $dest_len;
	$i = $source_len;
	while ($i>0 and $j>0) {
		if ($source[$i-1] == $dest[$j-1]) {
			array_unshift($stack, array('=', $source[$i-1]));
			$j = $j-1;
			$i = $i-1;
		} else {
			// find the best cell
			if ($d[$i-1][$j] < $d[$i][$j-1]) {
				array_unshift($stack, array('-', $source[$i-1]));
				$i = $i-1;
			} else {
				array_unshift($stack, array('+', $dest[$j-1]));
				$j = $j-1;
			}
		}
	}
	if ($i>0) { // source characters to be removed
		array_unshift($stack, array('-', substr($source, 0, $i-1)));
	}
	if ($j>0) { // dest characters to be added
		array_unshift($stack, array('+', substr($dest, 0, $j-1)));
	}

	// simplify the stack (put +, - or = together)
	$simplified_stack = array();
	$simplified_stack[0] = $stack[0];
	$i = 1;
	$i_s = 0; // index in the simplified stack
	while ($i < count($stack)) {
		if ($stack[$i][0] == $simplified_stack[$i_s][0]) {
			$simplified_stack[$i_s][1] .= $stack[$i][1];
		} else {
			$i_s ++;
			$simplified_stack[$i_s] = $stack[$i];
		}
		$i ++;
	}
	return $simplified_stack;

} // end of function diff

?>