Method and apparatus of automatically generating a procedure for extracting information from textual information sources

• US 6,304,870 B1
• Filed: 12/02/1997
• Issued: 10/16/2001
• Est. Priority Date: 12/02/1997
• Status: Expired due to Fees

• Current Assignee: Board of Regents of The University of Washington (University of Washington)
• Original Assignee: Board of Regents of The University of Washington (University of Washington)
• Inventors: Kushmerick, Nicholas, Weld, Daniel S., Doorenbos, Robert B.
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): Corrielus, Jean M.
• Application Number:
  US08/982,857
• Time in Patent Office: 1,414 Days
• Field of Search: 707/4, 707/10, 707/104, 707/3, 707/6
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9538 Presentation of query results
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A procedure is disclosed for automatically constructing wrappers for performing information-extraction from sites such as Internet resources that display relevant information, interspersed with extraneous text fragments, such as HTML formatting commands or advertisements. The procedure has three basic steps. First, a set of example pages are collected with a subroutine named GatherExamples. Gather Examples is provided with information describing how to pose example queries to the site whose wrapper is to be learned. Second, these example pages are labeled by a subroutine named LabelExamples—i.e., the information to be extracted from each example is identified for use in the third step. The LabelExamples subroutine uses a general framework for labeling pages using site-specific heuristics called recognizers, as well as allowing users to correct and modify the recognized instances. Finally, the labeled example pages are passed to a BuildWrapper subroutine, which constructs a wrapper.

Claims

1. A method of automatically generating a procedure for extracting information from textual information sources comprising the steps of:

collecting a set of example pages from the information sources;

identifying text fragments of interest from the example pages, and

constructing the procedure using delimiters of the text fragments by;

identifying possible delimiters of the text fragment;

considering different combinations of possible delimiters; and

using the combination which best matches the example pages to generate the procedure.

2. The method of claim 1, wherein the collecting step includes using a datum related to the textual information source as a guide for collecting the set of example pages.

3. The method of claim 2, wherein the datum comprises an identifier of the textual information source.

4. The method of claim 2, wherein the datum comprises a description of a method of querying the textual information source for the set of example pages.

5. The method of claim 2, wherein the datum comprises a set of variable names.

6. The method of claim 5, wherein the set of variable names includes an item category.

7. The method of claim 5, wherein the set of variable names includes an item category attribute.

8. The method of claim 2, wherein the datum comprises a variable binding.

9. The method of claim 8, wherein the variable binding comprises an item category and item category attribute set.

10. The method of claim 1 further comprising the step of labeling the set of example pages.

11. The method of claim 10, wherein the labeling step includes

extracting a potential text fragment of interest from the set of example pages; and

correcting the potential text fragment of interest to obtain a text fragment of interest.

12. The method of claim 11, further comprising the step creating a tuple from the text fragment of interest.

13. The method of claim 12, wherein the tuple comprises a row of a table data structure.

14. The method of claim 11 further comprising the step of applying heuristic techniques to identify the potential text fragment of interest.

15. The method of claim 11, wherein the extracting step employs recognizer algorithms to identify the potential text fragment of interest.

16. The method of claim 11, wherein the correcting step includes displaying the potential text fragment of interest for manual review.

17. The method of claim 1, wherein the identifying step comprises:

extracting a text fragment of interest from a label created in the labeling step; and

parsing an example page from the set of example pages to extract potential delimiters by reference to the text fragment of interest.

18. The method of claim 1, wherein the step of considering different combinations of possible delimiters includes

applying a set of requirements to a potential delimiter;

and

eliminating a potential delimiter that does not adhere to the set of requirements.

19. The method of claim 1, further comprising the step of selecting a procedure class, the procedure class governing the identifying, testing, and using steps.

20. The method of claim 19, wherein the procedure class is an LR procedure class.

21. The method of claim 19, wherein the procedure class is an HLRT procedure class.

22. The method of claim 19, wherein the procedure class is an OCLR procedure class.

23. A method of automatically generating a procedure for extracting information from a textual information source comprising the steps of

collecting a set of example pages from the information sources;

identifying text fragments of interest from the example pages, and

constructing the procedure using delimiters of the text fragments by;

defining a set of delimiters for a wrapper class,

defining a generic procedure specifying how the delimiters are used for information extraction,

determining a set of candidate values for each of the wrapper class'"'"'s delimiters,

defining a set of constraints that must be satisfied for a wrapper in the wrapper class to be correct and

finding a combination of candidate values for each delimiter that satisfies the set of constraints.

24. The method of claim 23 wherein the step of constructing the procedure using delimiters of the text fragments comprises the steps of:

identifying delimiters of the text fragments and

using such delimiters to generate the procedure.