Method and System for Extracting Web Query Interfaces

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.

1 - 21 . (canceled) 
   
   
       22 . A computer readable storage medium encoded with a computer program to be executed by a computer for extracting semantic information about a plurality of documents autonomously created by different sources and being accessible via a computer network, said computer readable storage medium comprising:
 a tokenizer for causing the computer to generate a set of tokens indicative of DOM nodes associated with visual information in a displayed document image from one of the plurality of autonomously created documents;   a grammar mechanism for causing the computer to derive a non-prescribed visual grammar from the set of tokens to represent a hidden syntax convention of a visual presentation; and   a best-effort parser for causing the computer to apply the derived visual grammar to construct multiple parse trees that represent semantic structure of the document and interpret as many of the set of tokens as the derived visual grammar can.   
   
   
       23 . The computer readable storage medium of  claim 22 , wherein said tokenizer for causing the computer to generate said set of tokens comprises computer executable instructions for:
 receiving a document in a mark-up language;   rendering said document by a layout engine into a document image;   extracting tokens indicative of DOM nodes with visual properties in the rendered document image; and   storing said tokens in a memory with visual properties.   
   
   
       24 . The computer readable storage medium of  claim 23 , wherein said visual properties include, for each token, the coordinates of the token in the displayed document image, the value of the token, the DOM path of the token in the DOM tree, the type of the token, and the name of the token. 
   
   
       25 . The computer readable storage medium of  claim 22 , wherein said non-prescribed visual grammar is derived from a plurality of autonomously created or heterogeneous Web documents to represent the hidden syntax convention of the visual presentation common among the plurality of autonomously created or heterogeneous Web documents. 
   
   
       26 . The computer readable storage medium of  claim 25  wherein said hidden syntax convention of visual presentation is derived by performing the following steps:
 observing the visual relationship of tokens on how they form semantic units, and deriving visual patterns to represent the semantic unit; and   observing precedence between different conflicting patterns and deriving pattern preference to represent their precedence.   
   
   
       27 . The computer readable storage medium of  claim 22  wherein said best-effort parser causes the computer to perform a procedure comprising of the steps of:
 building a schedule graph for determining an order of applying production rules;   building multiple parse trees simultaneously by grouping tokens using a set of production rules that represent visual patterns in determined orders;   pruning useless parse trees by checking a set of preference rules and that represent pattern precedence; and   outputting multiple potential useful parse trees that maximally cover the tokens in the document.   
   
   
       28 . The computer readable storage medium of  claim 27  wherein the step of building a schedule graph comprises:
 adding dependency edges from head symbol to each component symbol for each production rule;   adding restriction edges between two symbols for each preference rule;   transforming restriction edges when graph is acyclic; and   removing restriction edges if graph is still acyclic after said transformation.   
   
   
       29 . The computer readable storage medium of  claim 27  wherein the step of building multiple parse trees compromises the steps of:
 getting productions in the order determined by the schedule graph; and   applying each production (H, M, C, F), in the identified order, to generate new instances of the head H, from the instances of the components M, by using the construction function F, if the components M satisfy constraint C.   
   
   
       30 . The computer readable storage medium of  claim 27 , wherein the step of pruning useless parse trees compromises the steps of:
 for each newly generated instance, checking the conflicting condition of all preference rules to find all conflicts with existing instances; and   applying the winning criteria for conflict resolution to remove false instances.   
   
   
       31 . A method for extracting semantic information about a plurality of electronic documents autonomously created by different sources and being accessible via a computer network, comprising:
 accessing an electronic document via the computer network;   generating a set of tokens by a computer, the tokens indicative of DOM nodes associated with visual information in a displayed document image of the electronic document;   deriving a non-prescribed visual grammar from the set of tokens by the computer, to represent a hidden syntax convention of visual presentation in the displayed document image; and   applying said derived visual grammar by the computer to construct multiple parse trees that represent semantic structure of the electronic document and interpret as many of the set of tokens as said derived visual grammar can.   
   
   
       32 . The method of  claim 31 , wherein generating said set of tokens comprises:
 receiving data representing a document in a mark-up language;   rendering said document by a layout engine into a document image;   extracting tokens indicative of DOM nodes with visual properties in the rendered document image; and   storing said tokens in a memory with visual properties.   
   
   
       33 . The method of  claim 32 , wherein said visual properties include for each token, the coordinates of the token in the displayed document image, the value of the token, the DOM path of the token in the DOM tree, the type of the token, and the name of the token. 
   
   
       34 . The method of  claim 31 , wherein said non-prescribed visual grammar is derived from autonomous or heterogeneous Web documents to represent the hidden syntax convention of the visual presentation. 
   
   
       35 . The method of  claim 34  wherein said hidden syntax convention of visual presentation is derived by performing the following steps:
 observing the visual relationship of tokens on how they form semantic units, and deriving visual patterns to represent the semantic unit; and   observing precedence between different conflicting patterns and derive pattern preference to represent their precedence.   
   
   
       36 . The method of  claim 31  wherein said step of applying said derived visual grammar to construct multiple parse trees that represent semantic structure of the document and interpret as many tokens as said derived visual grammar can comprises the additional steps of:
 building a schedule graph for determining the order of applying production rules;   building multiple parse trees simultaneously by grouping tokens using production rules in determined orders;   pruning useless parse trees by checking preference rules; and   outputting multiple potential useful parse trees that maximally cover the tokens in the document.   
   
   
       37 . The method of  claim 36  wherein the step of building a schedule graph comprises:
 adding dependency edges from head symbol to each component symbol for each production rule;   adding restriction edges between two symbols for each preference rule;   transforming restriction edges when graph is acyclic; and   removing restriction edges if graph is still acyclic after said transformation.   
   
   
       38 . The method of  claim 36  wherein the step of building multiple parse trees compromises the steps of:
 getting productions in the order determined by the schedule graph; and   applying each production (H, M, C, F), in the identified order, to generate new instances of the head H, from the instances of the components M, by using the construction function F, if the components M satisfy constraint C.   
   
   
       39 . The method of  claim 36 , wherein the step of pruning useless parse trees compromises the additional steps of:
 for each newly generated instance, checking the conflicting condition of all preference rules to find all conflicts with existing instances; and   applying the winning criteria for conflict resolution to remove false instances.   
   
   
       40 . The computer readable storage medium of  claim 22 , wherein said non-prescribed visual grammar is derived from a plurality of autonomously created Web query forms to represent the hidden syntax convention among the plurality of autonomously created Web query forms. 
   
   
       41 . The method of  claim 31 , wherein said non-prescribed visual grammar is derived from a plurality of autonomously created Web query forms to represent the hidden syntax convention among the plurality of autonomously created Web query forms. 
   
   
       42 . A computer implemented system for extracting semantic information about a plurality of electronic documents autonomously created by different sources and being accessible via a computer network, comprising:
 a tokenizer for generating a set of tokens indicative of DOM nodes associated with visual information in a displayed document image from one of the plurality of autonomously created electronic documents accessed via the computer network;   a grammar mechanism for deriving a non-prescribed visual grammar from the set of tokens to represent a hidden syntax convention of a visual presentation; and   a best-effort parser for applying the derived visual grammar to construct multiple parse trees that represent semantic structure of the document and interpret as many of the set of tokens as the derived visual grammar can.   
   
   
       43 . The system of  claim 42 , wherein said visual properties include, for each token, the coordinates of the token in the displayed document image, the value of the token, the DOM path of the token in the DOM tree, the type of the token, and the name of the token. 
   
   
       44 . The system of  claim 42 , wherein said non-prescribed visual grammar is derived from a plurality of autonomously created or heterogeneous Web documents to represent the hidden syntax convention of the visual presentation common among the plurality of autonomously created or heterogeneous Web documents. 
   
   
       45 . The system of  claim 44  wherein said hidden syntax convention of visual presentation is derived by performing the following steps:
 observing the visual relationship of tokens on how they form semantic units, and deriving visual patterns to represent the semantic unit; and   observing precedence between different conflicting patterns and deriving pattern preference to represent their precedence.   
   
   
       46 . The system of  claim 42  wherein said best-effort parser performs a procedure comprising the steps of:
 building a schedule graph for determining the order of applying production rules;   building multiple parse trees simultaneously by grouping tokens using production rules in determined orders;   pruning useless parse trees by checking preference rules; and   outputting multiple potential useful parse trees that maximally cover the tokens in the document.   
   
   
       47 . The system of  claim 46 , wherein the step of building a schedule graph comprises:
 adding dependency edges from head symbol to each component symbol for each production rule;   adding restriction edges between two symbols for each preference rule;   transforming restriction edges when graph is acyclic; and   removing restriction edges if graph is still acyclic after said transformation.   
   
   
       48 . system of  claim 47 , wherein the step of building multiple parse trees compromises the steps of:
 getting productions in the order determined by the schedule graph; and   applying each production (H, M, C, F), in the identified order, to generate new instances of the head H, from the instances of the components M, by using the construction function F, if the components M satisfy constraint C.   
   
   
       49 . The system of  claim 47 , wherein the step of pruning useless parse trees compromises the steps of:
 for each newly generated instance, checking the conflicting condition of all preference rules to find all conflicts with existing instances; and   applying the winning criteria for conflict resolution to remove false instances.