AUTOMATED SCREEN SCRAPING VIA GRAMMAR INDUCTION

• US 20100256974A1
• Filed: 04/03/2009
• Published: 10/07/2010
• Est. Priority Date: 04/03/2009
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Yahoo! Inc. (Apollo Global Management, Inc.)
• Inventors: Yen, Peter, Song, Ning, Xu, Zhichen, Fu, Yun
• Granted Patent: US 8,838,625 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/186 Templates
• CPC Class Codes: G06F 40/216 using statistical methods

Abstract

A method and a computer-readable medium are provided which perform screen scraping via grammar induction. The computer-readable medium stores instructions of the method, the instructions directing a computer processor to intercept display information transmitted to a computer-implemented display device representing information stored in a data source; induce a grammar via statistical analysis of the intercepted display information; provide the grammar to a parser-generator to generate a parser corresponding to the induced grammar; and perform screen scraping using the generated parser.

Claims

1. A computer-implemented method of extracting information from a data source, comprising:

intercepting display information transmitted to a computer-implemented display device representing information stored in a data source;

inducing a grammar via statistical analysis of the intercepted display information;

generating a parser corresponding to the induced grammar; and

performing screen scraping using the generated parser to produce a sequence of return values representing the extracted information.

2. The method of claim 1, wherein inducing a grammar further comprises:

tokenizing the text;

counting occurrences of each token;

forming a histogram of tokens according to the frequency of each token; and

segmenting the text into records starting with tokens with lower frequency.

3. The method of claim 2, wherein inducing a grammar further comprises:

recursively segmenting the records to identify the underlying hierarchical structure.

4. The method of claim 1, wherein generating the parser further comprises:

receiving the induced grammar;

representing the induced grammar using a regular language; and

programming state transitions of a finite state machine to correspond to relationships represented in the regular language.

5. The method of claim 4, further comprising:

receiving additional annotations which specify fields to extract and how the fields map to the return values.

6. The method of claim 1, wherein screen scraping further comprises:

receiving the intercepted display information as an input to the finite state machine; and

producing the return values representing the extracted information.

7. A computer-readable medium in which are stored instructions directing a computer processor to:

intercept display information transmitted to a computer-implemented display device representing information stored in a data source;

induce a grammar via statistical analysis of the intercepted display information;

provide the grammar to a parser-generator to generate a parser corresponding to the induced grammar; and

perform screen scraping using the generated parser.

8. The medium of claim 7, wherein inducing a grammar further comprises:

tokenizing the text;

counting occurrences of each token;

forming a histogram of tokens according to the frequency of each token; and

segmenting the text into records starting with tokens with lower frequency.

9. The medium of claim 8, wherein inducing a grammar further comprises:

recursively segmenting the records to identify the underlying hierarchical structure.

10. The medium of claim 7, wherein generating the parser further comprises:

receiving the induced grammar;

representing the induced grammar using a regular language; and

programming state transitions of a finite state machine to correspond to relationships represented in the regular language.

11. The medium of claim 10, further comprising:

receiving additional annotations which specify fields to extract and how the fields map to the return values.

12. The medium of claim 7, wherein screen scraping further comprises:

receiving the intercepted display information as an input to the finite state machine; and

producing the return values representing the extracted information.

13. Apparatus for extracting information from a computer-based data source, comprising:

means for intercepting display information transmitted to a computer-implemented display device representing information stored in a data source; and

a computer processor executing a sequence of instructions configuring the computer processor as;

a grammar inducer producing a representation of a hierarchy as segmented records defined using a regular language;

a parser-generator receiving the segmented records defined using the regular language and configured to generate a parser corresponding thereto; and

a screen scraper configured to extract the information from the intercepted display information using the generated parser.

14. The apparatus of claim 13, wherein the sequence of instructions for the grammar inducer further comprise configuring the processor to perform:

tokenizing the text;

counting occurrences of each token;

forming a histogram of tokens according to the frequency of each token; and

segmenting the text into records starting with tokens with lower frequency.

15. The apparatus of claim 14, wherein the sequence of instructions for the grammar inducer further comprise configuring the processor to perform:

recursively segmenting the records to identify the underlying hierarchical structure.

16. The apparatus of claim 13, wherein the sequence of instructions for the parser-generator further comprise configuring the processor to perform:

receiving the induced grammar;

representing the induced grammar using a regular language; and

programming state transitions of a finite state machine to correspond to relationships represented in the regular language.

17. The apparatus of claim 16, wherein the sequence of instructions for the parser-generator further comprise configuring the processor to perform:

receiving additional annotations which specify fields to extract and how the fields map to the return values.

18. The apparatus of claim 13, wherein the sequence of instructions for the screen scraper further comprise configuring the processor to perform:

receiving the intercepted display information as an input to the finite state machine; and

producing the return values representing the extracted information.