Levenshtein Distance

levenshtein-distance.js

function levenshteinDistance(a, b) {
  // special cases
  if (a === b) { return 0; }
  if (a === '') { return b.length; }
  if (b === '') { return a.length; }
  // determine longer string
  let short = (a.length <= b.length) ? a : b;
  let long = (a.length <= b.length) ? b : a;
  // init vectors
  let vector1 = [];
  let vector2 = [];
  vector2.length = long.length + 1;
  for (let i = 0, max = long.length; i <= max; i++) { vector1.push(i); } // prefill vector1
  for (let i = 0, iMax = short.length; i < iMax; i++) {
    // vector2 - current distance from previous row
    vector2[0] = i + 1;
    for (let j = 0, jMax = long.length; j < jMax; j++) {
      const increment = (short[i] === long[j]) ? 0 : 1;
      vector2[j + 1] = Math.min(vector2[j] + 1, vector1[j + 1] + 1, vector1[j] + increment);
    }
    // copy vector2 to vector1 for next iteration
    vector2.forEach((item, index) => vector1[index] = item);
  }
  return vector2[long.length]; // return last element of vector2
}

LevenshteinDistance.markdown

Levenshtein Distance

Levenshtein distance algorythm realization. Function levenshteinDistance() calculates distance between two arbitrary strings provided as function parameters a and b.

A script by V.

License.