APTED Algorithm for Tree Edit Distance

raw JSON →
1.0.3 verified Thu Apr 16 auth: no python maintenance

APTED (All Path Tree Edit Distance) is a Python library that implements the state-of-the-art algorithm for computing the tree edit distance between two ordered, labeled trees. It is a pure Python port of the original Java implementation. The current stable version is 1.0.3, with updates primarily focusing on maintenance due to its long-standing stability.

pip install apted

Common errors

error 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.
error 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 '\}'.
error 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.

Imports