diff options
Diffstat (limited to 'node_modules/leven')
| -rw-r--r-- | node_modules/leven/index.js | 85 | ||||
| -rw-r--r-- | node_modules/leven/license | 21 | ||||
| -rw-r--r-- | node_modules/leven/package.json | 55 | ||||
| -rw-r--r-- | node_modules/leven/readme.md | 50 |
4 files changed, 211 insertions, 0 deletions
diff --git a/node_modules/leven/index.js b/node_modules/leven/index.js new file mode 100644 index 000000000..bb44b7919 --- /dev/null +++ b/node_modules/leven/index.js @@ -0,0 +1,85 @@ +/* eslint-disable no-nested-ternary */ +'use strict'; +var arr = []; +var charCodeCache = []; + +module.exports = function (a, b) { + if (a === b) { + return 0; + } + + var swap = a; + + // Swapping the strings if `a` is longer than `b` so we know which one is the + // shortest & which one is the longest + if (a.length > b.length) { + a = b; + b = swap; + } + + var aLen = a.length; + var bLen = b.length; + + if (aLen === 0) { + return bLen; + } + + if (bLen === 0) { + return aLen; + } + + // Performing suffix trimming: + // We can linearly drop suffix common to both strings since they + // don't increase distance at all + // Note: `~-` is the bitwise way to perform a `- 1` operation + while (aLen > 0 && (a.charCodeAt(~-aLen) === b.charCodeAt(~-bLen))) { + aLen--; + bLen--; + } + + if (aLen === 0) { + return bLen; + } + + // Performing prefix trimming + // We can linearly drop prefix common to both strings since they + // don't increase distance at all + var start = 0; + + while (start < aLen && (a.charCodeAt(start) === b.charCodeAt(start))) { + start++; + } + + aLen -= start; + bLen -= start; + + if (aLen === 0) { + return bLen; + } + + var bCharCode; + var ret; + var tmp; + var tmp2; + var i = 0; + var j = 0; + + while (i < aLen) { + charCodeCache[start + i] = a.charCodeAt(start + i); + arr[i] = ++i; + } + + while (j < bLen) { + bCharCode = b.charCodeAt(start + j); + tmp = j++; + ret = j; + + for (i = 0; i < aLen; i++) { + tmp2 = bCharCode === charCodeCache[start + i] ? tmp : tmp + 1; + tmp = arr[i]; + ret = arr[i] = tmp > ret ? tmp2 > ret ? ret + 1 : tmp2 : tmp2 > tmp ? tmp + 1 : tmp2; + } + } + + return ret; +}; diff --git a/node_modules/leven/license b/node_modules/leven/license new file mode 100644 index 000000000..654d0bfe9 --- /dev/null +++ b/node_modules/leven/license @@ -0,0 +1,21 @@ +The MIT License (MIT) + +Copyright (c) Sindre Sorhus <sindresorhus@gmail.com> (sindresorhus.com) + +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: + +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. diff --git a/node_modules/leven/package.json b/node_modules/leven/package.json new file mode 100644 index 000000000..4fd64bb22 --- /dev/null +++ b/node_modules/leven/package.json @@ -0,0 +1,55 @@ +{ + "name": "leven", + "version": "2.1.0", + "description": "Measure the difference between two strings using the fastest JS implementation of the Levenshtein distance algorithm", + "license": "MIT", + "repository": "sindresorhus/leven", + "author": { + "name": "Sindre Sorhus", + "email": "sindresorhus@gmail.com", + "url": "sindresorhus.com" + }, + "engines": { + "node": ">=0.10.0" + }, + "scripts": { + "test": "xo && ava", + "bench": "matcha bench.js" + }, + "files": [ + "index.js" + ], + "keywords": [ + "leven", + "levenshtein", + "distance", + "algorithm", + "algo", + "string", + "difference", + "diff", + "fast", + "fuzzy", + "similar", + "similarity", + "compare", + "comparison", + "edit", + "text", + "match", + "matching" + ], + "devDependencies": { + "ava": "^0.17.0", + "fast-levenshtein": "^2.0.5", + "ld": "^0.1.0", + "levdist": "^2.0.0", + "levenshtein": "^1.0.4", + "levenshtein-component": "0.0.1", + "levenshtein-edit-distance": "^2.0.0", + "matcha": "^0.7.0", + "natural": "^0.4.0", + "talisman": "^0.18.0", + "xo": "^0.16.0" + } +} diff --git a/node_modules/leven/readme.md b/node_modules/leven/readme.md new file mode 100644 index 000000000..9493c9f38 --- /dev/null +++ b/node_modules/leven/readme.md @@ -0,0 +1,50 @@ +# leven [](https://travis-ci.org/sindresorhus/leven) + +> Measure the difference between two strings<br> +> The fastest JS implementation of the [Levenshtein distance](http://en.wikipedia.org/wiki/Levenshtein_distance) algorithm + + +## Install + +``` +$ npm install --save leven +``` + + +## Usage + +```js +const leven = require('leven'); + +leven('cat', 'cow'); +//=> 2 +``` + + +## Benchmark + +``` +$ npm run bench +``` + +``` + 401,487 op/s » leven + 371,707 op/s » talisman + 264,191 op/s » levenshtein-edit-distance + 152,923 op/s » fast-levenshtein + 57,267 op/s » levenshtein-component + 19,915 op/s » levdist + 21,802 op/s » ld + 18,079 op/s » natural + 11,761 op/s » levenshtein +``` + + +## Related + +- [leven-cli](https://github.com/sindresorhus/leven-cli) - CLI for this module + + +## License + +MIT © [Sindre Sorhus](https://sindresorhus.com) |