Help language development. Donate to The Perl Foundation
Algorithm::ZhangShasha - Tree edit distance between trees
use Algorithm::ZhangShasha; my class SimpleHelper does Algorithm::ZhangShasha::Helpable[Algorithm::ZhangShasha::Node] { method delete-cost(Algorithm::ZhangShasha::Node $this --> Int) { 1; } method insert-cost(Algorithm::ZhangShasha::Node $another --> Int) { 1; } method replace-cost(Algorithm::ZhangShasha::Node $this, Algorithm::ZhangShasha::Node $another --> Int) { $another.content eq $this.content ?? 0 !! 1; } method children(Algorithm::ZhangShasha::Node $node) { $node.children } } my constant $ZN = 'Algorithm::ZhangShasha::Node'; my $root1 = ::($ZN).new(:content("f"))\ .add-child(::($ZN).new(:content("d"))\ .add-child(::($ZN).new(:content("a")))\ .add-child(::($ZN).new(:content("c"))\ .add-child(::($ZN).new(:content("b")))\ )\ )\ .add-child(::($ZN).new(:content("e"))); my $root2 = ::($ZN).new(:content("f"))\ .add-child(::($ZN).new(:content("c"))\ .add-child(::($ZN).new(:content("d"))\ .add-child(::($ZN).new(:content("a")))\ .add-child(::($ZN).new(:content("b")))\ )\ )\ .add-child(::($ZN).new(:content("e"))); my Algorithm::ZhangShasha::Tree[Algorithm::ZhangShasha::Node] $tree1 .= new(:root($root1), :helper(SimpleHelper.new)); my Algorithm::ZhangShasha::Tree[Algorithm::ZhangShasha::Node] $tree2 .= new(:root($root2), :helper(SimpleHelper.new)); say $tree1.tree-distance($tree2).key; # 2 say $tree1.tree-distance($tree2).value; # ({op => KEEP, pair => 1 => 1} {op => KEEP, pair => 2 => 2} {op => DELETE, pair => 3 => 2} {op => KEEP, pair => 4 => 3} {op => INSERT, pair => 4 => 4} {op => KEEP, pair => 5 => 5} {op => KEEP, pair => 6 => 6})
Algorithm::ZhangShasha is an implementation for efficiently computing tree edit distance between trees.
Defined as:
submethod BUILD(NodeT :$!root!, Algorithm::ZhangShasha::Helpable :$!helper!)
Creates an Algorithm::ZhangShasha::Tree
instance.
$!root
is the root node of the tree
$!helper
is the helper class that implements four methods: delete-cost
, insert-cost
, replace-cost
, children
. If you want to combine 3rd-party node representation (e.g., DOM::Tiny
), you should define a custom helper. (See t/01-basic.t
. It implements an exmple for DOM::Tiny
.)
Defined as:
method size(--> Int)
Returns the size of the tree.
Defined as:
method tree-distance(Algorithm::ZhangShasha::Tree $another --> Pair)
Returns a Pair
instance that has the optimal edit distance and the corresponding operations (e.g., DELETE(3,2)) between the two trees. Where .key
has the distance and .value
has the operations.
Itsuki Toyota [email protected]
Copyright 2020 Itsuki Toyota
This library is free software; you can redistribute it and/or modify it under the Artistic License 2.0.
This algorithm is from