Generating document templates that are robust to structural variations

• US 7,668,942 B2
• Filed: 05/02/2008
• Issued: 02/23/2010
• Est. Priority Date: 05/02/2008
• Status: Expired due to Fees

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Vydiswaran, V. G. Vinod, Tiwari, Charu
• Primary Examiner(s): Meky; Moustafa M
• Application Number:
  US12/114,568
• Publication Number:
  US 20090276506A1
• Time in Patent Office: 662 Days
• Field of Search: 709200-202, 709/220, 707/6, 707/100
• US Class Current: 709/220
• 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 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;

receiving a tree-based regular expression that represents the template;

below a given level in the tree-based regular expression, performing;

forming clusters of sub-trees of the tree-based regular expression via a cost measure;

generating a nested pattern regular expression based on the clusters;

merging sub-trees based on the nested pattern regular expression;

replacing sub-trees in the tree-based regular expression at the given level with the merged sub-trees; and

repeating, for a next higher level of the tree-based regular expression that is closer to a root of the corresponding tree, the actions of forming clusters, generating a nested pattern regular expression, merging sub-trees, and replacing sub-trees in the tree-based regular expression.

2. The network device of claim 1, wherein the generating, merging and replacing comprise:

forming a string of character symbols, wherein each cluster is uniquely labeled with a character symbol, and instances of character symbols in the string represent sub-trees that are members of the corresponding cluster;

generating a nested pattern regular expression based on the string;

mapping the sub-trees to character symbols in the nested pattern regular expression;

generating a tree from the nested pattern regular expression;

replacing each character symbol in the generated tree with a merge of the sub-trees that map to the character symbol, to form a generalized regular expression tree; and

replacing the sub-trees in the tree-based regular expression with the generalized regular expression tree.

3. The network device of claim 1, wherein the cost measure indicates a cost of a node in the tree-based regular expression and the cost is based at least in part on a level of the node in the tree-based regular expression.

4. The network device of claim 1, wherein the cost measure indicates a cost of a node in the tree-based regular expression and the cost of the node increases with a proximity of the node to a root of the tree corresponding to the tree-based regular expression.

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

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

associating the sub-tree with a cluster whose cost of generalizing is lowest and below a threshold value; and

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

6. The network device of claim 1, where the electronic document comprises an HTML HyperText Markup Language) page.

7. The network device of claim 1, wherein the received tree-based regular expression is formed via nested pattern discovery that proceeds from root to leaf of the corresponding tree.

8. A method for generalizing a structural template for an electronic document, comprising:

receiving a tree-based regular expression that represents the template;

below a given level in the tree-based regular expression, performing;

forming clusters of sub-trees of the tree-based regular expression via a cost measure;

generating a nested pattern regular expression based on the clusters;

merging sub-trees based on the nested pattern regular expression;

replacing sub-trees in the tree-based regular expression at the given level with the merged sub-trees; and

repeating, for a next higher level of the tree-based regular expression that is closer to a root of the corresponding tree, the actions of forming clusters, generating a nested pattern regular expression, merging sub-trees, and replacing sub-trees in the tree-based regular expression.

9. The method of claim 8, wherein the generating, merging and replacing comprise:

forming a string of character symbols, wherein each cluster is uniquely labeled with a character symbol, and instances of character symbols in the string represent sub-trees that are members of the corresponding cluster;

generating a nested pattern regular expression based on the string;

mapping the sub-trees to character symbols in the nested pattern regular expression;

generating a tree from the nested pattern regular expression;

replacing each character symbol in the generated tree with a merge of the sub-trees that map to the character symbol, to form a generalized regular expression tree; and

replacing the sub-trees in the tree-based regular expression with the generalized regular expression tree.

10. The method of claim 8, wherein the cost measure indicates a cost of a node in the tree-based regular expression and the cost is based at least in part on a level of the node in the tree-based regular expression.

11. The method of claim 8, wherein forming clusters comprises, for each of the sub-trees:

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

associating the sub-tree with a cluster whose cost of generalizing is lowest and below a threshold value; and

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

12. A processor readable medium that includes data and instructions, wherein the execution of the instructions provides for managing a document template by enabling actions, comprising:

receiving a tree-based regular expression that represents the template;

below a given level in the tree-based regular expression, performing;

forming clusters of sub-trees of the tree-based regular expression via a cost measure;

generating a nested pattern regular expression based on the clusters;

merging sub-trees based on the nested pattern regular expression;

replacing sub-trees in the tree-based regular expression at the given level with the merged sub-trees; and

