Suggest Similar

1const maxDistance = 3;
2
3function editDistance(a, b) {
4  // https://en.wikipedia.org/wiki/Damerau–Levenshtein_distance
5  // Calculating optimal string alignment distance, no substring is edited more than once.
6  // (Simple implementation.)
7
8  // Quick early exit, return worst case.
9  if (Math.abs(a.length - b.length) > maxDistance)
10    return Math.max(a.length, b.length);
11
12  // distance between prefix substrings of a and b
13  const d = [];
14
15  // pure deletions turn a into empty string
16  for (let i = 0; i <= a.length; i++) {
17    d[i] = [i];
18  }
19  // pure insertions turn empty string into b
20  for (let j = 0; j <= b.length; j++) {
21    d[0][j] = j;
22  }
23
24  // fill matrix
25  for (let j = 1; j <= b.length; j++) {
26    for (let i = 1; i <= a.length; i++) {
27      let cost;
28      if (a[i - 1] === b[j - 1]) {
29        cost = 0;
30      } else {
31        cost = 1;
32      }
33      d[i][j] = Math.min(
34        d[i - 1][j] + 1, // deletion
35        d[i][j - 1] + 1, // insertion
36        d[i - 1][j - 1] + cost, // substitution
37      );
38      // transposition
39      if (i > 1 && j > 1 && a[i - 1] === b[j - 2] && a[i - 2] === b[j - 1]) {
40        d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + 1);
41      }
42    }
43  }
44
45  return d[a.length][b.length];
46}
47
48/**
49 * Find close matches, restricted to same number of edits.
50 *
51 * @param {string} word
52 * @param {string[]} candidates
53 * @returns {string}
54 */
55
56export function suggestSimilar(word, candidates) {
57  if (!candidates || candidates.length === 0) return '';
58  // remove possible duplicates
59  candidates = Array.from(new Set(candidates));
60
61  const searchingOptions = word.startsWith('--');
62  if (searchingOptions) {
63    word = word.slice(2);
64    candidates = candidates.map((candidate) => candidate.slice(2));
65  }
66
67  let similar = [];
68  let bestDistance = maxDistance;
69  const minSimilarity = 0.4;
70  candidates.forEach((candidate) => {
71    if (candidate.length <= 1) return; // no one character guesses
72
73    const distance = editDistance(word, candidate);
74    const length = Math.max(word.length, candidate.length);
75    const similarity = (length - distance) / length;
76    if (similarity > minSimilarity) {
77      if (distance < bestDistance) {
78        // better edit distance, throw away previous worse matches
79        bestDistance = distance;
80        similar = [candidate];
81      } else if (distance === bestDistance) {
82        similar.push(candidate);
83      }
84    }
85  });
86
87  similar.sort((a, b) => a.localeCompare(b));
88  if (searchingOptions) {
89    similar = similar.map((candidate) => `--${candidate}`);
90  }
91
92  if (similar.length > 1) {
93    return `\n(Did you mean one of ${similar.join(', ')}?)`;
94  }
95  if (similar.length === 1) {
96    return `\n(Did you mean ${similar[0]}?)`;
97  }
98  return '';
99}