the Levenshtein distance (string extension)

Feb 4, 2011 at 11:41 AM

http://pastebin.com/7ih138ps

Apr 27, 2011 at 2:17 PM

Could you please repost this. Did you write any tests for your implementation?

Apr 27, 2011 at 4:13 PM

Nope. I use this in my project to search posible variants to correct words.

May 15, 2011 at 7:25 PM

the paste bin link expired can you repost the code?

May 15, 2011 at 8:08 PM
    /// <summary> Compute the distance between two strings. </summary>
    /// <param name="value">The first of the two strings.</param>
    /// <param name="text">The second of the two strings.</param>
    /// <param name="irregular">Irregular</param>
    /// <returns>The Levenshtein cost.</returns>
    public static int Levenshtein(this string value, string text, bool irregular = false)
    {
        if (text == null) throw new ArgumentNullException("text");
        if (value == null) throw new ArgumentNullException("value");

        if (irregular)
        {
            value = value.ToLower();
            text = text.ToLower();
        }

        var n = value.Length;
        var m = text.Length;
        var d = new int[n + 1, m + 1];

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

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

        for (var i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                var cost = (text[j - 1] == value[i - 1]) ? 0 : 1;
                d[i, j] = Math.Min(Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1), d[i - 1, j - 1] + cost);
            }
        }

        return d[n, m];
    }