Skip to content

Instantly share code, notes, and snippets.

@jhyland87
Created March 29, 2017 19:49
Show Gist options
  • Save jhyland87/c09132b31a2497ec102f9f3801245cd7 to your computer and use it in GitHub Desktop.
Save jhyland87/c09132b31a2497ec102f9f3801245cd7 to your computer and use it in GitHub Desktop.
Few separate ways to create a levenshtein function
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