Generating document templates that are robust to structural variations

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.

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.