Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
fast-levenshtein
Advanced tools
fast-levenshtein - npm Package Compare versions
Comparing version 1.1.4 to 2.0.0
| (function() { | ||
| 'use strict'; | ||
| // language-sensitive collator | ||
| var collator = Intl.Collator("generic", { sensitivity: "base" }); | ||
| /** | ||
| * Extend an Object with another Object's properties. | ||
| * | ||
| * The source objects are specified as additional arguments. | ||
| * | ||
| * @param dst Object the object to extend. | ||
| * | ||
| * @return Object the final object. | ||
| */ | ||
| var _extend = function(dst) { | ||
| var sources = Array.prototype.slice.call(arguments, 1); | ||
| for (var i=0; i<sources.length; ++i) { | ||
| var src = sources[i]; | ||
| for (var p in src) { | ||
| if (src.hasOwnProperty(p)) dst[p] = src[p]; | ||
| } | ||
| } | ||
| return dst; | ||
| }; | ||
| // arrays to re-use | ||
| var prevRow = [], | ||
| str2Char = []; | ||
| /** | ||
| * Defer execution of given function. | ||
| * @param {Function} func | ||
| */ | ||
| var _defer = function(func) { | ||
| if (typeof setImmediate === 'function') { | ||
| return setImmediate(func); | ||
| } else { | ||
| return setTimeout(func, 0); | ||
| } | ||
| }; | ||
| /** | ||
| * Based on the algorithm at http://en.wikipedia.org/wiki/Levenshtein_distance. | ||
@@ -46,28 +22,38 @@ */ | ||
| * @param str2 String the second string. | ||
| * @param [options] Additional options. | ||
| * @param [options.useCollator] Use `Intl.Collator` for more locale-sensitive string comparison. | ||
| * @return Integer the levenshtein distance (0 and above). | ||
| */ | ||
| get: function(str1, str2) { | ||
| get: function(str1, str2, options) { | ||
| var useCollator = (options && options.useCollator); | ||
| var str1Len = str1.length, | ||
| str2Len = str2.length; | ||
| // base cases | ||
| if (str1 === str2) return 0; | ||
| if (str1.length === 0) return str2.length; | ||
| if (str2.length === 0) return str1.length; | ||
| if (str1Len === 0) return str2Len; | ||
| if (str2Len === 0) return str1Len; | ||
| // two rows | ||
| var prevRow = new Array(str2.length + 1), | ||
| curCol, nextCol, i, j, tmp; | ||
| var curCol, nextCol, i, j, tmp; | ||
| // initialise previous row | ||
| for (i=0; i<prevRow.length; ++i) { | ||
| for (i=0; i<str2Len; ++i) { | ||
| prevRow[i] = i; | ||
| str2Char[i] = str2.charCodeAt(i); | ||
| } | ||
| prevRow[str2Len] = str2Len; | ||
| // calculate current row distance from previous row | ||
| for (i=0; i<str1.length; ++i) { | ||
| for (i=0; i<str1Len; ++i) { | ||
| nextCol = i + 1; | ||
| for (j=0; j<str2.length; ++j) { | ||
| for (j=0; j<str2Len; ++j) { | ||
| curCol = nextCol; | ||
| // substution | ||
| nextCol = prevRow[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 ); | ||
| var strCmp = useCollator ? (0 === collator.compare(str1.charAt(i), String.fromCharCode(str2Char[j]))) : str1.charCodeAt(i) === str2Char[j]; | ||
| nextCol = prevRow[j] + ( strCmp ? 0 : 1 ); | ||
| // insertion | ||
@@ -93,98 +79,2 @@ tmp = curCol + 1; | ||
| return nextCol; | ||
| }, | ||
| /** | ||
| * Asynchronously calculate levenshtein distance of the two strings. | ||
| * | ||
| * @param str1 String the first string. | ||
| * @param str2 String the second string. | ||
| * @param cb Function callback function with signature: function(Error err, int distance) | ||
| * @param [options] Object additional options. | ||
| * @param [options.progress] Function progress callback with signature: function(percentComplete) | ||
| */ | ||
| getAsync: function(str1, str2, cb, options) { | ||
| options = _extend({}, { | ||
| progress: null | ||
| }, options); | ||
| // base cases | ||
| if (str1 === str2) return cb(null, 0); | ||
| if (str1.length === 0) return cb(null, str2.length); | ||
| if (str2.length === 0) return cb(null, str1.length); | ||
| // two rows | ||
| var prevRow = new Array(str2.length + 1), | ||
| curCol, nextCol, | ||
| i, j, tmp, | ||
| startTime, currentTime; | ||
| // initialise previous row | ||
| for (i=0; i<prevRow.length; ++i) { | ||
| prevRow[i] = i; | ||
| } | ||
| nextCol = 1; | ||
| i = 0; | ||
| j = -1; | ||
| var __calculate = function() { | ||
| // reset timer | ||
| startTime = new Date().valueOf(); | ||
| currentTime = startTime; | ||
| // keep going until one second has elapsed | ||
| while (currentTime - startTime < 1000) { | ||
| // reached end of current row? | ||
| if (str2.length <= (++j)) { | ||
| // copy current into previous (in preparation for next iteration) | ||
| prevRow[j] = nextCol; | ||
| // if already done all chars | ||
| if (str1.length <= (++i)) { | ||
| return cb(null, nextCol); | ||
| } | ||
| // else if we have more left to do | ||
| else { | ||
| nextCol = i + 1; | ||
| j = 0; | ||
| } | ||
| } | ||
| // calculation | ||
| curCol = nextCol; | ||
| // substution | ||
| nextCol = prevRow[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 ); | ||
| // insertion | ||
| tmp = curCol + 1; | ||
| if (nextCol > tmp) { | ||
| nextCol = tmp; | ||
| } | ||
| // deletion | ||
| tmp = prevRow[j + 1] + 1; | ||
| if (nextCol > tmp) { | ||
| nextCol = tmp; | ||
| } | ||
| // copy current into previous (in preparation for next iteration) | ||
| prevRow[j] = curCol; | ||
| // get current time | ||
| currentTime = new Date().valueOf(); | ||
| } | ||
| // send a progress update? | ||
| if (null !== options.progress) { | ||
| try { | ||
| options.progress.call(null, (i * 100.0/ str1.length)); | ||
| } catch (err) { | ||
| return cb('Progress callback: ' + err.toString()); | ||
| } | ||
| } | ||
| // next iteration | ||
| _defer(__calculate); | ||
| }; | ||
| __calculate(); | ||
| } | ||
@@ -191,0 +81,0 @@ |
| { | ||
| "name": "fast-levenshtein", | ||
| "version": "1.1.4", | ||
| "version": "2.0.0", | ||
| "description": "Efficient implementation of Levenshtein algorithm with asynchronous callback support", | ||
@@ -5,0 +5,0 @@ "main": "levenshtein.js", |
@@ -11,4 +11,3 @@ # fast-levenshtein - Levenshtein algorithm in Javascript | ||
| * Better performance than other implementations by not needing to store the whole matrix ([more info](http://www.codeproject.com/Articles/13525/Fast-memory-efficient-Levenshtein-algorithm)). | ||
| * Provides synchronous and asynchronous versions of the algorithm. | ||
| * Asynchronous version is almost as fast as the synchronous version for small strings and can also provide progress updates. | ||
| * Locale-sensitive string comparisions if needed. | ||
| * Comprehensive test suite and performance benchmark. | ||
@@ -39,3 +38,3 @@ * Small: <1 KB minified and gzipped | ||
| **Synchronous** | ||
| **Default usage** | ||
@@ -49,28 +48,11 @@ ```javascript | ||
| **Asynchronous** | ||
| **Locale-sensitive string comparisons** | ||
| ```javascript | ||
| var levenshtein = require('fast-levenshtein'); | ||
| It supports using [Intl.Collator](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Collator) for locale-sensitive string comparisons: | ||
| levenshtein.getAsync('back', 'book', function (err, distance) { | ||
| // err is null unless an error was thrown | ||
| // distance equals 2 | ||
| }); | ||
| ``` | ||
| **Asynchronous with progress updates** | ||
| ```javascript | ||
| var levenshtein = require('fast-levenshtein'); | ||
| 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.get('mikailovitch', 'Mikhaïlovitch', { useCollator: true}); | ||
| // 1 | ||
| ``` | ||
@@ -77,0 +59,0 @@ |
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
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
Worsened metrics
- Total package byte prevSize
- decreased by-29.54%
7904
- Lines of code
- decreased by-55.25%
81
- Number of lines in readme file
- decreased by-14.88%
103
No dependency changes