# Levenshtein algorithms

## JavaScript performance comparison

Revision 2 of this test case created by isak

## Preparation code

``<script>  // http://webreflection.blogspot.com/2009/02/levenshtein-algorithm-revisited-25.html  var levenshtein1a = 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);  // http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#JavaScript  function levenshtein2a(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];  }  // https://raw.github.com/kvz/phpjs/master/functions/strings/levenshtein.js  function levenshtein3a(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 levenshtein3b(s1, s2) {    // Based on 3, cleaned up.    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; // Earlier IE may not support access by string index    }    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];  };  function levenshtein3c(s1, s2) {    // Based on 3b, dropped old IE support.    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];  };  // https://gist.github.com/1127070  function levenshtein4a(a, b, c, d, e, f, g) {    for (d = [e = 0]; a[e]; e++)    for (c = [f = 0]; b[++f];)    g = d[f] = e ? Math.min(d[--f], c[f] - (a[e - 1] == b[f]), c[++f] = d[f]) + 1 : f;    return g  }</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('he', 'hello there');      f('', 'hello');      f('asdfasdf', '');    };  };</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
1a
``test(levenshtein1a);``
pending…
2a
``test(levenshtein2a);``
pending…
3a
``test(levenshtein3a);``
pending…
4a
``test(levenshtein4a);``
pending…
3b
``test(levenshtein3b);``
pending…
3c
``test(levenshtein3c);``
pending…

## 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: