fast-levenshtein - npm Package Compare versions

Comparing version 1.0.1 to 1.0.2

benchmark/speed.js

@@ -1,4 +0,6 @@
-var fastLevenshtein = require('../Levenshtein.min').get,
+var fastLevenshtein = require('../levenshtein.min').get,
   levenshtein = require('levenshtein'),
   levenshteinEditDistance = require('levenshtein-edit-distance'),
+  levenshteinComponent = require('levenshtein-component'),
+  levenshteinDeltas = require('levenshtein-deltas'),
   natural = require('natural').LevenshteinDistance;
@@ -140,14 +142,22 @@
     {
-      name: 'fast-levenshtein',
+      name: 'levenshtein-edit-distance',
       fn: function() {
-        loop(fastLevenshtein);
+        loop(levenshteinEditDistance);
       }
     },
     {
-      name: 'levenshtein-edit-distance',
+      name: 'levenshtein-component',
       fn: function() {
-        loop(levenshteinEditDistance);
+        loop(levenshteinComponent);
       }
     },
     {
+      name: 'levenshtein-deltas',
+      fn: function() {
+        loop(function(v1,v2) {
+            return new levenshteinDeltas.Lev(v1,v2).distance();
+        });
+      }
+    },
+    {
       name: 'natural',
@@ -164,2 +174,8 @@ fn: function() {
     },
+    {
+      name: 'fast-levenshtein',
+      fn: function() {
+        loop(fastLevenshtein);
+      }
+    },
   ]
@@ -166,0 +182,0 @@ };

