Levenshtein algorithms more

JavaScript performance comparison

Revision 12 of this test case created

Preparation code

<script>
  function min3(a, b, c) {
    return (a < b ? (a < c ? a : c) : b < c ? b : c);
  }

  // https://raw.github.com/kvz/phpjs/master/functions/strings/levenshtein.js
  // http://kevin.vanzonneveld.net
  // +            original by: Carlos R. L. Rodrigues (http://www.jsfromhell.com)
  // +            bugfixed by: Onno Marsman
  // +             revised by: Andrea Giammarchi (http://webreflection.blogspot.com)
  // + reimplemented by: Brett Zamir (http://brett-zamir.me)
  // + reimplemented by: Alexander M Beedie
  // *                example 1: levenshtein('Kevin van Zonneveld', 'Kevin van Sommeveld');
  // *                returns 1: 3

  function levenshtein3a(s1, s2) {
    if (s1 == s2) {
      return 0;
    }

    var s1_len = s1.length;
    var s2_len = s2.length;
    if (s1_len === 0) {
      return s2_len;
    }
    if (s2_len === 0) {
      return s1_len;
    }

    var split = false;
    try {
      split = !('0')[0];
    } catch (e) {
      split = true; // Earlier IE may not support access by string index
    }

    if (split) {
      s1 = s1.split('');
      s2 = s2.split('');
    }

    var v0 = new Array(s1_len + 1);
    var v1 = new Array(s1_len + 1);

    var s1_idx = 0,
        s2_idx = 0,
        cost = 0;
    for (s1_idx = 0; s1_idx < s1_len + 1; s1_idx++) {
      v0[s1_idx] = s1_idx;
    }
    var char_s1 = '',
        char_s2 = '';
    for (s2_idx = 1; s2_idx <= s2_len; s2_idx++) {
      v1[0] = s2_idx;
      char_s2 = s2[s2_idx - 1];

      for (s1_idx = 0; s1_idx < s1_len; s1_idx++) {
        char_s1 = s1[s1_idx];
        cost = (char_s1 == char_s2) ? 0 : 1;
        var m_min = v0[s1_idx + 1] + 1;
        var b = v1[s1_idx] + 1;
        var c = v0[s1_idx] + cost;
        if (b < m_min) {
          m_min = b;
        }
        if (c < m_min) {
          m_min = c;
        }
        v1[s1_idx + 1] = m_min;
      }
      var v_tmp = v0;
      v0 = v1;
      v1 = v_tmp;
    }
    return v0[s1_len];
  }

  // Based on 3, cleaned up.

  function levenshtein3b(s1, s2) {

    var i, j, c1, c2, cost, v0, v1, v_tmp, b, c, min, split, L1 = s1.length,
        L2 = s2.length;

    if (L1 === 0) {
      return L2;
    } else if (L2 === 0) {
      return L1;
    } else if (s1 === s2) {
      return 0;
    }
    try {
      split = !('0')[0];
    } catch (e) {
      split = true;
    }
    if (split) {
      s1 = s1.split('');
      s2 = s2.split('');
    }
    v0 = new Array(L1 + 1);
    v1 = new Array(L1 + 1);
    for (i = 0; i < L1 + 1; i++) {
      v0[i] = i;
    }
    for (j = 1; j <= L2; j++) {
      v1[0] = j;
      c2 = s2[j - 1];
      for (i = 0; i < L1; i++) {
        c1 = s1[i];
        cost = (c1 === c2) ? 0 : 1;
        min = v0[i + 1] + 1;
        b = v1[i] + 1;
        c = v0[i] + cost;
        if (b < min) {
          min = b;
        }
        if (c < min) {
          min = c;
        }
        v1[i + 1] = min;
      }
      v_tmp = v0;
      v0 = v1;
      v1 = v_tmp;
    }
    return v0[L1];
  };

  // Based on 3b, dropped old IE support.

  function levenshtein3c(s1, s2) {
    var i, j, c1, c2, cost, v0, v1, v_tmp, b, c, min, L1 = s1.length,
        L2 = s2.length;

    if (Math.min(L1, L2) === 0) {
      return Math.max(L1, L2);
    } else if (s1 === s2) {
      return 0;
    }
    v0 = new Array(L1 + 1);
    v1 = new Array(L1 + 1);
    for (i = 0; i < L1 + 1; i++) {
      v0[i] = i;
    }
    for (j = 1; j <= L2; j++) {
      v1[0] = j;
      c2 = s2[j - 1];
      for (i = 0; i < L1; i++) {
        c1 = s1[i];
        cost = (c1 === c2) ? 0 : 1;
        v1[i + 1] = Math.min(v0[i + 1] + 1, v1[i] + 1, v0[i] + cost);
      }
      v_tmp = v0;
      v0 = v1;
      v1 = v_tmp;
    }
    return v0[L1];
  };

  function levenshtein3d(s1, s2) {
    var i, j, cost, v0, v1, v_tmp, b, c, L1 = s1.length,
        L2 = s2.length;

    if (L1 === 0) {
      return L2;
    } else if (L2 === 0) {
      return L1;
    } else if (s1 === s2) {
      return 0;
    }
    v0 = new Array(L1 + 1);
    v1 = new Array(L1 + 1);
    for (i = 0; i < L1 + 1; i++) {
      v0[i] = i;
    }
    for (j = 1; j <= L2; j++) {
      v1[0] = j;
      for (i = 0; i < L1; i++) {
        cost = (s1[i] === s2[j - 1]) ? 0 : 1;
        v1[i + 1] = min3(v0[i + 1] + 1, v1[i] + 1, v0[i] + cost);

      }
      v_tmp = v0;
      v0 = v1;
      v1 = v_tmp;
    }
    return v0[L1];
  };

  // More optimized
  function levenshtein3e(s1, s2) {
        var i, j, cost, v0, v1, v_tmp, a, b, c,
            L1 = s1.length,
            L2 = s2.length;

        if (L1 === 0) {
            return L2;
        } else if (L2 === 0) {
            return L1;
        } else if (s1 === s2) {
            return 0;
        }
        v0 = new Array(L1 + 1);
        v1 = new Array(L1 + 1);
        for (i = 0; i < L1 + 1; i++) {
            v0[i] = i;
        }
        for (j = 1; j <= L2; j++) {
            v1[0] = j;
            for (i = 0; i < L1; i++) {
                cost = (s1[i] === s2[j - 1]) ? 0 : 1;
                a = v0[i + 1] + 1;
                b = v1[i] + 1;
                c = v0[i] + cost;
                v1[i + 1] = a < b ? a < c ? a : c : b < c ? b : c;
            }
            v_tmp = v0;
            v0 = v1;
            v1 = v_tmp;
        }
        return v0[L1];
    };

  // https://raw.github.com/kvz/phpjs/master/functions/strings/levenshtein.js
  function levenshtein3 (s1, s2) {
      // http://kevin.vanzonneveld.net
      // +            original by: Carlos R. L. Rodrigues (http://www.jsfromhell.com)
      // +            bugfixed by: Onno Marsman
      // +             revised by: Andrea Giammarchi (http://webreflection.blogspot.com)
      // + reimplemented by: Brett Zamir (http://brett-zamir.me)
      // + reimplemented by: Alexander M Beedie
      // *                example 1: levenshtein('Kevin van Zonneveld', 'Kevin van Sommeveld');
      // *                returns 1: 3
      if (s1 == s2) {
          return 0;
      }
 
      var s1_len = s1.length;
      var s2_len = s2.length;
      if (s1_len === 0) {
          return s2_len;
      }
      if (s2_len === 0) {
          return s1_len;
      }
 
      // BEGIN STATIC
      var split = false;
      try {
          split = !('0')[0];
      } catch (e) {
          split = true; // Earlier IE may not support access by string index
      }
      // END STATIC
      if (split) {
          s1 = s1.split('');
          s2 = s2.split('');
      }
 
      var v0 = new Array(s1_len + 1);
      var v1 = new Array(s1_len + 1);
 
      var s1_idx = 0,
          s2_idx = 0,
          cost = 0;
      for (s1_idx = 0; s1_idx < s1_len + 1; s1_idx++) {
          v0[s1_idx] = s1_idx;
      }
      var char_s1 = '',
          char_s2 = '';
      for (s2_idx = 1; s2_idx <= s2_len; s2_idx++) {
          v1[0] = s2_idx;
          char_s2 = s2[s2_idx - 1];
 
          for (s1_idx = 0; s1_idx < s1_len; s1_idx++) {
              char_s1 = s1[s1_idx];
              cost = (char_s1 == char_s2) ? 0 : 1;
              var m_min = v0[s1_idx + 1] + 1;
              var b = v1[s1_idx] + 1;
              var c = v0[s1_idx] + cost;
              if (b < m_min) {
                  m_min = b;
              }
              if (c < m_min) {
                  m_min = c;
              }
              v1[s1_idx + 1] = m_min;
          }
          var v_tmp = v0;
          v0 = v1;
          v1 = v_tmp;
      }
      return v0[s1_len];
  }

