Public
Edited
Jun 15, 2023
Importers
6 stars
function* levenshtein(A, B) {
const a = A.length,
b = B.length,
M = Array.from({ length: b + 1 }).map(() =>
Array.from({ length: a + 1 }).map(() => "?")
),
path = Array.from({ length: b + 1 }).map(() =>
Array.from({ length: a + 1 }).map(() => "?")
);
for (let i = 0; i < b + 1; i++) {
M[i][0] = i;
path[i][0] = [i - 1, 0];
}
for (let j = 1; j < a + 1; j++) {
M[0][j] = j;
path[0][j] = [0, j - 1];
}
path[0][0] = [0, 0];
yield { M, path };
for (let j = 1; j < a + 1; j++) {
for (let i = 1; i < b + 1; i++) {
// Same letter in both words?
const c = substitution_cost(B[i - 1], A[j - 1]),
costs = [
M[i - 1][j] + 1, // delete
M[i][j - 1] + 1, // insert
M[i - 1][j - 1] + c // substitute for a cost
],
m = Math.min(...costs);
let pred = [i - 1, j - 1];
if (m === costs[0]) pred = [i - 1, j];
else if (m === costs[1]) pred = [i, j - 1];
M[i][j] = m;
path[i][j] = pred;
yield { M, path };
}
}
}
function levenshtein_path(A, B) {
const transition = [],
L = [...levenshtein(A, B)].pop(),
M = L.M,
path = L.path;
let i = B.length,
j = A.length;
let w = B;
transition.push(w);
while (i > 0 || j > 0) {
[i, j] = path[i][j];
let w0 = B.substring(0, i) + A.substring(j);
if (w0 !== w) {
w = w0;
transition.push(w);
}
}
return transition.reverse();
}
Purpose-built for displays of data
Observable is your go-to platform for exploring data and creating expressive data visualizations. Use reactive JavaScript notebooks for prototyping and a collaborative canvas for visual data exploration and dashboard creation.
