Determining word boundary likelihoods in potentially incomplete text

• US 8,364,709 B1
• Filed: 11/22/2010
• Issued: 01/29/2013
• 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:
  US12/951,529
• Time in Patent Office: 799 Days
• Field of Search: 707/780
• US Class Current: 707/780
• 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 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;

accessing queries stored in query logs, each query being one or more characters in a first sequence constituting one or more words in a second sequence;

for each query;

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 selected 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.

2. The system of claim 1, wherein selecting a query sequence from the query comprises:

selecting a next character in the first sequence of characters, the next character being either a first character of the first sequence of characters or a character that is next in sequence to a most recently selected next character in the first sequence of characters;

determining whether the query sequence constitutes more than a subsequence of up to n words from the second sequence of words of the query; and

in response to determining that the query sequence constitutes more than the subsequence of up to n words, deselecting a word that is first in the subsequence of words in the query sequence.

3. The system of claim 2, wherein determining one or more query sequence keys for the query sequence comprises:

determining a first query sequence key that is a key for the entire query sequence;

determining a second query sequence key that is a key for a last subsequence of characters in the query sequence that constitute only a unigram or only a portion of a unigram in the query.

4. The system of claim 3, wherein determining at least one of a word boundary count and a non-word boundary count for each query sequence comprises:

determining whether the query sequence ends in a word boundary;

in response to determining whether the query sequence ends in a word boundary, incrementing a word boundary count for the first query sequence key and incrementing a word boundary count for the second query sequence key; and

in response to determining whether the query sequence ends in a non-word boundary, incrementing a non-word boundary count for the first query sequence key and incrementing a non-word boundary count for the second query sequence key.

5. The system of claim 4, wherein determining whether the query sequence ends in a word boundary comprises:

selecting a subsequent character the subsequent character being a character that is next in sequence to a character that is last in the subsequence of the query sequence;

determining that the query sequence ends in a word boundary if the subsequent character is indicative of a word boundary; and

determining that the query sequence ends in a non-word boundary if the subsequent character is indicative of a non-word boundary.

6. The system of claim 5, wherein:

the subsequent character is indicative of a word boundary when the subsequent character is a space character; and

the subsequent character is indicative of a non-word boundary when the subsequent character is a letter character.

7. The system of claim 1, wherein:

selecting a query sequence from the query comprises;

determining whether a previously selected query sequence constitutes a subsequence of n words from the second sequence of words of the query, and in response to determining that the previously selected query sequence constitutes a subsequence of n words from the second sequence of words of the query, deselecting a word that is first in the subsequence of words in the query sequence; and

selecting a next character in the first sequence of characters, the next character being a character that is next in sequence to a most recently selected next character in the first sequence of characters;

determining one or more query sequence keys for the query sequence comprises;

determining a first query sequence key that is a key for the entire query sequence; and

determining a second query sequence key that is a key for a last subsequence of characters in the query sequence that constitute only a unigram or only a portion of a unigram in the query; and

determining at least one of a word boundary count and a non-word boundary count for each query sequence comprises;

determining whether the query sequence ends in a word boundary;

in response to determining whether the query sequence ends in a word boundary, incrementing a word boundary count for the first query sequence key and incrementing a word boundary count for the second query sequence key; and

in response to determining whether the query sequence ends in a non-word boundary, incrementing a non-word boundary count for the first query sequence key and incrementing a non-word boundary count for the second query sequence key.

8. The system of claim 7, wherein determining whether the query sequence ends in a word boundary comprises:

selecting a subsequent character the subsequent character being a character that is next in sequence to a character that is last in the subsequence of the query sequence;

determining that the query sequence ends in a word boundary if the subsequent character is indicative of a word boundary; and

determining that the query sequence ends in a non-word boundary if the subsequent character is indicative of a non-word boundary.

9. The system of claim 8, wherein:

the subsequent character is indicative of a word boundary when the subsequent character is a space character; and

the subsequent character is indicative of a non-word boundary when the subsequent character is a letter character.

10. The system of claim 1, wherein the data processing apparatus instructions cause the data processing apparatus to perform further operations comprising:

providing to a client device a search resource including interface instructions that cause the client device to generate a search interface that includes a query input field;

receive a query input from a client device, the query input having been input into the query input field and being one or more characters in a first input sequence constituting one or more words in a second input sequence;

in response to receiving data indicating a determination that the query input received from a client device does not meet a query suggestion threshold;

selecting a query input sequence from the query input, the query input sequence being up to a word n-gram of the most subsequent words of the one or more words in the second input sequence;

determining a likelihood that the query input sequence terminates at a word boundary from the word boundary count and non-word boundary count associated with a query sequence key matching the query input sequence; and

providing search results responsive to the client device at the expiration of a providing time delay that is based on the determined likelihood.

11. The system of claim 10, wherein providing search results responsive to the client device at the expiration of the providing time delay comprises determining a length of the providing time delay in inverse proportion to the likelihood that the query input sequence terminates at a word boundary.

