fast-fuzzy - npm Package Compare versions

Comparing version 1.4.0 to 1.5.0

lib/fuzzy.js

@@ -9,4 +9,5 @@ "use strict";
 
-var nonWordRegex = /[`~!@#$%^&*()\-=_+{}[\]\|\\;':",./<>?]+/g;
-var whitespaceRegex = /\s+/g;
+var whitespaceRegex = /(\s+)()/g;
+var nonWordRegex = /()([`~!@#$%^&*()\-=_+{}[\]\|\\;':",./<>?]+)/g;
+var bothRegex = /(\s+)|([`~!@#$%^&*()\-=_+{}[\]\|\\;':",./<>?]+)/g;
 
@@ -41,2 +42,75 @@ //the default options, which will be used for any unset option
 
+//return normalized string, with original and map included
+function normalizeWithMap(string, options) {
+	var original = string.normalize();
+	var normal = original;
+	if (options.ignoreCase) {
+		normal = normal.toLocaleLowerCase();
+	}
+
+	//track transformations
+	var map = [];
+	var regex = void 0;
+	if (options.normalizeWhitespace) {
+		var trimStart = normal.match(/^\s+/);
+		if (trimStart) {
+			map.push({ index: 0, offset: trimStart[0].length });
+		}
+		normal = normal.trim();
+
+		if (options.ignoreSymbols) {
+			regex = bothRegex;
+		} else {
+			regex = whitespaceRegex;
+		}
+	} else if (options.ignoreSymbols) {
+		regex = nonWordRegex;
+	} else {
+		return { original: original, normal: normal, map: [] };
+	}
+
+	var lastInd = 0;
+	var built = "";
+	var match = void 0;
+	var prev = map[map.length - 1] || { index: -.1 };
+	while (match = regex.exec(normal)) {
+		var length = match[0].length;
+		built += normal.slice(lastInd, match.index);
+
+		lastInd = match.index + length;
+		if (match[1]) {
+			built += " ";
+			if (length === 1) continue;
+			length--;
+		}
+
+		var start = built.length;
+		if (prev.index === start) {
+			prev.offset += length;
+		} else {
+			map.push(prev = { index: start, offset: length });
+		}
+	}
+
+	return { original: original, normal: built + normal.slice(lastInd), map: map };
+}
+
+//translate a match to the original string
+function denormalizeMatchPosition(match, map) {
+	var start = match.index;
+	var end = match.index + match.length;
+	var i = 0;
+	while (i < map.length && map[i].index <= end) {
+		if (map[i].index <= start) {
+			match.index += map[i].offset;
+		} else {
+			match.length += map[i].offset;
+		}
+
+		i++;
+	}
+
+	return match;
+}
+
 //finds the minimum value of the last row from the levenshtein-sellers matrix
@@ -154,8 +228,11 @@ //then walks back up the matrix to find the match index
 	var results = candidates.map(function (candidate) {
-		var matchData = scoreMethod(term, candidate.key);
+		var normalized = candidate.normalized;
+		var matchData = scoreMethod(term, normalized.normal);
+		var match = options.returnMatchData && denormalizeMatchPosition(matchData.match, normalized.map);
 		return {
 			item: candidate.item,
-			key: candidate.key,
+			original: normalized.normal,
+			key: normalized.normal,
 			score: matchData.score,
-			match: matchData.match
+			match: match
 		};
@@ -180,3 +257,6 @@ }).filter(function (candidate) {
 	return items.map(function (item) {
-		return { item: item, key: normalize(options.keySelector(item), options) };
+		return {
+			item: item,
+			normalized: normalizeWithMap(options.keySelector(item), options)
+		};
 	});
@@ -190,5 +270,11 @@ }
 	term = normalize(term, options);
-	candidate = normalize(candidate, options);
-	var result = scoreMethod(term, candidate);
-	return options.returnMatchData ? result : result.score;
+	var normalized = normalizeWithMap(candidate, options);
+	var result = scoreMethod(term, normalized.normal);
+	return options.returnMatchData ? {
+		item: candidate,
+		original: normalized.original,
+		key: normalized.normal,
+		score: result.score,
+		match: denormalizeMatchPosition(result.match, normalized.map)
+	} : result.score;
 }
@@ -195,0 +281,0 @@

package.json

 {
   "name": "fast-fuzzy",
-  "version": "1.4.0",
+  "version": "1.5.0",
   "description": "Fast and tiny fuzzy-search utility",
@@ -5,0 +5,0 @@ "main": "lib/fuzzy.js",

README.md

@@ -52,3 +52,3 @@ # 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)
 
-\*\* in the form `{item, key, score, match: {index, length}}`
+\*\* in the form `{item, original, key, score, match: {index, length}}`
 
@@ -79,3 +79,7 @@ `fuzzy` accepts a subset of these options (excluding keySelector and threshold) with the same defaults.
 //pass in a keySelector to search for objects
-search("abc", [{name: "def"}, {name: "bcd"}, {name: "cde"}, {name: "abc"}], {keySelector: (obj) => obj.name});
+search(
+    "abc",
+    [{name: "def"}, {name: "bcd"}, {name: "cde"}, {name: "abc"}],
+    {keySelector: (obj) => obj.name},
+);
 //returns [{name: "abc"}, {name: "bcd"}]
@@ -86,6 +90,6 @@
 /* returns [{
-    item: 'abc', key: 'abc', score: 1,
+    item: 'abc', original: 'abc', key: 'abc', score: 1,
     match: {index: 0, length: 3},
 }, { 
-    item: 'bcd', key: 'bcd', score: 0.6666666666666667,
+    item: 'bcd', original: 'bcd', key: 'bcd', score: 0.6666666666666667,
     match: {index: 0, length: 2},
@@ -104,3 +108,6 @@ }] */
 //options are passed in on construction
-const anotherSearcher = new Searcher([{name: "thing1"}, {name: "thing2"}], {keySelector: (obj) => obj.name});
+const anotherSearcher = new Searcher(
+    [{name: "thing1"}, {name: "thing2"}],
+    {keySelector: (obj) => obj.name},
+);
 
@@ -110,8 +117,8 @@ //some options can be overridden per call
 /* returns [{
-    item: 'abc', key: 'abc', score: 1,
+    item: 'abc', original: 'abc', key: 'abc', score: 1,
     match: {index: 0, length: 3},
 }, { 
-    item: 'bcd', key: 'bcd', score: 0.6666666666666667,
+    item: 'bcd', original: 'bcd', key: 'bcd', score: 0.6666666666666667,
     match: {index: 0, length: 2},
 }] */
 ```

test.js

@@ -82,2 +82,5 @@ /* global describe, it */
 				{
+					item: "acbd",
+					original: "acbd",
+					key: "acbd",
 					score: .75,
@@ -88,2 +91,15 @@ match: {index: 0, length: 4},
 		});
+
+		it("should map matches to their original positions", function() {
+			assert.deepEqual(
+				fuzzy("hello", "  h..e..l..l  ..o", {returnMatchData: true}),
+				{
+					item: "  h..e..l..l  ..o",
+					original: "  h..e..l..l  ..o",
+					key: "hell o",
+					score: .8,
+					match: {index: 2, length: 10},
+				}
+			);
+		});
 	});
@@ -139,2 +155,3 @@ });
 					item: "hello",
+					original: "hello",
 					key: "hello",
@@ -141,0 +158,0 @@ score: 1,

New alerts

License Policy Violation

License

This 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

License

This 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

22406

increased by13.32%

Lines of code

460

increased by25%

Number of lines in readme file

120

increased by6.19%

No dependency changes