EN
JavaScript - calculate Levenshtein distance between strings
20 points
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.
Quick solution:
xxxxxxxxxx
1
const calculateLevenshteinDistance = (a, b) => {
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')); // 0
21
console.log(calculateLevenshteinDistance('John1', 'John2')); // 1
22
console.log(calculateLevenshteinDistance('Google', 'Gogle')); // 1
23
console.log(calculateLevenshteinDistance('Ann', 'Matt' )); // 4
24
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.
xxxxxxxxxx
1
const calculateLevenshteinDistance = (a, b) => {
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] + substitutionCost
21
);
22
}
23
}
24
return distance[a.length][b.length];
25
};
26
27
28
// Usage example:
29
30
console.log(calculateLevenshteinDistance('Chris', 'Chris')); // 0
31
console.log(calculateLevenshteinDistance('John1', 'John2')); // 1
32
console.log(calculateLevenshteinDistance('Google', 'Gogle')); // 1
33
console.log(calculateLevenshteinDistance('Ann', 'Matt' )); // 4
34
35
console.log(calculateLevenshteinDistance('CHRIS', 'Chris')); // 4
It is necessary to wrap the existing algorithm with toLowerCase()
or toUpperCase()
string transformation.
xxxxxxxxxx
1
const calculateLevenshteinDistance = (a, b) => {
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] + substitutionCost
21
);
22
}
23
}
24
return distance[a.length][b.length];
25
};
26
27
const calculateImprovedLevenshteinDistance = (a, b) => {
28
return calculateLevenshteinDistance (a.toLowerCase(), b.toLowerCase());
29
};
30
31
32
// Usage example:
33
34
console.log(calculateImprovedLevenshteinDistance('CHRIS', 'Chris')); // 0
35
console.log(calculateImprovedLevenshteinDistance('JOHN1', 'John2')); // 1
36
console.log(calculateImprovedLevenshteinDistance('GOOGLE', 'Gogle')); // 1
37
console.log(calculateImprovedLevenshteinDistance('ANN', 'Matt' )); // 3