12. The system of claim 11, wherein the length of the providing time delay varies from 0 seconds to a maximum providing time delay.

13. The system of claim 12, wherein the length of the maximum providing time delay is 1 second.

14. The system of claim 10, wherein determining the likelihood that the query input sequence terminates at a word boundary from the word boundary count and non-word boundary count associated with the query sequence key matching the query input sequence comprises dividing the word boundary count by a sum of the word boundary count and non-word boundary count.

15. The system of claim 1, wherein the data processing apparatus instructions cause the data processing apparatus to perform further operations comprising:

providing to a client device a search resource including interface instructions that cause the client device to generate a search interface that includes a query input field;

receiving a query input from a client device, the query input having been input into the query input field and being one or more characters in a first input sequence constituting one or more words in a second input sequence;

in response to receiving a determination that the query input received from a client device does not meet a query suggestion threshold;

selecting a query input sequence from the query input, the query input sequence being up to a word n-gram of the most subsequent words of the one or more words in the second input sequence;

determining a likelihood that the query input sequence terminates at a word boundary from the word boundary count and non-word boundary count associated with a query sequence key matching the query input sequence; and

providing search results responsive to the client device only if the determined likelihood meets a minimum likelihood threshold.

16. The system of claim 1, wherein the word n-gram is a word bi-gram.

17. The system of claim 15, wherein determining a likelihood that the query input sequence terminates at a word boundary from the word boundary count and non-word boundary count associated with a query sequence key matching the query input sequence comprises:

determining that a query input sequence that includes at least one word and at least a portion of another word subsequent to the at least one word in the second input sequence does not have a matching query sequence key; and

in response to the determination;

using only the portion of the another word to search for a fallback query sequence key; and

determining a likelihood that the query input sequence terminates at a word boundary from the word boundary count and non-word boundary count associated with the fallback query sequence key.

18. The system of claim 1, wherein associating in the data storage device the at least one word boundary count and non-word boundary counts with each query sequence key comprises:

determining whether the word boundary count for a query sequence key is zero and whether the non-word boundary count for a query sequence key is below a minimum non-word boundary count threshold; and

associating in the data storage device the at least one word boundary count and non-word boundary counts the query sequence key only in response to determining at least one of;

the word boundary count for the query sequence key being greater than zero;

or

the word boundary count for the query sequence key being zero and the non-word boundary count for the query sequence being less than the minimum non-word boundary count threshold.

19. 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;

accessing queries stored in query logs, each query being one or more characters in a first sequence constituting one or more words in a second sequence;

for each query;

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;

for each query sequence key;

determining a likelihood that the query sequence for which the query sequence key is determined occurs a word boundary from the word boundary count and non-word boundary count associated with a query sequence key; and

associating, in a data storage device, the likelihood with the query sequence key.

20. The system of claim 19, wherein determining the likelihood that the query sequence for which the query sequence key is determined occurs a word boundary from the word boundary count and non-word boundary count associated with a query sequence key comprises dividing the word boundary count by a sum of the word boundary count and non-word boundary count.

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

accessing queries stored in query logs, each query being one or more characters in a first sequence constituting one or more words in a second sequence;

for each query;

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 selected 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.

22. 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;

providing to a client device a search resource including interface instructions that cause the client device to generate a search interface that includes a query input field;

receiving a query input from a client device, the query input having been input into the query input field and being one or more characters in a first input sequence constituting one or more words in a second input sequence;

in response to receiving data indicating a determination that the query input received from a client device does not meet a query suggestion threshold;

selecting a query input sequence from the query input, the query input sequence being up to a word n-gram of the most subsequent words of the one or more words in the second input sequence;

determining a likelihood that the query input sequence terminates at a word boundary from a word boundary count and a non-word boundary count associated with a query sequence key matching the query input sequence; and

providing search results responsive to the client device at the expiration of a providing time delay that is based on the determined likelihood.

23. The system of claim 22, wherein the word boundary counts and non-word boundary counts are determined from an analysis of query logs storing queries, each query being one or more characters in a first sequence constituting one or more words in a second sequence.

24. The system of claim 22, wherein the word boundary counts and non-word boundary counts are determined from an analysis of a document corpus.

25. The system of claim 22, wherein receiving data indicating a determination that the query input received from a client device does not meet a query suggestion threshold comprises receiving data indicating that no query suggestions are determined for the query input.

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

providing to a client device a search resource including interface instructions that cause the client device to generate a search interface that includes a query input field;

receiving a query input from a client device, the query input having been input into the query input field and being one or more characters in a first input sequence constituting one or more words in a second input sequence;

in response to receiving data indicating a determination that the query input received from a client device does not meet a query suggestion threshold;

selecting a query input sequence from the query input, the query input sequence being up to a word n-gram of the most subsequent words of the one or more words in the second input sequence;

determining a likelihood that the query input sequence terminates at a word boundary from a word boundary count and a non-word boundary count associated with a query sequence key matching the query input sequence; and

providing search results responsive to the client device at the expiration of a providing time delay that is based on the determined likelihood.