Data extraction using templates

• US 9,323,731 B1
• Filed: 10/15/2013
• Issued: 04/26/2016
• Est. Priority Date: 11/01/2007
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Younes, Haakan, Schafer, Charles F. III
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): Le, Jessica N
• Application Number:
  US14/054,406
• Time in Patent Office: 924 Days
• Field of Search: 707/705, 707/790
• US Class Current: 1/1
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]

Abstract

Systems and techniques for extracting data from unstructured documents are described. One such method involves assigning one or more labels to one or more nodes in a first object model of a first web page; comparing a second object model of a second web page to the first object model; if the first object model matches the second object model to a determined degree, extracting from the second web page data associated with nodes in the second object model that match labeled nodes in the first object model; and providing the extracted data for storage in a structured database in a manner associated with the labels.

Claims

1. A computer-implemented data analysis method, comprising:

assigning one or more labels to one or more nodes in object models of respective web pages to provide a plurality of annotated object models;

comparing the plurality of annotated object models;

based on comparing the plurality of annotated object models, forming a plurality of composite object models, the forming including;

for each composite object model of the plurality of object models, determining that two or more of the plurality of annotated object models have at least a specified level of similarity, and in response, storing data from the respective web pages in a single database to form the composite object model, the composite object model based on the two or more annotated object models and reflecting a structure of the web pages as a group;

comparing an object model of a web page to each of the plurality of composite object models;

based on comparing the object model of the web page to each of the plurality of composite object models, identifying a particular composite object model of the plurality of composite object models based on an edit distance between each of the plurality of composite object models and the object model of the web page;

mapping the object model of the web page to the particular composite object model based on a minimum edit distance between the object model of the web page and the particular composite object model;

extracting, from the web page, data associated with nodes in the object model of the web page that correspond to labeled nodes in the particular composite object model based on the mapping; and

providing the extracted data i) for storage in a structured database in a manner associated with the labels and ii) for display by an application executable by a computing device associated with the web page.

2. The method of claim 1, wherein each composite model of the plurality of object models is from a common web domain.

3. The method of claim 1, wherein assigning one or more labels comprises manually selecting elements on each of the respective web pages and manually selecting labels for the selected elements.

4. The method of claim 1, wherein fields in the structured database correspond to the labels.

5. The method of claim 1, wherein each of the object models is provided as a template tree that includes single nodes that comprise repeated or optional data structures from the respective web pages.

6. The method of claim 1, wherein the object models of the respective web pages comprise Document Object Model (DOM) models.

7. The method of claim 1, further comprising accessing the structured database in response to a search request, and providing one or more search results that include hyperlinks to web pages associated with data in the structured database that is responsive to the search request.

8. The method of claim 1, further comprising identifying the respective web pages by crawling the respective web pages at a domain.

9. A system comprising:

a computing device; and

a non-transitory computer-readable medium coupled to the computing device and having instructions stored thereon which, when executed by the computing device, cause the computing device to perform operations comprising;

assigning one or more labels to one or more nodes in object models of respective web pages to provide a plurality of annotated object models;

comparing the plurality of annotated object models;

based on comparing the plurality of annotated object models, forming a plurality of composite object models, the forming including;

for each composite object model of the plurality of object models, determining that two or more of the plurality of annotated object models have at least a specified level of similarity, and in response, storing data from the respective web pages in a single database to form the composite object model, the composite object model based on the two or more annotated object models and reflecting a structure of the web pages as a group;

comparing an object model of a web page to each of the plurality of composite object models;

based on comparing the object model of the web page to each of the plurality of composite object models, identifying a particular composite object model of the plurality of composite object models based on an edit distance between each of the plurality of composite object models and the object model of the web page;

mapping the object model of the web page to the particular composite object model based on a minimum edit distance between the object model of the web page and the particular composite object model;

extracting, from the web page, data associated with nodes in the object model of the web page that correspond to labeled nodes in the particular composite object model based on the mapping; and

providing the extracted data i) for storage in a structured database in a manner associated with the labels and ii) for display by an application executable by a computing device associated with the web page.

10. The system of claim 9, wherein each composite model of the plurality of object models is from a common web domain.

11. The system of claim 9, wherein assigning one or more labels comprises manually selecting elements on each of the respective web pages and manually selecting labels for the selected elements.

12. The system of claim 9, wherein fields in the structured database correspond to the labels.

13. The system of claim 9, wherein each of the object models is provided as a template tree that includes single nodes that comprise repeated or optional data structures from the respective web pages.

14. The system of claim 9, wherein the object models of the respective web pages comprise Document Object Model (DOM) models.

15. The system of claim 9, the operations further comprising accessing the structured database in response to a search request, and providing one or more search results that include hyperlinks to web pages associated with data in the structured database that is responsive to the search request.

16. The system of claim 9, the operations further comprising identifying the respective web pages by crawling the respective web pages at a domain.

17. A non-transitory computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

assigning one or more labels to one or more nodes in object models of respective web pages to provide a plurality of annotated object models;

comparing the plurality of annotated object models;

based on comparing the plurality of annotated object models, forming a plurality of composite object models, the forming including;

for each composite object model of the plurality of object models, determining that two or more of the plurality of annotated object models have at least a specified level of similarity, and in response, storing data from the respective web pages in a single database to form the composite object model, the composite object model based on the two or more annotated object models and reflecting a structure of the web pages as a group;

comparing an object model of a web page to each of the plurality of composite object models;

based on comparing the object model of the web page to each of the plurality of composite object models, identifying a particular composite object model of the plurality of composite object models based on an edit distance between each of the plurality of composite object models and the object model of the web page;

mapping the object model of the web page to the particular composite object model based on a minimum edit distance between the object model of the web page and the particular composite object model;

extracting, from the web page, data associated with nodes in the object model of the web page that correspond to labeled nodes in the particular composite object model based on the mapping; and

providing the extracted data i) for storage in a structured database in a manner associated with the labels and ii) for display by an application executable by a computing device associated with the web page.

18. The non-transitory computer storage medium of claim 17, wherein each composite model of the plurality of object models is from a common web domain.

19. The non-transitory computer storage medium of claim 17, wherein assigning one or more labels comprises manually selecting elements on each of the respective web pages and manually selecting labels for the selected elements.

20. The non-transitory computer storage medium of claim 17, wherein fields in the structured database correspond to the labels.