Suggesting and refining user input based on original user input

• US 20060253427A1
• Filed: 05/04/2005
• Published: 11/09/2006
• Est. Priority Date: 05/04/2005
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Lin, Dekang, Zhou, Jie, Wu, Jun, Qian, Zhe
• Granted Patent: US 8,438,142 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/242 Query formulation
• CPC Class Codes: G06F 16/24578 using ranking
• CPC Class Codes: G06F 16/3322 using system suggestions G06F16/3325 takes precedence
• CPC Class Codes: G06F 16/90324 using system suggestions

Abstract

Systems and methods to generate modified/refined user inputs based on the original user input, such as a search query, are disclosed. The method may be implemented for Roman-based and/or non-Roman based language such as Chinese. The method may generally include receiving an original user input and identifying core terms therein, determining potential alternative inputs by replacing core term(s) in the original input with another term according to a similarity matrix and/or substituting a word sequence in the original input with another word sequence according to an expansion/contraction table where one word sequence is a substring of the other, computing likelihood of each potential alternative input, and selecting most likely alternative inputs according to a predetermined criteria, e.g., likelihood of the alternative input being at least that of the original input. A cache containing pre-computed original user inputs and corresponding alternative inputs may be provided.

Claims

1. A method for suggesting alternative user inputs, comprising:

receiving an original user input, the input having at least one core term;

identifying the at least one core term in the original user input;

determining at least one potential alternative user input by performing at least one of (a) replacing at least one core term in the original user input with another term according to a similarity matrix, the similarity matrix having a similarity value between the two terms and (b) substituting a sequence of words in the original user input with another sequence of words according to an expansion/contraction table, one sequence being a substring of the other sequence, the expansion/contraction table having frequency values associated with sequence of terms;

computing likelihoods of the potential alternative user inputs; and

selecting one or more most likely alternative user inputs from the at least one potential alternative user input according to a predetermined criteria.

2. The method of claim 1, wherein the predetermined criteria for selecting the one or more most likely alternative user inputs includes the likelihoods of the selected alternative user inputs being at least that of the original user input.

3. The method of claim 1, wherein the original user input is an original user search query.

4. The method of claim 1, wherein the original user input is in a non-Roman based language.

5. The method of claim 1, further comprising:

determining whether the original user input is in a pre-computed cache of suggested alternative user inputs; and

upon determining that the original user input is in the pre-computed cache, outputting at least one of the pre-computed most likely alternative user inputs stored in the pre-computed cache.

6. The method of claim 1, wherein the similarity matrix is generated from at least one of a corpus, a user input log, and user session data.

7. The method of claim 6, wherein the similarity matrix is generated by constructing feature vectors for words in the corpus and determining a similarity value between two words using their feature vectors.

8. The method of claim 1, wherein the expansion/contraction table is generated from at least one of a user input log and a user input database.

9. The method of claim 8, wherein the expansion/contraction table is generated by determining frequent word sequences, filtering out non-phrasal word sequences, and associating counts with sequences of terms as the frequency values.

10. The method of claim 1, wherein computing the likelihoods of the potential alternative user inputs includes determining at least one of:

(a) a relevance between the original user input and the potential alternative user input, (b) a probability that the potential alternative user input will be selected by the user, and (c) a score of the position for the potential alternative user input.

11. The method of claim 10, wherein the relevance between the original user input and the potential alternative user input is determined using correlation values between aligned terms of the original input and the potential alternative user input.

12. A system for suggesting alternative user inputs, comprising:

a suggestion/refinement server configured to receive an original user input having at least one core term, to identify the at least one core term in the original user input, to determine at least one potential alternative user input by performing at least one of (a) replacing at least one core term in the original user input with another term according to a similarity matrix, the similarity matrix having a similarity value between the two terms and (b) substituting a sequence of words in the original user input with another sequence of words according to an expansion/contraction table, one sequence being a substring of the other sequence, the expansion/contraction table having frequency values associated with sequences of terms, to compute likelihoods of the potential alternative user inputs, and to select and output one or more most likely alternative user inputs from the at least one potential alternative user input according to a predetermined criteria.

