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.
-
$!rootis the root node of the tree -
$!helperis 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. (Seet/01-basic.t. It implements an exmple forDOM::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 titsuki@cpan.org
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
- [0] Zhang, Kaizhong, and Dennis Shasha. "Simple fast algorithms for the editing distance between trees and related problems." SIAM journal on computing 18.6 (1989): 1245-1262.