Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
fastest-levenshtein
Advanced tools
fastest-levenshtein - npm Package Compare versions
Comparing version 1.0.12 to 1.0.13
| { | ||
| "name": "fastest-levenshtein", | ||
| "version": "1.0.12", | ||
| "version": "1.0.13", | ||
| "description": "Fastest Levenshtein distance implementation in JS.", | ||
| "main": "index.js", | ||
| "main": "mod.js", | ||
| "types": "mod.d.ts", | ||
| "repository": { | ||
@@ -36,29 +37,35 @@ "type": "git", | ||
| "scripts": { | ||
| "test": "jest", | ||
| "test:coverage": "jest --coverage", | ||
| "test:coveralls": "jest --coverage --coverageReporters=text-lcov | coveralls" | ||
| "build": "tsc mod.ts --declaration", | ||
| "prepare": "npm run build", | ||
| "bench": "npm run build && tsc bench.ts && node bench.js", | ||
| "test": "npm run build && tsc test.ts && jest test.js", | ||
| "test:coverage": "npm run build && jest --coverage", | ||
| "test:coveralls": "npm run build && jest --coverage --coverageReporters=text-lcov | coveralls" | ||
| }, | ||
| "devDependencies": { | ||
| "@types/benchmark": "^1.0.33", | ||
| "@types/jest": "^26.0.15", | ||
| "@typescript-eslint/eslint-plugin": "^4.7.0", | ||
| "@typescript-eslint/parser": "^4.7.0", | ||
| "benchmark": "^2.1.4", | ||
| "coveralls": "^3.1.0", | ||
| "eslint": "^7.5.0", | ||
| "eslint-config-airbnb": "^18.2.0", | ||
| "eslint-config-airbnb-base": "^14.2.0", | ||
| "eslint": "^7.13.0", | ||
| "eslint-config-node": "^4.1.0", | ||
| "eslint-config-prettier": "^6.11.0", | ||
| "eslint-plugin-import": "^2.22.0", | ||
| "eslint-plugin-jsx-a11y": "^6.3.1", | ||
| "eslint-config-prettier": "^6.15.0", | ||
| "eslint-plugin-import": "^2.22.1", | ||
| "eslint-plugin-node": "^11.1.0", | ||
| "eslint-plugin-prettier": "^3.1.4", | ||
| "eslint-plugin-react": "^7.20.3", | ||
| "eslint-plugin-react-hooks": "^4.0.0", | ||
| "fast-levenshtein": "^2.0.6", | ||
| "jest": "^26.1.0", | ||
| "jest": "^26.6.3", | ||
| "js-levenshtein": "^1.1.6", | ||
| "leven": "^3.1.0", | ||
| "levenshtein-edit-distance": "^2.0.5", | ||
| "natural": "^2.1.5", | ||
| "prettier": "^2.0.5", | ||
| "talisman": "^1.1.2", | ||
| "levenshtein-edit-distance": "^2.0.5" | ||
| "prettier": "^2.1.2", | ||
| "talisman": "^1.1.3", | ||
| "typescript": "^4.0.5" | ||
| }, | ||
| "engines": { | ||
| "node": ">= 4.9.1" | ||
| } | ||
| } |
| # fastest-levenshtein :rocket: | ||
| > Fastest JS implemenation of [Levenshtein distance](https://en.wikipedia.org/wiki/Levenshtein_distance).<br> | ||
| > Fastest JS/TS implemenation of [Levenshtein distance](https://en.wikipedia.org/wiki/Levenshtein_distance).<br> | ||
| > Measure the difference between two strings. | ||
| [](https://travis-ci.org/ka-weihe/node-levenshtein) | ||
| [](https://travis-ci.org/ka-weihe/fastest-levenshtein) | ||
| [](https://coveralls.io/github/ka-weihe/node-levenshtein?branch=master) | ||
| ``` | ||
| [](https://lgtm.com/projects/g/ka-weihe/fastest-levenshtein/context:javascript) | ||
|  | ||
| ```bash | ||
| $ npm i fastest-levenshtein | ||
@@ -39,3 +41,3 @@ ``` | ||
| ## Benchmark | ||
| I generated 500 pairs of strings with length N. I measured the ops/sec each library achieves to process all the given pairs. Higher is better. `fastest-levenshtein` is a lot faster in all cases. | ||
| I generated 500 pairs of strings with length N. I measured the ops/sec each library achieves to process all the given pairs. Higher is better. | ||
@@ -51,3 +53,3 @@ | Test Target | N=4 | N=8 | N=16 | N=32 | N=64 | N=128 | N=256 | N=512 | N=1024 | | ||
| ### Relative Performance | ||
| This image shows the relative performance between `fastest-levenshtein` and `js-levenshtein` (the 2nd fastest). `fastest-levenshtein` is always a lot faster. x-axis shows "times faster". | ||
| This image shows the relative performance between `fastest-levenshtein` and `js-levenshtein` (the 2nd fastest). `fastest-levenshtein` is always a lot faster. y-axis shows "times faster". | ||
@@ -54,0 +56,0 @@  |
113
test.js
@@ -1,64 +0,55 @@ | ||
| const {distance, closest} = require("./index.js"); | ||
| const levenshtein = (a, b) => { | ||
| if (a.length === 0) return b.length; | ||
| if (b.length === 0) return a.length; | ||
| if (a.length > b.length) { | ||
| const tmp = a; | ||
| a = b; | ||
| b = tmp; | ||
| } | ||
| const row = []; | ||
| for (let i = 0; i <= a.length; i++) { | ||
| row[i] = i; | ||
| } | ||
| for (let i = 1; i <= b.length; i++) { | ||
| let prev = i; | ||
| for (let j = 1; j <= a.length; j++) { | ||
| let val; | ||
| if (b.charAt(i - 1) === a.charAt(j - 1)) { | ||
| val = row[j - 1]; | ||
| } else { | ||
| val = Math.min(row[j - 1] + 1, prev + 1, row[j] + 1); | ||
| } | ||
| row[j - 1] = prev; | ||
| prev = val; | ||
| var _a = require("./mod.js"), closest = _a.closest, distance = _a.distance; | ||
| var levenshtein = function (a, b) { | ||
| if (a.length === 0) { | ||
| return b.length; | ||
| } | ||
| row[a.length] = prev; | ||
| } | ||
| return row[a.length]; | ||
| if (b.length === 0) { | ||
| return a.length; | ||
| } | ||
| if (a.length > b.length) { | ||
| var tmp = a; | ||
| a = b; | ||
| b = tmp; | ||
| } | ||
| var row = []; | ||
| for (var i = 0; i <= a.length; i++) { | ||
| row[i] = i; | ||
| } | ||
| for (var i = 1; i <= b.length; i++) { | ||
| var prev = i; | ||
| for (var j = 1; j <= a.length; j++) { | ||
| var val = 0; | ||
| if (b.charAt(i - 1) === a.charAt(j - 1)) { | ||
| val = row[j - 1]; | ||
| } | ||
| else { | ||
| val = Math.min(row[j - 1] + 1, prev + 1, row[j] + 1); | ||
| } | ||
| row[j - 1] = prev; | ||
| prev = val; | ||
| } | ||
| row[a.length] = prev; | ||
| } | ||
| return row[a.length]; | ||
| }; | ||
| function makeid(length) { | ||
| let result = ""; | ||
| const characters = | ||
| "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"; | ||
| const charactersLength = characters.length; | ||
| for (let i = 0; i < length; i++) { | ||
| result += characters.charAt(Math.floor(Math.random() * charactersLength)); | ||
| } | ||
| return result; | ||
| var makeid = function (length) { | ||
| var result = ""; | ||
| var characters = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789"; | ||
| var charactersLength = characters.length; | ||
| for (var i = 0; i < length; i++) { | ||
| result += characters.charAt(Math.floor(Math.random() * charactersLength)); | ||
| } | ||
| return result; | ||
| }; | ||
| for (var i = 0; i < 10000; i++) { | ||
| var rnd_num1 = (Math.random() * 1000) | 0; | ||
| var rnd_num2 = (Math.random() * 1000) | 0; | ||
| var rnd_string1 = makeid(rnd_num1); | ||
| var rnd_string2 = makeid(rnd_num2); | ||
| var actual = distance(rnd_string1, rnd_string2); | ||
| var expected = levenshtein(rnd_string1, rnd_string2); | ||
| console.log(i); | ||
| if (actual !== expected) { | ||
| console.log("fail"); | ||
| } | ||
| } | ||
| test("test compare", () => { | ||
| const errors = 0; | ||
| for (let i = 0; i < 1000; i++) { | ||
| const rnd_num1 = (Math.random() * 1000) | 0; | ||
| const rnd_num2 = (Math.random() * 1000) | 0; | ||
| const rnd_string1 = makeid(rnd_num1); | ||
| const rnd_string2 = makeid(rnd_num2); | ||
| const actual = distance(rnd_string1, rnd_string2); | ||
| const expected = levenshtein(rnd_string1, rnd_string2); | ||
| expect(actual).toBe(expected); | ||
| } | ||
| }); | ||
| test("test find", () => { | ||
| const actual = closest("fast", ["slow", "faster", "fastest"]); | ||
| const expected = "faster"; | ||
| expect(actual).toBe(expected); | ||
| }); |
Sorry, the diff of this file is not supported yet
New alerts
License Policy Violation
LicenseThis 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 riskPackage 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
Filesystem access
Supply chain riskAccesses the file system, and could potentially read sensitive data.
Found 1 instance in 1 package
Fixed alerts
License Policy Violation
LicenseThis 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
- increased by55.01%
17054
- Number of package files
- increased by22.22%
11
- Lines of code
- increased by69.6%
385
- Number of lines in readme file
- increased by3.57%
58
Worsened metrics
- Number of low supply chain risk alerts
- increased byInfinity%
1
- Number of medium supply chain risk alerts
- increased byInfinity%
1
No dependency changes