13. The system of claim 12, wherein the original user input is an original user search query.

14. The system of claim 12, wherein the original user input is in a non-Roman based language.

15. The system of claim 12, further comprising a pre-computed cache of suggested alternative user inputs, wherein the suggestion/refinement server is further configured to determine whether the original user input is in the pre-computed cache and, upon determining that the original user input is in the pre-computed cache, to output pre-computed most likely alternative use inputs stored in the pre-computed cache.

16. The system of claim 12, further comprising at least one of a corpus, a user input log, and user session data, wherein the similarity matrix is generated using at least one of the corpus, the user input log, and user session data.

17. The system of claim 16, wherein the suggestion/refinement server is further configured to generate the similarity matrix by constructing feature vectors for words in the corpus and determining a similarity value between two words using their feature vectors.

18. The system of claim 12, further comprising at least one of a user input log and a user input database, wherein the suggestion/refinement server is further configured to generate the expansion/contraction table from at least one of the user input log and the user input database.

19. The system of claim 18, wherein the suggestion/refinement server is further configured to generate the expansion/contraction table by determining frequent word sequences, filtering out non-phrasal word sequences, and associating a count with each sequence of terms as the frequency value.

20. The system of claim 12, wherein the suggestion/refinement server is further configured to compute the likelihoods of the potential alternative user inputs by determining at least one of:

(a) a relevance between the original user input and the potential alternative user input, (b) a probability that the potential alternative user input will be selected by the user, and (c) a score of the position for the potential alternative user input.

21. The system of claim 20, wherein the suggestion/refinement server is further configured to determine the relevance between the original user input and the potential alternative user input by using correlation values between aligned terms of the original input and the potential alternative user input.

22. A computer program product for use in conjunction with a computer system, the computer program product comprising a computer readable storage medium on which are stored instructions executable on a computer processor, the instructions including:

receiving an original user input, the input having at least one core term;

identifying the at least one core term in the original user input;

determining at least one potential alternative user inputs by performing at least one of (a) replacing at least one core term in the original user input with another term according to a similarity matrix, the similarity matrix having a similarity value between the two terms and (b) substituting a sequence of words in the original user input with another sequence of words according to an expansion/contraction table, one sequence being a substring of the other sequence, the expansion/contraction table having a frequency value associated with each sequence of terms;

computing likelihoods of the potential alternative user inputs; and

selecting one or more most likely alternative user inputs from the at least one potential alternative user input according to a predetermined criteria.

23. The computer program product of claim 22, the instructions further including:

determining whether the original user input is in a pre-computed cache of suggested alternative user inputs and

upon determining that the original user input is in the pre-computed cache, outputting pre-computed most likely alternative use inputs stored in the pre-computed cache.

24. The computer program product of claim 22, wherein the similarity matrix is generated from at least one of a corpus, a user input log, and user session data.

25. The computer program product of claim 24, wherein the similarity matrix is generated by constructing feature vectors for words in the corpus and determining a similarity value between two words using their feature vectors.

26. The computer program product of claim 22, wherein the expansion/contraction table is generated from at least one of a user input log and a user input database.

27. The computer program product of claim 26, wherein the expansion/contraction table is generated by determining frequent word sequences, filtering out non-phrasal word sequences, and associating a count with each sequence of terms as the frequency value.

28. The computer program product of claim 22, wherein computing the likelihoods of the potential alternative user inputs includes determining at least one of:

(a) a relevance between the original user input and the potential alternative user input, (b) a probability that the potential alternative user input will be selected by the user, and (c) a score of the position for the potential alternative user input.

29. The computer program product of claim 28, wherein the relevance between the original user input and the potential alternative user input is determined using correlation values between aligned terms of the original input and the potential alternative user input.