Levenshtein Distance

JavaScript performance comparison

Revision 12 of this test case created by Marco de Wit

Info

*** Reupload of Revision 4, Updated by TheSpanishInquisition ***

Accidentally forgot to add functional optimisation. Its about 5 times faster than prototype optimisation. I cannot figure out why.

*** Fork of Revision 2, Updated by TheSpanishInquisition ***

Changed test data. Each test is now executed against exactly the same data set in the name of fairness. Added fully optimised adaptations of James Westgate's implementation. Removed old Damerau–Levenshtein Distance test CompareLD2 (see this jsPerf for comparison of Damerau–Levenshtein Distance, this is for Levenshtein Distance only).

Wiki Rosetta Code

*** Original ***

Prompted by a Stack Overflow question, this will compare implementations of the Levenshtein distance algorithm.

By adding a limit and optimising comparison operators, I hope to further increase the performance of the Westgate implementation.

Preparation code

 
<script>
Benchmark.prototype.setup = function() {
    Math.randomInt = function(min, max) {
        return Math.floor(Math.random() * (max - min + 1)) + min;
    };
   
    // Generate random strings.
    window.dataSet = [];
    window.dataSetLength = 50;
    for (var i = 0; i < dataSetLength; i++) {
        dataSet[i] = Math.randomInt(999, 999999).toString();
    }
   
    // Original.
    window.CompareLD1 = function(min, split) {
      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 minn(a, b, c) {
      if (a > b) a = b;
      if (a < c) return a;
      return c;
    }
   
    // Stoianovici's.
    window.CompareLD3 = function(S1, S2, limit) {
      if (S1 == null || S2 == null || typeof(S1) != "string" || typeof(S2) != "string") return 9999999;
      if (limit == null) limit = 9999999;
      if (Math.abs(S1.length - S2.length) > limit) return 9999999;
      S1 = S1.toLowerCase();
      S2 = S2.toLowerCase();
      if (S1 == S2) return 0;
      var n = S1.length;
      var m = S2.length;
      dist = new Array(new Array(m + 2), new Array(m + 2));
      current = 0;
      for (i = 0; i <= m + 1; i++) {
        dist[1][i] = i;
      }
      for (i = 1; i <= n; i++) {
        ok = 0;
        dist[current][0] = i;
        if (i - limit >= 1) dist[current][i - limit - 1] = 9999999;
        for (j = Math.max(i - limit, 1); j <= Math.min(i + limit, m); j++) {
          if (S1.substr(i - 1, 1) == S2.substr(j - 1, 1)) dist[current][j] = dist[1 - current][j - 1];
          else dist[current][j] = minn(dist[1 - current][j - 1], dist[1 - current][j], dist[current][j - 1]) + 1;
          if (dist[current][j] <= limit) ok = 1;
        }
        if (i + limit <= m) {
          dist[current][i + limit + 1] = 9999999;
        }
        if (!ok) return 9999999;
        current = 1 - current;
      }
      if (dist[1 - current][m] > limit) return 9999999;
      return dist[1 - current][m];
    };
   
    // Westgate's.
    window.CompareLD6 = function(s, t, lim) {
      if (!lim) lim = 20;
      if (Math.abs(s.length - t.length) > lim) return lim;
   
      var d = []; //2d matrix
      // Step 1
      var n = s.length,
          m = t.length;
   
      if (n === 0) return m;
      if (m === 0) return n;
   
      var i = n + 1;
      do {
        d[i] = [];
      } while (i--);
   
      // Step 2
      i = n + 1, j = m + 1;
      do {
        d[i][0] = i;
      } while (i--);
      do {
        d[0][j] = j;
      } while (j--);
   
      // Step 3
      for (var i = 1; i <= n; i++) {
        var s_i = s.charAt(i - 1);
   
        // Step 4
        for (var j = 1; j <= m; j++) {
   
          //Check the jagged ld total so far
          if (i === j && d[i][j] > 4) return n;
   
          var t_j = t.charAt(j - 1);
          var cost = (s_i === t_j) ? 0 : 1; // Step 5
          //Calculate the minimum
          var mi = d[i - 1][j] + 1;
          var b = d[i][j - 1] + 1;
          var c = d[i - 1][j - 1] + cost;
   
          if (b < mi) mi = b;
          if (c < mi) mi = c;
   
          d[i][j] = mi; // Step 6
        }
      }
   
      // Step 7
      return d[n][m];
    }
   
   
   
    // TheSpanishInquisition
   
    // Cache the matrix. Note this implementation is limited to
    // strings of 64 char or less. This could be altered to update
    // dynamically, or a larger value could be used.
    var matrix = [];
    for (var i = 0; i < 64; i++) {
        matrix[i] = [i];
        matrix[i].length = 64;
    }
    for (var i = 0; i < 64; i++) {
        matrix[0][i] = i;
    }
   
    // Functional implementation of Levenshtein Distance.
    String.levenshteinDistance = function(__this, that, limit) {
        var thisLength = __this.length, thatLength = that.length;
   
        if (Math.abs(thisLength - thatLength) > (limit || 32)) return limit || 32;
        if (thisLength === 0) return thatLength;
        if (thatLength === 0) return thisLength;
   
        // Calculate matrix.
        var this_i, that_j, cost, min, t;
        for (i = 1; i <= thisLength; ++i) {
                this_i = __this[i-1];
   
                // Step 4
                for (j = 1; j <= thatLength; ++j) {
                        // Check the jagged ld total so far
                        if (i === j && matrix[i][j] > 4) return thisLength;
   
                        that_j = that[j-1];
                        cost = (this_i === that_j) ? 0 : 1; // Step 5
                        // Calculate the minimum (much faster than Math.min(...)).
                        min    = matrix[i - 1][j    ] + 1;                                              // Deletion.
                        if ((t = matrix[i    ][j - 1] + 1   ) < min) min = t;   // Insertion.
                        if ((t = matrix[i - 1][j - 1] + cost) < min) min = t;   // Substitution.
   
                        matrix[i][j] = min;     // Update matrix.
                }
        }
   
        return matrix[thisLength][thatLength];
    };
   
    // Prototype implementation of Levenshtein Distance.
    String.prototype.levenshteinDistance = function(that, limit) {
        var thisLength = this.length, thatLength = that.length;
   
        if (Math.abs(thisLength - thatLength) > (limit || 32)) return limit || 32;
        if (thisLength === 0) return thatLength;
        if (thatLength === 0) return thisLength;
   
        // Calculate matrix.
        var this_i, that_j, cost, min, t;
        for (i = 1; i <= thisLength; ++i) {
                this_i = this[i-1];
   
                // Step 4
                for (j = 1; j <= thatLength; ++j) {
                        // Check the jagged ld total so far
                        if (i === j && matrix[i][j] > 4) return thisLength;
   
                        that_j = that[j-1];
                        cost = (this_i === that_j) ? 0 : 1; // Step 5
                        // Calculate the minimum (much faster than Math.min(...)).
                        min    = matrix[i - 1][j    ] + 1;                                              // Deletion.
                        if ((t = matrix[i    ][j - 1] + 1   ) < min) min = t;   // Insertion.
                        if ((t = matrix[i - 1][j - 1] + cost) < min) min = t;   // Substitution.
   
                        matrix[i][j] = min;     // Update matrix.
                }
        }
   
        return matrix[thisLength][thatLength];
    };
   
   
   
   
    var levDist = (function () {
        var _d, _i = 0, _j = 0;
   
        function allocate(i, j) {
                if (i > _i || j > _j) {
                        _d = new Array((i > j) ? i : j);
                        _i = i;
                        _j = j;
                        for (; i >= 0; i--) _d[i]    = [i];
                        for (; j >= 0; j--) _d[0][j] = j;
                }
                return _d;
        };
   
        allocate (64, 64);
   
        return function(s, t, damerau) {
                // Step 1
                var n = s.length;
                var m = t.length;
   
                if (n == 0) return m;
                if (m == 0) return n;
                if (s == t) return 0;
   
                //Create an array of arrays in javascript (a descending loop is quicker)
   
                var i = n, j = m; //, d = new Array(n + 1);
   
                // Step 2
                var d = allocate(i, j);
   
                // for (; i >= 0; i--) d[i]    = [i];
                // for (; j >= 0; j--) d[0][j] = j;
   
                var s_i, t_j, cost, mi, b, c, r, x1, x2, y1, y2;
   
                // Step 3
                for (i = 1, x1 = 0, x2 = -1; i <= n; i++, x1++, x2++) {
                        s_i = s[x1];
   
                        // Step 4
                        for (j = 1, y1 = 0, y2 = -1; j <= m; j++, y1++, y2++) {
   
                                //Check the jagged ld total so far
                                if (i == j && d[i][j] > 4) return n;
   
                                t_j = t[y1];
                                cost = (s_i === t_j) ? 0 : 1; // Step 5
   
                                //Calculate the minimum
                                mi     = d[x1][j ] + 1;
                                if ((r = d[i ][y1] + 1) < mi) mi = r;
                                if ((r = d[x1][y1] + cost) < mi) mi = r;
                                // b = d[i][j - 1] + 1;
                                // c = d[i - 1][j - 1] + cost;
   
                                // if (b < mi) mi = b;
                                // if (c < mi) mi = c;
   
                                //Damerau transposition
                                if (damerau && i > 1 && j > 1 && s_i == t[y2] && s[x2] == t_j) {
                                        if ((r = d[x2][y2] + cost) < mi) mi = r;
                                }
   
                                d[i][j] = mi; // Step 6
                        }
                }
   
                // Step 7
                return d[n][m];
        };
    })();
   
   
   
   
   
   
    function levenshtein_kitho(s, t, damerau) {
        // Step 1
        var n = s.length;
        var m = t.length;
   
        if (n == 0) return m;
        if (m == 0) return n;
        if (s == t) return 0;
   
        //Create an array of arrays in javascript (a descending loop is quicker)
        var d = new Array(n + 1);
   
        // Step 2
        for (var i = n; i >= 0; i--) d[i]    = [i];
        for (var j = m; j >= 0; j--) d[0][j] = j;
   
        // Step 3
        for (var i = 1; i <= n; i++) {
                var s_i = s[i - 1];
   
                // Step 4
                for (var j = 1; j <= m; j++) {
   
                        //Check the jagged ld total so far
                        if (i == j && d[i][j] > 4) return n;
   
                        var t_j = t[j - 1];
                        var cost = (s_i === t_j) ? 0 : 1; // Step 5
   
                        //Calculate the minimum
                        var mi = d[i - 1][j] + 1;
                        var b = d[i][j - 1] + 1;
                        var c = d[i - 1][j - 1] + cost;
   
                        if (b < mi) mi = b;
                        if (c < mi) mi = c;
   
                        //Damerau transposition
                        if (i > 1 && j > 1 && s_i == t[j - 2] && s[i - 2] == t_j) {
                                var r = d[i - 2][j - 2] + cost;
                                if (r < mi) mi = r;
                        }
   
                        d[i][j] = mi; // Step 6
                }
        }
   
        // Step 7
        return d[n][m];
    }
   
   
    // Functional implementation of Levenshtein Distance.
    var _levenshteinDistance = function(__this, that) {
        var thisLength = __this.length, thatLength = that.length;
   
    //  if (Math.abs(thisLength - thatLength) > (limit || 32)) return limit || 32;
        if (thisLength === 0) return thatLength;
        if (thatLength === 0) return thisLength;
        if (thisLength == thatLength) return 0;
   
   
        var matrix = new Array(thisLength + 1), i = thisLength, j = thatLength;
        for (; i >= 0; i--) matrix[i] = [i];
        for (; j >= 0; j--) matrix[0][j] = j;
   
        // Calculate matrix.
        var this_i, that_j, cost, min, t, x, y;
        for (i = 1, x = 0; i <= thisLength; ++i, ++x) {
                // x = i - 1;
                this_i = __this[x];
   
                // Step 4
                for (j = 1, y = 0; j <= thatLength; ++j, ++y) {
                        // Check the jagged ld total so far
                        if (i === j && matrix[i][j] > 4) return thisLength;
   
                        // y = j - 1;
                        that_j = that[y];
                        cost = (this_i === that_j) ? 0 : 1; // Step 5
                        // Calculate the minimum (much faster than Math.min(...)).
                        min    = matrix[x][j] + 1;                                              // Deletion.
                        if ((t = matrix[i][y] + 1   ) < min) min = t;   // Insertion.
                        if ((t = matrix[x][y] + cost) < min) min = t;   // Substitution.
   
                        matrix[i][j] = min;     // Update matrix.
                }
        }
   
        return matrix[thisLength][thatLength];
    };
                var levenshteinMdW = (function() {
                        var row2 = [];
                        return function(s1, s2) {
                                if (s1 === s2) {
                                        return 0;
                                } else {
                                        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 ? 1 : 0);
                                                                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;
                                        }
                                }
                        };
                })();
   
};
</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
Original [ no limit ]
for (var x = 0; x < dataSetLength; x++) {
    for (var y = 0; y < dataSetLength; y++) {
        CompareLD1(dataSet[x], dataSet[y]);
    }
}
pending…
Westgate's [ no limit ]
for (var x = 0; x < dataSetLength; x++) {
    for (var y = 0; y < dataSetLength; y++) {
        CompareLD6(dataSet[x], dataSet[y]);
    }
}
pending…
Stoianovici's [ no limit ]
for (var x = 0; x < dataSetLength; x++) {
    for (var y = 0; y < dataSetLength; y++) {
        CompareLD3(dataSet[x], dataSet[y]);
    }
}
pending…
TheSpanishInquisition's [ no limit ]
for (var x = 0; x < dataSetLength; x++) {
    for (var y = 0; y < dataSetLength; y++) {
        String.levenshteinDistance(dataSet[x], dataSet[y]);
    }
}
pending…
TheSpanishInquisition's [ prototype ] [ no limit ]
for (var x = 0; x < dataSetLength; x++) {
    for (var y = 0; y < dataSetLength; y++) {
        dataSet[x].levenshteinDistance(dataSet[y]);
    }
}
pending…
kitho
for (var x = 0; x < dataSetLength; x++) {
    for (var y = 0; y < dataSetLength; y++) {
        levDist(dataSet[x], dataSet[y]);
    }
}
pending…
kitho2
for (var x = 0; x < dataSetLength; x++) {
    for (var y = 0; y < dataSetLength; y++) {
        levenshtein_kitho(dataSet[x], dataSet[y]);
    }
}
pending…
kitho3
for (var x = 0; x < dataSetLength; x++) {
    for (var y = 0; y < dataSetLength; y++) {
        _levenshteinDistance(dataSet[x], dataSet[y]);
    }
}

 
pending…
Marco de Wit's Levenshtein
for (var x = 0; x < dataSetLength; x++) {
    for (var y = 0; y < dataSetLength; y++) {
        levenshteinMdW(dataSet[x], dataSet[y]);
    }
}

 
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