Techniques for inducing high quality structural templates for electronic documents

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.

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.

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.

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.