Tree edit distances using the Zhang-Shasha algorithm.
For generic string/sequence edit distances, see @alg/levenshtein.
deno add jsr:@alg/zhangshasha
Other Install Options
npx jsr add @alg/zhangshasha
bunx jsr add @alg/zhangshasha
pnpm i jsr:@alg/zhangshasha
yarn add jsr:@alg/zhangshasha
vlt install jsr:@alg/zhangshasha
Trees must be objects of the form Tree<T> = {root: T, cildren: Tree<T>[]}
. A
helper function, t(root, ...children)
, constructs trees from root node values.
import {distance, t} from "@alg/zhangshasha";
const tree1 = t(
"d",
t("b", t("a"), t("c")),
t("f", t("e"), t("g")),
);
const tree2 = t(
"f",
t("e", t("x")),
t("g"),
);
// Delete d, b, a, c; Insert x
const dist1 = distance(tree1, tree2, {
relabel: (e1, e2) => e1 === e2 ? 0 : 2,
insertion: () => 3,
deletion: () => 3,
});
console.log(dist1); // 15
// Delete c, e, g; Relabel f -> g, d -> f, b -> e, a -> x
const dist2 = distance(tree1, tree2, {
relabel: () => 2,
insertion: () => 3,
deletion: () => 3,
});
console.log(dist2); // 17