26
// Compute the edit distance between the two given strings
27
export function levenshtein(a: string, b: string) {
29
>
if (b.length === 0) return a.length;
30
>
31
>
const matrix = [];
32
>
33
>
// increment along the first column of each row
34
>
let i;
35
>
for (i = 0; i <= b.length; i++) {
36
>
matrix[i] = [i];
37
>
}
38
>
39
>
// increment each column in the first row
40
>
let j;
41
>
for (j = 0; j <= a.length; j++) {
42
>
matrix[0][j] = j;
43
>
}
44
>
45
>
// Fill in the rest of the matrix
46
>
for (i = 1; i <= b.length; i++) {
47
>
for (j = 1; j <= a.length; j++) {
48
>
if (b.charAt(i - 1) === a.charAt(j - 1)) {
49
>
matrix[i][j] = matrix[i - 1][j - 1];
50
>
} else {
51
>
if (
52
>
i > 1 &&
53
>
j > 1 &&
54
>
b.charAt(i - 2) === a.charAt(j - 1) &&
55
>
b.charAt(i - 1) === a.charAt(j - 2)
56
>
) {
57
matrix[i][j] = matrix[i - 2][j - 2] + 1; // transposition
59
>
matrix[i][j] = Math.min(
60
>
matrix[i - 1][j - 1] + 1, // substitution
61
>
Math.min(
62
>
matrix[i][j - 1] + 1, // insertion
63
>
matrix[i - 1][j] + 1
64
>
)
65
>
); // deletion
66
>
}
67
>
}
68
>
}
69
>
}
70
>
71
>
return matrix[b.length][a.length];
72
>
}