Techniques for inducing high quality structural templates for electronic documents

• US 8,046,681 B2
• Filed: 11/27/2007
• Issued: 10/25/2011
• Est. Priority Date: 07/05/2006
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Madaan, Amit, Vydiswaran, V. G. Vinod, Mehta, Rupesh R.
• Primary Examiner(s): RIES, LAURIE ANNE
• Application Number:
  US11/945,749
• Publication Number:
  US 20080072140A1
• Time in Patent Office: 1,428 Days
• Field of Search: 715/234, 715/235, 715/237, 715/241, 715/209, 715/243, 715/273, 715/255
• US Class Current: 715/234
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 16/986 Document structures and storage, e.g. HTML extensions
• CPC Class Codes: G06F 18/231 Hierarchical techniques, i.e. dividing or merging pattern sets so as to obtain a dendrogram
• CPC Class Codes: G06F 40/151 Transformation
• CPC Class Codes: G06F 40/186 Templates
• CPC Class Codes: G06F 40/194 Calculation of difference between files
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access

Abstract

Techniques are disclosed herein to automatically learn a template that describes a common structure present in documents in a training set. The structure of the template is compared to the structure of the documents (or at least a part of each document) in the training set, one-by-one, and generalized in response to differences between the template and the document to which the template is currently being compared. If the structure of any particular document is considered too dissimilar from the structure of the template, then the template is not modified. Various generalization operators are added to the template to generalize the template. One such generalization operator is an “OR”, which indicates that only one of “n” sub-trees below the “OR” operator in the template is allowed at the corresponding position in a document.

Claims

1. A method comprising:

comparing, one document at a time, a structure of documents in a training set with a structure of an initial template;

selecting at least one of the documents based on the comparing;

generalizing the initial template to create a generalized template that has a structure that matches each of the selected documents;

wherein generalizing the initial template to create the generalized template includes adding one or more operators to the initial template from a set of operators to create the generalized template, wherein the one or more operators includes a first operator that indicates that only one of a plurality of subtrees below the operator is allowed to occur at a position in the selected documents that corresponds to the position of the first operator in the generalized template.

2. The method of claim 1, wherein the generalized template includes:

a second operator having a first subtree associated therewith, wherein the second operator indicates that the first subtree must occur at least once at a position in the selected documents that corresponds to the position of the second operator in the generalized template; and

a third operator having a second subtree associated therewith, wherein the third operator indicates that the second subtree is optional at a position in the selected documents that corresponds to the position of the third operator.

3. The method of claim 2, wherein the document includes a first set of tags and relationships between tags in the first set of tags, and the initial template includes a second set of tags and relationships between tags in the second set of tags, and further comprising:

determining that the mismatch occurs, wherein determining that the mismatch occurs includes;

based on the relationships between tags in the first set of tags and the relationships between tags in the second set of tags, determining that a tag in the first set fails to match a tag in the second set;

wherein generalizing the initial template includes attempting to modify the initial template by adding the first operator prior to attempting to modify the initial template by adding the second operator and prior to attempting to modify the initial template by adding the third operator.

4. The method of claim 2, wherein the document includes a first set of tags and relationships between tags in the first set of tags, and the initial template includes a second set of tags and relationships between tags in the second set of tags, and further comprising:

determining that the mismatch occurs, wherein determining that the mismatch occurs includes;

based on the relationships between tags in the first set of tags and the relationships between tags in the second set of tags, determining that a tag in the first set fails to match a tag in the second set;

wherein generalizing the initial template includes attempting to modify the initial template by adding the second operator after an attempt to modify the initial template by adding the first operator fails and prior to attempting to modify the initial template by adding the third operator.

5. The method of claim 2, wherein the document includes a first set of tags and relationships between tags in the first set of tags, and the initial template includes a second set of tags and relationships between tags in the second set of tags, and further comprising:

determining that the mismatch occurs, wherein determining that the mismatch occurs includes;

based on the relationships between tags in the first set of tags and the relationships between tags in the second set of tags, determining that a tag in the first set fails to match a tag in the second set;

wherein generalizing the initial template includes attempting to modify the initial template by adding the third operator after an attempt to modify the initial template by adding the first operator fails and after an attempt to modify the initial template by adding the second operator fails.

6. The method of claim 1, wherein the initial template includes a structure defined by a plurality of logical levels, and further comprising:

after determining that a mismatch occurs at a first level of the plurality of logical levels, determining whether to modify the initial template at a second level of the plurality of levels in order to create the generalized template, wherein the first level is a different level from the second level.

7. The method of claim 1 further comprising:

comparing an extent to which the portion of the document matches with each of a plurality of sub-trees in the initial template; and

based on the extent to which the portion matches with each of the sub-trees, determining which sub-tree to modify to match the portion of the document.

8. A method of generalizing a template having a plurality of sub-trees, said method comprising:

comparing a structure of a first sub-tree of the plurality of sub-trees with a structure of a second sub-tree of the plurality of sub-trees, wherein the first sub-tree and the second sub-tree are not structurally identical;

determining a degree of structural similarity between the first sub-tree and the second sub-tree; and

in response to determining that the degree of structural similarity is more than a specified threshold, generalizing the structure of the first sub-tree to generate a modified first sub-tree in the template, wherein the structure of the modified first sub-tree matches the structure of first sub-tree and the structure of the second sub-tree.

