fast-levenshtein - npm Package Compare versions

Comparing version 1.0.0 to 1.0.1

Gruntfile.js

@@ -61,13 +61,21 @@ module.exports = function(grunt) {
       }
-    }
+    },
+
+    benchmarkConfig: {
+      speed: {
+        src: ['benchmark/speed.js']
+      }
+    },
   });
 
+  require('load-grunt-tasks')(grunt);
+  grunt.renameTask('benchmark', 'benchmarkConfig');
 
-  grunt.loadNpmTasks('grunt-contrib-uglify');
-  grunt.loadNpmTasks('grunt-contrib-jshint');
-  grunt.loadNpmTasks('grunt-mocha-test');
+  grunt.registerTask('build', ['jshint', 'uglify', 'mochaTest']);
 
-  grunt.registerTask('build', ['mochaTest', 'jshint', 'uglify']);
+  grunt.registerTask('default', ['build']);
 
-  grunt.registerTask('default', ['build']);
-};
+  grunt.registerTask('benchmark', ['npm-install:levenshtein-edit-distance:levenshtein:natural', 'benchmarkConfig']);
+};
+
+

levenshtein.js

@@ -43,4 +43,3 @@ (function() {
       var previous  = new Array(str2.length + 1),
-          current = new Array(str2.length + 1),
-          i, j;
+          curCol, nextCol, i, j;
 
@@ -54,20 +53,22 @@ // initialise previous row
       for (i=0; i<str1.length; ++i) {
-        current[0] = i + 1;
+        nextCol = i + 1;
 
         for (j=0; j<str2.length; ++j) {
-          current[j + 1] = Math.min(
-              previous[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 ),    // substitution
-              current[j] + 1,    // insertion
-              previous[j + 1] + 1 // deletion
+          curCol = nextCol;
+
+          nextCol = Math.min(
+            previous[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 ),    // substitution
+            curCol + 1,           // insertion
+            previous[j + 1] + 1   // deletion
           );
 
-          // copy current into previous (in preparation for next iteration)
-          previous[j] = current[j];
+          // copy current col value into previous (in preparation for next iteration)
+          previous[j] = curCol;
         }
 
-        // copy current into previous (in preparation for next iteration)
-        previous[j] = current[j];
+        // copy last col value into previous (in preparation for next iteration)
+        previous[j] = nextCol;
       }
 
-      return current[str2.length];
+      return nextCol;
     },
@@ -95,13 +96,12 @@
       // two rows
-      var previous  = new Array(str2.length + 1),
-          current = new Array(str2.length + 1),
+      var prevRow  = new Array(str2.length + 1),
+          curCol, nextCol,
           i, j, startTime, currentTime;
 
       // initialise previous row
-      for (i=0; i<previous.length; ++i) {
-        previous[i] = i;
+      for (i=0; i<prevRow.length; ++i) {
+        prevRow[i] = i;
       }
 
-      current[0] = 1;
-
+      nextCol = 1;
       i = 0;
@@ -120,11 +120,11 @@ j = -1;
             // copy current into previous (in preparation for next iteration)
-            previous[j] = current[j];
+            prevRow[j] = nextCol;
 
             // if already done all chars
             if (str1.length <= (++i)) {
-              return cb(null, current[str2.length]);
+              return cb(null, nextCol);
             }
             // else if we have more left to do
             else {
-              current[0] = i + 1;
+              nextCol = i + 1;
               j = 0;
@@ -135,10 +135,11 @@ }
           // calculation
-          current[j + 1] = Math.min(
-              previous[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 ),    // substitution
-              current[j] + 1,    // insertion
-              previous[j + 1] + 1 // deletion
+          curCol = nextCol;
+          nextCol = Math.min(
+              prevRow[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 ),    // substitution
+              curCol + 1,    // insertion
+              prevRow[j + 1] + 1 // deletion
           );
 
           // copy current into previous (in preparation for next iteration)
-          previous[j] = current[j];
+          prevRow[j] = curCol;
 
@@ -145,0 +146,0 @@ // get current time

levenshtein.min.js

@@ -1,2 +0,2 @@
-/*! fast-levenshtein 2013-04-18. 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=Array(e.length+1),u=Array(e.length+1);for(r=0;l.length>r;++r)l[r]=r;for(r=0;n.length>r;++r){for(u[0]=r+1,t=0;e.length>t;++t)u[t+1]=Math.min(l[t]+(n.charAt(r)===e.charAt(t)?0:1),u[t]+1,l[t+1]+1),l[t]=u[t];l[t]=u[t]}return u[e.length]},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,h,o=Array(r.length+1),a=Array(r.length+1);for(u=0;o.length>u;++u)o[u]=u;a[0]=1,u=0,f=-1;var g=function(){for(i=(new Date).valueOf(),h=i;1e3>h-i;){if(r.length<=++f){if(o[f]=a[f],e.length<=++u)return t(null,a[r.length]);a[0]=u+1,f=0}a[f+1]=Math.min(o[f]+(e.charAt(u)===r.charAt(f)?0:1),a[f]+1,o[f+1]+1),o[f]=a[f],h=(new Date).valueOf()}if(null!==l.progress)try{l.progress.call(null,100*u/e.length)}catch(n){return t("Progress callback: "+(""+n))}setTimeout(g(),0)};g()}};"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)})();
+/*! 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)})();

package.json

 {
   "name": "fast-levenshtein",
-  "version": "1.0.0",
+  "version": "1.0.1",
   "description": "Efficient implementation of Levenshtein algorithm with asynchronous callback support",
   "main": "levenshtein.js",
-  "directories": {
-    "test": "test"
+  "scripts": {
+    "build": "grunt build",
+    "benchmark": "grunt benchmark"
   },
@@ -16,3 +17,6 @@ "devDependencies": {
     "grunt-contrib-jshint": "~0.4.3",
-    "grunt-mocha-test": "~0.2.2"
+    "grunt-mocha-test": "~0.2.2",
+    "grunt-npm-install": "~0.1.0",
+    "load-grunt-tasks": "~0.6.0",
+    "grunt-benchmark": "~0.2.0"
   },
@@ -19,0 +23,0 @@ "repository": {

README.md

@@ -22,10 +22,20 @@ # fast-levenshtein - Levenshtein algorithm in Javascript
 
-    $ npm install fast-levenshtein
+```bash
+$ npm install fast-levenshtein
+```
 
 ### Browser
 
-Add the following inside your HTML:
+Using bower:
 
-    <script type="text/javascript" src="https://github.com/hiddentao/fast-levenshtein/raw/master/levenshtein.min.js"></script>
+```bash
+$ bower install fast-levenshtein
+```
 
+Or the following inside your HTML:
+
+```html
+<script type="text/javascript" src="https://github.com/hiddentao/fast-levenshtein/raw/master/levenshtein.min.js"></script>
+```
+
 The API will then be accessible via the `window.Levenshtein` object.
@@ -37,77 +47,79 @@
 
-    var levenshtein = require('fast-levenshtein');
+```javascript
+var levenshtein = require('fast-levenshtein');
 
-    var distance = levenshtein.get('back', 'book');   // 2
-    var distance = levenshtein.get('我愛你', '我叫你');   // 1
+var distance = levenshtein.get('back', 'book');   // 2
+var distance = levenshtein.get('我愛你', '我叫你');   // 1
+```
 
-
 **Asynchronous**
 
-    var levenshtein = require('fast-levenshtein');
+```javascript
+var levenshtein = require('fast-levenshtein');
 
-    levenshtein.getAsync('back', 'book', function (err, distance) {
-      // err is null unless an error was thrown
-      // distance equals 2
-    });
+levenshtein.getAsync('back', 'book', function (err, distance) {
+  // err is null unless an error was thrown
+  // distance equals 2
+});
+```
 
 **Asynchronous with progress updates**
 
-    var levenshtein = require('fast-levenshtein');
+```javascript
+var levenshtein = require('fast-levenshtein');
 
-    var hugeText1 = fs.readFileSync(...);
-    var hugeText2 = fs.readFileSync(...);
+var hugeText1 = fs.readFileSync(...);
+var hugeText2 = fs.readFileSync(...);
 
-    levenshtein.getAsync(hugeText1, hugeText2, function (err, distance) {
-      // process the results as normal
-    }, {
-      progress: function(percentComplete) {
-        console.log(percentComplete + ' % completed so far...');
-      }
-    );
+levenshtein.getAsync(hugeText1, hugeText2, function (err, distance) {
+  // process the results as normal
+}, {
+  progress: function(percentComplete) {
+    console.log(percentComplete + ' % completed so far...');
+  }
+);
+```
 
 ## Building and Testing
 
-To build the code simply run [grunt](http://gruntjs.com/):
+To build the code and run the tests:
 
-    $ grunt
+```bash
+$ npm install -g grunt-cli
+$ npm install
+$ npm run build
+```
 
-This will run the tests followed by [jshint](http://jshint.com) followed by [uglify](https://github.com/mishoo/UglifyJS). To run the tests on their own do:
+## Performance
 
-    $ grunt mochaTest
+_Thanks to [Titus Wormer](https://github.com/wooorm) for [encouraging me](https://github.com/hiddentao/fast-levenshtein/issues/1) to do this._
 
+Benchmarked against other node.js levenshtein distance modules (on Macbook Air 2012, Core i7, 8GB RAM):
 
-## Contributing
+```bash
+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)
+Benchmark done.
+Fastest test is fast-levenshtein at 1.13x faster than levenshtein-edit-distance
+```
 
-If you wish to submit a pull request please update and/or create new tests for any changes you make and ensure the grunt build passes.
+You can run this benchmark yourself using:
 
----
+```bash
+$ npm install -g grunt-cli
+$ npm install
+$ npm run benchmark
+```
 
-Homepage: [https://github.com/hiddentao/fast-levenshtein](https://github.com/hiddentao/fast-levenshtein)
+## Contributing
 
+If you wish to submit a pull request please update and/or create new tests for any changes you make and ensure the grunt build passes.
 
-Copyright (c) 2013 [Ramesh Nair](http://www.hiddentao.com/)
+See [CONTRIBUTING.md](https://github.com/hiddentao/fast-levenshtein/blob/master/CONTRIBUTING.md) for details.
 
-Permission is hereby granted, free of charge, to any person
-obtaining a copy of this software and associated documentation
-files (the "Software"), to deal in the Software without
-restriction, including without limitation the rights to use,
-copy, modify, merge, publish, distribute, sublicense, and/or sell
-copies of the Software, and to permit persons to whom the
-Software is furnished to do so, subject to the following
-conditions:
+## License
 
-The above copyright notice and this permission notice shall be
-included in all copies or substantial portions of the Software.
-
-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
-EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
-OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
-NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
-HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
-WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
-FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
-OTHER DEALINGS IN THE SOFTWARE.
-
-
-
-
+MIT - see [LICENSE.md](https://github.com/hiddentao/fast-levenshtein/blob/master/LICENSE.md)

test/tests.js

 var _ = require('lodash'),
     chai = require('chai'),
     fs = require('fs'),
-    levenshtein = require('../levenshtein');
+    levenshtein = require('../levenshtein.min');
 
@@ -6,0 +6,0 @@ var expect = chai.expect,

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

34637

increased by14.48%

Number of package files

15

increased by25%

Lines of code

514

increased by59.63%

Number of lines in readme file

124

increased by10.71%

Worsened metrics

Dev dependency count

10

increased by42.86%

No dependency changes