PARTIAL MATCH DERIVATION USING TEXT ANALYSIS

• US 20140337383A1
• Filed: 05/10/2013
• Published: 11/13/2014
• Est. Priority Date: 05/10/2013
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Boyle, Peter C., Rozsa, Eniko I., Trim, Craig M., Edwards, Stephen J., Povar, Victor, Salah El Din Ahmed, Ibrahim Mohamed, Serour Mousa El-Gamal, Ahmed Samir, Turner, Claire R.
• Granted Patent: US 9,268,823 B2
• Time in Patent Office: Days
• US Class Current: 707/780
• 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 when a natural language input query does not fully specify an entity, comprising:

receiving, using a computer processor, the 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(s) 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 entity(s) corresponding to each partial match query token; and

determining, using the computer processor, that the input query relates to a plurality of entities 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.

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

determining, using the computer processor, that the input query relates to a single entity if there is an intersection between the entity(s) corresponding to each partial match query token.

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 entities, 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 when a natural language input query does not fully specify an entity, 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 the 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(s) 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 entity(s) corresponding to each partial match query token; and

determine that the input query relates to a plurality of entities 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.

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

determine that the input query relates to a single entity if there is an intersection between the entity(s) corresponding to each partial match query token.

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 a 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 entity(s) corresponding to each partial match query token; and

selecting, using the computer processor, the identified entity(s) corresponding to each partial match query token 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.

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

determining, using the computer processor, that the input query relates to a single entity if there is an intersection between the entity(s) corresponding to each partial match query token.

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.