cpan:TITSUKI

# 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"))\
)\
)\

my \$root2 = ::(\$ZN).new(:content("f"))\
)\
)\

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.

• `\$!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`.)

### 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