EN
TypeScript - calculate Levenshtein distance between strings
0 points
In this short article, we would like to show simple TypeScript 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
0it means: compared objects are equal.
Quick solution:
xxxxxxxxxx1
const calculateLevenshteinDistance = (a: string, b: string): number => {2
const c = a.length + 1;3
const d = b.length + 1;4
const r = Array(c);5
for (let i = 0; i < c; ++i) r[i] = Array(d);6
for (let i = 0; i < c; ++i) r[i][0] = i;7
for (let j = 0; j < d; ++j) r[0][j] = j;8
for (let i = 1; i < c; ++i) {9
for (let j = 1; j < d; ++j) {10
const s = a[i - 1] === b[j - 1] ? 0 : 1;11
r[i][j] = Math.min(r[i - 1][j] + 1, r[i][j - 1] + 1, r[i - 1][j - 1] + s);12
}13
}14
return r[a.length][b.length];15
};16
17
18
// Usage example:19
20
console.log(calculateLevenshteinDistance('Chris', 'Chris')); // 021
console.log(calculateLevenshteinDistance('John1', 'John2')); // 122
console.log(calculateLevenshteinDistance('Google', 'Gogle')); // 123
console.log(calculateLevenshteinDistance('Ann', 'Matt' )); // 424
25
console.log(calculateLevenshteinDistance('CHRIS', 'Chris')); // 4
In this section, you can find some solution that is at the beginning of this article but with more clear variable names.
xxxxxxxxxx1
const calculateLevenshteinDistance = (a: string, b: string): number => {2
const aLimit = a.length + 1;3
const bLimit = b.length + 1;4
const distance = Array(aLimit);5
for (let i = 0; i < aLimit; ++i) {6
distance[i] = Array(bLimit);7
}8
for (let i = 0; i < aLimit; ++i) {9
distance[i][0] = i;10
}11
for (let j = 0; j < bLimit; ++j) {12
distance[0][j] = j;13
}14
for (let i = 1; i < aLimit; ++i) {15
for (let j = 1; j < bLimit; ++j) {16
const substitutionCost = a[i - 1] === b[j - 1] ? 0 : 1;17
distance[i][j] = Math.min(18
distance[i - 1][j] + 1,19
distance[i][j - 1] + 1,20
distance[i - 1][j - 1] + substitutionCost21
);22
}23
}24
return distance[a.length][b.length];25
};26
27
28
// Usage example:29
30
console.log(calculateLevenshteinDistance('Chris', 'Chris')); // 031
console.log(calculateLevenshteinDistance('John1', 'John2')); // 132
console.log(calculateLevenshteinDistance('Google', 'Gogle')); // 133
console.log(calculateLevenshteinDistance('Ann', 'Matt' )); // 434
35
console.log(calculateLevenshteinDistance('CHRIS', 'Chris')); // 4
It is necessary to wrap the existing algorithm with toLowerCase() or toUpperCase() string transformation.
xxxxxxxxxx1
const calculateLevenshteinDistance = (a: string, b: string): number => {2
const aLimit = a.length + 1;3
const bLimit = b.length + 1;4
const distance = Array(aLimit);5
for (let i = 0; i < aLimit; ++i) {6
distance[i] = Array(bLimit);7
}8
for (let i = 0; i < aLimit; ++i) {9
distance[i][0] = i;10
}11
for (let j = 0; j < bLimit; ++j) {12
distance[0][j] = j;13
}14
for (let i = 1; i < aLimit; ++i) {15
for (let j = 1; j < bLimit; ++j) {16
const substitutionCost = a[i - 1] === b[j - 1] ? 0 : 1;17
distance[i][j] = Math.min(18
distance[i - 1][j] + 1,19
distance[i][j - 1] + 1,20
distance[i - 1][j - 1] + substitutionCost21
);22
}23
}24
return distance[a.length][b.length];25
};26
27
const calculateImprovedLevenshteinDistance = (a: string, b: string): number => {28
return calculateLevenshteinDistance(a.toLowerCase(), b.toLowerCase());29
};30
31
32
// Usage example:33
34
console.log(calculateImprovedLevenshteinDistance('CHRIS', 'Chris')); // 035
console.log(calculateImprovedLevenshteinDistance('JOHN1', 'John2')); // 136
console.log(calculateImprovedLevenshteinDistance('GOOGLE', 'Gogle')); // 137
console.log(calculateImprovedLevenshteinDistance('ANN', 'Matt' )); // 338
