url-distance.js

/**
 * Levenshtein distance between two arrays or strings
 */
function arrDistance(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
    for(var i = 0; i <= b.length; i++){
        matrix[i] = [i];
    }

    // increment each column in the first row
    for(var 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[i-1] === a[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];
}

/**
 * Distance between two dictionaries.
 * Note: modifies dicts in-place
 */
function dictDistance(a, b){
    var distance = 0;
    for(var k of Object.keys(a)) {
        if (!(k in b) || b[k] !== a[k]) {
            distance++;
        }
        delete b[k];
    }
    return distance + Object.keys(b).length;
}

/**
 * Calculates the distance between two urls, taking into account
 * the URL's syntax.
 */
function urlDistance(url1, url2) {
    url1 = new URI(url1);
    url2 = new URI(url2);

    return arrDistance(url1.segment(), url2.segment()) +
        2*arrDistance(url1.domain().split('.'), url2.domain().split('.')) +
        dictDistance(url1.search(true), url2.search(true)) +
        (url1.fragment() === url2.fragment() ? 0 : 1);
}