GENERATING DOCUMENT TEMPLATES THAT ARE ROBUST TO STRUCTURAL VARIATIONS

• US 20100174715A1
• Filed: 02/22/2010
• Published: 07/08/2010
• Est. Priority Date: 05/02/2008
• Status: Abandoned Application

• Current Assignee: Oath Inc. (Verizon Communications Inc.)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Tiwari, Charu, Vydiswaran, V.G. Vinod
• Application Number:
  US12/710,165
• Publication Number:
  US 20100174715A1
• Time in Patent Office: Days
• US Class Current: 707/737
• CPC Class Codes: G06F 40/186 Templates

Abstract

A template or wrapper tree for a document such as a web page is generalized from the bottom up (from leaf toward root of a logical tree structure of the template). At a given level in the tree, sub-trees are clustered and the clustered sub-trees are generalized, and the process is repeated at a next higher level in the tree, resulting in a generalized template or wrapper tree. This can be done by generating a nested pattern regular expression based on the sub-tree clusters, merging sub-trees based on the nested pattern regular expression, and then replacing sub-trees in a tree-based regular expression of the template or wrapper at the given level with the merged sub-trees. This process is repeated at a next higher level of the tree (progressing from leaf towards root) until the wrapper or tree-based regular expression that represents the template is fully generalized.

Claims

1. A method for managing document templates, comprising:

forming a plurality of clusters for a plurality of sub-trees of a tree, at a first level of the tree, based on a cost measure of adding each sub-tree to each cluster;

generating a separate merged sub-tree for each cluster based on a merging of each sub-tree that corresponds to a particular cluster;

replacing each sub-tree that corresponds to the particular cluster with the corresponding merged sub-tree; and

repeating, for a next higher level of the tree in relation to a root of the tree, the actions of forming another plurality of clusters, generating another separate merged sub-tree for each of the plurality of other clusters, and replacing each sub-tree corresponding to another particular cluster of the plurality of other clusters with another corresponding merged sub-tree.

2. The method of claim 1, further comprising determining, for a set of sub-trees at the first level, a pattern in the plurality of clusters that correspond to each of the plurality of sub-trees.

3. The method of claim 1, wherein generating the separate merged sub-tree includes:

inserting a node into the merged sub-tree indicating that a set of nodes beneath the inserted node are at least one of;

singular, optional and repetitive.

4. The method of claim 1, wherein generating the separate merged sub-tree includes inserting a node into the merged sub-tree indicating that a particular one of the inserted node'"'"'s children is to be used for a document template.

5. The method of claim 1, wherein forming the plurality of clusters comprises, for each of the sub-trees:

determining for each cluster a cost of generalizing each cluster to accommodate a sub-tree;

corresponding the sub-tree to one of the plurality of clusters having a lowest cost for generalizing; and

if none of the costs for generalizing are below a threshold value, forming a new cluster based on the sub-tree.

6. The method of claim 1, wherein a pattern in the clusters associated with each of the sub-trees is determined, and merged sub-trees replace the sub-trees based on the pattern.

7. A network device configured to manage document templates, comprising:

a transceiver to send and receive data over a network; and

a processor that is operative to enable actions for;

forming a plurality of clusters for a plurality of sub-trees of a tree, at a first level of the tree, based on a cost measure of adding each sub-tree to each cluster;

generating a separate merged sub-tree for each cluster based on a merging of each sub-tree that corresponds to a particular cluster;

replacing each sub-tree that corresponds to the particular cluster with the corresponding merged sub-tree; and

repeating, for a next higher level of the tree in relation to a root of the tree, the actions of forming another plurality of clusters, generating another separate merged sub-tree for each of the plurality of other clusters, and replacing each sub-tree corresponding to another particular cluster of the plurality of other clusters with another corresponding merged sub-tree.

8. The network device of claim 7, further comprising:

determining, for a set of sub-trees at the first level, a pattern in the plurality of clusters that correspond to each of the plurality of sub-trees.

9. The network device of claim 7, wherein generating the separate merged sub-tree includes:

inserting a node into the merged sub-tree indicating that a set of nodes beneath the inserted node are at least one of;

singular, optional and repetitive.

10. The network device of claim 7, wherein generating the separate merged sub-tree includes:

inserting a node into the merged sub-tree indicating that a particular one of the inserted node'"'"'s children is to be used for a document template.

11. The network device of claim 7, wherein forming the plurality of clusters comprises, for each of the sub-trees:

determining for each cluster a cost of generalizing each cluster to accommodate a sub-tree;

corresponding the sub-tree to one of the plurality of clusters having a lowest cost for generalizing; and

if none of the costs for generalizing are below a threshold value, forming a new cluster based on the sub-tree.

12. The network device of claim 7, wherein a pattern in the clusters associated with each of the sub-trees is determined, and merged sub-trees replace the sub-trees based on the pattern.

13. The network device of claim 7, wherein the network device is at least one of a mobile device.

14. A processor readable storage medium that includes data and instructions that if executed by a processor enables actions for managing document templates, comprising:

forming a plurality of clusters for a plurality of sub-trees of a tree, at a first level of the tree, based on a cost measure of adding each sub-tree to each cluster;

generating a separate merged sub-tree for each cluster based on a merging of each sub-tree that corresponds to a particular cluster;

replacing each sub-tree that corresponds to the particular cluster with the corresponding merged sub-tree; and

repeating, for a next higher level of the tree in relation to a root of the tree, the actions of forming another plurality of clusters, generating another separate merged sub-tree for each of the plurality of other clusters, and replacing each sub-tree corresponding to another particular cluster of the plurality of other clusters with another corresponding merged sub-tree.

15. The processor readable storage medium of claim 14, further comprising determining, for a set of sub-trees at the first level, a pattern in the plurality of clusters that correspond to each of the plurality of sub-trees.

16. The processor readable storage medium of claim 14, wherein generating the separate merged sub-tree includes:

inserting a node into the merged sub-tree indicating that a set of nodes beneath the inserted node are at least one of;

singular, optional and repetitive.

17. The processor readable storage medium of claim 14, wherein generating the separate merged sub-tree includes inserting a node into the merged sub-tree indicating that a particular one of the inserted node'"'"'s children is to be used for a document template.

18. The processor readable storage medium of claim 14, wherein forming the plurality of clusters comprises, for each of the sub-trees:

determining for each cluster a cost of generalizing each cluster to accommodate a sub-tree;

corresponding the sub-tree to one of the plurality of clusters having a lowest cost for generalizing; and

if none of the costs for generalizing are below a threshold value, forming a new cluster based on the sub-tree.

19. The processor readable storage medium of claim 14, wherein a pattern in the clusters associated with each of the sub-trees is determined, and merged sub-trees replace the sub-trees based on the pattern.