Automatic completion of fragments of text

• US 8,521,515 B1
• Filed: 08/29/2012
• Issued: 08/27/2013
• Est. Priority Date: 10/31/2003
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Harik, Georges R., Tong, Simon, Cheng, David R.
• Primary Examiner(s): SPOONER, LAMONT M
• Application Number:
  US13/598,089
• Time in Patent Office: 363 Days
• Field of Search: 704/1, 704/9, 704/10, 707706-708, 715/261
• US Class Current: 704/9
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

A system offers potential completions for fragments of text. The system may obtain a text fragment and identify documents that include the text fragment. The system may locate sentences within the documents that include at least a portion of the text fragment, identify sentence endings associated with the located sentences, and present the sentence endings as potential completions for the text fragment.

Claims

1. A method comprising:

identifying, by one or more processors, sentences, within one or more documents, the sentences including text included in a query;

determining, by one or more processors and from the identified sentences, completions for the query,

the determining including merging similar completions into a single completion;

assigning, by the one or more processors, scores to the completions based on locations within the identified sentences at which the text occurs; and

selecting, by one or more processors, a set of completions, of the determined completions, as potential completions for the query based on the scores.

2. The method of claim 1, where identifying the sentences includes:

receiving the query;

performing a search for documents that contain the text included in the query; and

identifying the sentences within the one or more documents based on performing the search.

3. The method of claim 1, further comprising:

determining that a quantity of the documents that contain the text included in the query is less than a threshold;

forming a shortened query based on the text included in the query when the quantity of the documents is less than the threshold; and

performing a search for documents that contain text in the shortened query.

4. The method of claim 1, where determining the completions includes:

locating words between the text included in the query and ends of the identified sentences; and

determining the completions based on the located words.

5. The method of claim 1, where assigning scores to the completions further comprises:

assigning scores to the completions based on a quantity of the one or more documents in which the completions occur.

6. The method of claim 1, further comprising:

providing, for presentation, the set of completions as potential completions for the query in an ordered list based on the scores.

7. The method of claim 1, further comprising:

trimming text from a particular completion of the completions prior to assigning the score for the particular completion.

8. A system comprising:

one or more processors to;

identify sentences, within one or more documents, the sentences including text included in a query;

determine, from the identified sentences, completions for the query,

when determining, the one or more processors being to merge similar completions into a single completion;

assign scores to the completions based on locations within the identified sentences at which the text occurs; and

select a set of completions, of the determined completions, as potential completions for the query based on the scores.

9. The system of claim 8, where, when identifying the sentences, the one or more processors are further to:

receive the query;

perform a search for documents that contain the text included in the query; and

identify the sentences within the one or more documents based on performing the search.

10. The system of claim 8, where the one or more processors are further to:

determine that a quantity of the documents that contain the text included in the query is less than a threshold;

form a shortened query based on the text included in the query when the quantity of the documents is less than the threshold; and

perform a search for documents that contain text in the shortened query.

11. The system of claim 8, where, when determining the completions, the one or more processors are further to:

locate words between the text included in the query and ends of the identified sentences; and

determine the completions based on the located words.

12. The system of claim 8, where, when assigning scores to the completions, the one or more processors are further to:

assign scores to the completions based on a quantity of the one or more documents in which the completions occur.

13. The system of claim 8, where the one or more processors are further to:

provide, for presentation, the set of completions as potential completions for the query in an ordered list based on the scores.

14. The system of claim 8, where the one or more processors are further to trim text from a particular completion of the completions prior to assigning the score for the particular completion.

15. A non-transitory computer-readable medium including instructions executable by one or more processors, the instructions comprising:

one or more instructions that, when executed by the one or more processors, cause the one or more processors to;

identify sentences, within one or more documents, the sentences including text included in a query;

determine, from the identified sentences, completions for the query,

the one or more instructions that cause the one or more processors to determine completions for the query including one or more instructions that cause the one or more processors to merge similar completions into a single completion;

assign scores to the completions based on locations within the identified sentences at which the text occurs; and

select a set of completions, of the determined completions, as potential completions for the query based on the scores.

16. The computer-readable medium of claim 15, where the one or more instructions that cause the one or more processors to identify the sentences further include one or more instructions that cause the one or more processors to:

receive the query;

perform a search for documents that contain the text included in the query; and

identify the sentences within the one or more documents based on performing the search.

17. The computer-readable medium of claim 15, where the instructions further comprise:

one or more instructions that cause the one or more processors to;

determine that a quantity of the documents that contain the text included in the query is less than a threshold;

form a shortened query based on the text included in the query when the quantity of the documents is less than the threshold; and

perform a search for documents that contain text in the shortened query.

18. The computer-readable medium of claim 15, where the one or more instructions that cause the one or more processors to determine the completions include:

one or more instructions that cause the one or more processors to;

locate words between the text included in the query and ends of the identified sentences; and

determine the completions based on the located words.

19. The computer-readable medium of claim 15, where the one or more instructions that cause the one or more processors to assign scores to the completions include:

one or more instructions that cause the one or more processors to assign scores to the completions based on a quantity of the one or more documents in which the completions occur.

20. The computer-readable medium of claim 15, where the instructions further comprise:

one or more instructions that cause the one or more processors to trim text from a particular completion of the completions prior to assigning the score for the particular completion.