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 = "identical"
Text b = "different"

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 = 69 64 65 6e 74 69 63 61 6c
b_codes = 64 69 66 66 65 72 65 6e 74

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 3items.
StartA=0, StartB=0, deletedA=0, insertedB=1
StartA=1, StartB=2, deletedA=1, insertedB=4
StartA=5, StartB=9, deletedA=4, insertedB=0

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)) {
  } // 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

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

// write rest of unchanged chars
while (pos < b_line.Length) {
} // while

And here is the formatted result:


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