TMatch

TMatch computes the tree edit distance between two rooted, ordered, labeled trees encoded in preorder parenthesized form to identify edit operations (insertions, deletions, substitutions) required to transform one tree into another.

Key Features:

• Input Representation: Operates on rooted, ordered, labeled trees encoded in preorder parenthesized form.
• Tree Edit Distance Calculation: Computes the editing distance between two trees.
• Edit Operation Identification: Generates an edit script of insertions, deletions, and substitutions to transform one tree into the other.
• Inexact Matching: Supports approximate (inexact) tree matching rather than exact or regular-expression–based matching.
• ATBE Integration: Functions as part of the Approximate-Tree-by-Example (ATBE) system.

Scientific Applications:

• Molecular Biology: Analyzing newly sequenced RNA structures represented as ordered, labeled trees.
• Pattern Recognition: Classifying unknown patterns encoded as tree structures.
• Vision: Comparing ordered, labeled tree representations used in vision tasks.
• Programming Compilation: Generating interpreters for nonprocedural programming languages and facilitating automatic error recovery.
• Natural Language Processing / Semantic Taxonomy: Comparing semantic taxonomies and dictionary definition trees.

Methodology:

Represents trees in preorder parenthesized form and computes tree edit distance to produce edit scripts of insertions, deletions, and substitutions, supporting inexact matching.