Function levenshtein

src/common/fuzzy-string-match.ts:2–27

Calculate the Levenshtein distance between two strings using a two-row optimization

(source: string, target: string)

/**
 * Optimal string alignment distance (restricted Damerau–Levenshtein: handles
 * substitution, insertion, deletion, and adjacent transposition). Bails out
 * early, returning `max + 1`, once the distance is known to exceed `max`.
 */
export function osaDistance(a: string, b: string, max: number): number {
  const la = a.length;
  const lb = b.length;
  if (Math.abs(la - lb) > max) return max + 1;
  if (la === 0) return lb;
  if (lb === 0) return la;

  let prevPrev = new Array<number>(lb + 1);
  let prev = new Array<number>(lb + 1);
  let curr = new Array<number>(lb + 1);
  for (let j = 0; j <= lb; j++) prev[j] = j;

  for (let i = 1; i <= la; i++) {
    curr[0] = i;
    let rowMin = curr[0];
    for (let j = 1; j <= lb; j++) {
      const cost = a[i - 1] === b[j - 1] ? 0 : 1;
      let v = Math.min(
        prev[j] + 1, // deletion
        curr[j - 1] + 1, // insertion
        prev[j - 1] + cost // substitution
      );
      if (i > 1 && j > 1 && a[i - 1] === b[j - 2] && a[i - 2] === b[j - 1])
        v = Math.min(v, prevPrev[j - 2] + 1); // transposition
      curr[j] = v;