www.mathertel.deAn O(ND) Difference Algorithm for C#How to compate textlines.

This page contains a step by step sample to show how to use the Diff class for comparing the characters of 2 strings.

For more information about Diff class see the main page.

This page can be used with 2 URL parameters (a and b) to test this implementation:

Current parameters:

Text a = "This is a big thing."
Text b = "This is a small thing."

1. Parameter Preparation

Before the algorithm can be used the 2 input string must be converted into the datatype that is used by the algorithm: a int Array.

Because we compare on a character basis this task is very easy to complete by using the character code of each char. This is done by the DiffCharCodes:

private static int[] DiffCharCodes(string aText, bool ignoreCase) {
  int[] Codes;

  if (ignoreCase)
    aText = aText.ToUpperInvariant();

  Codes = new int[aText.Length];

  for (int n = 0; n < aText.Length; n++)
    Codes[n] = (int)aText[n];

  return (Codes);
} // DiffCharCodes

The codes for the 2 textlines are:

a_codes = 54 68 69 73 20 69 73 20 61 20 62 69 67 20 74 68 69 6e 67 2e
b_codes = 54 68 69 73 20 69 73 20 61 20 73 6d 61 6c 6c 20 74 68 69 6e 67 2e

2. Calling the Diff Algorithm

The main entry point for the Algorithm is the LCS function that can take 2 int[] parameters and will return an array Diff.Item structures that are describing the difference details as identical, inserted or deleted subarrays.

Diff.Item[] diffs = Diff.DiffInt(a_codes, b_codes);

Here is a dump of the actual content of this structure:

The diff result has 1items.
StartA=10, StartB=10, deletedA=3, insertedB=5

3. Formatting the result

Now we can use the original data together with the result items and generate a intuitive readable form of the result:

int pos = 0;
for (int n = 0; n < diffs.Length; n++) {
  Diff.Item it = diffs[n];

  // write unchanged chars
  while ((pos < it.StartB) && (pos < b_line.Length)) {
    this.Response.Write(b_line[pos]);
    pos++;
  } // while

  // write deleted chars
  if (it.deletedA > 0) {
    this.Response.Write("<span class='cd'>");
    for (int m = 0; m < it.deletedA; m++) {
      this.Response.Write(a_line[it.StartA + m]);
    } // for
    this.Response.Write("</span>");
  }

  // write inserted chars
  if (pos < it.StartB + it.insertedB) {
    this.Response.Write("<span class='ci'>");
    while (pos < it.StartB + it.insertedB) {
      this.Response.Write(b_line[pos]);
      pos++;
    } // while
    this.Response.Write("</span>");
  } // if
} // while

// write rest of unchanged chars
while (pos < b_line.Length) {
  this.Response.Write(b_line[pos]);
  pos++;
} // while

And here is the formatted result:

This is a bigsmall thing.

This page is part of the http://www.mathertel.de/ web site.