Method of comparing the closeness of a target tree to other trees using noisy sub-sequence tree processing

• US 7,287,026 B2
• Filed: 04/05/2002
• Issued: 10/23/2007
• Est. Priority Date: 04/05/2002
• Status: Expired due to Fees

• Current Assignee: John B. Oommen
• Original Assignee: John B. Oommen
• Inventors: Oommen, John B.
• Primary Examiner(s): Gaffin; Jeffrey
• Assistant Examiner(s): ABEL JALIL, NEVEEN
• Application Number:
  US10/116,970
• Publication Number:
  US 20030195890A1
• Time in Patent Office: 2,027 Days
• Field of Search: 707 1- 10, 707100-1041, 709/225, 709/227, 725/107
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

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.

Claims

1. A computer implemented method of comparing a closeness of a target tree to other trees located in a database of the other trees, said method comprising the steps of:

(a) calculating a constraint with respect of each other tree in the database based on an estimated number of edit operations and a characteristic of the target tree, the target tree having at least one node which has at least two branches, each other tree having at least two nodes and two branches;

(b) calculating a constrained tree edit distance between the target tree and each other tree in the database based on the constraint obtained in step (a); and

(c) comparing the calculated constrained tree edit distances; and

,

(d) reporting a closeness of the target tree to an other tree located in the database based on the comparison of step (c).

2. The method as in claim 1, wherein the step of calculating a constrained tree edit distance also uses an intersymbol edit distance.

3. The method as in claim 1, wherein the target tree is a noisy subfragment of an other tree located in the database of the other trees.

4. The method as in claim 2, wherein the target tree is a noisy subfragment of an other tree located in the database of the other trees.

5. The method as in claim 1, wherein step (a) is preceded by the step of estimating a probability of an edit operation being performed on a node value to transform each other tree in the database of the other trees into an arbitrary noisy version of itself.

6. The method as in claim 2, wherein step (a) is preceded by the step of estimating a probability of an edit operation being performed on a node value to transform each other tree in the database of the other trees into an arbitrary noisy version of itself.

7. The method as in claim 3, wherein step (a) is preceded by the step of estimating a probability of an edit operation being performed on a node value to transform each other tree in the database of the other trees into an arbitrary noisy version of itself.

8. The method as in claim 4, wherein step (a) is preceded by the step of estimating a probability of an edit operation being performed on a node value to transform each other tree in the database of the other trees into an arbitrary noisy version of itself.

9. The method as in claim 5, wherein the edit operation is a substitution operation.

10. The method as in claim 6, wherein the edit operation is a substitution operation.

11. The method as in claim 7, wherein the edit operation is a substitution operation.

12. The method as in claim 8, wherein the edit operation is a substitution operation.

13. The method as in claim 5, wherein the edit operation is an insertion operation.

14. The method as in claim 6, wherein the edit operation is an insertion operation.

15. The method as in claim 7, wherein the edit operation is an insertion operation.

16. The method as in claim 8, wherein the edit operation is an insertion operation.

17. The method as in claim 5, wherein the edit operation is a deletion operation.

18. The method as in claim 6, wherein the edit operation is a deletion operation.

19. The method as in claim 7, wherein the edit operation is a deletion operation.

20. The method as in claim 8, wherein the edit operation is a deletion operation.

21. The method as in claim 1, wherein the method is preceded by the step of generating the database of the other trees.

22. The method as in claim 2, wherein the method is preceded by the step of generating the database of the other trees.

23. The method as in claim 3, wherein the method is preceded by the step of generating the database of the other trees.

24. The method as in claim 4, wherein the method is preceded by the step of generating the database of the other trees.

25. The method as in claim 5, wherein the method is preceded by the step of generating the database of the other trees.

26. The method as in claim 6, wherein the method is preceded by the step of generating the database of the other trees.

27. The method as in claim 7, wherein the method is preceded by the step of generating the database of the other trees.

28. The method as in claim 8, wherein the method is preceded by the step of generating the database of the other trees.

29. The maethod as in claim 9, wherein the method is preceded by the step of generating the database of the other trees.

30. The method as in claim 10, wherein the method is preceded by the step of generating the database of the other trees.

31. the method as in claim 11, wherein the method is preceded by the step of generating the database of the other trees.

32. The method as in claim 12, wherein the method is preceded by the step of generating the database of the other trees.

33. The method as in claim 13, wherein the method is preceded by the step of generating the database of the other trees.

34. The method as in claim 14, wherein the method is preceded by the step of generating the database of the other trees.

35. The method as in claim 15, wherein the method is preceded by the step of generating the database of the other trees.

36. The method as in claim 16, wherein the method is preceded by the step of generating the database of the other trees.

37. The method as in claim 17, wherein the method is preceded by the step of generating the database of the other trees.

38. The method as in claim 18, wherein the method is preceded by the step of generating the database of the other trees.

39. The method as in claim 19, wherein the method is preceded by the step of generating the database of the other trees.

40. The method as in claim 20, wherein the method is preceded by the step of generating the database of the other trees.

41. A computer implemented method of matching a target tree representable structure to other tree representable structure, said method comprising the steps:

(a) generating at least one target tree for the target tree representable structure, each target tree having at least one node which has at least two branches and for the each of the other tree representable structures, generating at least one other tree, each of the other trees having at least two nodes and at least two branches;

(b) calculating a constraint with respect of each other tree 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 other tree based on the constraint obtained in step (b) and an intersymbol edit distance;

(d) comparing the calculated constrained tree edit distances; and

(e) reporting that other tree that has a smallest constrained tree edit distance, based on the comparison of step (d).