Levenshtein (v6)

Revision 6 of this benchmark created by pixnbits on

Preparation HTML

<script>
  var s1 = 'kitten',
      s2 = 'sitting';

  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];
  }

  var levenshtein5 = function(s, t) { /* @author: Gabor Zsoter http://zsitro.com */

      var s_l = s.length;
      var t_l = t.length;
      if (s == t) return 0;
      if (s_l == 0) return t_l;
      if (t_l == 0) return s_l;


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

      for (var i = 0; i < t_l + 1; i++) {
        v0[i] = i;
      }

      for (i = 0; i < s_l; i++) {
        v1[0] = i + 1;

        for (var j = 0; j < t_l; j++) {

          v1[j + 1] = (function(a, b, c) {
            var m = a;
            if (m > b) m = b;
            if (m > c) return c;
            return m;
          }(v1[j] + 1, v0[j + 1] + 1, v0[j] + ((s[i] == t[j]) ? 0 : 1)));
        }

        for (j = 0; j < t_l + 1; j++) {
          v0[j] = v1[j];
        }
      }

      return v1[t_l];
      };



  function levenshtein6(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];
  }
</script>

<script>
(function(root, factory){
  if (typeof define == 'function' && typeof define.amd == 'object' && define.amd) {
    define(function(){
      return factory(root);
    });
  } else if (typeof module == 'object' && module && module.exports) {
    module.exports = factory(root);
  } else {
    root.Levenshtein = factory(root);
  }
}(this, function(root){

  function forEach( array, fn ) { var i, length
    i = -1
    length = array.length
    while ( ++i < length )
      fn( array[ i ], i, array )
  }

  function map( array, fn ) { var result
    result = Array( array.length )
    forEach( array, function ( val, i, array ) {
      result.push( fn( val, i, array ) )
    })
    return result
  }

  function reduce( array, fn, accumulator ) {
    forEach( array, function( val, i, array ) {
      accumulator = fn( val, i, array )
    })
    return accumulator
  }

  // Levenshtein distance
  function Levenshtein( str_m, str_n ) { var previous, current, matrix
    // Constructor
    matrix = this._matrix = []

    // Sanity checks
    if ( str_m == str_n )
      return this.distance = 0
    else if ( str_m == '' )
      return this.distance = str_n.length
    else if ( str_n == '' )
      return this.distance = str_m.length
    else {
      // Danger Will Robinson
      previous = [ 0 ]
      forEach( str_m, function( v, i ) { i++, previous[ i ] = i } )

      matrix[0] = previous
      forEach( str_n, function( n_val, n_idx ) {
        current = [ ++n_idx ]
        forEach( str_m, function( m_val, m_idx ) {
          m_idx++
          if ( str_m.charAt( m_idx - 1 ) == str_n.charAt( n_idx - 1 ) )
            current[ m_idx ] = previous[ m_idx - 1 ]
          else
            current[ m_idx ] = Math.min
              ( previous[ m_idx ]     + 1   // Deletion
              , current[  m_idx - 1 ] + 1   // Insertion
              , previous[ m_idx - 1 ] + 1   // Subtraction
              )
        })
        previous = current
        matrix[ matrix.length ] = previous
      })

      return this.distance = current[ current.length - 1 ]
    }
  }

  Levenshtein.prototype.toString = Levenshtein.prototype.inspect = function inspect ( no_print ) { var matrix, max, buff, sep, rows
    matrix = this.getMatrix()
    max = reduce( matrix,function( m, o ) {
      return Math.max( m, reduce( o, Math.max, 0 ) )
    }, 0 )
    buff = Array( ( max + '' ).length ).join( ' ' )

    sep = []
    while ( sep.length < (matrix[0] && matrix[0].length || 0) )
      sep[ sep.length ] = Array( buff.length + 1 ).join( '-' )
    sep = sep.join( '-+' ) + '-'

    rows = map( matrix, function( row ) { var cells
      cells = map( row, function( cell ) {
        return ( buff + cell ).slice( - buff.length )
      })
      return cells.join( ' |' ) + ' '
    })

    return rows.join( "\n" + sep + "\n" )
  }

  Levenshtein.prototype.getMatrix = function () {
    return this._matrix.slice()
  }

  Levenshtein.prototype.valueOf = function() {
    return this.distance
  }

  return Levenshtein

}));
var NpmLevenshtein = Levenshtein;
</script>

<script>
(function(){"use strict";var e=function(e){for(var n=Array.prototype.slice.call(arguments,1),r=0;n.length>r;++r){var t=n[r];for(var l in t)t.hasOwnProperty(l)&&(e[l]=t[l])}return e},n={get:function(e,n){if(e===n)return 0;if(0===e.length)return n.length;if(0===n.length)return e.length;var r,t,l,u,f,o=Array(n.length+1);for(l=0;o.length>l;++l)o[l]=l;for(l=0;e.length>l;++l){for(t=l+1,u=0;n.length>u;++u)r=t,t=o[u]+(e.charAt(l)===n.charAt(u)?0:1),f=r+1,t>f&&(t=f),f=o[u+1]+1,t>f&&(t=f),o[u]=r;o[u]=t}return t},getAsync:function(n,r,t,l){if(l=e({},{progress:null},l),n===r)return t(null,0);if(0===n.length)return t(null,r.length);if(0===r.length)return t(null,n.length);var u,f,o,i,a,g,h,c=Array(r.length+1);for(o=0;c.length>o;++o)c[o]=o;f=1,o=0,i=-1;var d=function(){for(g=(new Date).valueOf(),h=g;1e3>h-g;){if(r.length<=++i){if(c[i]=f,n.length<=++o)return t(null,f);f=o+1,i=0}u=f,f=c[i]+(n.charAt(o)===r.charAt(i)?0:1),a=u+1,f>a&&(f=a),a=c[i+1]+1,f>a&&(f=a),c[i]=u,h=(new Date).valueOf()}if(null!==l.progress)try{l.progress.call(null,100*o/n.length)}catch(e){return t("Progress callback: "+(""+e))}setTimeout(d(),0)};d()}};"undefined"!=typeof define&&null!==define&&define.amd?define(function(){return n}):"undefined"!=typeof module&&null!==module?module.exports=n:"undefined"!=typeof window&&null!==window&&(window.Levenshtein=n)})();
var NpmFastLevenshtein = Levenshtein;
</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
Function 5 (zsitro)
levenshtein5(s1, s2);
ready
Function 6 (phpjs)
levenshtein6(s1, s2);
ready
levenshtein (npm)
NpmLevenshtein(s1, s2)
ready
fast-levenshtein (npm)
NpmFastLevenshtein.get(s1, s2)
ready

Revisions

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