Created
March 29, 2017 19:49
-
-
Save jhyland87/c09132b31a2497ec102f9f3801245cd7 to your computer and use it in GitHub Desktop.
Few separate ways to create a levenshtein function
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var levenshtein_es5 = function(a, b) { | |
if(a.length == 0) return b.length; | |
if(b.length == 0) return a.length; | |
// swap to save some memory O(min(a,b)) instead of O(a) | |
if(a.length > b.length) { | |
var tmp = a; | |
a = b; | |
b = tmp; | |
} | |
var row = []; | |
// init the row | |
for(var i = 0; i <= a.length; i++){ | |
row[i] = i; | |
} | |
// fill in the rest | |
for(var i = 1; i <= b.length; i++){ | |
var prev = i; | |
for(var j = 1; j <= a.length; j++){ | |
var val; | |
if(b.charAt(i-1) == a.charAt(j-1)){ | |
val = row[j-1]; // match | |
} else { | |
val = Math.min(row[j-1] + 1, // substitution | |
prev + 1, // insertion | |
row[j] + 1); // deletion | |
} | |
row[j - 1] = prev; | |
prev = val; | |
} | |
row[a.length] = prev; | |
} | |
return row[a.length]; | |
} | |
// --------------------------------------------------------------- | |
const levenshtein_es6 = (a, b) => { | |
if (a.length === 0) return b.length | |
if (b.length === 0) return a.length | |
let tmp, i, j, prev, val | |
// swap to save some memory O(min(a,b)) instead of O(a) | |
if (a.length > b.length) { | |
tmp = a | |
a = b | |
b = tmp | |
} | |
row = Array(a.length + 1) | |
// init the row | |
for (i = 0; i <= a.length; i++) { | |
row[i] = i | |
} | |
// fill in the rest | |
for (i = 1; i <= b.length; i++) { | |
prev = i | |
for (j = 1; j <= a.length; j++) { | |
if (b[i-1] === a[j-1]) { | |
val = row[j-1] // match | |
} else { | |
val = Math.min(row[j-1] + 1, // substitution | |
Math.min(prev + 1, // insertion | |
row[j] + 1)) // deletion | |
} | |
row[j - 1] = prev | |
prev = val | |
} | |
row[a.length] = prev | |
} | |
return row[a.length] | |
} | |
// --------------------------------------------------------------- | |
String.prototype.levenstein = function(string) { | |
var a = this, b = string + "", m = [], i, j, min = Math.min; | |
if (!(a && b)) return (b || a).length; | |
for (i = 0; i <= b.length; m[i] = [i++]); | |
for (j = 0; j <= a.length; m[0][j] = j++); | |
for (i = 1; i <= b.length; i++) { | |
for (j = 1; j <= a.length; j++) { | |
m[i][j] = b.charAt(i - 1) == a.charAt(j - 1) | |
? m[i - 1][j - 1] | |
: m[i][j] = min( | |
m[i - 1][j - 1] + 1, | |
min(m[i][j - 1] + 1, m[i - 1 ][j] + 1)) | |
} | |
} | |
return m[b.length][a.length]; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment