Levenshtein algorithms

JavaScript performance comparison

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

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