Efficient Javascript implementation of Levenshtein distance.

levenshtein.js

// Compute the Levenshtein distance between `Array`-like sequences `a` and `b`; the minimum number of
// single-element insertions, deletions and substitutions necessary to transform `a` into `b`.
// Strict equality semantics are used by default to compare sequence elements; a function `equal` can
// optionally be provided to alter this behavior.
function levenshtein(a, b, equal) {
	// `aii` and `bii` are used to track `ai - 1` and `bi - 1` more or less free of charge.
	// `d0` and `d1` are used to store the 'previous' and 'current' rows respectively.
	// `x`, `y` and `z` are used to permit the implementation of an optimized `min` using a ternary expression.
	var ai, aii, ae, al, bi, bii, bl, d0, d1, dd, x, y, z;
	if(a === b) return 0;

	al = a.length; bl = b.length;
	if(0 === al) return bl;
	if(0 === bl) return al;

	d0 = [0]; d1 = [];
	for(bi = 1; bi <= bl; bi++) d0[bi] = bi;

	// Here the entire core logic of the function is duplicated to avoid having the inner loop check if
	// `equal` has been provided.
	if(equal) {
		for(ai = 1, aii = 0; ai <= al; aii = ai++) {
			d1[0] = ai;
			ae = a[aii];
			for(bi = 1, bii = 0; bi <= bl; bii = bi++) {
				if(equal(ae, b[bii])) {
					d1[bi] = d0[bii];
				} else {
					x = d0[bii]; y = d0[bi]; z = d1[bii];
					d1[bi] = (x < y ? (x < z ? x : z) : (y < z ? y : z)) + 1;
				}
			}
			dd = d0; d0 = d1; d1 = dd;
		}
	} else {
		for(ai = 1, aii = 0; ai <= al; aii = ai++) {
			d1[0] = ai;
			ae = a[aii];
			for(bi = 1, bii = 0; bi <= bl; bii = bi++) {
				if(ae === b[bii]) {
					d1[bi] = d0[bii];
				} else {
					x = d0[bii]; y = d0[bi]; z = d1[bii];
					d1[bi] = (x < y ? (x < z ? x : z) : (y < z ? y : z)) + 1;
				}
			}
			dd = d0; d0 = d1; d1 = dd;
		}
	}	

	return d0[bl];
}