diff options
Diffstat (limited to 'node_modules/didyoumean')
| -rw-r--r-- | node_modules/didyoumean/LICENSE | 14 | ||||
| -rw-r--r-- | node_modules/didyoumean/README.md | 134 | ||||
| -rw-r--r-- | node_modules/didyoumean/didYouMean-1.2.1.js | 274 | ||||
| -rw-r--r-- | node_modules/didyoumean/didYouMean-1.2.1.min.js | 17 | ||||
| -rwxr-xr-x | node_modules/didyoumean/package.json | 27 |
5 files changed, 466 insertions, 0 deletions
diff --git a/node_modules/didyoumean/LICENSE b/node_modules/didyoumean/LICENSE new file mode 100644 index 0000000..32c23db --- /dev/null +++ b/node_modules/didyoumean/LICENSE @@ -0,0 +1,14 @@ +## License + +didYouMean.js copyright (c) 2013 Dave Porter. + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License +[here](http://www.apache.org/licenses/LICENSE-2.0). + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. diff --git a/node_modules/didyoumean/README.md b/node_modules/didyoumean/README.md new file mode 100644 index 0000000..cd16698 --- /dev/null +++ b/node_modules/didyoumean/README.md @@ -0,0 +1,134 @@ +didYouMean.js - A simple JavaScript matching engine +=================================================== + +[Available on GitHub](https://github.com/dcporter/didyoumean.js). + +A super-simple, highly optimized JS library for matching human-quality input to a list of potential +matches. You can use it to suggest a misspelled command-line utility option to a user, or to offer +links to nearby valid URLs on your 404 page. (The examples below are taken from a personal project, +my [HTML5 business card](http://dcporter.aws.af.cm/me), which uses didYouMean.js to suggest correct +URLs from misspelled ones, such as [dcporter.aws.af.cm/me/instagarm](http://dcporter.aws.af.cm/me/instagarm).) +Uses the [Levenshtein distance algorithm](https://en.wikipedia.org/wiki/Levenshtein_distance). + +didYouMean.js works in the browser as well as in node.js. To install it for use in node: + +``` +npm install didyoumean +``` + + +Examples +-------- + +Matching against a list of strings: +``` +var input = 'insargrm' +var list = ['facebook', 'twitter', 'instagram', 'linkedin']; +console.log(didYouMean(input, list)); +> 'instagram' +// The method matches 'insargrm' to 'instagram'. + +input = 'google plus'; +console.log(didYouMean(input, list)); +> null +// The method was unable to find 'google plus' in the list of options. +``` + +Matching against a list of objects: +``` +var input = 'insargrm'; +var list = [ { id: 'facebook' }, { id: 'twitter' }, { id: 'instagram' }, { id: 'linkedin' } ]; +var key = 'id'; +console.log(didYouMean(input, list, key)); +> 'instagram' +// The method returns the matching value. + +didYouMean.returnWinningObject = true; +console.log(didYouMean(input, list, key)); +> { id: 'instagram' } +// The method returns the matching object. +``` + + +didYouMean(str, list, [key]) +---------------------------- + +- str: The string input to match. +- list: An array of strings or objects to match against. +- key (OPTIONAL): If your list array contains objects, you must specify the key which contains the string + to match against. + +Returns: the closest matching string, or null if no strings exceed the threshold. + + +Options +------- + +Options are set on the didYouMean function object. You may change them at any time. + +### threshold + + By default, the method will only return strings whose edit distance is less than 40% (0.4x) of their length. + For example, if a ten-letter string is five edits away from its nearest match, the method will return null. + + You can control this by setting the "threshold" value on the didYouMean function. For example, to set the + edit distance threshold to 50% of the input string's length: + + ``` + didYouMean.threshold = 0.5; + ``` + + To return the nearest match no matter the threshold, set this value to null. + +### thresholdAbsolute + + This option behaves the same as threshold, but instead takes an integer number of edit steps. For example, + if thresholdAbsolute is set to 20 (the default), then the method will only return strings whose edit distance + is less than 20. Both options apply. + +### caseSensitive + + By default, the method will perform case-insensitive comparisons. If you wish to force case sensitivity, set + the "caseSensitive" value to true: + + ``` + didYouMean.caseSensitive = true; + ``` + +### nullResultValue + + By default, the method will return null if there is no sufficiently close match. You can change this value here. + +### returnWinningObject + + By default, the method will return the winning string value (if any). If your list contains objects rather + than strings, you may set returnWinningObject to true. + + ``` + didYouMean.returnWinningObject = true; + ``` + + This option has no effect on lists of strings. + +### returnFirstMatch + + By default, the method will search all values and return the closest match. If you're simply looking for a "good- + enough" match, you can set your thresholds appropriately and set returnFirstMatch to true to substantially speed + things up. + + +License +------- + +didYouMean copyright (c) 2013-2014 Dave Porter. + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License +[here](http://www.apache.org/licenses/LICENSE-2.0). + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. diff --git a/node_modules/didyoumean/didYouMean-1.2.1.js b/node_modules/didyoumean/didYouMean-1.2.1.js new file mode 100644 index 0000000..febb30e --- /dev/null +++ b/node_modules/didyoumean/didYouMean-1.2.1.js @@ -0,0 +1,274 @@ +/* + +didYouMean.js - A simple JavaScript matching engine +=================================================== + +[Available on GitHub](https://github.com/dcporter/didyoumean.js). + +A super-simple, highly optimized JS library for matching human-quality input to a list of potential +matches. You can use it to suggest a misspelled command-line utility option to a user, or to offer +links to nearby valid URLs on your 404 page. (The examples below are taken from a personal project, +my [HTML5 business card](http://dcporter.aws.af.cm/me), which uses didYouMean.js to suggest correct +URLs from misspelled ones, such as [dcporter.aws.af.cm/me/instagarm](http://dcporter.aws.af.cm/me/instagarm).) +Uses the [Levenshtein distance algorithm](https://en.wikipedia.org/wiki/Levenshtein_distance). + +didYouMean.js works in the browser as well as in node.js. To install it for use in node: + +``` +npm install didyoumean +``` + + +Examples +-------- + +Matching against a list of strings: +``` +var input = 'insargrm' +var list = ['facebook', 'twitter', 'instagram', 'linkedin']; +console.log(didYouMean(input, list)); +> 'instagram' +// The method matches 'insargrm' to 'instagram'. + +input = 'google plus'; +console.log(didYouMean(input, list)); +> null +// The method was unable to find 'google plus' in the list of options. +``` + +Matching against a list of objects: +``` +var input = 'insargrm'; +var list = [ { id: 'facebook' }, { id: 'twitter' }, { id: 'instagram' }, { id: 'linkedin' } ]; +var key = 'id'; +console.log(didYouMean(input, list, key)); +> 'instagram' +// The method returns the matching value. + +didYouMean.returnWinningObject = true; +console.log(didYouMean(input, list, key)); +> { id: 'instagram' } +// The method returns the matching object. +``` + + +didYouMean(str, list, [key]) +---------------------------- + +- str: The string input to match. +- list: An array of strings or objects to match against. +- key (OPTIONAL): If your list array contains objects, you must specify the key which contains the string + to match against. + +Returns: the closest matching string, or null if no strings exceed the threshold. + + +Options +------- + +Options are set on the didYouMean function object. You may change them at any time. + +### threshold + + By default, the method will only return strings whose edit distance is less than 40% (0.4x) of their length. + For example, if a ten-letter string is five edits away from its nearest match, the method will return null. + + You can control this by setting the "threshold" value on the didYouMean function. For example, to set the + edit distance threshold to 50% of the input string's length: + + ``` + didYouMean.threshold = 0.5; + ``` + + To return the nearest match no matter the threshold, set this value to null. + +### thresholdAbsolute + + This option behaves the same as threshold, but instead takes an integer number of edit steps. For example, + if thresholdAbsolute is set to 20 (the default), then the method will only return strings whose edit distance + is less than 20. Both options apply. + +### caseSensitive + + By default, the method will perform case-insensitive comparisons. If you wish to force case sensitivity, set + the "caseSensitive" value to true: + + ``` + didYouMean.caseSensitive = true; + ``` + +### nullResultValue + + By default, the method will return null if there is no sufficiently close match. You can change this value here. + +### returnWinningObject + + By default, the method will return the winning string value (if any). If your list contains objects rather + than strings, you may set returnWinningObject to true. + + ``` + didYouMean.returnWinningObject = true; + ``` + + This option has no effect on lists of strings. + +### returnFirstMatch + + By default, the method will search all values and return the closest match. If you're simply looking for a "good- + enough" match, you can set your thresholds appropriately and set returnFirstMatch to true to substantially speed + things up. + + +License +------- + +didYouMean copyright (c) 2013-2014 Dave Porter. + +Licensed under the Apache License, Version 2.0 (the "License"); +you may not use this file except in compliance with the License. +You may obtain a copy of the License +[here](http://www.apache.org/licenses/LICENSE-2.0). + +Unless required by applicable law or agreed to in writing, software +distributed under the License is distributed on an "AS IS" BASIS, +WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +See the License for the specific language governing permissions and +limitations under the License. + +*/ +(function() { + "use strict"; + + // The didYouMean method. + function didYouMean(str, list, key) { + if (!str) return null; + + // If we're running a case-insensitive search, smallify str. + if (!didYouMean.caseSensitive) { str = str.toLowerCase(); } + + // Calculate the initial value (the threshold) if present. + var thresholdRelative = didYouMean.threshold === null ? null : didYouMean.threshold * str.length, + thresholdAbsolute = didYouMean.thresholdAbsolute, + winningVal; + if (thresholdRelative !== null && thresholdAbsolute !== null) winningVal = Math.min(thresholdRelative, thresholdAbsolute); + else if (thresholdRelative !== null) winningVal = thresholdRelative; + else if (thresholdAbsolute !== null) winningVal = thresholdAbsolute; + else winningVal = null; + + // Get the edit distance to each option. If the closest one is less than 40% (by default) of str's length, + // then return it. + var winner, candidate, testCandidate, val, + i, len = list.length; + for (i = 0; i < len; i++) { + // Get item. + candidate = list[i]; + // If there's a key, get the candidate value out of the object. + if (key) { candidate = candidate[key]; } + // Gatekeep. + if (!candidate) { continue; } + // If we're running a case-insensitive search, smallify the candidate. + if (!didYouMean.caseSensitive) { testCandidate = candidate.toLowerCase(); } + else { testCandidate = candidate; } + // Get and compare edit distance. + val = getEditDistance(str, testCandidate, winningVal); + // If this value is smaller than our current winning value, OR if we have no winning val yet (i.e. the + // threshold option is set to null, meaning the caller wants a match back no matter how bad it is), then + // this is our new winner. + if (winningVal === null || val < winningVal) { + winningVal = val; + // Set the winner to either the value or its object, depending on the returnWinningObject option. + if (key && didYouMean.returnWinningObject) winner = list[i]; + else winner = candidate; + // If we're returning the first match, return it now. + if (didYouMean.returnFirstMatch) return winner; + } + } + + // If we have a winner, return it. + return winner || didYouMean.nullResultValue; + } + + // Set default options. + didYouMean.threshold = 0.4; + didYouMean.thresholdAbsolute = 20; + didYouMean.caseSensitive = false; + didYouMean.nullResultValue = null; + didYouMean.returnWinningObject = null; + didYouMean.returnFirstMatch = false; + + // Expose. + // In node... + if (typeof module !== 'undefined' && module.exports) { + module.exports = didYouMean; + } + // Otherwise... + else { + window.didYouMean = didYouMean; + } + + var MAX_INT = Math.pow(2,32) - 1; // We could probably go higher than this, but for practical reasons let's not. + function getEditDistance(a, b, max) { + // Handle null or undefined max. + max = max || max === 0 ? max : MAX_INT; + + var lena = a.length; + var lenb = b.length; + + // Fast path - no A or B. + if (lena === 0) return Math.min(max + 1, lenb); + if (lenb === 0) return Math.min(max + 1, lena); + + // Fast path - length diff larger than max. + if (Math.abs(lena - lenb) > max) return max + 1; + + // Slow path. + var matrix = [], + i, j, colMin, minJ, maxJ; + + // Set up the first row ([0, 1, 2, 3, etc]). + for (i = 0; i <= lenb; i++) { matrix[i] = [i]; } + + // Set up the first column (same). + for (j = 0; j <= lena; j++) { matrix[0][j] = j; } + + // Loop over the rest of the columns. + for (i = 1; i <= lenb; i++) { + colMin = MAX_INT; + minJ = 1; + if (i > max) minJ = i - max; + maxJ = lenb + 1; + if (maxJ > max + i) maxJ = max + i; + // Loop over the rest of the rows. + for (j = 1; j <= lena; j++) { + // If j is out of bounds, just put a large value in the slot. + if (j < minJ || j > maxJ) { + matrix[i][j] = max + 1; + } + + // Otherwise do the normal Levenshtein thing. + else { + // If the characters are the same, there's no change in edit distance. + if (b.charAt(i - 1) === a.charAt(j - 1)) { + matrix[i][j] = matrix[i - 1][j - 1]; + } + // Otherwise, see if we're substituting, inserting or deleting. + else { + matrix[i][j] = Math.min(matrix[i - 1][j - 1] + 1, // Substitute + Math.min(matrix[i][j - 1] + 1, // Insert + matrix[i - 1][j] + 1)); // Delete + } + } + + // Either way, update colMin. + if (matrix[i][j] < colMin) colMin = matrix[i][j]; + } + + // If this column's minimum is greater than the allowed maximum, there's no point + // in going on with life. + if (colMin > max) return max + 1; + } + // If we made it this far without running into the max, then return the final matrix value. + return matrix[lenb][lena]; + } + +})(); diff --git a/node_modules/didyoumean/didYouMean-1.2.1.min.js b/node_modules/didyoumean/didYouMean-1.2.1.min.js new file mode 100644 index 0000000..c41abd8 --- /dev/null +++ b/node_modules/didyoumean/didYouMean-1.2.1.min.js @@ -0,0 +1,17 @@ +/* + didYouMean.js copyright (c) 2013-2014 Dave Porter. + + [Available on GitHub](https://github.com/dcporter/didyoumean.js). + + Licensed under the Apache License, Version 2.0 (the "License"); + you may not use this file except in compliance with the License. + You may obtain a copy of the License + [here](http://www.apache.org/licenses/LICENSE-2.0). + + Unless required by applicable law or agreed to in writing, software + distributed under the License is distributed on an "AS IS" BASIS, + WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + See the License for the specific language governing permissions and + limitations under the License. +*/ +(function(){"use strict";function e(t,r,i){if(!t)return null;if(!e.caseSensitive){t=t.toLowerCase()}var s=e.threshold===null?null:e.threshold*t.length,o=e.thresholdAbsolute,u;if(s!==null&&o!==null)u=Math.min(s,o);else if(s!==null)u=s;else if(o!==null)u=o;else u=null;var a,f,l,c,h,p=r.length;for(h=0;h<p;h++){f=r[h];if(i){f=f[i]}if(!f){continue}if(!e.caseSensitive){l=f.toLowerCase()}else{l=f}c=n(t,l,u);if(u===null||c<u){u=c;if(i&&e.returnWinningObject)a=r[h];else a=f;if(e.returnFirstMatch)return a}}return a||e.nullResultValue}function n(e,n,r){r=r||r===0?r:t;var i=e.length;var s=n.length;if(i===0)return Math.min(r+1,s);if(s===0)return Math.min(r+1,i);if(Math.abs(i-s)>r)return r+1;var o=[],u,a,f,l,c;for(u=0;u<=s;u++){o[u]=[u]}for(a=0;a<=i;a++){o[0][a]=a}for(u=1;u<=s;u++){f=t;l=1;if(u>r)l=u-r;c=s+1;if(c>r+u)c=r+u;for(a=1;a<=i;a++){if(a<l||a>c){o[u][a]=r+1}else{if(n.charAt(u-1)===e.charAt(a-1)){o[u][a]=o[u-1][a-1]}else{o[u][a]=Math.min(o[u-1][a-1]+1,Math.min(o[u][a-1]+1,o[u-1][a]+1))}}if(o[u][a]<f)f=o[u][a]}if(f>r)return r+1}return o[s][i]}e.threshold=.4;e.thresholdAbsolute=20;e.caseSensitive=false;e.nullResultValue=null;e.returnWinningObject=null;e.returnFirstMatch=false;if(typeof module!=="undefined"&&module.exports){module.exports=e}else{window.didYouMean=e}var t=Math.pow(2,32)-1})();
\ No newline at end of file diff --git a/node_modules/didyoumean/package.json b/node_modules/didyoumean/package.json new file mode 100755 index 0000000..1301d03 --- /dev/null +++ b/node_modules/didyoumean/package.json @@ -0,0 +1,27 @@ +{ + "name": "didyoumean", + "version": "1.2.2", + "description": "Match human-quality input to potential matches by edit distance.", + "homepage": "https://github.com/dcporter/didyoumean.js", + "author": { + "name": "Dave Porter", + "email": "dcporter@gmail.com", + "url": "http://dcporter.net/" + }, + "keywords": [ + "didyoumean", + "mean", + "edit", + "distance", + "levenshtein" + ], + "main": "./didYouMean-1.2.1.js", + "repository": { + "type": "git", + "url": "https://github.com/dcporter/didyoumean.js.git" + }, + "bugs": { + "url": "https://github.com/dcporter/didyoumean.js/issues" + }, + "license": "Apache-2.0" +} |