Method of comparing the closeness of a target tree to other trees using noisy sub-sequence tree processing
OwnerJohn B. Oommeninventor
Life of this patent
Estimating the term…
Abstract
A method of comparing the closeness of a target tree to other trees located in a database of trees, said method comprising the steps of: (a) calculating a constraint in respect of each tree in the database based on an estimated number of edit operations and a characteristic of the target tree; (b) calculating a constrained tree edit distance between the target tree and each tree in the database using the constraint obtained in step (a); and (c) comparing the calculated constrained tree edit distances. The method can also be applied to matching a target tree representable structure to its closest tree representable structure.
Claims44
A method of comparing the closeness of a target tree to other trees located in a database of trees, said method comprising the steps of:
- (a) calculating a constraint in respect of each tree in the database based on an estimated number of edit operations and a characteristic of the target tree;
- (b) calculating a constrained tree edit distance between the target tree and each tree in the database using the constraint obtained in step (a);
- and
- (c) comparing the calculated constrained tree edit distances.
A method of matching a target tree representable structure to its closest tree representable structure, said method comprising the steps:
- (a) generating one or more target trees for the target tree representable structure;
- (b) calculating a constraint in respect of each tree in the database based on an estimated number of edit operations and a characteristic of the target tree;
- (c) calculating a constrained tree edit distance between the target tree and each tree in the library using the constraint obtained in step (b) and the intersymbol edit distance;
- (d) comparing the calculated constrained tree edit distances;
- and
- (e) reporting the tree in the database that has the smallest constrained tree distance.
Dependencies are inferred from the claim text.