Sort String Array using Levenstein Algorithm results

Question

Hi, I've been working on an Access file editor in C#, and i've been trying to get a search feature added to my program. So far, I have the database file populate a 2D array, which i then use to populate a ListView box in another window. From this new window, I would like to be able to search each entry by Model Number. So far, i've managed to incorporate the Levenstein Algorithm, which seems to have much use. I can get the algorithm to assign the distance value between each entry and the search keyboard, and assign that value to another integer array. I can also sort the results in increasing order.

However, my current problem is that i'd would like to have the Model numbers sorted with the same respect to the distance values from the Levenstein Algorithm, so that the most relevant result becomes the first choice in the ListView box. Any ideas anyone??!?!

Here's what i've got so far:

 private void OnSearch(object sender, System.EventArgs e)
    {

        string a;
        string b;
        int[] result = new int[1000];
        int[] sorted = new int[1000];

            for (int i = 0; i < rowC; i++)
            {
                a = PartNum[i];   // Array to search
                b = SearchBox1.Text;     // keyword to search with

                if (GetDistance(a, b) == 0)
                {
                    return;
                }

                result[i] = GetDistance(a, b);  //add each distance result into array 

            }

            int index;
            int x;

            for (int j = 1; j < rowC; j++)   //quick insertion sort
            {
                index = result[j];
                x = j;

                while ((x > 0) && (result[x - 1] > index))
                {
                    result[x] = result[x - 1];
                    x = x - 1;
                }
                result[x] = index;
            }

        }


  public static int GetDistance(string s, string t)
    {
        if (String.IsNullOrEmpty(s) || String.IsNullOrEmpty(t))
        {
            MessageBox.Show("Please enter something to search!!");
            return 0;

        }

        int n = s.Length;
        int m = t.Length;
        if (n == 0)
        {
            return m;
        }

        else if (m == 0)
        {
            return n;
        }

        int[] p = new int[n + 1];
        int[] d = new int[n + 1];
        int[] _d;
        char t_j;
        int cost;

        for (int i = 0; i <= n; i++)
        {
            p[i] = i;
        }

        for (int j = 1; j <= m; j++)
        {
            t_j = t[j - 1];
            d[0] = j;

            for (int i = 1; i <= n; i++)
            {
                cost = (s[i - 1] == t_j) ? 0 : 1;
                d[i] = Math.Min(Math.Min(d[i - 1] + 1, p[i] + 1), p[i - 1] + cost);
            }
            _d = p;
            p = d;
            d = _d;
        }
        return p[n];
    }

Answer 1

Do you have LINQ available to you? If so:

var ordered = PartNum.OrderBy(x => GetDistance(x, SearchBox1.Text))
                     .ToList();

// Do whatever with the ordered list

Note that this has the disadvantage of not aborting early if you find an exact match, as well as not making the actual distances available - but it's not entirely clear how you're using the results anyway...

Another option would be:

var ordered = (from word in PartNum
              let distance = GetDistance(word, SearchBox1.Text))
              orderby distance
              select new { word, distance }).ToList();

Then you've got the distance as well.

Answer 2

In order to sort your array by Levenstein distance you need to include the model numbers as part of your array so that, when you sort the array by Levenstein number, the model numbers will go along for the ride.

To do this, create a class representing each part:

public class Part
{
    public string PartNumber;
    public int LevensteinDistance;
}

and then create an array of Part:

Part[] parts;

You can then reference each element like so:

parts[n].LevensteinDistance
parts[n].PartNumber