didYouMean-1.2.1.js 9.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274
  1. /*
  2. didYouMean.js - A simple JavaScript matching engine
  3. ===================================================
  4. [Available on GitHub](https://github.com/dcporter/didyoumean.js).
  5. A super-simple, highly optimized JS library for matching human-quality input to a list of potential
  6. matches. You can use it to suggest a misspelled command-line utility option to a user, or to offer
  7. links to nearby valid URLs on your 404 page. (The examples below are taken from a personal project,
  8. my [HTML5 business card](http://dcporter.aws.af.cm/me), which uses didYouMean.js to suggest correct
  9. URLs from misspelled ones, such as [dcporter.aws.af.cm/me/instagarm](http://dcporter.aws.af.cm/me/instagarm).)
  10. Uses the [Levenshtein distance algorithm](https://en.wikipedia.org/wiki/Levenshtein_distance).
  11. didYouMean.js works in the browser as well as in node.js. To install it for use in node:
  12. ```
  13. npm install didyoumean
  14. ```
  15. Examples
  16. --------
  17. Matching against a list of strings:
  18. ```
  19. var input = 'insargrm'
  20. var list = ['facebook', 'twitter', 'instagram', 'linkedin'];
  21. console.log(didYouMean(input, list));
  22. > 'instagram'
  23. // The method matches 'insargrm' to 'instagram'.
  24. input = 'google plus';
  25. console.log(didYouMean(input, list));
  26. > null
  27. // The method was unable to find 'google plus' in the list of options.
  28. ```
  29. Matching against a list of objects:
  30. ```
  31. var input = 'insargrm';
  32. var list = [ { id: 'facebook' }, { id: 'twitter' }, { id: 'instagram' }, { id: 'linkedin' } ];
  33. var key = 'id';
  34. console.log(didYouMean(input, list, key));
  35. > 'instagram'
  36. // The method returns the matching value.
  37. didYouMean.returnWinningObject = true;
  38. console.log(didYouMean(input, list, key));
  39. > { id: 'instagram' }
  40. // The method returns the matching object.
  41. ```
  42. didYouMean(str, list, [key])
  43. ----------------------------
  44. - str: The string input to match.
  45. - list: An array of strings or objects to match against.
  46. - key (OPTIONAL): If your list array contains objects, you must specify the key which contains the string
  47. to match against.
  48. Returns: the closest matching string, or null if no strings exceed the threshold.
  49. Options
  50. -------
  51. Options are set on the didYouMean function object. You may change them at any time.
  52. ### threshold
  53. By default, the method will only return strings whose edit distance is less than 40% (0.4x) of their length.
  54. For example, if a ten-letter string is five edits away from its nearest match, the method will return null.
  55. You can control this by setting the "threshold" value on the didYouMean function. For example, to set the
  56. edit distance threshold to 50% of the input string's length:
  57. ```
  58. didYouMean.threshold = 0.5;
  59. ```
  60. To return the nearest match no matter the threshold, set this value to null.
  61. ### thresholdAbsolute
  62. This option behaves the same as threshold, but instead takes an integer number of edit steps. For example,
  63. if thresholdAbsolute is set to 20 (the default), then the method will only return strings whose edit distance
  64. is less than 20. Both options apply.
  65. ### caseSensitive
  66. By default, the method will perform case-insensitive comparisons. If you wish to force case sensitivity, set
  67. the "caseSensitive" value to true:
  68. ```
  69. didYouMean.caseSensitive = true;
  70. ```
  71. ### nullResultValue
  72. By default, the method will return null if there is no sufficiently close match. You can change this value here.
  73. ### returnWinningObject
  74. By default, the method will return the winning string value (if any). If your list contains objects rather
  75. than strings, you may set returnWinningObject to true.
  76. ```
  77. didYouMean.returnWinningObject = true;
  78. ```
  79. This option has no effect on lists of strings.
  80. ### returnFirstMatch
  81. By default, the method will search all values and return the closest match. If you're simply looking for a "good-
  82. enough" match, you can set your thresholds appropriately and set returnFirstMatch to true to substantially speed
  83. things up.
  84. License
  85. -------
  86. didYouMean copyright (c) 2013-2014 Dave Porter.
  87. Licensed under the Apache License, Version 2.0 (the "License");
  88. you may not use this file except in compliance with the License.
  89. You may obtain a copy of the License
  90. [here](http://www.apache.org/licenses/LICENSE-2.0).
  91. Unless required by applicable law or agreed to in writing, software
  92. distributed under the License is distributed on an "AS IS" BASIS,
  93. WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  94. See the License for the specific language governing permissions and
  95. limitations under the License.
  96. */
  97. (function() {
  98. "use strict";
  99. // The didYouMean method.
  100. function didYouMean(str, list, key) {
  101. if (!str) return null;
  102. // If we're running a case-insensitive search, smallify str.
  103. if (!didYouMean.caseSensitive) { str = str.toLowerCase(); }
  104. // Calculate the initial value (the threshold) if present.
  105. var thresholdRelative = didYouMean.threshold === null ? null : didYouMean.threshold * str.length,
  106. thresholdAbsolute = didYouMean.thresholdAbsolute,
  107. winningVal;
  108. if (thresholdRelative !== null && thresholdAbsolute !== null) winningVal = Math.min(thresholdRelative, thresholdAbsolute);
  109. else if (thresholdRelative !== null) winningVal = thresholdRelative;
  110. else if (thresholdAbsolute !== null) winningVal = thresholdAbsolute;
  111. else winningVal = null;
  112. // Get the edit distance to each option. If the closest one is less than 40% (by default) of str's length,
  113. // then return it.
  114. var winner, candidate, testCandidate, val,
  115. i, len = list.length;
  116. for (i = 0; i < len; i++) {
  117. // Get item.
  118. candidate = list[i];
  119. // If there's a key, get the candidate value out of the object.
  120. if (key) { candidate = candidate[key]; }
  121. // Gatekeep.
  122. if (!candidate) { continue; }
  123. // If we're running a case-insensitive search, smallify the candidate.
  124. if (!didYouMean.caseSensitive) { testCandidate = candidate.toLowerCase(); }
  125. else { testCandidate = candidate; }
  126. // Get and compare edit distance.
  127. val = getEditDistance(str, testCandidate, winningVal);
  128. // If this value is smaller than our current winning value, OR if we have no winning val yet (i.e. the
  129. // threshold option is set to null, meaning the caller wants a match back no matter how bad it is), then
  130. // this is our new winner.
  131. if (winningVal === null || val < winningVal) {
  132. winningVal = val;
  133. // Set the winner to either the value or its object, depending on the returnWinningObject option.
  134. if (key && didYouMean.returnWinningObject) winner = list[i];
  135. else winner = candidate;
  136. // If we're returning the first match, return it now.
  137. if (didYouMean.returnFirstMatch) return winner;
  138. }
  139. }
  140. // If we have a winner, return it.
  141. return winner || didYouMean.nullResultValue;
  142. }
  143. // Set default options.
  144. didYouMean.threshold = 0.4;
  145. didYouMean.thresholdAbsolute = 20;
  146. didYouMean.caseSensitive = false;
  147. didYouMean.nullResultValue = null;
  148. didYouMean.returnWinningObject = null;
  149. didYouMean.returnFirstMatch = false;
  150. // Expose.
  151. // In node...
  152. if (typeof module !== 'undefined' && module.exports) {
  153. module.exports = didYouMean;
  154. }
  155. // Otherwise...
  156. else {
  157. window.didYouMean = didYouMean;
  158. }
  159. var MAX_INT = Math.pow(2,32) - 1; // We could probably go higher than this, but for practical reasons let's not.
  160. function getEditDistance(a, b, max) {
  161. // Handle null or undefined max.
  162. max = max || max === 0 ? max : MAX_INT;
  163. var lena = a.length;
  164. var lenb = b.length;
  165. // Fast path - no A or B.
  166. if (lena === 0) return Math.min(max + 1, lenb);
  167. if (lenb === 0) return Math.min(max + 1, lena);
  168. // Fast path - length diff larger than max.
  169. if (Math.abs(lena - lenb) > max) return max + 1;
  170. // Slow path.
  171. var matrix = [],
  172. i, j, colMin, minJ, maxJ;
  173. // Set up the first row ([0, 1, 2, 3, etc]).
  174. for (i = 0; i <= lenb; i++) { matrix[i] = [i]; }
  175. // Set up the first column (same).
  176. for (j = 0; j <= lena; j++) { matrix[0][j] = j; }
  177. // Loop over the rest of the columns.
  178. for (i = 1; i <= lenb; i++) {
  179. colMin = MAX_INT;
  180. minJ = 1;
  181. if (i > max) minJ = i - max;
  182. maxJ = lenb + 1;
  183. if (maxJ > max + i) maxJ = max + i;
  184. // Loop over the rest of the rows.
  185. for (j = 1; j <= lena; j++) {
  186. // If j is out of bounds, just put a large value in the slot.
  187. if (j < minJ || j > maxJ) {
  188. matrix[i][j] = max + 1;
  189. }
  190. // Otherwise do the normal Levenshtein thing.
  191. else {
  192. // If the characters are the same, there's no change in edit distance.
  193. if (b.charAt(i - 1) === a.charAt(j - 1)) {
  194. matrix[i][j] = matrix[i - 1][j - 1];
  195. }
  196. // Otherwise, see if we're substituting, inserting or deleting.
  197. else {
  198. matrix[i][j] = Math.min(matrix[i - 1][j - 1] + 1, // Substitute
  199. Math.min(matrix[i][j - 1] + 1, // Insert
  200. matrix[i - 1][j] + 1)); // Delete
  201. }
  202. }
  203. // Either way, update colMin.
  204. if (matrix[i][j] < colMin) colMin = matrix[i][j];
  205. }
  206. // If this column's minimum is greater than the allowed maximum, there's no point
  207. // in going on with life.
  208. if (colMin > max) return max + 1;
  209. }
  210. // If we made it this far without running into the max, then return the final matrix value.
  211. return matrix[lenb][lena];
  212. }
  213. })();