Socket
Socket
Sign inDemoInstall

levenshtein-edit-distance

Package Overview
Dependencies
Maintainers
1
Versions
15
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

levenshtein-edit-distance - npm Package Compare versions

Comparing version 0.1.0 to 0.1.1

bower.json

268

.jscs.json
{
"requireCurlyBraces": [
"if",
"else",
"for",
"while",
"do",
"try",
"catch"
],
"requireSpaceAfterKeywords": [
"if",
"else",
"for",
"while",
"do",
"switch",
"return",
"try",
"catch"
],
"requireSpaceBeforeBlockStatements": true,
"requireParenthesesAroundIIFE": true,
"requireSpacesInConditionalExpression": true,
"requireSpacesInFunctionExpression": {
"beforeOpeningCurlyBrace": true
},
"requireSpacesInAnonymousFunctionExpression": {
"beforeOpeningRoundBrace": true,
"beforeOpeningCurlyBrace": true
},
"requireSpacesInNamedFunctionExpression": {
"beforeOpeningRoundBrace": true,
"beforeOpeningCurlyBrace": true
},
"requireSpacesInFunctionExpression": {
"beforeOpeningCurlyBrace": true
},
"requireMultipleVarDecl": true,
"requireBlocksOnNewline": true,
"disallowPaddingNewlinesInBlocks": true,
"disallowEmptyBlocks": true,
"disallowSpacesInsideObjectBrackets": true,
"disallowSpacesInsideArrayBrackets": true,
"disallowSpacesInsideParentheses": true,
"requireSpacesInsideObjectBrackets": "all",
"disallowDanglingUnderscores": true,
"requireSpaceAfterObjectKeys": true,
"requireCommaBeforeLineBreak": true,
"requireOperatorBeforeLineBreak": [
"?",
"+",
"-",
"/",
"*",
"=",
"==",
"===",
"!=",
"!==",
">",
">=",
"<",
"<="
],
"requireSpaceBeforeBinaryOperators": [
"=",
",",
"+",
"-",
"/",
"*",
"==",
"===",
"!=",
"!=="
],
"requireSpaceAfterBinaryOperators": [
"=",
",",
"+",
"-",
"/",
"*",
"==",
"===",
"!=",
"!=="
],
"disallowSpaceAfterPrefixUnaryOperators": ["++", "--", "+", "-", "~", "!"],
"disallowSpaceBeforePostfixUnaryOperators": ["++", "--"],
"requireSpaceBeforeBinaryOperators": [
"+",
"-",
"/",
"*",
"=",
"==",
"===",
"!=",
"!=="
],
"requireSpaceAfterBinaryOperators": [
"+",
"-",
"/",
"*",
"=",
"==",
"===",
"!=",
"!=="
],
"disallowImplicitTypeConversion": ["numeric", "boolean", "binary", "string"],
"requireCamelCaseOrUpperCaseIdentifiers": true,
"disallowKeywords": ["with"],
"disallowMultipleLineStrings": true,
"disallowMultipleLineBreaks": true,
"validateLineBreaks": "LF",
"validateQuoteMarks": "'",
"disallowMixedSpacesAndTabs": true,
"disallowTrailingWhitespace": true,
"disallowTrailingComma": true,
"disallowKeywordsOnNewLine": ["else"],
"requireLineFeedAtFileEnd": true,
"maximumLineLength": 78,
"requireCapitalizedConstructors": true,
"safeContextKeyword": "self",
"requireDotNotation": true,
"disallowYodaConditions": true,
"validateJSDoc": {
"checkParamNames": true,
"checkRedundantParams": true,
"requireParamTypes": true
}
"requireCurlyBraces": [
"if",
"else",
"for",
"while",
"do",
"try",
"catch"
],
"requireSpaceAfterKeywords": [
"if",
"else",
"for",
"while",
"do",
"switch",
"return",
"try",
"catch"
],
"requireSpaceBeforeBlockStatements": true,
"requireParenthesesAroundIIFE": true,
"requireSpacesInConditionalExpression": true,
"requireSpacesInFunctionExpression": {
"beforeOpeningCurlyBrace": true
},
"requireSpacesInAnonymousFunctionExpression": {
"beforeOpeningRoundBrace": true,
"beforeOpeningCurlyBrace": true
},
"requireSpacesInNamedFunctionExpression": {
"beforeOpeningRoundBrace": true,
"beforeOpeningCurlyBrace": true
},
"requireSpacesInFunctionExpression": {
"beforeOpeningCurlyBrace": true
},
"requireMultipleVarDecl": true,
"requireBlocksOnNewline": true,
"disallowPaddingNewlinesInBlocks": true,
"disallowEmptyBlocks": true,
"disallowSpacesInsideObjectBrackets": true,
"disallowSpacesInsideArrayBrackets": true,
"disallowSpacesInsideParentheses": true,
"requireSpacesInsideObjectBrackets": "all",
"disallowDanglingUnderscores": true,
"requireSpaceAfterObjectKeys": true,
"requireCommaBeforeLineBreak": true,
"requireOperatorBeforeLineBreak": [
"?",
"+",
"-",
"/",
"*",
"=",
"==",
"===",
"!=",
"!==",
">",
">=",
"<",
"<="
],
"requireSpaceBeforeBinaryOperators": [
"=",
",",
"+",
"-",
"/",
"*",
"==",
"===",
"!=",
"!=="
],
"requireSpaceAfterBinaryOperators": [
"=",
",",
"+",
"-",
"/",
"*",
"==",
"===",
"!=",
"!=="
],
"disallowSpaceAfterPrefixUnaryOperators": ["++", "--", "+", "-", "~", "!"],
"disallowSpaceBeforePostfixUnaryOperators": ["++", "--"],
"requireSpaceBeforeBinaryOperators": [
"+",
"-",
"/",
"*",
"=",
"==",
"===",
"!=",
"!=="
],
"requireSpaceAfterBinaryOperators": [
"+",
"-",
"/",
"*",
"=",
"==",
"===",
"!=",
"!=="
],
"disallowImplicitTypeConversion": ["numeric", "boolean", "binary", "string"],
"requireCamelCaseOrUpperCaseIdentifiers": true,
"disallowKeywords": ["with"],
"disallowMultipleLineStrings": true,
"disallowMultipleLineBreaks": true,
"validateLineBreaks": "LF",
"validateQuoteMarks": "'",
"disallowMixedSpacesAndTabs": true,
"disallowTrailingWhitespace": true,
"disallowTrailingComma": true,
"disallowKeywordsOnNewLine": ["else"],
"requireLineFeedAtFileEnd": true,
"maximumLineLength": 78,
"requireCapitalizedConstructors": true,
"safeContextKeyword": "self",
"requireDotNotation": true,
"disallowYodaConditions": true,
"validateJSDoc": {
"checkParamNames": true,
"checkRedundantParams": true,
"requireParamTypes": true
}
}

