Real time parsing and suggestions from pre-generated corpus with hypernyms

• US 10,289,680 B2
• Filed: 05/31/2016
• Issued: 05/14/2019
• Est. Priority Date: 05/31/2016
• Status: Active Grant

• Current Assignee: Yahoo Assets LLC
• Original Assignee: Oath Inc. (Verizon Communications Inc.)
• Inventors: Scally, Jonathan R., Caneba, Richard, Cassimatis, Nick
• Primary Examiner(s): Yang, Qian
• Application Number:
  US15/169,101
• Publication Number:
  US 20170344534A1
• Time in Patent Office: 1,078 Days
• CPC Class Codes: G06F 16/3344 using natural language analysis
• CPC Class Codes: G06F 16/374 Thesaurus
• CPC Class Codes: G06F 16/90332 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/247 Thesauruses; Synonyms
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

Systems and methods of natural language processing in an environment with no existing corpus are disclosed. The method includes defining an input grammar specific to a chosen domain, the input grammar having a domain specific knowledge and general grammatical knowledge. Groups of tokens are identified within the input grammar having syntactic and semantic equivalence. The identified groups are assembled into hypernyms, wherein the hypernyms include a semantic output for each token in the hypernyms. A list of fields is then combined with the hypernyms for combination with the hypernyms. A corpus of possible combinations of hypernyms and fields is created. A data structure mapping each possible combination to a partial semantic output is generated and the data structure is saved for use in later processing.

Claims

1. A method for determining semantics of domain queries comprising:

receiving an input query string from a remote device via a network connection;

pre-defining an input grammar data structure specific to a chosen domain, the input grammar data structure comprising tokens identified by semantic identifiers and syntactic identifiers;

identifying semantic groups of tokens corresponding to the semantic identifiers within the input grammar data structure having syntactic equivalence as signified by the syntactic identifiers;

assembling each one of the identified semantic groups into a hypernym to obtain a plurality of hypernyms, wherein the hypernym comprises a hypernym data structure including a hypernym identifier combining a corresponding semantic identifier and syntactic identifier of the each one of the identified semantic groups, and tokens of the each one of the identified semantic groups mapped to semantic outputs, wherein at least one of the semantic outputs corresponding to one of the tokens includes a semantic identifier linking to another hypernym;

providing a list of fields for combination with the plurality of hypernyms, wherein the list of fields comprises text fields for input of names and keywords and custom tokens for input of dates and locations;

generating a corpus of valid combinations of hypernyms and fields, based on at least some of the plurality of hypernyms and at least some of the list of fields, according to a set of grammatical rules;

generating a first mapping data structure mapping each valid combination to a partial semantic output by combining the semantic outputs of the hypernym data structure;

determining semantics of the input query string based on a tokenization of the input query string, the corpus, and the first mapping data structure; and

transmitting, to the remote device, a communication associated with a meaning of the input query string based on the semantics.

2. The method of claim 1, wherein the corpus of valid combinations includes all valid combinations less than a given length.

3. The method of claim 1, further comprising generating a second mapping data structure mapping partial tokens to each valid combination whose first several tokens match the partial tokens.

4. The method of claim 3, wherein determining semantics of the input query string based on the tokenization of the input query string, the corpus, and the first mapping data structure comprises:

tokenizing the input query string based on the input grammar data structure to obtain the tokenization of the input query string;

identifying a combination of hypernyms and fields in the corpus that matches a portion of the tokenization; and

determining the semantics of the input query string based on the combination and the first mapping data structure.

5. The method of claim 1, further comprising filtering the corpus to remove pragmatically irrelevant items.

6. The method of claim 1, wherein the input grammar data structure comprises a lexicon, grammatical structures, and a semantic output for each lexical item in the lexicon.

7. The method of claim 1, wherein determining semantics of the input query string based on the tokenization of the input query string, the corpus, and the first mapping data structure comprises:

tokenizing the input query string based on the input grammar data structure to obtain the tokenization of the input query string;

identifying a combination of hypernyms and fields in the corpus that matches the tokenization; and

determining the semantics of the input query string based on the combination and the first mapping data structure.

8. A system, comprising:

a processor; and

memory storing computer executable instructions that cause the processor to perform acts comprising;

receiving an input query string from a remote device via a network connection;

pre-defining an input grammar data structure specific to a chosen domain, the input grammar data structure comprising tokens identified by semantic identifiers and syntactic identifiers;