function levenshtein4(str1, str2) {
        var i, j,
                len1 = str1.length,
                len2 = str2.length,
            matrix = new Array(len1+1);

        for (i = 0; i <= len1; i++) {
                matrix[i] = new Array(len2+1);
                matrix[i][0] = i;
        }
        for (j = 0; j <= len2; j++) {
                matrix[0][j] = j;
        }

        for (j = 1; j <= len2; j++) {
                for(i = 1; i <= len1; i++) {
                        if (str1.charAt(i-1) === str2.charAt(j-1)) {
                                matrix[i][j] = matrix[i-1][j-1];
                        } else {
                                matrix[i][j] = Math.min(
                                        matrix[i-1][j] + 1,
                                        matrix[i][j-1] + 1,
                                        matrix[i-1][j-1] + 1
                                );
                        }
                }
        }

        return matrix[len1][len2];      
}

function levenshtein7(a, b){
  if(a.length == 0) return b.length;
  if(b.length == 0) return a.length;

  var matrix = [];

  // increment along the first column of each row
  var i;
  for(i = 0; i <= b.length; i++){
    matrix[i] = [i];
  }

  // increment each column in the first row
  var j;
  for(j = 0; j <= a.length; j++){
    matrix[0][j] = j;
  }

  // Fill in the rest of the matrix
  for(i = 1; i <= b.length; i++){
    for(j = 1; j <= a.length; j++){
      if(b.charAt(i-1) == a.charAt(j-1)){
        matrix[i][j] = matrix[i-1][j-1];
      } else {
        matrix[i][j] = Math.min(matrix[i-1][j-1] + 1, // substitution
                                Math.min(matrix[i][j-1] + 1, // insertion
                                         matrix[i-1][j] + 1)); // deletion
      }
    }
  }

  return matrix[b.length][a.length];
}

