C# Levenshtein Distance (Difference Between 2 Strings)

If you want to match approximate strings with fuzzy logic, use the Levenshtein distance algorithm. Many projects need this logic, including programs such as spell-checkers, suggestion searches and plagiarism detectors.

In information theory and computer science, the Levenshtein distance is a metric for measuring the amount of difference between two sequences (i.e., the so called edit distance). The Levenshtein distance between two strings is given by the minimum number of operations needed to transform one string into the other, where an operation is an insertion, deletion, or substitution of a single character. A generalization of the Levenshtein distance (Damerau–Levenshtein distance) allows the transposition of two characters as an operation.

I needed to simply to measure the difference between two independant strings.  This was my saving grace, and the C# implementation I found:

using System;

/// 
/// Contains approximate string matching
/// 
static class LevenshteinDistance
{
    /// 
    /// Compute the distance between two strings.
    /// 
    ///The first of the two strings.
    ///The second of the two strings.
    /// The Levenshtein cost.
    public static int Compute(string s, string t)
    {
        int n = s.Length;
        int m = t.Length;
        int[,] d = new int[n + 1, m + 1];

        // Step 1
        if (n == 0)
        {
            return m;
        }

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

        // Step 2
        for (int i = 0; i <= n; d[i, 0] = i++)
        {
        }

        for (int j = 0; j <= m; d[0, j] = j++)
        {
        }

        // Step 3
        for (int i = 1; i <= n; i++)
        {
            //Step 4
            for (int j = 1; j <= m; j++)
            {
                // Step 5
                int cost = (t[j - 1] == s[i - 1]) ? 0 : 1;

                // Step 6
                d[i, j] = Math.Min(
                    Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
                    d[i - 1, j - 1] + cost);
            }
        }
        // Step 7
        return d[n, m];
    }
}

One Reply to “C# Levenshtein Distance (Difference Between 2 Strings)”

Leave a Reply

Your email address will not be published. Required fields are marked *