distance algorithms

by bradleytrager

JavaScript

function dice_coefficient(string1, string2) {
    var intersection = 0;
    var length1 = string1.length - 1;
    var length2 = string2.length - 1;
    if (length1 < 1 || length2 < 1) return 0;
    var bigrams2 = [];
    for (var i = 0; i < length2; i++) {
        bigrams2.push(string2.substr(i, 2));
    }
    for (var i = 0; i < length1; i++) {
        var bigram1 = string1.substr(i, 2);
        for (var j = 0; j < length2; j++) {
            if (bigram1 == bigrams2[j]) {
                intersection++;
                bigrams2[j] = null;
                break;
            }
        }
    }
    return (2.0 * intersection) / (length1 + length2);
}

// function levenshteinDistance(s, t) {
// 	if (s.length === 0) return t.length;
// 	if (t.length === 0) return s.length;

// 	return Math.min(
// 		levenshteinDistance(s.substr(1), t) + 1,
// 		levenshteinDistance(t.substr(1), s) + 1,
// 		levenshteinDistance(s.substr(1), t.substr(1)) + (s[0] !== t[0] ? 1 : 0)
// 	);
// }

// Compute the edit distance between the two given strings
function getEditDistance(a, b) {
    if (a.length === 0) return b.length;
    if (b.length === 0) return a.length;

    var matrix = [];

    // increment along the first column of each row
    var i;
    for (i = 0; i <= b.length; i++) {
        matrix[i] = [i];
    }

    // increment each column in the first row
    var j;
    for (j = 0; j <= a.length; j++) {
        matrix[0][j] = j;
    }

    // Fill in the rest of the matrix
    for (i = 1; i <= b.length; i++) {
        for (j = 1; j <= a.length; j++) {
            if (b.charAt(i - 1) == a.charAt(j - 1)) {
                matrix[i][j] = matrix[i - 1][j - 1];
            } else {
                matrix[i][j] = Math.min(matrix[i - 1][j - 1] + 1, // substitution
                Math.min(matrix[i][j - 1] + 1, // insertion
                matrix[i - 1][j] + 1)); // deletion
            }
        }
    }

    return matrix[b.length][a.length];
};

var s1 = '';
var s2 =...