levenshtein distance algorithm

levenshtein-distance-algorithm.js

/**
 * 
 * Levenshtein Distance Algorithm
 * Source: https://en.wikipedia.org/wiki/Levenshtein_distance
 *  
 */

function getThreshold(word) {
    if (word.length < 5) return 3;
    return 5;
}



function levenshtein(a, b) {

    if (a.length == 0) {
        return b.length;
    }
    if (b.length == 0) {
        return a.length;
    }

    const matrix = [];

    for (let i = 0; i <= b.length; i++) {
        matrix[i] = [i];
    }

    for (let j = 0; j <= a.length; j++) {
        matrix[0][j] = j;
    }

    for (let i = 1; i <= b.length; i++) {
        for (let 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,
                    matrix[i][j - 1] + 1,
                    matrix[i - 1][j - 1] + 1,
                );
            }
        }
    }

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


function sortByDistances(word, dictionary) {

    const dictDistance = {};
    dictionary.sort((a, b) => {
        if (!(a in dictDistance)) {
            dictDistance[a] = levenshtein(a, word);
        }
        if (!(b in dictDistance)) {
            dictDistance[b] = levenshtein(b, word);
        }

        return dictDistance[a] - dictDistance[b];
    });


    return dictionary;

}


function getLevenshtein(word, dict) {
    const threshold = getThreshold(word);
    let list = Object.values(dict)
        .filter(wd => Math.abs(wd.length - word.length) < threshold);

    if (!list.length) return null;

    list = sortByDistances(word, list);

    return list[0];
}



const dict = {
    home: 'home',
    about: 'about',
    contact: 'contact',
    clone: 'clone',
    push: 'push',
    pull: 'pull'
}


let word = process.argv[2] || 'hame' || 'cone';


let closestWord = getLevenshtein(word, dict);


console.log(`Do you mean (${closestWord})?`);