Blog

How does diff/patch work? When I first started to do research on this problem I had no idea about the complexity of the math involved and the lack of C# examples around. It turns out that finding the right resources can make life easier, and in the end the Wikipedia entry and this screencast did a great job making me understand and implement a small diff algorithm in C#. In this post I’ll try to lightly explain the problems faced by diff applications and publish a simple implementation. I strongly recommend the screencast if you’re really trying to understand this.

The bulk of the problem is solved by an algorithm called the Longest Common Subsequence which, as the name says, finds the longest, therefore, most suitable start point to create the diff. The Longest Common Subsequence by itself, or its size, its not really useful to create a diff, but the inner workings of the algorithm produce a matrix which can be used to directly create the list of operations needed to go from the original to the target file.

The Longest Common Subsequence is mathematically classified as a NP-hard problem and very CPU/RAM hungry problem. This is due to the fact a matrix by the size of the product of both file sizes is needed. Therefore to compare 1KB the algorithm would need a full mega byte just for the matrix. Luckily this problem can be simplified although the bigger the data the more time and resources the algorithm will consume.

One simplification done by most diff applications is to divide the file in chucks of characters or more commonly by lines. This reduces greatly the number of items taken into account by the matrix but comparing strings is still an expensive process because each item is compared several times to the others. To make comparisons faster diff applications also use hashing as an optimization, ending up doing the same number of comparisons but comparing integers instead (which is one of the fastest operations modern PCs can do).

Binary diffs (I didn’t study this type of diff deeply yet) seems very similar in concept. Although there are no lines delimiting the contents we can simply use a predefined chuck size (for example 1024) and do a MD5 hash. Due to the nature of binary files I expect the biggest challenge to be optimizing the output and making it more compressible as possible.

I’ve not implemented all this techniques yet although I plan to. Another thing I realized is how easy, using generics, it will be to extend the algorithm to make a diff on random object types like 2 arrays. I expect this to be a very useful library once its completed, but for now I leave here the code for the Longest Common Subsequence and the code to get a simple diff from it:

using System;

namespace DiffSharp
{
	public class LCS
	{
		public static int[,] GetLongestCommonSubsequenceMatrix(string s1, string s2)
		{
			int[,] lcsMatrix = new int[s1.Length, s2.Length];
			char letter1, letter2;

			for (int i = 0; i < s1.Length; i++)
			{
				for (int j = 0; j < s2.Length; j++)
				{
					letter1 = s1[i];
					letter2 = s2[j];

					if (letter1 == letter2)
					{
						if ((i == 0) || (j == 0))
							lcsMatrix[i, j] = 1;
						else
							lcsMatrix[i, j] = 1 + lcsMatrix[i - 1, j - 1];
					}
					else
					{
						if ((i == 0) && (j == 0))
							lcsMatrix[i, j] = 0;
						else if ((i == 0) && !(j == 0))
							lcsMatrix[i, j] = Math.Max(0, lcsMatrix[i, j - 1]);
						else if (!(i == 0) && (j == 0))
							lcsMatrix[i, j] = Math.Max(lcsMatrix[i - 1, j], 0);
						else if (!(i == 0) && !(j == 0))
							lcsMatrix[i, j] = Math.Max(lcsMatrix[i - 1, j], lcsMatrix[i, j - 1]);
					}
				}
			}

			return lcsMatrix;
		}

		public static void GetDiffTreeFromBacktrackMatrix(int[,] lcsMatrix, string s1, string s2, int i, int j)
		{
			if (i > 0 && j > 0 && s1[i - 1] == s2[j - 1])
			{
				GetDiffTreeFromBacktrackMatrix(lcsMatrix, s1, s2, i - 1, j - 1);
				Console.WriteLine("  " + s1[i - 1]);
			}
			else
			{
				if (j > 0 && (i == 0 || lcsMatrix[i, j - 1] >= lcsMatrix[i - 1, j]))
				{
					GetDiffTreeFromBacktrackMatrix(lcsMatrix, s1, s2, i, j - 1);
					Console.WriteLine("+ " + s2[j - 1]);
				}
				else if (i > 0 && (j == 0 || lcsMatrix[i, j - 1] < lcsMatrix[i - 1, j]))
				{
					GetDiffTreeFromBacktrackMatrix(lcsMatrix, s1, s2, i - 1, j);
					Console.WriteLine("- " + s1[i - 1]);
				}
			}
		}
	}

public class Program
	{
		static void Main(string[] args)
		{
			string s1 = "1ac";
			string s2 = "abc";

			LCS.GetDiffTreeFromBacktrackMatrix(LCS.GetLongestCommonSubsequenceMatrix(s1, s2), s1, s2, s1.Length, s2.Length); 

			Console.ReadKey();
		}
	}
}

Tags: .Net, C#, Diff, LCS, Longest Common Subsequence, Mono, Sample Code

This entry was posted on Monday, November 10th, 2008 at 13:00 pm and is filed under .Net, Featured, Mono, Monologue. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.