Package jazzparser :: Package misc :: Package tree :: Module lces

Module lces

Largest Common Embeddable Subtree.

Implementation of the algorithm from On the Maximum Common Embedded Subtree Problem for Ordered Trees by Loxano and Valiente. This is for unlabeled, ordered trees.

Author: Mark Granroth-Wilding <mark.granroth-wilding@ed.ac.uk>

Functions

[hide private]

lces_size(tree1, tree2)
Computes the size of the largest common embedded subtree for two unlabeled trees.

source code

lces(tree1, tree2)
Computes the largest common embedded subtree for two unlabeled trees.

source code

Variables

[hide private]

__package__ = 'jazzparser.misc.tree'

Function Details

[hide private]

lces_size(tree1, tree2)

source code

Computes the size of the largest common embedded subtree for two unlabeled trees. It is quicker to compute the size than to compute the common tree itself, so this function doesn't actually compute what the tree is.

lces(tree1, tree2)

source code

Computes the largest common embedded subtree for two unlabeled trees. Even you only need to know the size, use lces_size, since it's a slightly simpler problem.