APTED Algorithm for Tree Edit Distance

Common errors

• AttributeError: module 'apted' has no attribute 'StartJVM'

  cause Attempting to use a `StartJVM()` function that exists in Java-dependent APTED implementations but not in the pure Python `apted` library.
  fix Remove any `import jpype` or calls to `apted.StartJVM()`. The Python `apted` library does not require a JVM.

• apted.parser.errors.ParseError: Unexpected character 'X' at position Y

  cause The input tree string does not conform to the expected bracket notation. Common issues include unescaped curly braces within labels, unmatched braces, or incorrect nesting.
  fix Carefully review your tree string for correct bracket notation syntax. Ensure all labels are properly enclosed (or not) and all braces are matched. If you have labels containing '{' or '}', they must be escaped as '\{' or '\}'.

• TypeError: __init__() missing 1 required positional argument: 'config'

  cause The `APTED` constructor requires a `config` object (even if it's the default unit cost configuration). You might have forgotten to pass it or tried to initialize `APTED` with only the trees.
  fix Pass a configuration object to `APTED`. You can use the default `apted.config.Config()` for unit costs, or define your own custom class inheriting from `object` (or `Config`) and implement `rename`, `cost_insert`, and `cost_delete` methods.

Warnings

• gotcha The `apted` Python library is a pure Python implementation and does not rely on Java or `jpype`. Older examples or discussions might refer to a `StartJVM()` function, which is not applicable to this Python package and will result in errors.
  Fix: Do not attempt to import or use `jpype` or `StartJVM()` with the Python `apted` library. It is designed to run natively in Python.
• gotcha The library primarily supports tree input in a specific 'bracket notation' string format (e.g., `{A{B}{C}}`). Using malformed strings or attempting other formats directly will lead to parsing errors.
  Fix: Ensure your input tree strings strictly adhere to the bracket notation. For other formats (like JSON), you must implement your own conversion logic to the `Node` object structure or bracket notation.
• gotcha The `apted` library's primary Python package has not been updated since November 2017, meaning new features or significant performance improvements found in the actively developed Java version might not be present. While stable, development is slow for the Python port.
  Fix: Be aware that the Python version's feature set and performance are tied to its last release. If you need the absolute latest features or optimizations, consider looking at the original Java implementation or other tree similarity libraries.

Install

• pip install apted Install stable version

Imports

• APTED

  from apted import APTED

• Node
  wrong:

  from apted import Node

  correct:

  from apted.nodes import Node

  While 'from apted import Node' might work in some contexts, the canonical path is 'from apted.nodes import Node' for clarity and future compatibility.
• BracketStringInputParser

  from apted.parser import BracketStringInputParser

  For parsing tree strings into Node objects.
• StartJVM
  wrong:

  import jpype; apted.StartJVM()

  correct:
  The Python apted library (version 1.x) is a pure Python port and does not use or require JPype or a JVM. This pattern is from older, Java-dependent implementations and will cause errors.

Quickstart

This example demonstrates how to calculate the tree edit distance between two trees represented in bracket notation strings. It shows how to define a custom cost model for rename, insert, and delete operations, and then use the APTED class to compute the distance.

from apted import APTED
from apted.nodes import Node

# Define a custom configuration for costs (optional, unit costs are default)
class CustomConfig(object):
    def rename(self, node1, node2):
        return 0 if node1.label == node2.label else 1
    def cost_insert(self, node):
        return 1
    def cost_delete(self, node):
        return 1

# Create trees using the bracket notation string format
tree1 = Node.from_string('{a{b}{c}}')
tree2 = Node.from_string('{a{b{d}}}')

# Initialize APTED with the two trees and the custom config
apted = APTED(tree1, tree2, CustomConfig())

# Compute the tree edit distance
distance = apted.compute_edit_distance()

print(f"Tree 1: {tree1.root.to_string()}")
print(f"Tree 2: {tree2.root.to_string()}")
print(f"Edit distance: {distance}")