Skip to content

alg-js/zhangshasha

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

7 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

@alg/zhangshasha

JSR License

Tree edit distances using the Zhang-Shasha algorithm.

For generic string/sequence edit distances, see @alg/levenshtein.

Install

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

Example

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

About

Tree edit distances using the Zhang-Shasha algorithm

Topics

Resources

License

Stars

Watchers

Forks

Releases

No releases published