repeating, for a next higher level of the tree-based regular expression that is closer to a root of the corresponding tree, the actions of forming clusters, generating a nested pattern regular expression, merging sub-trees, and replacing sub-trees in the tree-based regular expression.

13. The medium of claim 12, wherein the generating, merging and replacing comprise:

forming a string of character symbols, wherein each cluster is uniquely labeled with a character symbol, and instances of character symbols in the string represent sub-trees that are members of the corresponding cluster;

generating a nested pattern regular expression based on the string;

mapping the sub-trees to character symbols in the nested pattern regular expression;

generating a tree from the nested pattern regular expression;

replacing each character symbol in the generated tree with a merge of the sub-trees that map to the character symbol, to form a generalized regular expression tree; and

replacing the sub-trees in the tree-based regular expression with the generalized regular expression tree.

14. The processor readable medium of claim 12, wherein the cost measure indicates a cost of a node in the tree-based regular expression and the cost is based at least in part on a level of the node in the tree-based regular expression.

15. The processor readable medium of claim 12, wherein forming clusters comprises, for each of the sub-trees:

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

associating the sub-tree with a cluster whose cost of generalizing is lowest and below a threshold value; and

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

16. A system that manages document templates, comprising:

a network device that includes;

a transceiver for communicating with at least one mobile device over a network; and

processor for enabling actions, comprising;

receiving a tree-based regular expression that represents a document template;

below a given level in the tree-based regular expression, performing;

forming clusters of sub-trees of the tree-based regular expression via a cost measure;

generating a nested pattern regular expression based on the clusters;

merging sub-trees based on the nested pattern regular expression;

replacing sub-trees in the tree-based regular expression at the given level with the merged sub-trees;

repeating, for a next higher level of the tree-based regular expression that is closer to a root of the corresponding tree, the actions of forming clusters, generating a nested pattern regular expression, merging sub-trees, and replacing sub-trees in the tree-based regular expression; and

extracting information from a web page based on a document template corresponding to the tree-based regular expression; and

the at least one mobile device that further includes;

a transceiver for communicating with at least the network device over the network; and

a processor for enabling actions, comprising;

receiving the extracted information.

17. The system of claim 16, wherein:

the generating, merging and replacing comprise;

forming a string of character symbols, wherein each cluster is uniquely labeled with a character symbol, and instances of character symbols in the string represent sub-trees that are members of the corresponding cluster;

generating a nested pattern regular expression based on the string;

mapping the sub-trees to character symbols in the nested pattern regular expression;

generating a tree from the nested pattern regular expression;

replacing each character symbol in the generated tree with a merge of the sub-trees that map to the character symbol, to form a generalized regular expression tree; and

replacing the sub-trees in the tree-based regular expression with the generalized regular expression tree;

and

the forming clusters comprises, for each of the sub-trees;

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

associating the sub-tree with a cluster whose cost of generalizing is lowest and below a threshold value;

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

18. The system of claim 16, wherein:

the cost measure indicates a cost of a node in the tree-based regular expression and the cost is based at least in part on a level of the node in the tree-based regular expression; and

the network device comprises a mobile device.

19. A mobile 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;

receiving a tree-based regular expression that represents a document template;

below a given level in the tree-based regular expression, performing;

forming clusters of sub-trees of the tree-based regular expression via a cost measure;

generating a nested pattern regular expression based on the clusters;

merging sub-trees based on the nested pattern regular expression; and

replacing sub-trees in the tree-based regular expression at the given level with the merged sub-trees;

repeating, for a next higher level of the tree-based regular expression that is closer to a root of the corresponding tree, the actions of forming clusters, generating a nested pattern regular expression, merging sub-trees, and replacing sub-trees in the tree-based regular expression;

extracting information from a web page based on the document template corresponding to the tree-based regular expression; and

displaying the extracted information to a user.

20. The mobile device of claim 19, wherein the generating, merging and replacing comprise:

forming a string of character symbols, wherein each cluster is uniquely labeled with a character symbol, and instances of character symbols in the string represent sub-trees that are members of the corresponding cluster;

generating a nested pattern regular expression based on the string;

mapping the sub-trees to character symbols in the nested pattern regular expression;

generating a tree from the nested pattern regular expression;

replacing each character symbol in the generated tree with a merge of the sub-trees that map to the character symbol, to form a generalized regular expression tree; and

replacing the sub-trees in the tree-based regular expression with the generalized regular expression tree; and

wherein forming clusters comprises, for each of the sub-trees, determining for each cluster a cost of generalizing the cluster to accommodate the sub-tree, associating the sub-tree with a cluster whose cost of generalizing is lowest and below a threshold value, and if none of the costs of generalizing are below the threshold value, then forming a new cluster based on the sub-tree.