identifying semantic groups of tokens corresponding to the semantic identifiers within the input grammar data structure having syntactic equivalence as signified by the syntactic identifiers;

assembling each one of the identified semantic groups into a hypernym to obtain a plurality of hypernyms, wherein each hypernym comprises a hypernym data structure including a hypernym identifier combining a corresponding semantic identifier and syntactic identifier of at least one of the identified semantic groups, and tokens of at least one of the identified semantic groups mapped to semantic outputs, wherein at least one of the semantic outputs corresponding to at least one of the tokens includes a semantic identifier linking to another hypernym;

providing a list of fields for combination with the plurality of hypernyms, wherein the list of fields comprises text fields for input of names and keywords and custom tokens for input of dates and locations;

generating a corpus of valid combinations of hypernyms and fields, based on at least some of the plurality of hypernyms and at least some of the list of fields, according to a set of grammatical rules;

generating a first mapping data structure mapping each valid combination to a partial semantic output by combining the semantic outputs of the hypernym data structure;

determining semantics of the input query string based on a tokenization of the input query string, the corpus, and the first mapping data structure; and

transmitting, to the remote device, a communication associated with a meaning of the input query string based on the semantics.

9. The system of claim 8, wherein the corpus of valid combinations includes all valid combinations less than a given length.

10. The system of claim 8, the acts further comprising generating a second mapping data structure mapping partial tokens to each valid combination whose first several tokens match the partial tokens.

11. The system of claim 8, the acts further comprising filtering the corpus to remove pragmatically irrelevant items.

12. The system of claim 8, wherein the input grammar data structure comprises a lexicon, grammatical structures, and a semantic output for each lexical item in the lexicon.

13. The system of claim 8, wherein determining semantics of the input query string based on the tokenization of the input query string, the corpus, and the first mapping data structure comprises:

tokenizing the input query string based on the input grammar data structure to obtain the tokenization of the input query string;

identifying a combination of hypernyms and fields in the corpus that matches the tokenization; and

determining the semantics of the input query string based on the combination and the first mapping data structure.

14. A non-transitory computer readable medium storing computer executable instructions that when executed by a processor cause the processor to perform acts comprising:

receiving an input query string from a remote device via a network connection;

pre-defining an input grammar data structure specific to a chosen domain, the input grammar data structure comprising tokens identified by semantic identifiers and syntactic identifiers;

identifying semantic groups of tokens corresponding to the semantic identifiers within the input grammar data structure having syntactic equivalence as signified by the syntactic identifiers;

assembling each one of the identified semantic groups into a hypernym to obtain a plurality of hypernyms, wherein each hypernym comprises a hypernym data structure including a hypernym identifier combining a corresponding semantic identifier and syntactic identifier of at least one of the identified semantic groups, and tokens of at least one of the identified semantic groups mapped to semantic outputs, wherein at least one of the semantic outputs corresponding to at least one of the tokens includes a semantic identifier linking to another hypernym;

providing a list of fields for combination with the plurality of hypernyms, wherein the list of fields comprises text fields for input of names and keywords and custom tokens for input of dates and locations;

generating a corpus of valid combinations of hypernyms and fields, based on at least some of the plurality of hypernyms and at least some of the list of fields, according to a set of grammatical rules;

generating a first mapping data structure mapping each valid combination to a partial semantic output by combining the semantic outputs of the hypernym data structure;

determining semantics of the input query string based on a tokenization of the input query string, the corpus, and the first mapping data structure; and

transmitting, to the remote device, a communication associated with a meaning of the input query string based on the semantics.

15. The computer readable medium of claim 14, wherein the corpus of valid combinations includes all valid combinations less than a given length.

16. The computer readable medium of claim 14, the acts further comprising generating a second mapping data structure mapping partial tokens to each valid combination whose first several tokens match the partial tokens.

17. The computer readable medium of claim 14, the acts further comprising filtering the corpus to remove pragmatically irrelevant items.

18. The computer readable medium of claim 14, wherein the input grammar data structure comprises a lexicon, grammatical structures, and a semantic output for each lexical item in the lexicon.

19. The computer readable medium of claim 14, wherein determining semantics of the input query string based on the tokenization of the input query string, the corpus, and the first mapping data structure comprises:

tokenizing the input query string based on the input grammar data structure to obtain the tokenization of the input query string;

identifying a combination of hypernyms and fields in the corpus that matches the tokenization; and

determining the semantics of the input query string based on the combination and the first mapping data structure.