JavaScript Levenshtein Algorithm Implementation

One of the most known algorithms used by spell checkers and auto-complete fields is perhaps the Levenshtein algorithm, which basically minimizes the Levenshtein distance between the target word and the user input; or, in other words, the minimum number of missing characters and additions needed to transform a string into another from an existing dictionary.

The algorithm is amazing and works like a charm, however, you should carefully think how you are going to use it because it has a very high computational cost, and it is better to consider designing ideas before starting using it.

For many applications, the information to fulfill a dropdown control comes from a RESTFUL service, and it brings thousands of options from a database . In these cases, using the Levenshtein algorithm probably is not a good idea, because you will have to implement the algorithm in the data query (or, in the worst in the cases, in a stored procedure) to avoid bringing all the options and perform the algorithm in memory. Sounds good at first, but the user doesn’t want to wait for seconds on every keypress, so you need to think what is your best scenario to use it.

Here some ideas about what to consider for a fast selection logic:

• Number of choices: 1-50 -> the dropdown is enough
• Number of choices: >50 but < few thousands -> auto-complete is great, and good to apply Levenshtein algorithm ✅
• Number of choices: more than 10,000 items -> think in a kind of chain of dropdown controls to reduce the number of items by categories

In conclusion, using this algorithm depends on your scenario. For most of the times I needed it, I had to use it in the browser, so here is it in Javascript:

class LevenshteinModel {

    compute(first: string, second: string): number {
        if (first.length == 0)
            return second.length;

        if (second.length == 0)
            return first.length;

        let current = 1;
        let previous = 0;
        let r: number[][] = [[], []];

        for (let i = 0; i <= second.length; i++)
            r[previous][i] = i;

        for (let i = 0; i < first.length; i++) {
            r[current][0] = i + 1;

            for (let j = 1; j <= second.length; j++) {
                const cost = (second[j - 1] === first[i]) ? 0 : 1;
                r[current][j] = Math.min(
                    r[previous][j] + 1, 
                    r[current][j - 1] + 1, 
                    r[previous][j - 1] + cost);
            }

            previous = (previous + 1) % 2; 
            current = (current + 1) % 2;
        }

        const weight = r[previous][second.length];
        return weight;
    }
}

---

If you think this content was helpful, consider buy me a cup of coffee. 😉 ☕👉

Tags: javascriptlevenshtein