Levenshtein distance

levenshtein.js

// (c) 2018 Andrea Giammarchi
function levenshtein(from, to)
{
  const fromLength = from.length + 1;
  const toLength = to.length + 1;
  const size = fromLength * toLength;
  const grid = new Array(size);
  let x = 0;
  let y = 0;
  let X = 0;
  let Y = 0;
  let crow = 0;
  grid[0] = 0;
  while (++x < toLength)
    grid[x] = x;
  while (++y < fromLength)
  {
    X = x = 0;
    const prow = crow;
    crow = y * toLength;
    grid[crow + x] = y;
    while (++x < toLength)
    {
      const del = grid[prow + x] + 1;
      const ins = grid[crow + X] + 1;
      const sub = grid[prow + X] + (from[Y] === to[X] ? 0 : 1);
      grid[crow + x] = del < ins ?
                        (del < sub ?
                          del : sub) :
                        (ins < sub ?
                          ins : sub);
      ++X;
    }
    Y = y;
  }
  return grid[size - 1];
}