StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Here are two methods that calculate the <a href="http://en.wikipedia.org/wiki/Levenshtein_Distance" rel="nofollow noreferrer">Levenshtein Distance</a> between strings.</p> <blockquote> <p>The Levenshtein distance between two strings is defined as the minimum number of edits needed to transform one string into the other, with the allowable edit operations being insertion, deletion, or substitution of a single character.</p> </blockquote> <p>Once you have the result, you'll need to define what value you want to use as a threshold for a match or not. Run the function on a bunch of sample data to get a good idea of how it works to help decide on your particular threshold.</p> <pre><code> /// <summary> /// Calculates the Levenshtein distance between two strings--the number of changes that need to be made for the first string to become the second. /// </summary> /// <param name="first">The first string, used as a source.</param> /// <param name="second">The second string, used as a target.</param> /// <returns>The number of changes that need to be made to convert the first string to the second.</returns> /// <remarks> /// From http://www.merriampark.com/ldcsharp.htm /// </remarks> public static int LevenshteinDistance(string first, string second) { if (first == null) { throw new ArgumentNullException("first"); } if (second == null) { throw new ArgumentNullException("second"); } int n = first.Length; int m = second.Length; var d = new int[n + 1, m + 1]; // matrix if (n == 0) return m; if (m == 0) return n; for (int i = 0; i <= n; d[i, 0] = i++) { } for (int j = 0; j <= m; d[0, j] = j++) { } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { int cost = (second.Substring(j - 1, 1) == first.Substring(i - 1, 1) ? 0 : 1); // cost 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]; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload