# Levenshtein distance (v16)

## Description

Prompted by a [Stack Overflow question][http://stackoverflow.com/questions/11919065/sort-an-array-by-the-levenshtein-distance-with-best-performance-in-javascript], this will compare implementations of the Levenshtein distance algorithm.

## Setup

``````// Screen names grabbed from Lady Gaga's twitter followers.
// http://jsfiddle.net/Jordan/UMKzq/1/

Math.RandomInt = function(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
};

window.randomScreenName = function() {
return screenNames[Math.RandomInt(0, screenNames.length - 1)];
}

window.CompareLD1 = function(min, split) {
try {
split = !("0")[0];
} catch (i) {
split = true;
}
return function(a, b) {
if (a == b) return 0;
if (!a.length || !b.length) return b.length || a.length;
if (split) {
a = a.split("");
b = b.split("");
}
var len1 = a.length + 1,
len2 = b.length + 1,
I = 0,
i = 0,
d = [
[0]
],
c, j, J;
while (++i < len2) d[0][i] = i;
i = 0;
while (++i < len1) {
J = j = 0;
c = a[I];
d[i] = [i];
while (++j < len2) {
d[i][j] = min(d[I][j] + 1, d[i][J] + 1, d[I][J] + (c != b[J]));
++J;
}++I;
}
return d[len1 - 1][len2 - 1];
}
}(Math.min, false);

window.CompareLD2 = function(s, t) {
var d = [];
var n = s.length;
var m = t.length;
if (n == 0) return m;
if (m == 0) return n;
for (var i = n; i >= 0; i--) d[i] = [];
for (var i = n; i >= 0; i--) d[i][0] = i;
for (var j = m; j >= 0; j--) d[0][j] = j;
for (var i = 1; i <= n; i++) {
var s_i = s.charAt(i - 1);
for (var j = 1; j <= m; j++) {
if (i == j && d[i][j] > 4) return n;
var t_j = t.charAt(j - 1);
var cost = (s_i == t_j) ? 0 : 1;
var mi = d[i - 1][j] + 1;
var b = d[i][j - 1] + 1;
var c = d[i - 1][j - 1] + cost;
if (b < mi) mi = b;
if (c < mi) mi = c;
d[i][j] = mi;
if (i > 1 && j > 1 && s_i == t.charAt(j - 2) && s.charAt(i - 2) == t_j) {
d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost);
}
}
}
return d[n][m];
};

function minn(a, b, c) {
if (a > b) a = b;
if (a < c) return a;
return c;
}

window.CompareLD3 = function(S1, S2, limit) {
if (S1 == null || S2 == null || typeof(S1) != "string" || typeof(S2) != "string") return 9999999;
if (limit == null) limit = 9999999;
if (Math.abs(S1.length - S2.length) > limit) return 9999999;
S1 = S1.toLowerCase();
S2 = S2.toLowerCase();
if (S1 == S2) return 0;
var n = S1.length;
var m = S2.length;
dist = new Array(new Array(m + 2), new Array(m + 2));
current = 0;
for (i = 0; i <= m + 1; i++) {
dist[1][i] = i;
}
for (i = 1; i <= n; i++) {
ok = 0;
dist[current][0] = i;
if (i - limit >= 1) dist[current][i - limit - 1] = 9999999;
for (j = Math.max(i - limit, 1); j <= Math.min(i + limit, m); j++) {
if (S1.substr(i - 1, 1) == S2.substr(j - 1, 1)) dist[current][j] = dist[1 - current][j - 1];
else dist[current][j] = minn(dist[1 - current][j - 1], dist[1 - current][j], dist[current][j - 1]) + 1;
if (dist[current][j] <= limit) ok = 1;
}
if (i + limit <= m) {
dist[current][i + limit + 1] = 9999999;
}
if (!ok) return 9999999;
current = 1 - current;
}
if (dist[1 - current][m] > limit) return 9999999;
return dist[1 - current][m];
};

window.CompareLD6 = function(s, t, lim) {
if (lim == null) lim = 9999999;
if (Math.abs(s.length - t.length) > lim) return 9999999;

var d = []; //2d matrix
// Step 1
var n = s.length,
m = t.length;

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

var i = n + 1;
do {
d[i] = [];
} while (i--);

// Step 2
i = n + 1, j = m + 1;
do {
d[i][0] = i;
} while (i--);
do {
d[0][j] = j;
} while (j--);

// Step 3
for (var i = 1; i <= n; i++) {
var s_i = s.charAt(i - 1);

// Step 4
for (var j = 1; j <= m; j++) {

//Check the jagged ld total so far
if (i == j && d[i][j] > 4) return n;

var t_j = t.charAt(j - 1);
var cost = (s_i == t_j) ? 0 : 1; // Step 5
//Calculate the minimum
var mi = d[i - 1][j] + 1;
var b = d[i][j - 1] + 1;
var c = d[i - 1][j - 1] + cost;

if (b < mi) mi = b;
if (c < mi) mi = c;

d[i][j] = mi; // Step 6
}
}

// Step 7
return d[n][m];
}

// Levenshtein Distance
// from https://github.com/systemed/iD/blob/1e78ee5c87669aac407c69493f3f532c823346ef/js/id/util.js#L97-L115
window.CompareLD7 = function (a, b) {
if (a.length === 0) return b.length;
if (b.length === 0) return a.length;
var matrix = [];
for (var i = 0; i <= b.length; i++) { matrix[i] = [i]; }
for (var j = 0; j <= a.length; j++) { matrix[0][j] = j; }
for (i = 1; i <= b.length; i++) {
for (j = 1; j <= a.length; j++) {
if (b.charAt(i-1) === a.charAt(j-1)) {
matrix[i][j] = matrix[i-1][j-1];
} else {
matrix[i][j] = Math.min(matrix[i-1][j-1] + 1, // substitution
Math.min(matrix[i][j-1] + 1, // insertion
matrix[i-1][j] + 1)); // deletion
}
}
}
return matrix[b.length][a.length];
};``````

## Test runner

Testing in
TestOps/sec
Original implementation
``CompareLD1(randomScreenName(), randomScreenName());``
Westgate's implementation
``CompareLD2(randomScreenName(), randomScreenName());``
Stoianovici's implementation (no limit)
``CompareLD3(randomScreenName(), randomScreenName());``
Stoianovici's implementation (limit of 10)
``CompareLD3(randomScreenName(), randomScreenName(), 10);``
``CompareLD3(randomScreenName(), randomScreenName(), 5);``
``CompareLD6(randomScreenName(), randomScreenName());``
``CompareLD7(randomScreenName(), randomScreenName());``