bower.json

 {
   "name": "fast-levenshtein",
-  "version": "1.0.1",
+  "version": "1.0.2",
   "homepage": "https://github.com/hiddentao/fast-levenshtein",
@@ -5,0 +5,0 @@ "authors": [

Gruntfile.js

@@ -77,5 +77,5 @@ module.exports = function(grunt) {
 
-  grunt.registerTask('benchmark', ['npm-install:levenshtein-edit-distance:levenshtein:natural', 'benchmarkConfig']);
+  grunt.registerTask('benchmark', ['npm-install:levenshtein-edit-distance:levenshtein:natural:levenshtein-component:levenshtein-deltas', 'benchmarkConfig']);
 };
 
 

levenshtein.js

@@ -42,8 +42,8 @@ (function() {
       // two rows
-      var previous  = new Array(str2.length + 1),
+      var prevRow  = new Array(str2.length + 1),
           curCol, nextCol, i, j;
 
       // initialise previous row
-      for (i=0; i<previous.length; ++i) {
-        previous[i] = i;
+      for (i=0; i<prevRow.length; ++i) {
+        prevRow[i] = i;
       }
@@ -58,14 +58,19 @@
 
-          nextCol = Math.min(
-            previous[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 ),    // substitution
-            curCol + 1,           // insertion
-            previous[j + 1] + 1   // deletion
-          );
+          // substution
+          nextCol = prevRow[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 );
+          // insertion
+          if (nextCol > curCol + 1) {
+            nextCol = curCol + 1;
+          }
+          // deletion
+          else if (nextCol > prevRow[j + 1] + 1) {
+            nextCol = prevRow[j + 1] + 1;
+          }
 
           // copy current col value into previous (in preparation for next iteration)
-          previous[j] = curCol;
+          prevRow[j] = curCol;
         }
 
         // copy last col value into previous (in preparation for next iteration)
-        previous[j] = nextCol;
+        prevRow[j] = nextCol;
       }
@@ -134,8 +139,14 @@
           curCol = nextCol;
-          nextCol = Math.min(
-              prevRow[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 ),    // substitution
-              curCol + 1,    // insertion
-              prevRow[j + 1] + 1 // deletion
-          );
 
+          // substution
+          nextCol = prevRow[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 );
+          // insertion
+          if (nextCol > curCol + 1) {
+            nextCol = curCol + 1;
+          }
+          // deletion
+          else if (nextCol > prevRow[j + 1] + 1) {
+            nextCol = prevRow[j + 1] + 1;
+          }
+
           // copy current into previous (in preparation for next iteration)
@@ -142,0 +153,0 @@ prevRow[j] = curCol;

levenshtein.min.js

 /*! fast-levenshtein 2014-07-10. Copyright Ramesh Nair <[e-mail]> (http://www.hiddentao.com/) */
-(function(){"use strict";var n=function(n){for(var e=Array.prototype.slice.call(arguments,1),r=0;e.length>r;++r){var t=e[r];for(var l in t)t.hasOwnProperty(l)&&(n[l]=t[l])}return n},e={get:function(n,e){if(n===e)return 0;if(0===n.length)return e.length;if(0===e.length)return n.length;var r,t,l,u,f=Array(e.length+1);for(l=0;f.length>l;++l)f[l]=l;for(l=0;n.length>l;++l){for(t=l+1,u=0;e.length>u;++u)r=t,t=Math.min(f[u]+(n.charAt(l)===e.charAt(u)?0:1),r+1,f[u+1]+1),f[u]=r;f[u]=t}return t},getAsync:function(e,r,t,l){if(l=n({},{progress:null},l),e===r)return t(null,0);if(0===e.length)return t(null,r.length);if(0===r.length)return t(null,e.length);var u,f,i,o,a,h,g=Array(r.length+1);for(i=0;g.length>i;++i)g[i]=i;f=1,i=0,o=-1;var c=function(){for(a=(new Date).valueOf(),h=a;1e3>h-a;){if(r.length<=++o){if(g[o]=f,e.length<=++i)return t(null,f);f=i+1,o=0}u=f,f=Math.min(g[o]+(e.charAt(i)===r.charAt(o)?0:1),u+1,g[o+1]+1),g[o]=u,h=(new Date).valueOf()}if(null!==l.progress)try{l.progress.call(null,100*i/e.length)}catch(n){return t("Progress callback: "+(""+n))}setTimeout(c(),0)};c()}};"undefined"!=typeof define&&null!==define&&define.amd?define(function(){return e}):"undefined"!=typeof module&&null!==module?module.exports=e:"undefined"!=typeof window&&null!==window&&(window.Levenshtein=e)})();
+(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=Array(n.length+1);for(l=0;f.length>l;++l)f[l]=l;for(l=0;e.length>l;++l){for(t=l+1,u=0;n.length>u;++u)r=t,t=f[u]+(e.charAt(l)===n.charAt(u)?0:1),t>r+1?t=r+1:t>f[u+1]+1&&(t=f[u+1]+1),f[u]=r;f[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=Array(r.length+1);for(o=0;h.length>o;++o)h[o]=o;f=1,o=0,i=-1;var c=function(){for(a=(new Date).valueOf(),g=a;1e3>g-a;){if(r.length<=++i){if(h[i]=f,n.length<=++o)return t(null,f);f=o+1,i=0}u=f,f=h[i]+(n.charAt(o)===r.charAt(i)?0:1),f>u+1?f=u+1:f>h[i+1]+1&&(f=h[i+1]+1),h[i]=u,g=(new Date).valueOf()}if(null!==l.progress)try{l.progress.call(null,100*o/n.length)}catch(e){return t("Progress callback: "+(""+e))}setTimeout(c(),0)};c()}};"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)})();

package.json

 {
   "name": "fast-levenshtein",
-  "version": "1.0.1",
+  "version": "1.0.2",
   "description": "Efficient implementation of Levenshtein algorithm with asynchronous callback support",
@@ -5,0 +5,0 @@ "main": "levenshtein.js",

README.md

@@ -10,6 +10,6 @@ # fast-levenshtein - Levenshtein algorithm in Javascript
 * Works in node.js and in the browser.
-* Reduced memory usage compared to other implementations by not needing to store the whole matrix ([more info](http://www.codeproject.com/Articles/13525/Fast-memory-efficient-Levenshtein-algorithm)).
+* Better performance than other implementations by not needing to store the whole matrix ([more info](http://www.codeproject.com/Articles/13525/Fast-memory-efficient-Levenshtein-algorithm)).
 * Provides synchronous and asynchronous versions of the algorithm.
 * Asynchronous version is almost as fast as the synchronous version for small strings and can also provide progress updates.
-* Comprehensive test suite.
+* Comprehensive test suite and performance benchmark.
 * Small: <1 KB minified and gzipped
@@ -100,11 +100,13 @@
 Running suite Implementation comparison [benchmark/speed.js]...
->> fast-levenshtein x 357 ops/sec ±2.32% (89 runs sampled)
->> levenshtein-edit-distance x 317 ops/sec ±4.16% (83 runs sampled)
->> natural x 219 ops/sec ±5.26% (77 runs sampled)
->> levenshtein x 179 ops/sec ±2.49% (73 runs sampled)
+>> levenshtein-edit-distance x 385 ops/sec ±3.14% (87 runs sampled)
+>> levenshtein-component x 369 ops/sec ±5.41% (72 runs sampled)
+>> levenshtein-deltas x 216 ops/sec ±4.95% (65 runs sampled)
+>> natural x 260 ops/sec ±1.57% (91 runs sampled)
+>> levenshtein x 178 ops/sec ±2.17% (78 runs sampled)
+>> fast-levenshtein x 1,985 ops/sec ±0.47% (100 runs sampled)
 Benchmark done.
-Fastest test is fast-levenshtein at 1.13x faster than levenshtein-edit-distance
+Fastest test is fast-levenshtein at 5.4x faster than levenshtein-component and levenshtein-edit-distance
 ```
 
-You can run this benchmark yourself using:
+You can run this benchmark yourself by doing:
 
@@ -114,2 +116,3 @@ ```bash
 $ npm install
+$ npm run build
 $ npm run benchmark
@@ -116,0 +119,0 @@ ```

New alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Fixed alerts

License Policy Violation

License

This package is not allowed per your license policy. Review the package's license to ensure compliance.

Found 1 instance in 1 package

Improved metrics

Total package byte prevSize

35532

increased by2.58%

Lines of code

540

increased by5.06%

Number of lines in readme file

127

increased by2.42%

No dependency changes