Determining word boundary likelihoods in potentially incomplete text

• US 9,239,888 B1
• Filed: 12/04/2014
• Issued: 01/19/2016
• Est. Priority Date: 11/22/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Das, Abhinandan S., Fung, Harry S.
• Primary Examiner(s): Hu, Jensen
• Application Number:
  US14/560,091
• Time in Patent Office: 411 Days
• Field of Search: 707/780
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2468 Fuzzy queries
• CPC Class Codes: G06F 16/9032 Query formulation
• CPC Class Codes: G06F 16/90324 using system suggestions
• CPC Class Codes: G06F 16/90335 Query processing

Abstract

Methods, systems, and apparatus, including computer programs encoded on a computer storage medium, for determining word boundary likelihoods in potentially incomplete text. In one aspect, a method includes selecting query sequences from the query, each query sequence being at least a portion of a word n-gram, the word n-gram being a subsequence of up to n words selected from the second sequence of words of the query, and for each query sequence: determining one or more query sequence keys for the query sequence; determining at least one of a word boundary count and a non-word boundary count for each query sequence key, each word-boundary count and non-word boundary count being dependent on the context of the query sequence; and associating, in a data storage device, the at least one word boundary count and non-word boundary counts with each query sequence key.

Claims

1. A method performed by a data processing apparatus, the method comprising:

receiving, for a query sequence, a word boundary likelihood that represents a likelihood that the query sequence terminates at a word boundary;

determining, based on the word boundary likelihood, a time delay for delaying providing search results for the query sequence;

determining that an amount of time since receipt of the query sequence exceeds the time delay, and in response;

identifying search results responsive to the query sequence; and

providing the identified search results.

2. The method of claim 1, wherein the time delay is inversely proportional to the word boundary likelihood.

3. The method of claim 1, wherein determining the time delay comprises:

determining that the query sequence ends with one or more words indicative of additional query input; and

increasing the time delay in response to determining that the query sequence ends with one or more words indicative of additional query input.

4. The method of claim 1, wherein identifying search results responsive to the query sequence comprises:

determining that the word boundary likelihood is less than a threshold; and

identifying the search results based on a portion of the query sequence that does not include a last word portion that is located at the end of the query sequence.

5. The method of claim 1, wherein determining the time delay comprises determining the time delay based on an amount of network latency between a device that submitted the query sequence and the data processing apparatus.

6. The method of claim 1, wherein determining the time delay comprises determining that the word boundary likelihood exceeds a threshold and, in response, setting the time delay to a particular value.

7. The method of claim 1, wherein the word boundary likelihood is based on a word boundary count and a non-word boundary count for the query sequence.

8. A system, comprising:

a data processing apparatus; and

a computer storage medium encoded with a computer program, the program comprising data processing apparatus instructions that when executed by the data processing apparatus cause the data processing apparatus to perform operations comprising;

receiving, for a query sequence, a word boundary likelihood that represents a likelihood that the query sequence terminates at a word boundary;

determining, based on the word boundary likelihood, a time delay for delaying providing search results for the query sequence;

determining that an amount of time since receipt of the query sequence exceeds the time delay, and in response;

identifying search results responsive to the query sequence; and

providing the identified search results.

9. The system of claim 8, wherein the time delay is inversely proportional to the word boundary likelihood.

10. The system of claim 8, wherein determining the time delay comprises:

determining that the query sequence ends with one or more words indicative of additional query input; and

increasing the time delay in response to determining that the query sequence ends with one or more words indicative of additional query input.

11. The system of claim 8, wherein identifying search results responsive to the query sequence comprises:

determining that the word boundary likelihood is less than a threshold; and

identifying the search results based on a portion of the query sequence that does not include a last word portion that is located at the end of the query sequence.

12. The system of claim 8, wherein determining the time delay comprises determining the time delay based on an amount of network latency between a device that submitted the query sequence and the data processing apparatus.

13. The system of claim 8, wherein determining the time delay comprises determining that the word boundary likelihood exceeds a threshold and, in response, setting the time delay to a particular value.

14. The system of claim 8, wherein the word boundary likelihood is based on a word boundary count and a non-word boundary count for the query sequence.

15. A computer storage medium encoded with a computer program, the program comprising instructions that when executed by one or more data processing apparatus cause the data processing apparatus to perform operations comprising:

receiving, for a query sequence, a word boundary likelihood that represents a likelihood that the query sequence terminates at a word boundary;

determining, based on the word boundary likelihood, a time delay for delaying providing search results for the query sequence;

determining that an amount of time since receipt of the query sequence exceeds the time delay, and in response;

identifying search results responsive to the query sequence; and

providing the identified search results.

16. The computer storage medium of claim 15, wherein the time delay is inversely proportional to the word boundary likelihood.

17. The computer storage medium of claim 15, wherein determining the time delay comprises:

determining that the query sequence ends with one or more words indicative of additional query input; and

increasing the time delay in response to determining that the query sequence ends with one or more words indicative of additional query input.

18. The computer storage medium of claim 15, wherein identifying search results responsive to the query sequence comprises:

determining that the word boundary likelihood is less than a threshold; and

identifying the search results based on a portion of the query sequence that does not include a last word portion that is located at the end of the query sequence.

19. The computer storage medium of claim 15, wherein determining the time delay comprises determining the time delay based on an amount of network latency between a device that submitted the query sequence and the data processing apparatus.

20. The computer storage medium of claim 15, wherein determining the time delay comprises determining that the word boundary likelihood exceeds a threshold and, in response, setting the time delay to a particular value.