Levenshtein algorithms

JavaScript performance comparison

Revision 19 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 (s1, s2) {
        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;

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

        var s1_idx = 0, s2_idx = 0;
        for (s1_idx = 0; s1_idx < s1_len + 1; s1_idx++) {
                v0[s1_idx] = s1_idx;
        }

        var char_s1, char_s2, cost, m_min, m, vv;

        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;

                        m_min  = v0[s1_idx + 1] +    1;
                        if ((m = v1[s1_idx    ] +    1) < m_min) m_min = m;
                        if ((m = v0[s1_idx    ] + cost) < m_min) m_min = m;

                        v1[s1_idx + 1] = m_min;
                }
               
                vv = v0; v0 = v1; v1 = vv;
        }
        return v0[s1_len];
}

function levenshtein5 (s1, s2) {
        if (s1 === s2) return 0;

        var s1_len = s1.length, s2_len = s2.length;

        if (s1_len === 0) return s2_len;
        if (s2_len === 0) return s1_len;

        var v0 = new Array(s1_len + 1), v1 = new Array(s1_len + 1);

        var s1_idx, s2_idx, char_s1, char_s2, cost, m_min, m, vv;

        for (s1_idx = s1_len; s1_idx >= 0; s1_idx--) {
                v0[s1_idx] = s1_idx;
        }
        // for (s1_idx = 0; s1_idx <= s1_len; s1_idx++) {
        //      v0[s1_idx] = s1_idx;
        // }

        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;

                        m_min  = v0[s1_idx + 1] +    1;
                        if ((m = v1[s1_idx    ] +    1) < m_min) m_min = m;
                        if ((m = v0[s1_idx    ] + cost) < m_min) m_min = m;

                        v1[s1_idx + 1] = m_min;
                }

                vv = v0; v0 = v1; v1 = vv;
        }
        return v0[s1_len];
}

var levenshtein6 = function (source, target) {
  if (!source || source.length === 0)
    if (!target || target.length === 0)
      return 0;
    else
      return target.length;
  else if (!target)
    return source.length;
     
  var sourceLength = source.length;
  var targetLength = target.length;
  var score = [];

  var INF = sourceLength + targetLength;
  score[0] = [INF];
  for (var i=0 ; i <= sourceLength ; i++) { score[i + 1] = []; score[i + 1][1] = i; score[i + 1][0] = INF; }
  for (var i=0 ; i <= targetLength ; i++) { score[1][i + 1] = i; score[0][i + 1] = INF; }

  var sd = {};
  var combinedStrings = source + target;
  var combinedStringsLength = combinedStrings.length;
  for(var i=0 ; i < combinedStringsLength ; i++) {
    var letter = combinedStrings[i];
    if (!sd.hasOwnProperty(letter))
      sd[letter] = 0;
  }

  for (var i=1 ; i <= sourceLength ; i++) {
    var DB = 0;
    for (var j=1 ; j <= targetLength ; j++) {
      var i1 = sd[target[j - 1]];
      var j1 = DB;

      if (source[i - 1] == target[j - 1]) {
        score[i + 1][j + 1] = score[i][j];
        DB = j;
      }
      else
        score[i + 1][j + 1] = Math.min(score[i][j], Math.min(score[i + 1][j], score[i][j + 1])) + 1;
       
      score[i + 1][j + 1] = Math.min(score[i + 1][j + 1], score[i1][j1] + (i - i1 - 1) + 1 + (j - j1 - 1));
    }
    sd[source[i - 1]] = i;
  }
  return score[sourceLength + 1][targetLength + 1];
}

function levenshtein7(a, b) {
  if (a == b) return 0;

  var aLen = a.length, bLen = b.length;

  if (!aLen) return bLen;
  if (!bLen) return aLen;

  var len = aLen + 1,
      v0 = new Array(len),
      v1 = new Array(len),
      c2, min, tmp,
      i = 0,
      j = 0;

  while(i < len) v0[i] = i++;

  while(j < bLen) {
    v1[0] = j + 1;
    c2 = b.charAt(j++);
    i = 0;

    while(i < aLen) {
      min = v0[i] - (a.charAt(i) == c2 ? 1 : 0);
      if (v1[i] < min) min = v1[i];
      if (v0[++i] < min) min = v0[i];
      v1[i] = min + 1;
    }

    tmp = v0; v0 = v1; v1 = tmp;
  }
  return v0[aLen];
}

                var levenshtein8 = (function() {
                        var row2 = new Uint16Array(1e6);
                        return function(s1, s2) {
                                var s1_len = s1.length, s2_len = s2.length;
                                if (s1_len && s2_len) {
                                        var i1 = 0, i2 = 0, a, b, c, c2, row = row2;
                                        while (i1 < s1_len)
                                                row[i1] = ++i1;
                                        while (i2 < s2_len) {
                                                c2 = s2.charCodeAt(i2);
                                                a = i2;
                                                ++i2;
                                                b = i2;
                                                for (i1 = 0; i1 < s1_len; ++i1) {
                                                        c = a + (s1.charCodeAt(i1) !== c2);
                                                        a = row[i1];
                                                        b = b < a ? (b < c ? b + 1 : c) : (a < c ? a + 1 : c);
                                                        row[i1] = b;
                                                }
                                        }
                                        return b;
                                } else {
                                        return s1_len + s2_len;
                                }
                        };
                })();

  // http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#JavaScript
function levenshtein9(a, b) {
  var aLen = a.length;
  var bLen = b.length;

  if(!aLen) return bLen;
  if(!bLen) return aLen;
 
  var matrix = [];
 
  // increment along the first column of each row
  var i;
  for(i = 0; i <= bLen; i++){
    matrix[i] = [i];
  }
 
  // increment each column in the first row
  var j;
  for(j = 0; j <= aLen; j++){
    matrix[0][j] = j;
  }
 
  // Fill in the rest of the matrix
  for(i = 1; i <= bLen; i++){
    for(j = 1; j <= aLen; 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[bLen][aLen];
};
</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
levenshtein5('levenshtein testing', 'levenstein test');
pending…
6
levenshtein6('levenshtein testing', 'levenstein test');
pending…
7
levenshtein7('levenshtein testing', 'levenstein test');
pending…
8
levenshtein8('levenshtein testing', 'levenstein test');
pending…
9
levenshtein9('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