Raku Land

Algorithm::ZhangShasha

cpan:TITSUKI

Build Status

NAME

Algorithm::ZhangShasha - Tree edit distance between trees

SYNOPSIS

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})

DESCRIPTION

Algorithm::ZhangShasha is an implementation for efficiently computing tree edit distance between trees.

METHODS of Algorithm::ZhangShasha::Tree

BUILD

Defined as:

submethod BUILD(NodeT :$!root!, Algorithm::ZhangShasha::Helpable :$!helper!)

Creates an Algorithm::ZhangShasha::Tree instance.

size

Defined as:

method size(--> Int)

Returns the size of the tree.

tree-distance

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.

AUTHOR

Itsuki Toyota titsuki@cpan.org

COPYRIGHT AND LICENSE

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