Help language development. Donate to The Perl Foundation

Algorithm::ZhangShasha cpan:TITSUKI last updated on 2020-05-04

Algorithm-ZhangShasha-0.0.3/

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 [email protected]

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