Levenshtein

Benchmark created on

Preparation HTML

<script>
  var s1 = "jhonny",
      s2 = "ponny";
  
  function levenshtein1(str1, str2) {
   var l1 = str1.length,
       l2 = str2.length;
   if (Math.min(l1, l2) === 0) {
    return Math.max(l1, l2);
   }
   var i = 0,
       j = 0,
       d = [];
   for (i = 0; i <= l1; i++) {
    d[i] = [];
    d[i][0] = i;
   }
   for (j = 0; j <= l2; j++) {
    d[0][j] = j;
   }
   for (i = 1; i <= l1; i++) {
    for (j = 1; j <= l2; j++) {
     d[i][j] = Math.min(
     d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + (str1.charAt(i - 1) === str2.charAt(j - 1) ? 0 : 1));
    }
   }
   return d[l1][l2];
  }
  
  function levenshtein2(s1, s2) {
   if (s1 === s2) {
    return 0;
   }
   if (s1.length === 0) {
    return s2.length;
   }
   if (s2.length === 0) {
    return s1.length;
   }
   var v0 = [],
       v1 = [],
       j = 0,
       k = 0;
   s1 = s1.split('');
   s2 = s2.split('');
   for (j = 0; j <= s1.length; j++) {
    v0[j] = j;
   }
   for (k = 1; k <= s2.length; k++) {
    v1[0] = k;
    for (j = 0; j < s1.length; j++) {
     v1[j + 1] = Math.min(v0[j + 1] + 1, v1[j] + 1, v0[j] + ((s1[j] === s2[k - 1]) ? 0 : 1));
    }
    var v_tmp = v0;
    v0 = v1;
    v1 = v_tmp;
   }
   return v0[s1.length];
  }
  
  
  var levenshtein3 = function(min, split) {
   // Levenshtein Algorithm Revisited - WebReflection
   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);
  
  
  function levenshtein4(a, b) {
   var i;
   var j;
   var cost;
   var d = new Array();
  
   if (a.length == 0) {
    return b.length;
   }
  
   if (b.length == 0) {
    return a.length;
   }
  
   for (i = 0; i <= a.length; i++) {
    d[i] = new Array();
    d[i][0] = i;
   }
  
   for (j = 0; j <= b.length; j++) {
    d[0][j] = j;
   }
  
   for (i = 1; i <= a.length; i++) {
    for (j = 1; j <= b.length; j++) {
     if (a.charAt(i - 1) == b.charAt(j - 1)) {
      cost = 0;
     }
     else {
      cost = 1;
     }
  
     d[i][j] = Math.min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + cost);
  
     if (
     i > 1 && j > 1 && a.charAt(i - 1) == b.charAt(j - 2) && a.charAt(i - 2) == b.charAt(j - 1)) {
      d[i][j] = Math.min(
      d[i][j], d[i - 2][j - 2] + cost)
  
     }
    }
   }
  
   return d[a.length][b.length];
  }
</script>

Test runner

Ready to run.

Testing in
TestOps/sec
Function 1
levenshtein1(s1, s2);
ready
Function 2
levenshtein2(s1, s2);
ready
Function 3
levenshtein3(s1, s2);
ready
Function 4
levenshtein4(s1, s2);
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.