1 | const maxDistance = 3;
|
2 |
|
3 | function editDistance(a, b) {
|
4 |
|
5 |
|
6 |
|
7 |
|
8 |
|
9 | if (Math.abs(a.length - b.length) > maxDistance) return Math.max(a.length, b.length);
|
10 |
|
11 |
|
12 | const d = [];
|
13 |
|
14 |
|
15 | for (let i = 0; i <= a.length; i++) {
|
16 | d[i] = [i];
|
17 | }
|
18 |
|
19 | for (let j = 0; j <= b.length; j++) {
|
20 | d[0][j] = j;
|
21 | }
|
22 |
|
23 |
|
24 | for (let j = 1; j <= b.length; j++) {
|
25 | for (let i = 1; i <= a.length; i++) {
|
26 | let cost = 1;
|
27 | if (a[i - 1] === b[j - 1]) {
|
28 | cost = 0;
|
29 | } else {
|
30 | cost = 1;
|
31 | }
|
32 | d[i][j] = Math.min(
|
33 | d[i - 1][j] + 1,
|
34 | d[i][j - 1] + 1,
|
35 | d[i - 1][j - 1] + cost
|
36 | );
|
37 |
|
38 | if (i > 1 && j > 1 && a[i - 1] === b[j - 2] && a[i - 2] === b[j - 1]) {
|
39 | d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + 1);
|
40 | }
|
41 | }
|
42 | }
|
43 |
|
44 | return d[a.length][b.length];
|
45 | }
|
46 |
|
47 |
|
48 |
|
49 |
|
50 |
|
51 |
|
52 |
|
53 |
|
54 |
|
55 | function suggestSimilar(word, candidates) {
|
56 | if (!candidates || candidates.length === 0) return '';
|
57 |
|
58 | candidates = Array.from(new Set(candidates));
|
59 |
|
60 | const searchingOptions = word.startsWith('--');
|
61 | if (searchingOptions) {
|
62 | word = word.slice(2);
|
63 | candidates = candidates.map(candidate => candidate.slice(2));
|
64 | }
|
65 |
|
66 | let similar = [];
|
67 | let bestDistance = maxDistance;
|
68 | const minSimilarity = 0.4;
|
69 | candidates.forEach((candidate) => {
|
70 | if (candidate.length <= 1) return;
|
71 |
|
72 | const distance = editDistance(word, candidate);
|
73 | const length = Math.max(word.length, candidate.length);
|
74 | const similarity = (length - distance) / length;
|
75 | if (similarity > minSimilarity) {
|
76 | if (distance < bestDistance) {
|
77 |
|
78 | bestDistance = distance;
|
79 | similar = [candidate];
|
80 | } else if (distance === bestDistance) {
|
81 | similar.push(candidate);
|
82 | }
|
83 | }
|
84 | });
|
85 |
|
86 | similar.sort((a, b) => a.localeCompare(b));
|
87 | if (searchingOptions) {
|
88 | similar = similar.map(candidate => `--${candidate}`);
|
89 | }
|
90 |
|
91 | if (similar.length > 1) {
|
92 | return `\n(Did you mean one of ${similar.join(', ')}?)`;
|
93 | }
|
94 | if (similar.length === 1) {
|
95 | return `\n(Did you mean ${similar[0]}?)`;
|
96 | }
|
97 | return '';
|
98 | }
|
99 |
|
100 | exports.suggestSimilar = suggestSimilar;
|