You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
34 lines
1.0 KiB
34 lines
1.0 KiB
export function levenshtein(a, b) { |
|
if (a.length === 0) |
|
return b.length; |
|
if (b.length === 0) |
|
return a.length; |
|
const matrix = []; |
|
let i; |
|
for (i = 0; i <= b.length; i++) { |
|
matrix[i] = [i]; |
|
} |
|
let j; |
|
for (j = 0; j <= a.length; j++) { |
|
matrix[0][j] = j; |
|
} |
|
for (i = 1; i <= b.length; i++) { |
|
for (j = 1; j <= a.length; j++) { |
|
if (b.charAt(i - 1) === a.charAt(j - 1)) { |
|
matrix[i][j] = matrix[i - 1][j - 1]; |
|
} |
|
else { |
|
if (i > 1 && |
|
j > 1 && |
|
b.charAt(i - 2) === a.charAt(j - 1) && |
|
b.charAt(i - 1) === a.charAt(j - 2)) { |
|
matrix[i][j] = matrix[i - 2][j - 2] + 1; |
|
} |
|
else { |
|
matrix[i][j] = Math.min(matrix[i - 1][j - 1] + 1, Math.min(matrix[i][j - 1] + 1, matrix[i - 1][j] + 1)); |
|
} |
|
} |
|
} |
|
} |
|
return matrix[b.length][a.length]; |
|
}
|
|
|