1/** 2 * Copyright (c) 2015-present, Facebook, Inc. 3 * 4 * This source code is licensed under the MIT license found in the 5 * LICENSE file in the root directory of this source tree. 6 * 7 * strict 8 */ 9 10/** 11 * Given an invalid input string and a list of valid options, returns a filtered 12 * list of valid options sorted based on their similarity with the input. 13 */ 14export default function suggestionList(input, options) { 15 var optionsByDistance = Object.create(null); 16 var oLength = options.length; 17 var inputThreshold = input.length / 2; 18 for (var i = 0; i < oLength; i++) { 19 var distance = lexicalDistance(input, options[i]); 20 var threshold = Math.max(inputThreshold, options[i].length / 2, 1); 21 if (distance <= threshold) { 22 optionsByDistance[options[i]] = distance; 23 } 24 } 25 return Object.keys(optionsByDistance).sort(function (a, b) { 26 return optionsByDistance[a] - optionsByDistance[b]; 27 }); 28} 29 30/** 31 * Computes the lexical distance between strings A and B. 32 * 33 * The "distance" between two strings is given by counting the minimum number 34 * of edits needed to transform string A into string B. An edit can be an 35 * insertion, deletion, or substitution of a single character, or a swap of two 36 * adjacent characters. 37 * 38 * Includes a custom alteration from Damerau-Levenshtein to treat case changes 39 * as a single edit which helps identify mis-cased values with an edit distance 40 * of 1. 41 * 42 * This distance can be useful for detecting typos in input or sorting 43 * 44 * @param {string} a 45 * @param {string} b 46 * @return {int} distance in number of edits 47 */ 48function lexicalDistance(aStr, bStr) { 49 if (aStr === bStr) { 50 return 0; 51 } 52 53 var i = void 0; 54 var j = void 0; 55 var d = []; 56 var a = aStr.toLowerCase(); 57 var b = bStr.toLowerCase(); 58 var aLength = a.length; 59 var bLength = b.length; 60 61 // Any case change counts as a single edit 62 if (a === b) { 63 return 1; 64 } 65 66 for (i = 0; i <= aLength; i++) { 67 d[i] = [i]; 68 } 69 70 for (j = 1; j <= bLength; j++) { 71 d[0][j] = j; 72 } 73 74 for (i = 1; i <= aLength; i++) { 75 for (j = 1; j <= bLength; j++) { 76 var cost = a[i - 1] === b[j - 1] ? 0 : 1; 77 78 d[i][j] = Math.min(d[i - 1][j] + 1, d[i][j - 1] + 1, d[i - 1][j - 1] + cost); 79 80 if (i > 1 && j > 1 && a[i - 1] === b[j - 2] && a[i - 2] === b[j - 1]) { 81 d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost); 82 } 83 } 84 } 85 86 return d[aLength][bLength]; 87}