Tree Edit Distance

TED defines transformation cost through three atomic operations on a tree's nodes:

• Insertion: Adding a new node and connecting it to a parent, representing a new clause or section.
• Deletion: Removing a node (and its subtree), representing a struck provision.
• Relabeling: Changing a node's label while preserving its position, representing a modified term or value.

The algorithm finds the minimum-cost sequence of these operations, known as the edit script.

The classic dynamic programming solution for computing the exact tree edit distance between two ordered, labeled trees. It operates by decomposing the problem into subproblems of comparing keyroots—nodes that have left siblings.

• Time Complexity: O(n⁴) in its naive form, though optimized to O(n³) or O(n²) in practice.
• Relevance: Forms the theoretical backbone for comparing XML legal documents where element ordering (e.g., clause numbering) is semantically significant.

The choice of tree model critically impacts comparison semantics:

• Ordered Trees: The left-to-right sibling order is fixed. Essential for comparing structured legal documents where section numbering (1.1, 1.2) carries meaning.
• Unordered Trees: Sibling order is irrelevant. Useful for comparing sets of obligations or party lists where sequence does not imply priority. Unordered TED is NP-hard, requiring heuristic or approximation algorithms for practical use.

When legal rules are parsed into an Abstract Syntax Tree (AST), TED enables structural comparison of the logic itself, not just the text.

• A change from 'A and B' to 'A or B' is a single node relabeling.
• A new exception clause inserted as a subtree is detected as a block insertion. This allows AI systems to identify semantically significant structural modifications that a text diff would miss.

The practical utility of TED depends entirely on the cost function assigned to operations:

• Uniform Cost: All operations cost 1. Simple but fails to distinguish a typo fix from a liability shift.
• Domain-Weighted Cost: Relabeling a 'Limitation of Liability' node costs more than relabeling a 'Notice Address' node.
• Semantic Cost: Uses embedding distance between node labels, so changing 'promptly' to 'within 30 days' incurs a higher cost than changing 'promptly' to 'forthwith'.

Standard TED cannot natively detect when an entire subtree is moved from one parent to another—it would be computed as a deletion plus an insertion. Advanced variants like the Tree Edit Distance with Moves (TEDM) extend the operation set to include a subtree move primitive.

• Critical for detecting when a clause is relocated from the body of a contract to an appendix.
• Significantly increases computational complexity, often requiring approximation algorithms.

The foundational quantitative metric measuring the minimum number of operations required to transform one sequence into another. While Levenshtein distance operates on flat strings using character insertions, deletions, and substitutions, tree edit distance generalizes this concept to hierarchical structures. The cost of each node operation—insertion, deletion, or relabeling—is parameterized, allowing domain-specific tuning for legal document comparison where certain structural changes carry higher significance.

A classic dynamic programming algorithm that identifies the longest sequence of elements appearing in the same relative order in two sequences. For tree structures, this extends to the largest common subtree problem. In legal document differencing, LCS forms the basis for aligning corresponding clauses across contract versions before computing fine-grained edits. The algorithm runs in O(n*m) time for sequences of length n and m, with optimized variants reducing memory consumption through Hirschberg's algorithm.

An O(ND) greedy algorithm that finds the shortest edit script between two sequences by exploring an edit graph where diagonal moves represent matches and horizontal/vertical moves represent insertions and deletions. While originally designed for flat text and forming the basis of the Unix diff utility, the conceptual framework extends to tree comparison through edit mapping between ordered node sequences. The algorithm guarantees a minimal diff with respect to the number of changed lines.

A technique that identifies non-identical but similar strings or subtrees across document versions. Unlike exact matching required by strict tree edit distance, fuzzy matching employs token-based similarity metrics such as Jaccard index or TF-IDF cosine similarity to align corresponding clauses even when wording has been paraphrased. This is critical for legal documents where the same obligation may be expressed with different syntactic structures across negotiation rounds.

A text comparison method that decomposes document nodes into contiguous sequences of n words or characters and measures their overlap. For tree edit distance applications, n-gram profiles of leaf-node text content enable approximate node matching before computing structural edits. Common configurations include:

• Word 3-grams: Captures phrasal similarity for clause alignment
• Character 4-grams: Robust to spelling variations and OCR errors
• Jaccard coefficient: Measures overlap ratio between n-gram sets

A semantic comparison method that converts text nodes into high-dimensional mathematical vectors using transformer models, then measures cosine distance between embeddings to identify meaning-level changes. This extends tree edit distance beyond syntactic operations by enabling semantic relabeling detection—identifying when a node's text has changed but its legal meaning remains equivalent. Embedding-based node matching significantly reduces false-positive structural diffs in contract comparison.