Method and system for extracting web query interfaces

• US 20060031202A1
• Filed: 08/06/2004
• Published: 02/09/2006
• Est. Priority Date: 08/06/2004
• Status: Active Grant

• Current Assignee: Board of Trustees of The University of Illinois
• Original Assignee: Board of Trustees of The University of Illinois
• Inventors: Zhang, Zhen, He, Bin, Chang, Kevin Chen-Chuan
• Granted Patent: US 7,552,116 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 40/174 Form filling; Merging
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99936 Pattern matching access

Abstract

A computer program product being embodied on a computer readable medium for extracting semantic information about a plurality of documents being accessible via a computer network, the computer program product including computer-executable instructions for: generating a plurality of tokens from at least one of the documents, each token being indicative of a displayed item and a corresponding position; and, constructing at least one parse tree indicative of a semantic structure of the at least one document from the tokens dependently upon a grammar being indicative of presentation conventions.

Claims

1. A computer program product being embodied on a computer readable medium for extracting semantic information about a plurality of documents being accessible via a computer network, said computer program product comprising computer-executable instructions for:

generating a plurality of tokens from at least one of the documents, each token being indicative of a displayed item and a corresponding position; and

,

constructing at least one parse tree indicative of a semantic structure of the at least one document from said tokens dependently upon a grammar being indicative of presentation conventions.

2. The product of claim 1, wherein said grammar provides a plurality of parsing rules.

3. The product of claim 1, wherein the parse tree Is associated with the document as a whole and groups tokens dependently upon their semantic roles.

4. The product of claim 3, wherein each of said tokens is indicative of an independent visual unit of one of the documents.

5. The product of claim 4, wherein said constructing at least one parse tree comprises enforcing at least one precedence.

6. The product of claim 5, wherein said at least one precedence is suitable for resolving at least one potential ambiguity.

7. The product of claim 1, wherein the grammar takes the form of a five-tuple (Σ

, N, s, P_d, P_f), where Σ

is a set of terminal symbols, N is a set of nonterminal symbols. sε

N is a start symbol, P_d is a set of production rules, and P_f is a set of preference rules.

8. The product of claim 1, wherein said generating the plurality of tokens is dependent upon HTML DOM API.

9. The product of claim 1, wherein the presentation conventions include topology and proximity.

10. A web querying device comprising:

a form extractor for generating a plurality of tokens from at least one of the documents, each token being indicative of a displayed item and a corresponding position; and

,

a soft parser for constructing at least one parse tree indicative of a semantic structure of the at least one document from said tokens dependently upon a grammar being indicative of presentation conventions.

11. The device of claim 10, wherein said grammar provides a plurality of parsing rules.

12. The device of claim 11, wherein the parse tree is associated with the document as a whole and groups tokens dependently upon their semantic roles.

13. The device of claim 12, wherein each of said tokens is indicative of an independent visual unit of one of the documents.

14. The device of claim 13, wherein said constructing a parse tree comprises enforcing at least one precedence.

15. The device of claim 14, wherein said at least one precedence is suitable for resolving at least one potential ambiguity.

16. The device of claim 15, wherein the grammar takes the form of a five-tuple (Σ

, N, s, P_d, P_f), where Σ

is a set of terminal symbols, N is a set of nonterminal symbols. sε

N is a start symbol, P_d is a set of production rules, and P_f is a set of preference rules.

17. The device of claim 16, wherein said generating the plurality of tokens is dependent upon HTML DOM API.

18. The device of claim 17, wherein the presentation conventions include topology and proximity.

19. A device for automatically querying a plurality of electronic query documents comprising:

means for generating a plurality of tokens from at least one of the documents, each token being indicative of a displayed item and a corresponding position; and

,

means for constructing at least one parse tree indicative of a semantic structure of the at least one document from said tokens dependently upon a grammar being indicative of presentation conventions.

20. The device of claim 19, wherein a pattern P in a grammar G=(Σ

, N, s, P_d, P_f) is a four-tuple (H, M, C, F), where head Hε

N is a nonterminal symbol;

components M⊂

Σ

∪

N is a multiset of symbols;

constraint C is a Boolean expression defined on M; and

Constructor F is a function defined on M, returning an instance of H.

21. A method for extracting semantic information about a plurality of documents being accessible via a computer network, said method comprising:

generating a plurality of tokens from at least one of the documents, each token being indicative of a displayed item and a corresponding position; and

,

constructing at least one parse tree indicative of a semantic structure of the at least one document from said tokens dependently upon a grammar being indicative of presentation conventions.