Skip to content

Instantly share code, notes, and snippets.

@JDMcKinstry
Forked from andrei-m/levenshtein.js
Last active May 7, 2016 15:13
Show Gist options
  • Save JDMcKinstry/a6d4e73f15ed5b03b92950091464a349 to your computer and use it in GitHub Desktop.
Save JDMcKinstry/a6d4e73f15ed5b03b92950091464a349 to your computer and use it in GitHub Desktop.
Levenshtein distance between two given strings implemented in JavaScript and usable as a Node.js module
/* String.similarTo("compare", [BOOL (default TRUE) if do reverse check])
* Credit to for base formula Andrei Mackenzie
* https://gist.github.com/andrei-m/982927
**/
;(function() {
function l(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 (var i=1;i<=b.length;i++)
for (var j=1;j<=a.length;j++)
b.charAt(i - 1) == a.charAt(j - 1) ? matrix[i][j] = matrix[i - 1][j - 1] : matrix[i][j] = Math.min(matrix[i - 1][j - 1] + 1, Math.min(matrix[i][j - 1] + 1, matrix[i - 1][j] + 1));
return matrix[b.length][a.length];
}
function s(b, x) {
var a = this.toString(),
i = l(a, b);
return x ? i : function() {
var r = function (a){a=a.split("");for(var c=[],b=a.length-1;0<=b;b--)c.push(a[b]);return c.join("")};
c = r(b),
j = l(a, c);
return i < j ? i : j;
}();
}
if (Object['defineProperty'] && !String.prototype.hasOwnProperty('similarTo')) Object.defineProperty(String.prototype, 'similarTo', { value: s });
})();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment