Partial match derivation using text analysis

• US 9,471,627 B2
• Filed: 01/02/2016
• Issued: 10/18/2016
• Est. Priority Date: 05/10/2013
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Boyle, Peter C., Edwards, Stephen J., Povar, Victor, Rozsa, Eniko I., Salah El Din Ahmed, Ibrahim Mohamed, Serour Mousa El-Gamal, Ahmed Samir, Trim, Craig M., Turner, Claire R.
• Primary Examiner(s): Fan, Shiow-jy
• Application Number:
  US14/986,666
• Publication Number:
  US 20160117361A1
• Time in Patent Office: 290 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/24522 Translation of natural language queries to structured queries
• CPC Class Codes: G06F 16/2468 Fuzzy queries

Abstract

A natural language processing system and method resolves partial matches when a natural language input query does not fully specify an entity. The input query is tokenized into a set of query tokens, which are compared to contents of a searchable index, the contents representing entities, each of which is tokenized into a set of entity tokens associated with the tokenized entity. A plurality of partial match query tokens are identified from the set of query tokens, each partial match query token matching at least one entity token in the index. The entity(s) corresponding to each partial match query token are selected if a sequential break exists in the input query between the partial match query tokens and there is no intersection between the entity(s) corresponding to each partial match query token.

Claims

1. A computer implemented natural language processing method for resolving partial matches, comprising:

receiving, using a computer processor, a natural language input query that does not fully specify an entity;

tokenizing, using the computer processor, the input query into a constituent set of query tokens;

searching, using the computer processor, an entity index by comparing the query tokens to contents of the index, the contents representing a plurality of entities, each of which is tokenized into a constituent set of entity tokens associated with the tokenized entity;

identifying, using the computer processor, a plurality of partial match query tokens from the set of query tokens, each partial match query token matching at least one entity token in the index;

determining, using the computer processor, whether a sequential break exists in the input query between the partial match query tokens;

for each partial match query token, determining, using the computer processor, the entity corresponding to each partial match query token by identifying the entity associated with each entity token in the index that matches the partial match query token;

determining, using the computer processor, whether there is an intersection between the identified entities corresponding to the partial match query tokens; and

when a sequential break exists in the input query between the partial match query tokens and there is no intersection between the identified entities corresponding to the partial match query tokens

determining, using the computer processor, that the input query relates to a plurality of entities, and

presenting a response to the received natural language input query to a user based upon the identified entities.

2. The computer-implemented method according to claim 1, further comprising:

when there is an intersection between the identified entities corresponding to the partial match query tokens

resolving and reducing the identified entities into a single entity, and

presenting a response to the received natural language input query to the user based upon the single entity.

3. The computer-implemented method according to claim 1, wherein the constituent set of entity tokens associated with the tokenized entity in the index are derived by the processor using a combination of language modeling principles of high-frequency products, n-gram modeling and TF-IDF tokenization techniques.

4. The computer-implemented method according to claim 1, wherein the constituent set of entity tokens associated with the tokenized entity in the index includes information obtained from an external source.

5. The computer-implemented method according to claim 1, wherein the constituent set of entity tokens associated with the tokenized entity in the index includes morphological variations of the tokenized entity.

6. The computer-implemented method according to claim 1, wherein each entity in the entity index is a product name.

7. The computer-implemented method according to claim 1, further comprising:

generating, using the computer processor, a query response to a user that initiated the input query, the query response requesting information from the user about the input query;

transmitting, using the computer processor, the query response to the user; and

receiving information from the user in response to the query response.

8. The computer-implemented method according to claim 7, wherein the query response includes a set of choices that the user may select from to respond to the query response.

9. A natural language processing system for resolving partial matches, comprising:

a computer processor;

an index stored in computer memory and searchable by the computer processor, the index having contents representing a plurality of entities, each entity having been tokenized into a constituent set of entity tokens associated with the tokenized entity; and

computer memory, the computer memory storing a series of program instructions, wherein the program instructions are executable by the computer processor to;

receive a natural language input query that does not fully specify an entity;

tokenize the input query into a constituent set of query tokens;

search the index by comparing the query tokens to the entity tokens in the index;

identify a plurality of partial match query tokens from the set of query tokens, each partial match query token matching at least one entity token in the index;

determine whether a sequential break exists in the input query between the partial match query tokens;

for each partial match query token, determine the entity corresponding to each partial match query token by identifying the entity associated with each entity token in the index that matches the partial match query token;

determine whether there is an intersection between the identified entities corresponding to the partial match query tokens; and

when a sequential break exists in the input query between the partial match query tokens and there is no intersection between the identified entities corresponding to the partial match query tokens

determine that the input query relates to a plurality of entities, and

generate and provide a response to the received natural language input query to a user based upon the identified entities.

10. The natural language processing system according to claim 9, wherein the program instructions, when executed, further cause the computer processor to:

when there is an intersection between the identified entities corresponding to the partial match query tokens

resolve and reduce the identified entities into a single entity, and

generate and provide a response to the received natural language input query to the user based upon the single entity.

11. The natural language processing system according to claim 9, wherein the constituent set of entity tokens associated with the tokenized entity in the index are derived by the processor using a combination of language modeling principles of high-frequency entities, n-gram modeling and TF-IDF tokenization techniques.

12. The natural language processing system according to claim 9, wherein the constituent set of entity tokens associated with the tokenized entity in the index includes information obtained from an external source.

13. The natural language processing system according to claim 9, wherein the constituent set of entity tokens associated with the tokenized entity in the index includes morphological variations of the tokenized entity.

14. The natural language processing system according to claim 9, wherein each entity in the index is a product name.

15. The natural language processing system according to claim 9, wherein the program instructions, when executed, further cause the computer processor to:

generate a query response to a user that initiated the input query, the query response requesting information from the user about the input query;

transmit the query response to the user; and

receive information from the user in response to the query response.

16. The natural language processing system according to claim 15, wherein the query response includes a set of choices that the user may select from to respond to the query response.

17. A computer implemented natural language processing method for resolving partial matches when a natural language input query does not fully specify an entity, comprising:

tokenizing, using a computer processor, the input query into a constituent set of query tokens;

comparing the query tokens to contents of an index searchable by the processor, the contents representing a plurality of entities, each of which is tokenized into a constituent set of entity tokens associated with the tokenized entity;

identifying, using the computer processor, a plurality of partial match query tokens from the set of query tokens, each partial match query token matching at least one entity token in the index;

determining, using the computer processor, whether there is a sequential break in the input query between the partial match query tokens;

for each partial match query token, identifying, using the computer processor, the entity associated with each entity token in the index that matches the partial match query token;

determining, using the computer processor, whether there is an intersection between the identified entities corresponding to the partial match query tokens; and

when a sequential break exists in the input query between the partial match query tokens and there is no intersection between the identified entities corresponding to the partial match query tokens

determining, using the computer processor, that the input query relates to a plurality of entities, and

generate and provide a response to the received natural language input query to a user based upon the identified entities.

18. The computer-implemented method according to claim 17, further comprising:

when there is an intersection between the identified entities corresponding to the partial match query tokens

resolving and reducing the identified entities into a single entity, and

generate and provide a response to the received natural language input query to the user based upon the single entity.

19. The computer-implemented method according to claim 17, further comprising:

generating, using the computer processor, a query response to the input query, the query response requesting information about the input query;

transmitting, using the computer processor, the query response to the user; and

receiving information from the user in response to the query response.

20. The computer-implemented method according to claim 19, wherein the query response includes a set of choices that the user may select from to respond to the query response.