levenshtein.algo

levenshtein.md

Javascript implementation of levenshtein distance.

function levenshtein(a,b) {
  var matrix = [];
  var cost = 0;
 
  // cols 1,2,...,n-1,n
  for(var i = 0; i <= b.length; i++) {
    matrix[i] = [i];
  }
 
  // rows 1,2,...,n-1,n
  for(var j = 0; j <= a.length; j++) {
    matrix[0][j] = j;
  }
 
  for(var i = 1; i <= b.length; i++) {
    for(var j = 1; j <= a.length; j++) {
      if(a.charAt(j-1) === b.charAt(i-1)) {
        cost = 0;
      } else {
        cost = 1;
      }
      matrix[i][j] = Math.min(
        matrix[i-1][j] + 1, // deletion
        matrix[i][j-1] + 1, // insertion
        matrix[i-1][j-1] + cost // substitution
      );
    }
  }
 
  return matrix[b.length][a.length];
}

console.log(levenshtein("niche", "chiens")); // 5