Languages
[Edit]
EN

JavaScript - calculate Levenshtein distance between strings

20 points
Created by:
mkrieger1
516

In this short article, we would like to show simple JavaScript implementation for the Levenstein distance algorithm.

Levenstein distance algorithm is used to measure the difference between two sequences (e.g. between two strings).

When the algorithm returns 0 it means: compared objects are equal.

Simple implementation:

// ONLINE-RUNNER:browser;

const calculateLevenshteinDistance = (a, b) => {
  	const aLimit = a.length + 1;
  	const bLimit = b.length + 1;
  	const distance = Array(aLimit);
  	for (let i = 0; i < aLimit; ++i) {
      	distance[i] = Array(bLimit);
    }
    for (let i = 0; i < aLimit; ++i) {
      	distance[i][0] = i;
    }
    for (let j = 0; j < bLimit; ++j) {
      	distance[0][j] = j;
    }
    for (let i = 1; i < aLimit; ++i) {
        for (let j = 1; j <  bLimit; ++j) {
            const substitutionCost = (a[i - 1] === b[j - 1] ? 0 : 1);
          	distance[i][j] = Math.min(
                distance[i - 1][j] + 1,
                distance[i][j - 1] + 1,
                distance[i - 1][j - 1] + substitutionCost
            );
        }
    }
  	return distance[a.length][b.length];
};


// Usage example:

console.log(calculateLevenshteinDistance('Chris',  'Chris'));  // 0
console.log(calculateLevenshteinDistance('John1',  'John2'));  // 1
console.log(calculateLevenshteinDistance('Google', 'Gogle'));  // 1
console.log(calculateLevenshteinDistance('Ann',    'Matt' ));  // 4

console.log(calculateLevenshteinDistance('CHRIS',  'Chris'));  // 4

 

Levenstein distance algorithm with case-insensitive

It is necessary to wrap the existing algorithm with toLowerCase() or toUpperCase() string transformation.

// ONLINE-RUNNER:browser;

const calculateLevenshteinDistance = (a, b) => {
  	const aLimit = a.length + 1;
  	const bLimit = b.length + 1;
  	const distance = Array(aLimit);
  	for (let i = 0; i < aLimit; ++i) {
      	distance[i] = Array(bLimit);
    }
    for (let i = 0; i < aLimit; ++i) {
      	distance[i][0] = i;
    }
    for (let j = 0; j < bLimit; ++j) {
      	distance[0][j] = j;
    }
    for (let i = 1; i < aLimit; ++i) {
        for (let j = 1; j <  bLimit; ++j) {
            const substitutionCost = (a[i - 1] === b[j - 1] ? 0 : 1);
          	distance[i][j] = Math.min(
                distance[i - 1][j] + 1,
                distance[i][j - 1] + 1,
                distance[i - 1][j - 1] + substitutionCost
            );
        }
    }
  	return distance[a.length][b.length];
};

const calculateImprovedLevenshteinDistance = (a, b) => {
    return calculateLevenshteinDistance (a.toLowerCase(), b.toLowerCase());
};


// Usage example:

console.log(calculateImprovedLevenshteinDistance('CHRIS',  'Chris'));  // 0
console.log(calculateImprovedLevenshteinDistance('JOHN1',  'John2'));  // 1
console.log(calculateImprovedLevenshteinDistance('GOOGLE', 'Gogle'));  // 1
console.log(calculateImprovedLevenshteinDistance('ANN',    'Matt' ));  // 3

See also

  1. JavaScript - check words similarity (fuzzy compare with bigrams)

  2. JavaScript - soundex algorithm implementation

References

  1. Levenshtein distance - Wikipedia

JavaScript - string metrics algorithms

Native Advertising
🚀
Get your tech brand or product in front of software developers.
For more information Contact us
Dirask - we help you to
solve coding problems.
Ask question.

❤️💻 🙂

Join