Machine Identification of Grammar Rules That Match a Search Query

Patent metadata

Field	Value
Publication number	US-2017193099-A1
Application number	US-201615396643-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 receives a first grammar rule and a second grammar rule via a network communication device. The first grammar rule specifies a first set of entity types and the second grammar rule specifies a second set of entity types. The intersection of the first and second sets includes at least one entity type. The search server generates a first grammar tree to represent the first grammar rule and a second grammar tree to represent the second grammar rule. The first root node of the first grammar tree and a second root node of the second grammar tree are identical. The search server merges the first and second grammar trees to form a merged grammar tree that represents a union of the first and second sets of entity types. The search server optimizes the merged grammar tree by purging duplicate nodes from each level of the merged grammar tree.

First claim

What is claimed is:

1 . A search server comprising:
a network communication device; and a processing device that executes computer-readable instructions that, when executed by the processing device, cause the processing device to:
receive a first grammar rule and a second grammar rule via the network communication device, wherein the first grammar rule specifies a first set of entity types and the second grammar rule specifies a second set of entity types, and wherein the intersection of the first set and the second set comprises at least one entity type;
generate a first grammar tree to represent the first grammar rule and a second grammar tree to represent the second grammar rule, wherein a first root node of the first grammar tree and a second root node of the second grammar tree are identical;
merge the first grammar tree and the second grammar tree to form a merged grammar tree that represents a union of the first set of entity types and the second set of entity types; and
optimize the merged grammar tree by purging duplicate nodes from each level of the merged grammar tree.

2 . The search server of claim 1 , wherein generating the first grammar tree comprises:
instantiating a tree data structure; identifying the first set of entity types; instantiating a tree node for each entity type in the first set of entity types; and instantiating tree edges to connect the tree nodes that correspond with adjacent entity types.

3 . The search server of claim 1 , wherein the first root node of the first grammar tree represents a starting point for the first grammar rule and the second root node of the second grammar tree represents a starting point for the second grammar rule.

4 . The search server of claim 1 , wherein merging the first grammar tree and the second grammar tree comprises:
purging the second root node of the second grammar tree; and appending child nodes of the second root node to the first root node of the first grammar tree as child nodes of the first root node.

5 . The search server of claim 4 , wherein merging the first grammar tree and the second grammar tree further comprises:
determining a first value that represents a size of the first grammar tree; determining a second value that represents a size of the second grammar tree; and determining that the second value is smaller than the first value.

6 . The search server of claim 1 , wherein optimizing the merged grammar tree comprises:
determining that a first node and a second node on a particular level of the merged grammar tree are identical; purging the second node; and appending child nodes of the second node to the first node as child nodes of the first node.

7 . The search server of claim 1 , wherein the computer-readable instructions further cause the processing device to:
receive a search query via the network communication device; and utilize the merged grammar tree to determine whether the search query satisfies the first grammar rule and/or the second grammar rule.

8 . The search server of claim 7 , wherein determining whether the search query satisfies the first grammar rule and/or the second grammar rule comprises:
tokenizing the search query to generate tokens; utilizing the tokens to form n-grams; identifying entity types associated with the n-grams; generating a mapping of the entity types and token start positions of the entity types to token end positions of the entity types; and utilizing the mapping to determine whether the search query matches the first grammar rule and/or the second grammar rule.

9 . The search server of claim 8 , wherein generating the mapping comprises:
generating a first mapping mechanism that maps the token start positions and token end positions to the entity types; generating a second mapping mechanism by inverting the first mapping mechanism, wherein the second mapping mechanism maps the entity types to the token start positions and the token end positions; and generating a third mapping mechanism by transforming the second mapping mechanism, wherein the third mapping mechanism maps the entity types and the token start positions of the entity types to the token end positions of the entity types.

10 . The search server of claim 8 , wherein utilizing the mapping comprises:
initiating a token index and setting the token index to zero; initiating a level index and setting the level index to one; querying the mapping with the token index to identify the entity type that starts at the token index; determining that the merged grammar tree includes a node for the identified entity type at a level indicated by the level index; retrieving the end token position of the entity type from the mapping; setting the token index to one plus the end token position; incrementing the level index by one; and determining that the token index points to null and the level index points to the end of the first grammar rule or the second grammar rule.

11 . The search server of claim 7 , wherein the computer-readable instructions further cause the processing device to:
determine a set of entity types that the search query must include in order to utilize the merged grammar tree for grammar matching; and store the entity types in the set as a list in a storage device.

12 . The search server of claim 11 , wherein utilizing the merged grammar tree comprises:
retrieving the list from the storage device; and determining that the search query includes the entity types specified in the list.

13 . A computer program product encoded on a non-transitory computer readable storage medium comprising instructions that when executed by a processing device cause the processing device to perform operations comprising:
receiving a first grammar rule and a second grammar rule via a network communication device, wherein the first grammar rule specifies a first set of entity types and the second grammar rule specifies a second set of entity types, and wherein the intersection of the first set and the second set comprises at least one entity type; generating a first grammar tree to represent the first grammar rule and a second grammar tree to represent the second grammar rule, wherein a first root node of the first grammar tree and a second root node of the second grammar tree are identical; merging the first grammar tree and the second grammar tree to form a merged grammar tree that represents a union of the first set of entity types and the second set of entity types; optimizing the merged grammar tree by purging duplicate nodes from each level of the merged grammar tree; receiving a search query via the network communication device; and utilizing the merged grammar tree to determine whether the search query satisfies the first grammar rule and/or the second grammar rule.

14 . The computer program product of claim 13 , wherein generating the first grammar tree comprises:
instantiating a tree data structure; identifying the first set of entity types; instantiating a tree node for each entity type in the first set of entity types; and instantiating tree edges to connect the tree nodes that correspond with adjacent entity types.

15 . The computer program product of claim 13 , wherein merging the first grammar tree and the second grammar tree comprises:
purging the second root node of the second grammar tree; and appending child nodes of the second root node to the first root node of the first grammar tree as child nodes of the first root node.

16 . The computer program product of claim 13 , wherein determining whether the

Assignees

• Quixey Inc

Inventors

• Ben-Tzur Jonathan
• Glover Eric

Classifications

• G06F16/332 Primary

  Query formulation · CPC title

• G06F17/30625

  Physics · mapped topic

• G06F17/30637

  Physics · mapped topic

• G06F17/30734 Primary

  Physics · mapped topic

• G06F17/30634

  Physics · mapped topic