JOINT OPTIMIZATION OF WRAPPER GENERATION AND TEMPLATE DETECTION

• US 20080046441A1
• Filed: 08/16/2006
• Published: 02/21/2008
• Est. Priority Date: 08/16/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Ma, Wei-Ying, Wen, Ji-Rong, Wan, Min, Song, Ruihua, Zeng, Shuyi
• Granted Patent: US 7,660,804 B2
• Time in Patent Office: Days
• US Class Current: 707/100
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 40/137 Hierarchical processing, e.g. outlines
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]

Abstract

A method and system for generating wrappers for hierarchically organized documents by jointly optimizing template detection and wrapper generation is provided. A wrapper generation system generates a wrapper for documents with similar templates by identifying a cluster of document trees and generating a wrapper tree for the cluster. A wrapper tree defines the wrapper for documents that match the template of the cluster. The wrapper generation system clusters document trees by generating a wrapper tree for the cluster based on an initial document tree. The wrapper generation system then repeatedly determines whether any other document tree matches or nearly matches the wrapper tree for the cluster and, if so, adds the document tree to the cluster and adjusts the wrapper tree as appropriate so that all the document trees, including the newly added one, match the wrapper tree.

Claims

1. A method in a computing device for generating a wrapper for hierarchically organized documents, each document having a document tree, the method comprising:

creating a wrapper tree for a document tree;

selecting a document tree whose distance to the wrapper tree is within a threshold; and

adjusting the wrapper tree based on the document tree wherein the wrapper is based on the adjusted wrapper tree.

2. The method of claim 1 wherein the adjusting of the wrapper tree includes merging a wrapper tree for the selected document tree and the created wrapper tree.

3. The method of claim 2 wherein the creating of a wrapper tree for a document tree includes combining consecutive sub-forests of nodes within the document tree.

4. The method of claim 1 including performing the selecting and adjusting for multiple document trees.

5. The method of claim 1 wherein the wrapper tree is for a cluster of document trees that includes the document tree for which the wrapper tree is created and the document trees for which the wrapper tree is adjusted.

6. The method of claim 5 including after the wrapper tree is generated, generating another wrapper tree for another cluster of document trees.

7. The method of claim 1 wherein distance between a document tree and wrapper tree is based on number of wrapper nodes that do not match document nodes and number of document nodes that do not match wrapper nodes.

8. The method of claim 7 wherein the distance is normalized based on weight of the document tree and the wrapper tree.

9. The method of claim 1 wherein when multiple wrapper trees have been generated, identifying a wrapper to use for extracting data from a document tree based on distance between the document tree and the wrapper trees.

10. The method of claim 1 wherein the threshold is adaptive.

11. The method of claim 10 wherein the threshold increases until the adjusting of the wrapper tree based on a document selected because of the increased threshold reduces the effectiveness of the wrapper tree.

12. A computing system that determines similarity between a hierarchically organized document and a wrapper tree, the document having a document tree, the system comprising:

a component that aligns nodes of the document tree with nodes of the wrapper tree; and

a component that generates a metric from the number of misaligned nodes, the metric indicating similarity between the document tree and the wrapper tree.

13. The computing system of claim 12 wherein the metric is based on number of nodes of the document tree not aligned with nodes of the wrapper tree and number of nodes of the wrapper tree not aligned with nodes of the document tree.

14. The computing system of claim 13 wherein the number of misaligned nodes is normalized based on weight of the trees.

15. The computing system of claim 12 wherein the metric is represented by the following equation:

$\mathrm{\Psi <br><br>}<br><br>\left(T_{\mathrm{\varpi <br><br>}},T_d\right)=\left(\frac{C_{\mathrm{\varpi <br><br>}}<br><br>\left(T_{\mathrm{\varpi <br><br>}},T_d\right)}{W<br><br>\left(T_{\mathrm{\varpi <br><br>}}\right)}+\frac{C_d<br><br>\left(T_{\mathrm{\varpi <br><br>}},T_d\right)}{W<br><br>\left(T_{\mathrm{\varpi <br><br>}}\right)}\right)/2$

16. A computer-readable medium containing instructions for controlling a computing system to generate wrapper trees for document trees, by a method comprising:

for each wrapper tree,

selecting a document tree that has not been previously selected;

creating the wrapper tree for the selected document tree; and

when there exists an unselected document tree whose distance from the wrapper is less than a threshold, selecting the document tree and adjusting the wrapper tree based on the selected document tree.

17. The computer-readable medium of claim 16 wherein when the distance is zero, selecting the document tree without adjusting the wrapper tree.

18. The computer-readable medium of claim 17 wherein the selected document trees for a wrapper tree form a cluster of document trees.

19. The computer-readable medium of claim 16 wherein the distance is based on number of misaligned nodes between the document tree and the wrapper tree.

20. The computer-readable medium of claim 16 including extracting data from a document by identifying the wrapper tree whose distance from a document tree of the document is smallest and using the identified wrapper tree as a template for extracting data from the document.