Machine Processing of Search Query based on Grammar Rules

Patent metadata

Field	Value
Publication number	US-2017193095-A1
Application number	US-201615396648-A
Country	US
Kind code	A1
Filing date	Dec 31, 2016
Priority date	Dec 31, 2015
Publication date	Jul 6, 2017
Grant date	—

Abstract

A search server stores a plurality of keywords, each associated with an entity type. The server stores grammar rules, each specifying one or more entity types. The server receives a search query with search terms and generates tokens by splitting the search terms, each token associated with a token position that indicates a location of the token within the query. The server generates n-grams. Each n-gram is associated with a start token position and an end token position. The server determines entity types for n-grams that correspond to the keywords and generates a mapping that maps the received entity types and the start token positions of the n-grams that correspond with the received entity types to the end token positions of the n-grams that correspond with the received entity types. The server identifies grammar rules based on the mapping and transmits a result based on the identified grammar rules.

First claim

What is claimed is:

1 . A search server comprising:
a network communication device; a storage device comprising:
a keyword data store that stores a plurality of keywords, wherein each keyword is associated with an entity type, the entity type representing a category of entities, an entity being a physical object or a logical object; and
a grammar data store that stores grammar rules, wherein each grammar rule specifies one or more entity types and each grammar rule is associated with an access mechanism that provides access to an application; and
a processing device that executes computer-readable instructions that, when executed by the processing device, cause the processing device to:
receive a search request via the network communication device, the search request comprising a search query with one or more search terms;
generate tokens by splitting the search terms with a defined delimiter, wherein each token is associated with a token position that indicates a location of the token within the search query;
generate n-grams by selecting individual tokens and/or contiguous sequences of tokens, wherein each n-gram is associated with a start token position that indicates a start location of the first token of the n-gram within the search query and an end token position that indicates an end location of the last token of the n-gram within the search query;
query the keyword data store with the n-grams and receive the entity types for n-grams that correspond with the keywords stored in the keyword data store;
generate a mapping that maps the received entity types and the start token positions of the n-grams that correspond with the received entity types to the end token positions of the n-grams that correspond with the received entity types;
identify grammar rules that match the search query by querying the grammar data store for grammar rules that specify the entity types included in the mapping; and
transmit a search result object that comprises access mechanisms that are associated with the grammar rules that match the search query.

2 . The search server of claim 1 , wherein generating the mapping comprises:
generating a first mapping mechanism that maps the start token positions and the end token positions of the n-grams to the entity types associated with the n-grams; inverting the first mapping mechanism to generate a second mapping mechanism that maps the entity types associated with the n-grams to the start token positions and the end token positions of the n-grams; and modifying the second mapping mechanism to generate a third mapping mechanism that maps the entity types associated with the n-grams and the start token positions of the n-grams to the end token positions of the n-grams.

3 . The search server of claim 2 , wherein:
generating the first mapping mechanism comprises generating a chart parse; inverting the first mapping mechanism comprises inverting the chart parse to generate an inverse chart parse; and modifying the second mapping mechanism comprises augmenting the inverse chart parse to generate an augmented inverse chart parse.

4 . The search server of claim 1 , wherein identifying the grammar rules that match the search query comprises filtering out grammar rules that do not include all the entity types specified in the mapping.

5 . The search server of claim 4 , wherein identifying the grammar rules comprises verifying that the grammar rules that include all the entity types specified in the mapping do not include additional entity types that are not specified in the mapping.

6 . The search server of claim 5 , wherein identifying the grammar rules comprises determining that the search query matches a grammar rule if the grammar rule specifies all the entity types in the mapping and the grammar rule specifies no additional entity types.

7 . The search server of claim 1 , wherein transmitting the search result object comprises:
instantiating a data container; retrieving the access mechanisms for the matching grammar rules from the grammar data store; and writing the access mechanisms to the data container.

8 . A server that categorizes search queries, the server comprising:
a network communication device; a storage device comprising:
a keyword data store that stores a plurality of keywords, wherein each keyword is associated with an entity type, the entity type representing a category of entities, an entity being a physical object or a logical object; and
a grammar data store that stores grammar rules, wherein each grammar rule specifies one or more entity types and each grammar rule is associated with a query category; and
a processing device that executes computer-readable instructions that, when executed by the processing device, cause the processing device to:
receive a search request via the network communication device, the search request comprising a search query with one or more search terms;
generate tokens by splitting the search terms with a defined delimiter, wherein each token is associated with a token position that indicates a location of the token within the search query;
generate n-grams by selecting individual tokens and/or contiguous sequences of tokens, wherein each n-gram is associated with a start token position that indicates a start location of the first token of the n-gram within the search query and an end token position that indicates an end location of the last token of the n-gram within the search query;
query the keyword data store with the n-grams and receive the entity types for n-grams that correspond with the keywords stored in the keyword data store;
generate a mapping that maps the received entity types and the start token positions of the n-grams that correspond with the received entity types to the end token positions of the n-grams that correspond with the received entity types;
identify grammar rules that match the search query by querying the grammar data store for grammar rules that specify the entity types included in the mapping; and
categorize the search query into the query category associated with the grammar rule that matches the search query.

9 . The server of claim 8 , wherein generating the mapping comprises:
generating a first mapping mechanism that maps the start token positions and the end token positions of n-grams to the entity types associated with the n-grams; inverting the first mapping mechanism to generate a second mapping mechanism that maps the entity types associated with the n-grams to the start token positions and the end token positions of the n-grams; and modifying the second mapping mechanism to generate a third mapping mechanism that maps the entity types associated with the n-grams and the start token positions of the n-grams to the end token positions of the n-grams.

10 . The server of claim 9 , wherein:
generating the first mapping mechanism comprises generating a chart parse; inverting the first mapping mechanism comprises inverting the chart parse to generate an inverse chart parse; and modifying the second mapping mechanism comprises augmenting the inverse chart parse to generate an augmented inverse chart parse.

11 . The server of claim 8 , wherein identifying the grammar rules that match the search query comprises filtering out grammar rules that do not include all the entity types specified in the mapping.

12 . The server of claim 11 , wherein identifying the grammar rules comprises verifying that the grammar rules that include all the entity types specified in the mapping do not include additional entity types that are not specified in the mapping.

13 . The server of claim 12 ,

Assignees

• Quixey Inc

Inventors

• Ben-Tzur Jonathan
• Glover Eric

Classifications

• G06F40/30

  Semantic analysis · CPC title

• G06F16/35

  Clustering; Classification · CPC title

• G06F16/3334

  Selection or weighting of terms from queries, including natural language queries · CPC title

• G06F40/253

  Grammatical analysis; Style critique · CPC title

• G06F16/319

  Inverted lists · CPC title