Method of comparing the closeness of a target tree to other trees using noisy sub-sequence tree processing
First Claim
1. 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.
0 Assignments
0 Petitions
Accused Products
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.
134 Citations
44 Claims
-
1. 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42)
-
-
43. 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. - View Dependent Claims (44)
-
Specification