Brunobkr/llama.cpp_AlgMor24_github

1const maxDistance = 3;2 3function editDistance(a, b) {4  // https://en.wikipedia.org/wiki/Damerau–Levenshtein_distance5  // 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) return Math.max(a.length, b.length);10 11  // distance between prefix substrings of a and b12  const d = [];13 14  // pure deletions turn a into empty string15  for (let i = 0; i <= a.length; i++) {16    d[i] = [i];17  }18  // pure insertions turn empty string into b19  for (let j = 0; j <= b.length; j++) {20    d[0][j] = j;21  }22 23  // fill matrix24  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, // deletion34        d[i][j - 1] + 1, // insertion35        d[i - 1][j - 1] + cost // substitution36      );37      // transposition38      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 * Find close matches, restricted to same number of edits.49 *50 * @param {string} word51 * @param {string[]} candidates52 * @returns {string}53 */54 55function suggestSimilar(word, candidates) {56  if (!candidates || candidates.length === 0) return '';57  // remove possible duplicates58  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; // no one character guesses71 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        // better edit distance, throw away previous worse matches78        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 100exports.suggestSimilar = suggestSimilar;101