Levenshtein algorithms

JavaScript performance comparison

Revision 7 of this test case created

Preparation code

<script>
  // http://webreflection.blogspot.com/2009/02/levenshtein-algorithm-revisited-25.html
  var levenshtein1 = 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 levenshtein2(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 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];     
}

String.prototype.levenshtein5=
  function(t) {
    // ith character of s
    var si;
    // cost
    var c;
    // Step 1
    var n = this.length;
    var m = t.length;
    if (!n)
      return m;
    if (!m)
      return n;
    // Matrix
    var mx = [];
    // Step 2 - Init matrix
    for (var i=0; i<=n; i++) {
      mx[i] = [];
      mx[i][0] = i;
    }
    for (var j=0; j<=m; j++)
      mx[0][j] = j;
    // Step 3 - For each character in this
    for (var i=1; i<=n; i++) {
      si = this.charAt(i - 1);
      // Step 4 - For each character in t do step 5 (si == t.charAt(j - 1) ? 0 : 1) and 6
      for (var j=1; j<=m; j++)
        mx[i][j] = Math.min(mx[i - 1][j] + 1, mx[i][j - 1] + 1, mx[i - 1][j - 1] + (si == t.charAt(j - 1) ? 0 : 1));
    }
    // Step 7
    return mx[n][m];
  }

// Generics
if ( ! Array.forEach ) {
  Array.forEach = function forEach ( array, iterator, context ) {
    iterator = context
      ? iterator.bind( context )
      : iterator
    Array.prototype.forEach.call( array, iterator )
  }
}

// Levenshtein distance
function levenshtein6( str_m, str_n ) { var previous, current, matrix
  // Instance methods
  this.valueOf = function() {
    return this.distance
  }

  this.toString = this.inspect = function inspect ( no_print ) { var max, buff, sep, rows
    max = matrix.reduce( function( m, o ) {
      return Math.max( m, o.reduce( 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 = matrix.map( function( row ) { var cells
      cells = row.map( function( cell ) {
        return ( buff + cell ).slice( - buff.length )
      })
      return cells.join( ' |' ) + ' '
    })

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

  // Constructor
  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 ]
    Array.forEach( str_m, function( v, i ) { i++, previous[ i ] = i } )

    matrix[0] = previous
    Array.forEach( str_n, function( n_val, n_idx ) {
      current = [ ++n_idx ]
      Array.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 ]
  }
}

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 levenshtein8(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>

Test runner

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

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
1
levenshtein1( 'levenshtein testing', 'levenstein test' );
pending…
2
levenshtein2( 'levenshtein testing', 'levenstein test' );
pending…
3
levenshtein3( 'levenshtein testing', 'levenstein test' );
pending…
4
levenshtein4( 'levenshtein testing', 'levenstein test' );
pending…
5
"levenshtein testing".levenshtein5("levenstein test");
pending…
6
levenshtein6( 'levenshtein testing', 'levenstein test' );
pending…
7
levenshtein7( 'levenshtein testing', 'levenstein test' );
pending…
8
levenshtein8( 'levenshtein testing', 'levenstein test' );
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