172

benchmark/index.js
'use strict';
/* eslint-disable no-cond-assign */
/* eslint-disable no-new */
var distance, source, fastLevenshtein, natural, Levenshtein, LevenshteinDeltas, levenshteinComponent;
/**
* Dependencies.
*/
var distance,
fastLevenshtein,
natural,
Levenshtein,
LevenshteinDeltas,
levenshteinComponent,
leven;
distance = require('..');

@@ -15,4 +26,5 @@

levenshteinComponent = require('levenshtein-component');
leven = require('leven');
} catch (error) {
throw new Error(
console.log(
'\u001B[0;31m' +

@@ -26,4 +38,13 @@ 'The libraries needed by this benchmark could not be found. ' +

/* The first 100 words from Letterpress: https://github.com/atebits/Words */
source = Array(11).join([
/**
* Fixtures: 1000 words.
*
* Source:
* https://github.com/atebits/Words
*/
var fixtures;
/* The first 100 words from Letterpress: */
fixtures = Array(11).join([
'aa',

@@ -132,92 +153,85 @@ 'aah',

suite('levenshtein-distance — this module', function () {
bench('op/s * 1,000', function (next) {
var iterator = -1,
previousValue = '',
value;
function benchAll(callback) {
var index,
prev,
value;
while (value = source[++iterator]) {
distance(previousValue, value);
previousValue = value;
}
index = fixtures.length;
value = fixtures[0];
next();
});
});
while (index--) {
prev = value;
value = fixtures[index];
callback(value, prev);
}
}
suite('fast-levenshtein', function () {
bench('op/s * 1,000', function (next) {
var iterator = -1,
previousValue = '',
value;
while (value = source[++iterator]) {
fastLevenshtein(previousValue, value);
previousValue = value;
if (Levenshtein) {
suite('Levenshtein — to be fair, it lets you inspect a matrix',
function () {
bench('op/s * 1,000', function () {
benchAll(function (value, other) {
new Levenshtein(value, other);
});
});
}
);
}
next();
if (natural) {
suite('natural — to be fair, it offers more options', function () {
bench('op/s * 1,000', function () {
benchAll(function (value, other) {
natural(value, other);
});
});
});
});
}
suite('levenshtein-component', function () {
bench('op/s * 1,000', function (next) {
var iterator = -1,
previousValue = '',
value;
if (LevenshteinDeltas) {
suite('levenshtein-deltas', function () {
bench('op/s * 1,000', function () {
benchAll(function (value, other) {
new LevenshteinDeltas(value, other).distance();
});
});
});
}
while (value = source[++iterator]) {
levenshteinComponent(previousValue, value);
previousValue = value;
}
next();
if (levenshteinComponent) {
suite('levenshtein-component', function () {
bench('op/s * 1,000', function () {
benchAll(function (value, other) {
levenshteinComponent(value, other);
});
});
});
});
}
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();
if (fastLevenshtein) {
suite('fast-levenshtein', function () {
bench('op/s * 1,000', function () {
benchAll(function (value, other) {
fastLevenshtein(value, other);
});
});
});
});
}
suite('natural — to be fair, it offers more options', function () {
bench('op/s * 1,000', function (next) {
var iterator = -1,
previousValue = '',
value;
while (value = source[++iterator]) {
natural(previousValue, value);
previousValue = value;
}
next();
if (leven) {
suite('Leven — fast.', function () {
bench('op/s * 1,000', function () {
benchAll(function (value, other) {
leven(value, other);
});
});
});
});
}
/* eslint-disable no-new */
suite('Levenshtein — to be fair, it lets you inspect a matrix', function () {
bench('op/s * 1,000', function (next) {
var iterator = -1,
previousValue = '',
value;
while (value = source[++iterator]) {
new Levenshtein(previousValue, value);
previousValue = value;
}
next();
suite('levenshtein-edit-distance — this module', function () {
bench('op/s * 1,000', function () {
benchAll(function (value, other) {
distance(value, other);
});
});
});

4

component.json
{
"name": "levenshtein-edit-distance",
"version": "0.1.0",
"version": "0.1.1",
"description": "Levenshtein edit distance. No cruft. Real fast.",
"license": "MIT",
"keywords": [

@@ -12,3 +13,2 @@ "vladimir",

"repository": "wooorm/levenshtein-edit-distance",
"license": "MIT",
"scripts" : [

@@ -15,0 +15,0 @@ "index.js"

25

History.md
0.1.1 / 2014-09-29
==================
* Refactor spec
* Refactor Readme.md
* Remove browser test
* Refactor benchmark
* Fix indentation in .jscs.json
* Add npm deployment to travis
* Remove `npm update npm` from travis
* Update Installation in docs
* Update copyright in Readme.md
* Remove testling
* Add bower.json
* Update .gitignore, .npmignore
* Fix property order in component.json, package.json
* Update mocha, eslint, jscs
* Update benchmark results in Readme.md
* Refactor benchmark
* Refactor API for performance
* Add looser linting to API
* Add leven to benchmark and other libraries
* Added components to gitignore
* Fixed code style in benchmark
0.1.0 / 2014-07-12

@@ -3,0 +28,0 @@ ==================

82

index.js

@@ -1,13 +0,18 @@

'use strict';
var cache,
codes;
function levenshtein(value, alternative) {
var previousRow, previousRowIterator, columnIterator,
character, next, current, length, alternativeLength, temporary;
cache = [];
codes = [];
/* Convert both values to string. */
value = String(value);
alternative = String(alternative);
function levenshtein(value, other) {
var length,
lengthOther,
code,
result,
distance,
distanceOther,
index,
indexOther;
/* Basic cases. */
if (value === alternative) {
if (value === other) {
return 0;

@@ -17,57 +22,46 @@ }

length = value.length;
alternativeLength = alternative.length;
lengthOther = other.length;
if (!length) {
return alternativeLength;
if (length === 0) {
return lengthOther;
}
if (!alternativeLength) {
if (lengthOther === 0) {
return length;
}
/* Initialise the previous row, this just creates an array from 0..N */
previousRow = [];
previousRowIterator = -1;
index = 0;
while (++previousRowIterator <= alternativeLength) {
previousRow[previousRowIterator] = previousRowIterator;
while (index < length) {
codes[index] = value.charCodeAt(index);
cache[index] = ++index;
}
previousRowIterator = -1;
indexOther = 0;
while (++previousRowIterator < length) {
character = value.charAt(previousRowIterator);
next = previousRowIterator + 1;
columnIterator = -1;
while (indexOther < lengthOther) {
code = other.charCodeAt(indexOther);
while (++columnIterator < alternativeLength) {
current = next;
result = distance = indexOther++;
next = previousRow[columnIterator];
index = -1;
if (character !== alternative.charAt(columnIterator)) {
next += 1;
}
while (++index < length) {
distanceOther = code === codes[index] ? distance : distance + 1;
temporary = current + 1;
distance = cache[index];
if (next > temporary) {
next = temporary;
}
temporary = previousRow[columnIterator + 1] + 1;
if (next > temporary) {
next = temporary;
}
previousRow[columnIterator] = current;
cache[index] = result = distance > result
? distanceOther > result
? result + 1
: distanceOther
: distanceOther > distance
? distance + 1
: distanceOther;
}
previousRow[alternativeLength] = next;
}
return next;
return result;
}
module.exports = levenshtein;

42

package.json
{
"name": "levenshtein-edit-distance",
"version": "0.1.0",
"version": "0.1.1",
"description": "Levenshtein edit distance. No cruft. Real fast.",
"license": "MIT",
"keywords": [

@@ -11,15 +12,14 @@ "vladimir",

],
"repository": {
"type": "git",
"url": "https://github.com/wooorm/levenshtein-edit-distance.git"
},
"author": "Titus Wormer <tituswormer@gmail.com>",
"license": "MIT",
"devDependencies": {
"eslint": "^0.7.4",
"eslint": "^0.8.0",
"istanbul": "^0.3.0",
"jscs": "^1.5.6",
"jscs": "^1.6.0",
"matcha": "^0.5.0",
"mocha": "~1.20.1"
"mocha": "^1.20.0"
},
"repository": {
"type": "git",
"url": "https://github.com/wooorm/levenshtein-edit-distance.git"
},
"scripts": {

@@ -29,29 +29,11 @@ "test": "node_modules/.bin/_mocha --reporter spec --check-leaks -u exports spec/levenshtein-edit-distance.spec.js",

"lint": "npm run lint-api && npm run lint-test && npm run lint-style && npm run lint-benchmark",
"lint-api": "node_modules/.bin/eslint index.js --env node --env browser --rule 'quotes: [2, single], no-cond-assign: false'",
"lint-api": "node_modules/.bin/eslint index.js --env node --env browser --rule 'quotes: [2, single], no-cond-assign: false, strict: false'",
"lint-test": "node_modules/.bin/eslint spec/levenshtein-edit-distance.spec.js --env node --env mocha --rule 'quotes: [2, single], no-loop-func: false'",
"lint-benchmark": "node_modules/.bin/eslint benchmark/index.js --env node --global suite,set,bench --rule 'quotes: [2, single]'",
"lint-style": "node_modules/.bin/jscs index.js spec/levenshtein-edit-distance.spec.js benchmark/index.js --reporter=inline",
"install-browser-test": "npm install browserify",
"build-browser-test": "node_modules/.bin/browserify spec/levenshtein-edit-distance.spec.js -o spec/browser.spec.js",
"lint-style": "node_modules/.bin/jscs spec/levenshtein-edit-distance.spec.js benchmark/index.js --reporter=inline",
"coverage": "node_modules/.bin/istanbul cover node_modules/.bin/_mocha -- -- spec/levenshtein-edit-distance.spec.js",
"install-benchmark": "npm install natural fast-levenshtein levenshtein levenshtein-component levenshtein-deltas",
"install-benchmark": "npm install natural fast-levenshtein levenshtein levenshtein-component levenshtein-deltas leven",
"benchmark": "node_modules/.bin/matcha",
"make": "npm run lint && npm run coverage"
},
"testling": {
"files": "spec/levenshtein-edit-distance.spec.js",
"harness": "mocha",
"browsers": [
"iexplore/latest",
"chrome/latest",
"chrome/canary",
"firefox/latest",
"firefox/nightly",
"opera/latest",
"opera/next",
"safari/latest",
"iphone/latest",
"android-browser/latest"
]
}
}

46

Readme.md
# 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)
[![browser support](https://ci.testling.com/wooorm/levenshtein-edit-distance.png) ](https://ci.testling.com/wooorm/levenshtein-edit-distance)
---
[Levenshtein edit distance](http://en.wikipedia.org/wiki/Levenshtein_distance) (by [Vladimir Levenshtein](http://en.wikipedia.org/wiki/Vladimir_Levenshtein)). No cruft. Real fast.

@@ -11,3 +7,3 @@

NPM:
npm:
```sh

@@ -17,3 +13,3 @@ $ npm install levenshtein-edit-distance

Component.js:
Component:
```sh

@@ -23,2 +19,7 @@ $ component install wooorm/levenshtein-edit-distance

Bower:
```sh
$ bower install levenshtein-edit-distance
```
## Usage

@@ -38,3 +39,3 @@

/* Order insensitive */
levenshteinDistance("aarrgh", "aargh") === levenshteinDistance("aargh", "aarrgh"); // true
levenshteinDistance('aarrgh', 'aargh') === levenshteinDistance('aargh', 'aarrgh'); // true
```

@@ -44,2 +45,3 @@

- [sindresorhus/leven](https://github.com/sindresorhus/leven) — Supports a CLI;
- [hiddentao/fast-levenshtein](http://github.com/hiddentao/fast-levenshtein) — Supports async functionality;

@@ -53,3 +55,3 @@ - [NaturalNode/natural](http://github.com/NaturalNode/natural) — Supports settings weight of substitutions, insertions, and deletions.

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.
On a MacBook Air, it runs about 1,915,000 op/s.

@@ -59,3 +61,2 @@ Run the benchmark yourself:

```sh
$ npm run install-benchmark # Just once of course.
$ npm run benchmark

@@ -65,19 +66,22 @@ ```

```
levenshtein-distance — this module
1,223 op/s » op/s * 1,000
Levenshtein — to be fair, it lets you inspect a matrix
129 op/s » op/s * 1,000
fast-levenshtein
1,209 op/s » op/s * 1,000
natural — to be fair, it offers more options
212 op/s » op/s * 1,000
levenshtein-deltas
252 op/s » op/s * 1,000
levenshtein-component
330 op/s » op/s * 1,000
335 op/s » op/s * 1,000
levenshtein-deltas
244 op/s » op/s * 1,000
fast-levenshtein
1,251 op/s » op/s * 1,000
natural — to be fair, it offers more options
208 op/s » op/s * 1,000
Leven — fast.
1,541 op/s » op/s * 1,000
Levenshtein — to be fair, it lets you inspect a matrix
134 op/s » op/s * 1,000
levenshtein-edit-distance — this module
1,915 op/s » op/s * 1,000
```

@@ -87,2 +91,2 @@

MIT
MIT © Titus Wormer

71

spec/levenshtein-edit-distance.spec.js
'use strict';
var levenshteinDistance, assert;
/**
* Dependencies.
*/
var levenshteinDistance,
assert;
levenshteinDistance = require('..');
assert = require('assert');
/**
* Tests.
*/
describe('levenshteinDistance()', function () {
it('should work', function () {
assert(levenshteinDistance('', 'a') === 1);
assert(levenshteinDistance('a', '') === 1);
assert(levenshteinDistance('', '') === 0);
assert(levenshteinDistance('levenshtein', 'levenshtein') === 0);
assert(levenshteinDistance('sitting', 'kitten') === 3);
assert(levenshteinDistance('gumbo', 'gambol') === 2);
assert(levenshteinDistance('saturday', 'sunday') === 3);
});
/* Tests from https://github.com/hiddentao/fast-levenshtein,
* just to make sure thing are interoperable. */
it('should not match case insensitive', function () {
assert(
levenshteinDistance('DwAyNE', 'DUANE') !==
levenshteinDistance('dwayne', 'DuAnE')
);
});
it('should not care about parameter order', function () {
assert(
levenshteinDistance('aarrgh', 'aargh') ===
levenshteinDistance('aargh', 'aarrgh')
);
});
});
/**
* Tests from fast-levenshtein, just to make sure thing
* are interoperable.
*
* Source:
* https://github.com/hiddentao/fast-levenshtein
*/
describe('Compatibility with `fast-levenshtein`', function () {
it('should work', function () {
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(

@@ -43,16 +94,2 @@ 'Morbi interdum ultricies neque varius condimentum. Donec ' +

});
it('should not match case insensitive', function () {
assert(
levenshteinDistance('DwAyNE', 'DUANE') !==
levenshteinDistance('dwayne', 'DuAnE')
);
});
it('should not care about parameter order', function () {
assert(
levenshteinDistance('aarrgh', 'aargh') ===
levenshteinDistance('aargh', 'aarrgh')
);
});
});
spec/index.html
.npmignore

Sorry, the diff of this file is not supported yet

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc