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…

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