levenshtein-edit-distance - npm Package Compare versions

Comparing version 0.0.1 to 0.1.0

benchmark/index.js

@@ -5,3 +5,3 @@ 'use strict';
 
-var distance, source, fastLevenshtein, natural, Levenshtein;
+var distance, source, fastLevenshtein, natural, Levenshtein, LevenshteinDeltas, levenshteinComponent;
 
@@ -14,2 +14,4 @@ distance = require('..');
     natural = require('natural').LevenshteinDistance;
+    LevenshteinDeltas = require('levenshtein-deltas').Lev;
+    levenshteinComponent = require('levenshtein-component');
 } catch (error) {
@@ -145,3 +147,3 @@ throw new Error(
 
-suite('fast-levenshtein — “fast”... pff ;)', function () {
+suite('fast-levenshtein', function () {
     bench('op/s * 1,000', function (next) {
@@ -161,2 +163,32 @@ var iterator = -1,
 
+suite('levenshtein-component', function () {
+    bench('op/s * 1,000', function (next) {
+        var iterator = -1,
+            previousValue = '',
+            value;
+
+        while (value = source[++iterator]) {
+            levenshteinComponent(previousValue, value);
+            previousValue = value;
+        }
+
+        next();
+    });
+});
+
+suite('levenshtein-deltas', function () {
+    bench('op/s * 1,000', function (next) {
+        var iterator = -1,
+            previousValue = '',
+            value;
+
+        while (value = source[++iterator]) {
+            new LevenshteinDeltas(previousValue, value).distance()
+            previousValue = value;
+        }
+
+        next();
+    });
+});
+
 suite('natural — to be fair, it offers more options', function () {
@@ -163,0 +195,0 @@ bench('op/s * 1,000', function (next) {

component.json

 {
   "name": "levenshtein-edit-distance",
-  "version": "0.0.1",
+  "version": "0.1.0",
   "description": "Levenshtein edit distance. No cruft. Real fast.",
@@ -5,0 +5,0 @@ "keywords": [

History.md

 
+0.1.0 / 2014-07-12
+==================
+
+ * Updated benchmark results
+ * Added two more competition benchmarks
+ * Added more unit tests
+ * Performance improvements
+ * Update eslint, istanbul
+ * Removed functionality to browserify unit tests by default
+
 0.0.1 / 2014-06-28
 ==================
-
- * 0.0.1

index.js

 'use strict';
 
 function levenshtein(value, alternative) {
-    var row, rowIterator, columnIterator,
-        character, previous, current, length, alternativeLength;
+    var previousRow, previousRowIterator, columnIterator,
+        character, next, current, length, alternativeLength, temporary;
 
+    /* Convert both values to string. */
     value = String(value);
     alternative = String(alternative);
 
+    /* Basic cases. */
     if (value === alternative) {
@@ -25,36 +27,47 @@ return 0;
 
-    row = [];
+    /* Initialise the previous row, this just creates an array from 0..N */
+    previousRow = [];
+    previousRowIterator = -1;
 
-    rowIterator = -1;
-
-    while (++rowIterator <= alternativeLength) {
-        row[rowIterator] = rowIterator;
+    while (++previousRowIterator <= alternativeLength) {
+        previousRow[previousRowIterator] = previousRowIterator;
     }
 
-    rowIterator = -1;
+    previousRowIterator = -1;
 
-    while (++rowIterator < length) {
-        character = value.charAt(rowIterator);
-        previous = rowIterator + 1;
+    while (++previousRowIterator < length) {
+        character = value.charAt(previousRowIterator);
+        next = previousRowIterator + 1;
         columnIterator = -1;
 
         while (++columnIterator < alternativeLength) {
-            current = Math.min(
-                row[columnIterator] + (
-                    character === alternative.charAt(columnIterator) ? 0 : 1
-                ),
-                previous + 1,
-                row[columnIterator + 1] + 1
-            );
+            current = next;
 
-            row[columnIterator] = previous;
-            previous = current;
+            next = previousRow[columnIterator];
+
+            if (character !== alternative.charAt(columnIterator)) {
+                next += 1;
+            }
+
+            temporary = current + 1;
+
+            if (next > temporary) {
+                next = temporary;
+            }
+
+            temporary = previousRow[columnIterator + 1] + 1;
+
+            if (next > temporary) {
+                next = temporary;
+            }
+
+            previousRow[columnIterator] = current;
         }
 
-        row[alternativeLength] = previous;
+        previousRow[alternativeLength] = next;
     }
 
-    return previous;
+    return next;
 }
 
 module.exports = levenshtein;

package.json

 {
   "name": "levenshtein-edit-distance",
-  "version": "0.0.1",
+  "version": "0.1.0",
   "description": "Levenshtein edit distance. No cruft. Real fast.",
@@ -14,5 +14,4 @@ "keywords": [
   "devDependencies": {
-    "browserify": "^4.2.0",
-    "eslint": "^0.6.2",
-    "istanbul": "~0.2.13",
+    "eslint": "^0.7.4",
+    "istanbul": "^0.3.0",
     "jscs": "^1.5.6",
@@ -34,8 +33,8 @@ "matcha": "^0.5.0",
     "lint-style": "node_modules/.bin/jscs index.js spec/levenshtein-edit-distance.spec.js benchmark/index.js --reporter=inline",
-    "prepublish": "npm run build-browser",
-    "build-browser": "browserify spec/levenshtein-edit-distance.spec.js -o spec/browser.spec.js",
+    "install-browser-test": "npm install browserify",
+    "build-browser-test": "node_modules/.bin/browserify spec/levenshtein-edit-distance.spec.js -o spec/browser.spec.js",
     "coverage": "node_modules/.bin/istanbul cover node_modules/.bin/_mocha -- -- spec/levenshtein-edit-distance.spec.js",
-    "install-benchmark": "npm install natural fast-levenshtein levenshtein",
+    "install-benchmark": "npm install natural fast-levenshtein levenshtein levenshtein-component levenshtein-deltas",
     "benchmark": "node_modules/.bin/matcha",
-    "make": "npm run build-browser && npm run lint && npm run coverage"
+    "make": "npm run lint && npm run coverage"
   },
@@ -42,0 +41,0 @@ "testling": {

Readme.md

@@ -43,6 +43,8 @@ # levenshtein-edit-distance [![Build Status](https://travis-ci.org/wooorm/levenshtein-edit-distance.svg?branch=master)](https://travis-ci.org/wooorm/levenshtein-edit-distance) [![Coverage Status](https://img.shields.io/coveralls/wooorm/levenshtein-edit-distance.svg)](https://coveralls.io/r/wooorm/levenshtein-edit-distance?branch=master)
 - [gf3/Levenshtein](http://github.com/gf3/Levenshtein) — Supports inspecting the matrix.
+- [levenshtein-component](https://www.npmjs.org/package/levenshtein-component);
+- [chrisdew/levenshtein-deltas](https://github.com/chrisdew/levenshtein-deltas);
 
 ## Benchmark
 
-On a MacBook Air, it runs about 313,000 op/s, which is faster than the competition.
+On a MacBook Air, it runs about 1,223,000 op/s, which is marginally faster than [hiddentao/fast-levenshtein](http://github.com/hiddentao/fast-levenshtein), and loads faster than the other competition.
 
@@ -57,13 +59,19 @@ Run the benchmark yourself:
 ```
-         levenshtein-edit-distance — this module
-313 op/s » op/s * 1,000
+             levenshtein-distance — this module
+  1,223 op/s » op/s * 1,000
 
-         fast-levenshtein — “fast”... pff ;)
-268 op/s » op/s * 1,000
+             fast-levenshtein
+  1,209 op/s » op/s * 1,000
 
-         natural — to be fair, it offers more options
-213 op/s » op/s * 1,000
+             levenshtein-component
+    330 op/s » op/s * 1,000
 
-         Levenshtein — to be fair, it lets you inspect a matrix
-141 op/s » op/s * 1,000
+             levenshtein-deltas
+    244 op/s » op/s * 1,000
+
+             natural — to be fair, it offers more options
+    208 op/s » op/s * 1,000
+
+             Levenshtein — to be fair, it lets you inspect a matrix
+    134 op/s » op/s * 1,000
 ```
@@ -70,0 +78,0 @@

spec/levenshtein-edit-distance.spec.js

@@ -17,2 +17,27 @@ 'use strict';
         assert(levenshteinDistance('saturday', 'sunday') === 3);
+
+        /* Tests from https://github.com/hiddentao/fast-levenshtein,
+         * just to make sure thing are interoperable. */
+        assert(levenshteinDistance('a', 'b') === 1);
+        assert(levenshteinDistance('ab', 'ac') === 1);
+        assert(levenshteinDistance('ac', 'bc') === 1);
+        assert(levenshteinDistance('abc', 'axc') === 1);
+        assert(levenshteinDistance('xabxcdxxefxgx', '1ab2cd34ef5g6') === 6);
+        assert(levenshteinDistance('xabxcdxxefxgx', 'abcdefg') === 6);
+        assert(levenshteinDistance('javawasneat', 'scalaisgreat') === 7);
+        assert(levenshteinDistance('example', 'samples') === 3);
+        assert(levenshteinDistance('sturgeon', 'urgently') === 6);
+        assert(levenshteinDistance('levenshtein', 'frankenstein') === 6);
+        assert(levenshteinDistance('distance', 'difference') === 5);
+        assert(levenshteinDistance('因為我是中國人所以我會說中文', '因為我是英國人所以我會說英文') === 2);
+        assert(levenshteinDistance(
+                'Morbi interdum ultricies neque varius condimentum. Donec ' +
+                'volutpat turpis interdum metus ultricies vulputate. Duis ' +
+                'ultricies rhoncus sapien, sit amet fermentum risus ' +
+                'imperdiet vitae. Ut et lectus',
+                'Duis erat dolor, cursus in tincidunt a, lobortis in odio. ' +
+                'Cras magna sem, pharetra et iaculis quis, faucibus quis ' +
+                'tellus. Suspendisse dapibus sapien in justo cursus'
+            ) === 143
+        );
     });
@@ -19,0 +44,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

Major refactor

Supply chain risk

Package has recently undergone a major refactor. It may be unstable or indicate significant internal changes. Use caution when updating to versions that include significant changes.

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

Dynamic require

Supply chain risk

Dynamic require can indicate the package is performing dangerous or unsafe dynamic code execution.

Found 1 instance in 1 package

Environment variable access

Supply chain risk

Package accesses environment variables, which may be a sign of credential stuffing or data theft.

Found 2 instances in 1 package

Improved metrics

Dev dependency count

5

decreased by-16.67%

Number of lines in readme file

80

increased by11.11%

Number of low supply chain risk alerts

0

decreased by-100%

Worsened metrics

Total package byte prevSize

19911

decreased by-59.22%

Number of package files

11

decreased by-8.33%

Lines of code

450

decreased by-66.89%

Number of medium supply chain risk alerts

1

increased byInfinity%

No dependency changes