Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More โ†’
Socket
Sign inDemoInstall
Socket

fast-fuzzy

Package Overview
Dependencies
Maintainers
1
Versions
47
Alerts
File Explorer

Advanced tools

Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

fast-fuzzy - npm Package Compare versions

Comparing version 1.9.1 to 1.9.2

430

lib/fuzzy.js
"use strict";
function _classCallCheck(instance, Constructor) { if (!(instance instanceof Constructor)) { throw new TypeError("Cannot call a class as a function"); } }
function _defineProperties(target, props) { for (var i = 0; i < props.length; i++) { var descriptor = props[i]; descriptor.enumerable = descriptor.enumerable || false; descriptor.configurable = true; if ("value" in descriptor) descriptor.writable = true; Object.defineProperty(target, descriptor.key, descriptor); } }
function _createClass(Constructor, protoProps, staticProps) { if (protoProps) _defineProperties(Constructor.prototype, protoProps); if (staticProps) _defineProperties(Constructor, staticProps); return Constructor; }
function ownKeys(object, enumerableOnly) { var keys = Object.keys(object); if (Object.getOwnPropertySymbols) { var symbols = Object.getOwnPropertySymbols(object); if (enumerableOnly) symbols = symbols.filter(function (sym) { return Object.getOwnPropertyDescriptor(object, sym).enumerable; }); keys.push.apply(keys, symbols); } return keys; }
function _objectSpread(target) { for (var i = 1; i < arguments.length; i++) { var source = arguments[i] != null ? arguments[i] : {}; if (i % 2) { ownKeys(source, true).forEach(function (key) { _defineProperty(target, key, source[key]); }); } else if (Object.getOwnPropertyDescriptors) { Object.defineProperties(target, Object.getOwnPropertyDescriptors(source)); } else { ownKeys(source).forEach(function (key) { Object.defineProperty(target, key, Object.getOwnPropertyDescriptor(source, key)); }); } } return target; }
function _objectSpread(target) { for (var i = 1; i < arguments.length; i++) { var source = arguments[i] != null ? arguments[i] : {}; if (i % 2) { ownKeys(Object(source), true).forEach(function (key) { _defineProperty(target, key, source[key]); }); } else if (Object.getOwnPropertyDescriptors) { Object.defineProperties(target, Object.getOwnPropertyDescriptors(source)); } else { ownKeys(Object(source)).forEach(function (key) { Object.defineProperty(target, key, Object.getOwnPropertyDescriptor(source, key)); }); } } return target; }
function _defineProperty(obj, key, value) { if (key in obj) { Object.defineProperty(obj, key, { value: value, enumerable: true, configurable: true, writable: true }); } else { obj[key] = value; } return obj; }
var split = require("graphemesplit");
const split = require("graphemesplit");
var whitespaceRegex = /^\s+$/;
var nonWordRegex = /^[`~!@#$%^&*()\-=_+{}[\]\|\\;':",./<>?]+$/; // the default options, which will be used for any unset option
const whitespaceRegex = /^\s+$/;
const nonWordRegex = /^[`~!@#$%^&*()\-=_+{}[\]\|\\;':",./<>?]+$/; // the default options, which will be used for any unset option
var defaultOptions = {
keySelector: function keySelector(s) {
return s;
},
const defaultOptions = {
keySelector: s => s,
threshold: .6,

@@ -33,55 +25,34 @@ ignoreCase: true,

var noop = function noop() {};
const noop = () => {};
var arrayWrap = function arrayWrap(item) {
return item instanceof Array ? item : [item];
}; // return normalized string, with map included
const arrayWrap = item => item instanceof Array ? item : [item]; // return normalized string, with map included
function normalize(string, options) {
var lower = options.ignoreCase ? string.toLocaleLowerCase() : string; // track transformations
const lower = options.ignoreCase ? string.toLocaleLowerCase() : string; // track transformations
var normal = [];
var map = [];
var lastWasWhitespace = true;
var length = 0;
var _iteratorNormalCompletion = true;
var _didIteratorError = false;
var _iteratorError = undefined;
const normal = [];
const map = [];
let lastWasWhitespace = true;
let length = 0;
try {
for (var _iterator = split(lower)[Symbol.iterator](), _step; !(_iteratorNormalCompletion = (_step = _iterator.next()).done); _iteratorNormalCompletion = true) {
var grapheme = _step.value;
whitespaceRegex.lastIndex = 0;
nonWordRegex.lastIndex = 0;
for (const grapheme of split(lower)) {
whitespaceRegex.lastIndex = 0;
nonWordRegex.lastIndex = 0;
if (options.normalizeWhitespace && whitespaceRegex.test(grapheme)) {
if (!lastWasWhitespace) {
normal.push(" ");
map.push(length);
lastWasWhitespace = true;
}
} else if (!(options.ignoreSymbols && nonWordRegex.test(grapheme))) {
normal.push(grapheme.normalize());
if (options.normalizeWhitespace && whitespaceRegex.test(grapheme)) {
if (!lastWasWhitespace) {
normal.push(" ");
map.push(length);
lastWasWhitespace = false;
lastWasWhitespace = true;
}
} else if (!(options.ignoreSymbols && nonWordRegex.test(grapheme))) {
normal.push(grapheme.normalize());
map.push(length);
lastWasWhitespace = false;
}
length += grapheme.length;
} // add the end of the string
length += grapheme.length;
} // add the end of the string
} catch (err) {
_didIteratorError = true;
_iteratorError = err;
} finally {
try {
if (!_iteratorNormalCompletion && _iterator["return"] != null) {
_iterator["return"]();
}
} finally {
if (_didIteratorError) {
throw _iteratorError;
}
}
}

@@ -97,4 +68,4 @@ map.push(string.length);

original: string,
normal: normal,
map: map
normal,
map
};

@@ -120,6 +91,6 @@ } // translates a match to the original string

var start = scoreIndex;
let start = scoreIndex;
for (var i = rows.length - 2; i > 0 && start > 1; i--) {
var row = rows[i];
for (let i = rows.length - 2; i > 0 && start > 1; i--) {
const row = rows[i];
start = row[start] < row[start - 1] ? start : start - 1;

@@ -134,14 +105,10 @@ }

var levUpdateScore = function levUpdateScore() {
return true;
};
const levUpdateScore = () => true;
var sellersUpdateScore = function sellersUpdateScore(cur, min) {
return cur < min;
};
const sellersUpdateScore = (cur, min) => cur < min;
function getLevScore(rows, length) {
var lastRow = rows[rows.length - 1];
var lastCell = lastRow[length - 1];
var scoreLength = Math.max(rows.length, length);
const lastRow = rows[rows.length - 1];
const lastCell = lastRow[length - 1];
const scoreLength = Math.max(rows.length, length);
return {

@@ -162,8 +129,8 @@ score: 1 - lastCell / (scoreLength - 1),

var lastRow = rows[rows.length - 1];
var minValue = lastRow[0];
var minIndex = 0;
const lastRow = rows[rows.length - 1];
let minValue = lastRow[0];
let minIndex = 0;
for (var i = 1; i < length; i++) {
var val = lastRow[i];
for (let i = 1; i < length; i++) {
const val = lastRow[i];

@@ -183,5 +150,5 @@ if (val < minValue) {

function initLevRows(rowCount, columnCount) {
var rows = new Array(rowCount);
const rows = new Array(rowCount);
for (var i = 0; i < rowCount; i++) {
for (let i = 0; i < rowCount; i++) {
rows[i] = new Array(columnCount);

@@ -191,4 +158,4 @@ rows[i][0] = i;

for (var _i = 0; _i < columnCount; _i++) {
rows[0][_i] = _i;
for (let i = 0; i < columnCount; i++) {
rows[0][i] = i;
}

@@ -200,6 +167,6 @@

function initSellersRows(rowCount, columnCount) {
var rows = new Array(rowCount);
const rows = new Array(rowCount);
rows[0] = new Array(columnCount).fill(0);
for (var i = 1; i < rowCount; i++) {
for (let i = 1; i < rowCount; i++) {
rows[i] = new Array(columnCount);

@@ -214,7 +181,7 @@ rows[i][0] = i;

function levCore(term, candidate, rows, i, j) {
var rowA = rows[i];
var rowB = rows[i + 1];
var cost = term[i] === candidate[j] ? 0 : 1;
var m;
var min = rowB[j] + 1; // insertion
const rowA = rows[i];
const rowB = rows[i + 1];
const cost = term[i] === candidate[j] ? 0 : 1;
let m;
let min = rowB[j] + 1; // insertion

@@ -231,3 +198,3 @@ if ((m = rowA[j + 1] + 1) < min) min = m; // deletion

function levenshtein(term, candidate, rows, j) {
for (var i = 0; i < term.length; i++) {
for (let i = 0; i < term.length; i++) {
levCore(term, candidate, rows, i, j);

@@ -254,10 +221,10 @@ }

for (var i = 1; i < term.length; i++) {
var rowA = rows[i - 1];
var rowB = rows[i];
var rowC = rows[i + 1];
var cost = term[i] === candidate[j] ? 0 : 1;
var m = void 0; // insertion
for (let i = 1; i < term.length; i++) {
const rowA = rows[i - 1];
const rowB = rows[i];
const rowC = rows[i + 1];
const cost = term[i] === candidate[j] ? 0 : 1;
let m; // insertion
var min = rowC[j] + 1; // deletion
let min = rowC[j] + 1; // deletion

@@ -276,9 +243,9 @@ if ((m = rowB[j + 1] + 1) < min) min = m; // substitution

function trieInsert(trie, string, item) {
var walker = trie;
let walker = trie;
for (var i = 0; i < string.length; i++) {
var _char = string[i]; // add child node if not already present
for (let i = 0; i < string.length; i++) {
const char = string[i]; // add child node if not already present
if (walker.children[_char] == null) {
walker.children[_char] = {
if (walker.children[char] == null) {
walker.children[char] = {
children: {},

@@ -293,3 +260,3 @@ candidates: [],

walker = walker.children[_char];
walker = walker.children[char];
}

@@ -304,59 +271,14 @@

function createSearchTrie(trie, index, items, options) {
var _iteratorNormalCompletion2 = true;
var _didIteratorError2 = false;
var _iteratorError2 = undefined;
for (const item of items) {
const candidates = arrayWrap(options.keySelector(item)).map((key, keyIndex) => ({
index,
keyIndex,
item,
normalized: normalize(key, options)
}));
index++;
try {
var _loop = function _loop() {
var item = _step2.value;
var candidates = arrayWrap(options.keySelector(item)).map(function (key, keyIndex) {
return {
index: index,
keyIndex: keyIndex,
item: item,
normalized: normalize(key, options)
};
});
index++;
var _iteratorNormalCompletion3 = true;
var _didIteratorError3 = false;
var _iteratorError3 = undefined;
try {
for (var _iterator3 = candidates[Symbol.iterator](), _step3; !(_iteratorNormalCompletion3 = (_step3 = _iterator3.next()).done); _iteratorNormalCompletion3 = true) {
var candidate = _step3.value;
trieInsert(trie, candidate.normalized.normal, candidate);
}
} catch (err) {
_didIteratorError3 = true;
_iteratorError3 = err;
} finally {
try {
if (!_iteratorNormalCompletion3 && _iterator3["return"] != null) {
_iterator3["return"]();
}
} finally {
if (_didIteratorError3) {
throw _iteratorError3;
}
}
}
};
for (var _iterator2 = items[Symbol.iterator](), _step2; !(_iteratorNormalCompletion2 = (_step2 = _iterator2.next()).done); _iteratorNormalCompletion2 = true) {
_loop();
for (const candidate of candidates) {
trieInsert(trie, candidate.normalized.normal, candidate);
}
} catch (err) {
_didIteratorError2 = true;
_iteratorError2 = err;
} finally {
try {
if (!_iteratorNormalCompletion2 && _iterator2["return"] != null) {
_iterator2["return"]();
}
} finally {
if (_didIteratorError2) {
throw _iteratorError2;
}
}
}

@@ -367,3 +289,3 @@ } // scored item comparator

function compareItems(a, b) {
var scoreDiff = b.score - a.score;
const scoreDiff = b.score - a.score;

@@ -374,3 +296,3 @@ if (scoreDiff !== 0) {

var keyIndexDiff = a.keyIndex - b.keyIndex;
const keyIndexDiff = a.keyIndex - b.keyIndex;

@@ -381,3 +303,3 @@ if (keyIndexDiff !== 0) {

var lengthDiff = a.lengthDiff - b.lengthDiff;
const lengthDiff = a.lengthDiff - b.lengthDiff;

@@ -393,10 +315,10 @@ if (lengthDiff !== 0) {

function addResult(results, resultMap, candidate, score, match, lengthDiff) {
var scoredItem = {
const scoredItem = {
item: candidate.item,
normalized: candidate.normalized,
score: score,
match: match,
score,
match,
index: candidate.index,
keyIndex: candidate.keyIndex,
lengthDiff: lengthDiff
lengthDiff
};

@@ -412,7 +334,5 @@

var getLevLength = Math.max;
const getLevLength = Math.max;
var getSellersLength = function getSellersLength(termLength) {
return termLength;
}; // skip any subtrees for which it is impossible to score >= threshold
const getSellersLength = termLength => termLength; // skip any subtrees for which it is impossible to score >= threshold

@@ -422,9 +342,9 @@

// earliest point (length) at which sValue could return to 0
var p1 = pos + sValue; // point (length) at which string lengths would match
const p1 = pos + sValue; // point (length) at which string lengths would match
var p2 = Math.min(term.length, pos + node.depth + 1); // the best score possible is the string which minimizes the value
const p2 = Math.min(term.length, pos + node.depth + 1); // the best score possible is the string which minimizes the value
// max(sValue, strLenDiff), which is always halfway between p1 and p2
var length = Math.ceil((p1 + p2) / 2);
var bestPossibleValue = length - p2;
const length = Math.ceil((p1 + p2) / 2);
const bestPossibleValue = length - p2;
return 1 - bestPossibleValue / length >= threshold;

@@ -434,3 +354,3 @@ }

function sellersShouldContinue(node, _, term, threshold, sValue, lastValue) {
var bestPossibleValue = Math.min(sValue, lastValue - (node.depth + 1));
const bestPossibleValue = Math.min(sValue, lastValue - (node.depth + 1));
return 1 - bestPossibleValue / term.length >= threshold;

@@ -444,4 +364,4 @@ } // recursively walk the trie

var lastIndex = len;
var lastValue = rows[rows.length - 1][lastIndex];
const lastIndex = len;
const lastValue = rows[rows.length - 1][lastIndex];

@@ -455,30 +375,11 @@ if (scoreMethods.shouldUpdateScore(lastValue, sValue)) {

if (node.candidates.length > 0) {
var length = scoreMethods.getLength(term.length, len);
var score = 1 - sValue / length;
const length = scoreMethods.getLength(term.length, len);
const score = 1 - sValue / length;
if (score >= options.threshold) {
var match = scoreMethods.walkBack(rows, sIndex);
var lengthDiff = Math.abs(len - term.length);
var _iteratorNormalCompletion4 = true;
var _didIteratorError4 = false;
var _iteratorError4 = undefined;
const match = scoreMethods.walkBack(rows, sIndex);
const lengthDiff = Math.abs(len - term.length);
try {
for (var _iterator4 = node.candidates[Symbol.iterator](), _step4; !(_iteratorNormalCompletion4 = (_step4 = _iterator4.next()).done); _iteratorNormalCompletion4 = true) {
var candidate = _step4.value;
addResult(results, resultMap, candidate, score, match, lengthDiff);
}
} catch (err) {
_didIteratorError4 = true;
_iteratorError4 = err;
} finally {
try {
if (!_iteratorNormalCompletion4 && _iterator4["return"] != null) {
_iterator4["return"]();
}
} finally {
if (_didIteratorError4) {
throw _iteratorError4;
}
}
for (const candidate of node.candidates) {
addResult(results, resultMap, candidate, score, match, lengthDiff);
}

@@ -489,4 +390,4 @@ }

for (var key in node.children) {
var child = node.children[key];
for (const key in node.children) {
const child = node.children[key];

@@ -503,4 +404,4 @@ if (scoreMethods.shouldContinue(child, len, term, options.threshold, sValue, lastValue)) {

function searchCore(term, trie, options) {
var initMethod = options.useSellers ? initSellersRows : initLevRows;
var scoreMethods = {
const initMethod = options.useSellers ? initSellersRows : initLevRows;
const scoreMethods = {
score: options.useDamerau ? damerauLevenshtein : levenshtein,

@@ -513,38 +414,18 @@ getLength: options.useSellers ? getSellersLength : getLevLength,

var resultMap = {};
var results = [];
var rows = initMethod(term.length + 1, trie.depth + 1);
const resultMap = {};
const results = [];
const rows = initMethod(term.length + 1, trie.depth + 1);
if (options.threshold <= 0 || term.length === 0) {
var _iteratorNormalCompletion5 = true;
var _didIteratorError5 = false;
var _iteratorError5 = undefined;
try {
for (var _iterator5 = trie.candidates[Symbol.iterator](), _step5; !(_iteratorNormalCompletion5 = (_step5 = _iterator5.next()).done); _iteratorNormalCompletion5 = true) {
var candidate = _step5.value;
addResult(results, resultMap, candidate, 0, {
index: 0,
length: 0
}, term.length);
}
} catch (err) {
_didIteratorError5 = true;
_iteratorError5 = err;
} finally {
try {
if (!_iteratorNormalCompletion5 && _iterator5["return"] != null) {
_iterator5["return"]();
}
} finally {
if (_didIteratorError5) {
throw _iteratorError5;
}
}
for (const candidate of trie.candidates) {
addResult(results, resultMap, candidate, 0, {
index: 0,
length: 0
}, term.length);
}
}
for (var key in trie.children) {
var value = trie.children[key];
var acc = new Array(trie.depth);
for (const key in trie.children) {
const value = trie.children[key];
const acc = new Array(trie.depth);
acc[0] = key;

@@ -554,20 +435,16 @@ searchRecurse(value, acc, 1, term, scoreMethods, rows, results, resultMap, options, 0, term.length);

var sorted = results.sort(compareItems);
const sorted = results.sort(compareItems);
if (options.returnMatchData) {
var denormalize = options.useSellers ? denormalizeMatchPosition : noop;
return sorted.map(function (candidate) {
return {
item: candidate.item,
original: candidate.normalized.original,
key: candidate.normalized.normal.join(""),
score: candidate.score,
match: denormalize(candidate.match, candidate.normalized.map)
};
});
const denormalize = options.useSellers ? denormalizeMatchPosition : noop;
return sorted.map(candidate => ({
item: candidate.item,
original: candidate.normalized.original,
key: candidate.normalized.normal.join(""),
score: candidate.score,
match: denormalize(candidate.match, candidate.normalized.map)
}));
}
return sorted.map(function (candidate) {
return candidate.item;
});
return sorted.map(candidate => candidate.item);
} // wrapper for exporting sellers while allowing options to be passed in

@@ -578,14 +455,14 @@

options = _objectSpread({}, defaultOptions, {}, options);
var initMethod = options.useSellers ? initSellersRows : initLevRows;
var scoreMethod = options.useDamerau ? damerauLevenshtein : levenshtein;
var getScore = options.useSellers ? getSellersScore : getLevScore;
const initMethod = options.useSellers ? initSellersRows : initLevRows;
const scoreMethod = options.useDamerau ? damerauLevenshtein : levenshtein;
const getScore = options.useSellers ? getSellersScore : getLevScore;
term = normalize(term, options).normal;
var normalized = normalize(candidate, options);
var rows = initMethod(term.length + 1, normalized.normal.length + 1);
const normalized = normalize(candidate, options);
const rows = initMethod(term.length + 1, normalized.normal.length + 1);
for (var j = 0; j < normalized.normal.length; j++) {
for (let j = 0; j < normalized.normal.length; j++) {
scoreMethod(term, normalized.normal, rows, j);
}
var scoreResult = getScore(rows, normalized.normal.length + 1);
const scoreResult = getScore(rows, normalized.normal.length + 1);
return options.returnMatchData ? {

@@ -602,4 +479,4 @@ item: candidate,

function search(term, candidates, options) {
options = Object.assign({}, defaultOptions, options);
var trie = {
options = _objectSpread({}, defaultOptions, {}, options);
const trie = {
children: {},

@@ -615,8 +492,4 @@ candidates: [],

var Searcher =
/*#__PURE__*/
function () {
function Searcher(candidates, options) {
_classCallCheck(this, Searcher);
class Searcher {
constructor(candidates, options) {
this.options = Object.assign({}, defaultOptions, options);

@@ -632,27 +505,18 @@ this.trie = {

_createClass(Searcher, [{
key: "add",
value: function add() {
for (var _len = arguments.length, candidates = new Array(_len), _key = 0; _key < _len; _key++) {
candidates[_key] = arguments[_key];
}
add(...candidates) {
createSearchTrie(this.trie, this.count, candidates, this.options);
this.count += candidates.length;
}
createSearchTrie(this.trie, this.count, candidates, this.options);
this.count += candidates.length;
}
}, {
key: "search",
value: function search(term, options) {
options = Object.assign({}, this.options, options);
return searchCore(normalize(term, this.options).normal, this.trie, options);
}
}]);
search(term, options) {
options = Object.assign({}, this.options, options);
return searchCore(normalize(term, this.options).normal, this.trie, options);
}
return Searcher;
}();
}
module.exports = {
fuzzy: fuzzy,
search: search,
Searcher: Searcher
fuzzy,
search,
Searcher
};
{
"name": "fast-fuzzy",
"version": "1.9.1",
"version": "1.9.2",
"description": "Fast and tiny fuzzy-search utility",

@@ -31,11 +31,12 @@ "main": "lib/fuzzy.js",

"homepage": "https://github.com/EthanRutherford/fast-fuzzy#readme",
"browserslist": "> 1%, not ie > 0, not op_mini all",
"devDependencies": {
"@babel/cli": "^7.5.5",
"@babel/core": "^7.5.5",
"@babel/preset-env": "^7.5.5",
"@babel/cli": "^7.8.4",
"@babel/core": "^7.8.7",
"@babel/preset-env": "^7.8.7",
"mocha": "^5.2.0"
},
"dependencies": {
"graphemesplit": "^2.0.3"
"graphemesplit": "^2.3.0"
}
}

@@ -1,2 +0,2 @@

# fast-fuzzy [![Build Status](https://travis-ci.org/EthanRutherford/fast-fuzzy.svg?branch=master)](https://travis-ci.org/EthanRutherford/fast-fuzzy) [![npm](https://img.shields.io/npm/v/fast-fuzzy.svg)](https://www.npmjs.com/package/fast-fuzzy)
# fast-fuzzy [![Build Status](https://travis-ci.com/EthanRutherford/fast-fuzzy.svg?branch=master)](https://travis-ci.com/EthanRutherford/fast-fuzzy) [![npm](https://img.shields.io/npm/v/fast-fuzzy.svg)](https://www.npmjs.com/package/fast-fuzzy)
Fast fuzzy-search utility

@@ -3,0 +3,0 @@

SocketSocket SOC 2 Logo

Product

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

Packages

npm

Stay in touch

Get open source security insights delivered straight into your inbox.


  • Terms
  • Privacy
  • Security

Made with โšก๏ธ by Socket Inc