Useful Algorithms

LevenshteinDistance.js

function levenshteinDistance(strA, strB) {
  // Function to calculate levenshtein distance of two string
  // Algorithm description: http://en.wikipedia.org/wiki/Levenshtein_distance

  if (strA == strB) { return 0; }
  if (!strA || !strB) { return strA.length || strB.length; }

  var distance = [], lenA = strA.length, lenB = strB.length;

  for (var i=0; i <= lenA; i++) { distance[i] = [i]; }

  for (var j=0; j <= lenB; j++) { distance[0][j] = j;}

  for (i=1; i <= lenA; i++) {
    for (j=1; j <= lenB; j++) {
      distance[i][j] = Math.min(distance[i-1][j] + 1,
                                distance[i][j-1] + 1,
                                distance[i-1][j-1] + (strA.charAt(i-1) === strB.charAt(j-1) ? 0 : 1));
    }
  }
  return distance[lenA][lenB];
}

function strSimilarity(strA, strB) {
  // Function to calculate similar percent use levenshtein distance

  var str1 = strA || '',
      str2 = strB || '',
      maxLen = str1.length > str2.length ? str1.length : str2.length,
      distance = levenshteinDistance(str1, str2);

  return !distance ? 1 : ((maxLen - distance) / maxLen);
}