9. The method of claim 8, further comprising determining a co-efficient of similarity between sub-trees in the plurality of sub-trees.

10. A system comprising:

template storage; and

template induction logic that is operable to;

compare, one document at a time, a structure of documents in a training set with a structure of an initial template;

select at least one of the documents based on the comparing;

generalize the initial template to create a generalized template that has a structure that matches each of the selected documents;

wherein to generalize the initial template to create the generalized template the logic is operable to add one or more operators to the initial template from a set of operators to create the generalized template, wherein the one or more operators includes a first operator that indicates that only one of a plurality of subtrees below the operator is allowed to occur at a position in the selected documents that corresponds to the position of the first operator in the generalized template; and

store the generalized template in the template storage.

11. The system of claim 10, further comprising an information extraction engine that is operable to extract information from documents based on the generalized template stored in the template storage.

12. The system of claim 11, wherein the documents from which information is extracted are structurally similar to the training documents.

13. A non-transitory computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, cause the one or more processors to perform:

comparing, one document at a time, a structure of documents in a training set with a structure of an initial template;

selecting at least one of the documents based on the comparing;

generalizing the initial template to create a generalized template that has a structure that matches each of the selected documents;

wherein generalizing the initial template to create the generalized template includes adding one or more operators to the initial template from a set of operators to create the generalized template, wherein the one or more operators includes a first operator that indicates that only one of a plurality of subtrees below the operator is allowed to occur at a position in the selected documents that corresponds to the position of the first operator in the generalized template.

14. The non-transitory computer-readable storage medium of claim 13, wherein the generalized template includes:

a second operator having a first subtree associated therewith, wherein the second operator indicates that the first subtree must occur at least once at a position in the selected documents that corresponds to the position of the second operator in the generalized template; and

a third operator having a second subtree associated therewith, wherein the third operator indicates that the second subtree is optional at a position in the selected documents that corresponds to the position of the third operator.

15. The non-transitory computer-readable storage medium of claim 14, wherein the document includes a first set of tags and relationships between tags in the first set of tags, and the initial template includes a second set of tags and relationships between tags in the second set of tags, and further comprising instructions for carrying out the steps of:

determining that the mismatch occurs, wherein determining that the mismatch occurs includes;

based on the relationships between tags in the first set of tags and the relationships between tags in the second set of tags, determining that a tag in the first set fails to match a tag in the second set;

wherein generalizing the initial template includes attempting to modify the initial template by adding the first operator prior to attempting to modify the initial template by adding the second operator and prior to attempting to modify the initial template by adding the third operator.

16. The non-transitory computer-readable storage medium of claim 14, wherein the document includes a first set of tags and relationships between tags in the first set of tags, and the initial template includes a second set of tags and relationships between tags in the second set of tags, and further comprising instructions for carrying out the steps of:

determining that the mismatch occurs, wherein determining that the mismatch occurs includes;

based on the relationships between tags in the first set of tags and the relationships between tags in the second set of tags, determining that a tag in the first set fails to match a tag in the second set;

wherein generalizing the initial template includes attempting to modify the initial template by adding the second operator after an attempt to modify the initial template by adding the first operator fails and prior to attempting to modify the initial template by adding the third operator.

17. The non-transitory computer-readable storage medium of claim 14, wherein the document includes a first set of tags and relationships between tags in the first set of tags, and the initial template includes a second set of tags and relationships between tags in the second set of tags, and further comprising instructions for carrying out the steps of:

determining that the mismatch occurs, wherein determining that the mismatch occurs includes;

based on the relationships between tags in the first set of tags and the relationships between tags in the second set of tags, determining that a tag in the first set fails to match a tag in the second set;

wherein generalizing the initial template includes attempting to modify the initial template by adding the third operator after an attempt to modify the initial template by adding the first operator fails and after an attempt to modify the initial template by adding the second operator fails.

18. The non-transitory computer-readable storage medium of claim 13, wherein the initial template includes a structure defined by a plurality of logical levels, and further comprising instructions for carrying out the steps of:

after determining that a mismatch occurs at a first level of the plurality of logical levels, determining whether to modify the initial template at a second level of the plurality of levels in order to create the generalized template, wherein the first level is a different level from the second level.

19. The non-transitory computer-readable storage medium of claim 13 further comprising instructions for carrying out the steps of:

comparing an extent to which the portion of the document matches with each of a plurality of sub-trees in the initial template; and

based on the extent to which the portion matches with each of the sub-trees, determining which sub-tree to modify to match the portion of the document.

20. A non-transitory computer-readable storage medium storing one or more sequences of instructions which, when executed by one or more processors, cause the one or more processors to perform:

comparing a structure of a first sub-tree, of a plurality of sub-trees associated with a template, with a structure of a second sub-tree of the plurality of sub-trees, wherein the first sub-tree and the second sub-tree are not structurally identical;

determining a degree of structural similarity between the first sub-tree and the second sub-tree; and

in response to determining that the degree of structural similarity is more than a specified threshold, generalizing the structure of the first sub-tree to generate a modified first sub-tree in the template, wherein the structure of the modified first sub-tree matches the structure of first sub-tree and the structure of the second sub-tree.

21. The non-transitory computer-readable storage medium of claim 20, further comprising instructions for determining a co-efficient of similarity between sub-trees in the plurality of sub-trees.