TECHNIQUES FOR INDUCING HIGH QUALITY STRUCTURAL TEMPLATES FOR ELECTRONIC DOCUMENTS

• US 20080072140A1
• Filed: 11/27/2007
• Published: 03/20/2008
• 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: Vydiswaran, V.G., Mehta, Rupesh, Madaan, Amit
• Granted Patent: US 8,046,681 B2
• Time in Patent Office: Days
• US Class Current: 715/243
• 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 a structure of at least a portion of a document with a structure of an initial template;

in response to determining a mismatch between the structure of the portion of the document and the structure of the initial template, determining a cost of generalizing the structure of the initial template to create a generalized template that has a structure that;

(a) will match the portion of the document, and

(b) will match any structure that the structure of the initial template would match; and

if the cost is less than a specified threshold, then creating the generalized template by generalizing the structure of the initial template to match the structure of the portion of the document.

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

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

a second operator having a second subtree associated therewith, wherein the second operator indicates that the second subtree is optional at a position in the document that corresponds to the position of the second operator; and

a third operator having a plurality of subtrees associated therewith, wherein the third operator indicates that only one of the plurality of subtrees are allowed to occur at a position in the document 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 structure of 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 structure of 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 structure of 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 2, wherein the cost is based, at least in part, on which of the operators is involved in generalizing the structure of the initial template.

7. 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.

8. The method of claim 7, wherein the second level is a higher level than the first level.

9. 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.

10. The method of claim 1, wherein the initial template includes a plurality of logical levels and the cost is based, at least in part, on the logical level at which a change is to be made to the initial template to create the generalized template.

11. The method of claim 1, further comprising storing the generalized template on a computer readable medium.

12. The method of claim 1, further comprising:

if the cost is not less than the specified threshold, then determining not to create the generalized template.

20. The method of claim 1, further comprising storing the generalized template on a computer readable medium.

13. 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.

14. The method 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 method 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:

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 method 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:

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 method 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:

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 method of claim 13, 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.

19. The method of claim 13 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.

21. 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.

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

23. A system comprising:

template storage; and

template induction logic that is operable to;

compare a structure of at least a portion of a document with a structure of an initial template;

in response to determining a mismatch between the structure of the portion of the document and the structure of the initial template, determine a cost of generalizing the structure of the initial template to create a generalized template that has a structure that;

(a) will match the portion of the document, and

(b) will match any structure that the structure of the initial template would match; and

if the cost is less than a specified threshold, create the generalized template by generalizing the structure of the initial template to match the structure of the portion of the document;

store the generalized template in the template storage.

24. 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.

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

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