C# Levenshtein Distance

Implement the Levenshtein distance algorithm and compute edit distances.

Levenshtein. In 1965 Vladmir Levenshtein created a distance algorithm. This tells us the number of edits needed to turn one string into another. With Levenshtein distance, we measure similarity and match approximate strings with fuzzy logic.

Info: Returns the number of character edits (removals, inserts, replacements) that must occur to get from string A to string B.

Example. First, credit at the conceptual level goes to Vladimir Levenshtein. This code uses a two-dimensional array instead of a jagged array because the space required will only have one width and one height.

Tip: The two-dimensional array requires fewer allocations upon the managed heap and may be faster in this context.

2D Array

Static: This Compute method doesn't need to store state or instance data, which means you can declare it as static.

Static

Verify: You can verify the algorithm's correctness using a computer science textbook.

C# program that implements the algorithm using System; /// <summary> /// Contains approximate string matching /// </summary> static class LevenshteinDistance { /// <summary> /// Compute the distance between two strings. /// </summary> 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]; } } class Program { static void Main() { Console.WriteLine(LevenshteinDistance.Compute("aunt", "ant")); Console.WriteLine(LevenshteinDistance.Compute("Sam", "Samantha")); Console.WriteLine(LevenshteinDistance.Compute("flomax", "volmax")); } } Output 1 5 3

Example 2. Continuing on, we call the method. You will often want to compare multiple strings with the Levenshtein algorithm. The example here shows how to compare strings in a loop. We use a List of string arrays.List Array

C# program that calls Levenshtein in loop static void Main() { List<string[]> l = new List<string[]> { new string[]{"ant", "aunt"}, new string[]{"Sam", "Samantha"}, new string[]{"clozapine", "olanzapine"}, new string[]{"flomax", "volmax"}, new string[]{"toradol", "tramadol"}, new string[]{"kitten", "sitting"} }; foreach (string[] a in l) { int cost = Compute(a[0], a[1]); Console.WriteLine("{0} -> {1} = {2}", a[0], a[1], cost); } } Output ant -> aunt = 1 Sam -> Samantha = 5 clozapine -> olanzapine = 3 flomax -> volmax = 3 toradol -> tramadol = 3 kitten -> sitting = 3

Notes, edit distance. Here is a table showing the edit distance of some word pairs. It is important to verify the correctness of all computer code (particularly from websites).

Levenshtein distance computations: Words: ant, aunt Levenshtein distance: 1 Note: Only 1 edit is needed. The 'u' must be added at index 2. Words: Samantha, Sam Levenshtein distance: 5 Note: The final 5 letters must be removed. Words: Flomax, Volmax Levenshtein distance: 3 Note: The first 3 letters must be changed Drug names are commonly confused.

Summary. With the Levenshtein distance algorithm, we implement approximate string matching. The difference between two strings is not represented as true or false, but as the number of steps needed to get from one to the other.

The Dev Codes

.Net

.NET Array Dictionary List String 2D Async DataTable Dates DateTime Enum File For Foreach Format IEnumerable If IndexOf Lambda LINQ Parse Path Process Property Regex Replace Sort Split Static StringBuilder Substring Switch Tuple

Java

Core Array ArrayList HashMap String 2D Cast Character Console Deque Duplicates File For Format HashSet If IndexOf Lambda Math ParseInt Process Random Regex Replace Sort Split StringBuilder Substring Switch Vector While

TheDeveloperBlog.com

C# Levenshtein Distance

Related Links:

.Net

Java

Related Links