Joint optimization of wrapper generation and template detection

• US 7,660,804 B2
• Filed: 08/16/2006
• Issued: 02/09/2010
• Est. Priority Date: 08/16/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wan, Min, Zeng, Shuyi, Ma, Wei-Ying, Wen, Ji-Rong, Song, Ruihua
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): Shmatov; Alexey
• Application Number:
  US11/465,026
• Publication Number:
  US 20080046441A1
• Time in Patent Office: 1,273 Days
• Field of Search: 707/100, 715/234
• US Class Current: 1/1
• 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 with a processor and a memory for generating wrappers for hierarchically organized documents, each document having a document tree with nodes, the method comprising:

generating by the processor, for each of a plurality of clusters of documents, a wrapper by repeating the following until all the documents have been selected;

selecting a document that has not yet been selected for creation of a wrapper tree having nodes;

creating the wrapper tree for the document tree of the selected document;

for each document whose distance from its document tree to the wrapper tree is within a threshold distance,

selecting the document; and

adjusting the wrapper tree based on the document tree of the selected document; and

establishing the wrapper for the documents selected for creation and adjustment of the wrapper tree based on the adjusted wrapper tree

wherein a wrapper tree is created and adjusted for each cluster of documents whose document trees are within a threshold distance of the wrapper tree at the time of selection of the document, and

wherein distance is represented by the following equation;

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 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.

5. The method of claim 1 wherein the threshold distance is adaptive.

6. The method of claim 5 wherein the threshold distance is increased after each adjustment until the adjusting of the wrapper tree based on a document selected because of the increased threshold distance results in an adjusted wrapper tree whose effectiveness is reduced compared to the effectiveness of the wrapper before the adjustment.

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

components implemented as instructions stored in memory for execution by the processor that include;

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

wherein the metric is represented by the following equation;

8. A computer-readable storage medium containing instructions for controlling a computing system to generate wrapper trees for document trees, the document trees and wrapper trees having nodes, comprising:

for each of a plurality of wrapper trees,

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 tree is less than a threshold distance, selecting the document tree and adjusting the wrapper tree based on the selected document tree

wherein each wrapper tree represents a wrapper for a cluster of documents whose document tree is within a threshold distance of the wrapper tree before the wrapper tree is adjusted, and

wherein distance is represented by the following equation;

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

10. The computer-readable storage medium of claim 9 wherein the selected document trees for a wrapper tree form a cluster of document trees.

11. The computer-readable storage medium of claim 8 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.