function levenshteinX(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];
  }

function levenshteinXX(str1, str2) {
        var current = [], prev, value;

        for (var i = 0; i <= str2.length; i++)
          for (var j = 0; j <= str1.length; j++) {
            if (i && j)
              if (str1.charAt(j - 1) === str2.charAt(i - 1))
                value = prev;
              else
                value = Math.min(current[j], current[j - 1], prev) + 1;
            else
              value = i + j;

            prev = current[j];
            current[j] = value;
          }

        return current.pop();
      }

// -----------------------------------
function levenshtein_n(str1, str2) {
    var m = str1.length,
        n = str2.length,
        d = [],
        i, j;
 
    if (!m) return n;
    if (!n) return m;
 
    for (i = 0; i <= m; i++) d[i] = [i];
    for (j = 0; j <= n; j++) d[0][j] = j;
 
    for (j = 1; j <= n; j++) {
        for (i = 1; i <= m; i++) {
            if (str1[i-1] == str2[j-1]) d[i][j] = d[i - 1][j - 1];
            else d[i][j] = Math.min(d[i-1][j], d[i][j-1], d[i-1][j-1]) + 1;
        }
    }
    return d[m][n];
}

</script>
<script>
Benchmark.prototype.setup = function() {
    test = function(f) {
      f('levenshtein testing', 'levenstein test');
      f('levenshtein testing', 'levenstein test');
      f('letein testing', 'levensein test');
      f('letein tsesting', 'letein tsestinh');
      f('letein tsesting', 'letein tsesting');
      f('lasheflkshekljf', 'asevöiafsveln as vevenstein test');
      f('asdf', 'asfe');
      f('hello', 'hello');
      f('hello', 'hallo');
      f('he', 'hello there');
      f('', 'hello');
      f('asdfasdf', '');
      f('I claudia', 'I, Claudia');
      f('Claudia', 'I, Claudia');
      f('lord of the rings fellowship of the ring', 'the lord of the rings: the fellowship of the ring');
    };
};
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
3
test(levenshtein3);
pending…
3a
test(levenshtein3a);
pending…
3b
test(levenshtein3b);
pending…
3c
test(levenshtein3c);
pending…
3d
test(levenshtein3d);
pending…
3e
test(levenshtein3e);
pending…
4
test(levenshtein4);
pending…
7
test(levenshtein7);
pending…
8
test(levenshteinX);
pending…
9
test(levenshteinXX);
pending…
10
test(levenshtein_n);
pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL. Here’s a list of current revisions for this page:

0 comments

Add a comment