suggestionList.mjs 3.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131
  1. import naturalCompare from "./naturalCompare.mjs";
  2. /**
  3. * Given an invalid input string and a list of valid options, returns a filtered
  4. * list of valid options sorted based on their similarity with the input.
  5. */
  6. export default function suggestionList(input, options) {
  7. var optionsByDistance = Object.create(null);
  8. var lexicalDistance = new LexicalDistance(input);
  9. var threshold = Math.floor(input.length * 0.4) + 1;
  10. for (var _i2 = 0; _i2 < options.length; _i2++) {
  11. var option = options[_i2];
  12. var distance = lexicalDistance.measure(option, threshold);
  13. if (distance !== undefined) {
  14. optionsByDistance[option] = distance;
  15. }
  16. }
  17. return Object.keys(optionsByDistance).sort(function (a, b) {
  18. var distanceDiff = optionsByDistance[a] - optionsByDistance[b];
  19. return distanceDiff !== 0 ? distanceDiff : naturalCompare(a, b);
  20. });
  21. }
  22. /**
  23. * Computes the lexical distance between strings A and B.
  24. *
  25. * The "distance" between two strings is given by counting the minimum number
  26. * of edits needed to transform string A into string B. An edit can be an
  27. * insertion, deletion, or substitution of a single character, or a swap of two
  28. * adjacent characters.
  29. *
  30. * Includes a custom alteration from Damerau-Levenshtein to treat case changes
  31. * as a single edit which helps identify mis-cased values with an edit distance
  32. * of 1.
  33. *
  34. * This distance can be useful for detecting typos in input or sorting
  35. */
  36. var LexicalDistance = /*#__PURE__*/function () {
  37. function LexicalDistance(input) {
  38. this._input = input;
  39. this._inputLowerCase = input.toLowerCase();
  40. this._inputArray = stringToArray(this._inputLowerCase);
  41. this._rows = [new Array(input.length + 1).fill(0), new Array(input.length + 1).fill(0), new Array(input.length + 1).fill(0)];
  42. }
  43. var _proto = LexicalDistance.prototype;
  44. _proto.measure = function measure(option, threshold) {
  45. if (this._input === option) {
  46. return 0;
  47. }
  48. var optionLowerCase = option.toLowerCase(); // Any case change counts as a single edit
  49. if (this._inputLowerCase === optionLowerCase) {
  50. return 1;
  51. }
  52. var a = stringToArray(optionLowerCase);
  53. var b = this._inputArray;
  54. if (a.length < b.length) {
  55. var tmp = a;
  56. a = b;
  57. b = tmp;
  58. }
  59. var aLength = a.length;
  60. var bLength = b.length;
  61. if (aLength - bLength > threshold) {
  62. return undefined;
  63. }
  64. var rows = this._rows;
  65. for (var j = 0; j <= bLength; j++) {
  66. rows[0][j] = j;
  67. }
  68. for (var i = 1; i <= aLength; i++) {
  69. var upRow = rows[(i - 1) % 3];
  70. var currentRow = rows[i % 3];
  71. var smallestCell = currentRow[0] = i;
  72. for (var _j = 1; _j <= bLength; _j++) {
  73. var cost = a[i - 1] === b[_j - 1] ? 0 : 1;
  74. var currentCell = Math.min(upRow[_j] + 1, // delete
  75. currentRow[_j - 1] + 1, // insert
  76. upRow[_j - 1] + cost // substitute
  77. );
  78. if (i > 1 && _j > 1 && a[i - 1] === b[_j - 2] && a[i - 2] === b[_j - 1]) {
  79. // transposition
  80. var doubleDiagonalCell = rows[(i - 2) % 3][_j - 2];
  81. currentCell = Math.min(currentCell, doubleDiagonalCell + 1);
  82. }
  83. if (currentCell < smallestCell) {
  84. smallestCell = currentCell;
  85. }
  86. currentRow[_j] = currentCell;
  87. } // Early exit, since distance can't go smaller than smallest element of the previous row.
  88. if (smallestCell > threshold) {
  89. return undefined;
  90. }
  91. }
  92. var distance = rows[aLength % 3][bLength];
  93. return distance <= threshold ? distance : undefined;
  94. };
  95. return LexicalDistance;
  96. }();
  97. function stringToArray(str) {
  98. var strLength = str.length;
  99. var array = new Array(strLength);
  100. for (var i = 0; i < strLength; ++i) {
  101. array[i] = str.charCodeAt(i);
  102. }
  103. return array;
  104. }