Automatic completion of fragments of text

• US 8,280,722 B1
• Filed: 09/16/2011
• Issued: 10/02/2012
• Est. Priority Date: 10/31/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Harik, Georges R., Tong, Simon, Cheng, David R.
• Primary Examiner(s): Hudspeth, David R
• Assistant Examiner(s): SPOONER, LAMONT M
• Application Number:
  US13/235,025
• Time in Patent Office: 382 Days
• Field of Search: 704/1, 704/9, 704/10, 707706-708, 715/256, 715/810, 715/816
• 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, that include text represented by a query;

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

determining, by one or more processors, that two or more of the completions have text in common;

merging, by one or more processors, the two or more completions based on the text in common; and

outputting, by one or more processors and for presentation, the completions as potential completions for the query.

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

obtaining the query;

identifying the one or more documents based, at least in part, on the query; and

identifying the sentences, within the one or more documents, that include the query.

3. The method of claim 2, where identifying the one or more documents includes:

searching for documents that include synonyms of one or more words within the obtained query to identify the one or more documents.

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

assigning scores for the completions;

ordering the completions based on the assigned scores; and

outputting the ordered completions as potential completions for the query.

5. The method of claim 4, where assigning the scores includes:

assigning a higher score to a completion, of the completions, that occurs more frequently in the one or more documents than a score assigned to another completion, of the completions, that occurs less frequently in the one or more documents.

6. The method of claim 1, further comprising:

trimming at least one of the completions by dropping one or more words from the at least one completion.

7. The method of claim 1, further comprising:

determining measures of importance of the completions based, at least in part, on at least one of a table of common beginnings of sentences or a table of common endings of sentences, and

where the outputting the completions includes;

outputting the completions in an order based, at least in part, on the determined measures of importance.

8. The method of claim 1, where merging the two or more completions includes:

merging the two or more completions to form a merged completion, and where outputting, for presentation, the completions includes;

outputting, for presentation, the completions, including the merged completion, as potential completions for the query.

9. A non-transitory computer-readable memory device including one or more instructions for execution by one or more processors, the instructions comprising:

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

identify sentences, within one or more documents, that include text represented by a query;

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

determine that two or more of the completions have text in common;

merge the two or more completions based on the text in common; and

output, for presentation, the completions as potential completions for the query.

10. The non-transitory computer-readable memory device of claim 9, where the one or more instructions that cause the one or more processors to identify the sentences comprise:

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

obtain the query;

identify the one or more documents based, at least in part, on the query; and

identify the sentences, within the one or more documents, where the sentences include the query.

11. The non-transitory computer-readable memory device of claim 10, where the one or more instructions that cause the one or more processors to identify the sentences comprise:

one or more instructions that, when executed by the one or more processors, cause that one or more processors to search for documents that include synonyms of one or more words within the obtained query to identify the one or more documents.

12. The non-transitory computer-readable memory device of claim 9, where the one or more instructions that cause the one or more processors to output the completions include:

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

assign scores for the completions;

order the completions based on the assigned scores; and

output the ordered completions as potential completions for the query.

13. The non-transitory computer-readable memory device of claim 12, where the one or more instructions that cause the one or more processors to assign the scores include:

one or more instructions that, when executed by the one or more processors, cause that one or more processors to assign a higher score to a completion, of the completions, that occurs more frequently in the one or more documents than a score assigned to another completion, of the completions, that occurs less frequently in the one or more documents.

14. The non-transitory computer-readable memory device of claim 9, the one or more instructions further comprising:

one or more instructions that, when executed by the one or more processors, cause that one or more processors to trim at least one of the completions by dropping one or more words from the at least one completion.

15. The non-transitory computer-readable memory device of claim 9, the one or more instructions further comprising:

one or more instructions that, when executed by the one or more processors, cause that one or more processors to determine measures of importance of the completions based, at least in part, on at least one of a table of common beginnings of sentences or a table of common endings of sentences, and

where the one or more instructions that cause the one or more processors to output the completions include;

one or more instructions that, when executed by the one or more processors, cause that one or more processors to output the completions in an order based, at least in part, on the determined measures of importance.

16. The non-transitory computer-readable memory device of claim 9, where the one or more instructions that cause the one or more processors to merge the two or more completions include:

one or more instructions that, when executed by the one or more processors, cause the one or more processors to merge the two or more completions to form a merged completion, and

where the one or more instructions that cause the one or more processors to output, for presentation, the completions include;

one or more instructions that, when executed by the one or more processors, cause the one or more processors to output, for presentation, the completions, including the merged completion, as potential completions for the query.

17. A system comprising:

one or more severs to;

identify sentences, within one or more documents, that include text represented by a query;

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

determine that two or more of the completions have text in common;

merge the two or more completions based on the text in common;

score the completions; and

output, for presentation, the scored completions as potential completions for the query.

18. The system of claim 17, where, when identifying the sentences, the one or more servers are further to:

obtain the query;

identify the one or more documents based, at least in part, on the query; and

identify the sentences, within the one or more documents, that include the query.

19. The system of claim 18, where, when identifying the one or more documents, the one or more servers are further to:

search for documents that include synonyms of one or more words within the obtained query to identify the one or more documents.

20. The system of claim 17, where, when scoring the completions, the one or more servers are further to:

assign a higher score to a completion, of the completions, that occurs more frequently in the one or more documents than a score assigned to another completion, of the completions, that occurs less frequently in the one or more documents.

21. The system of claim 17, where the one or more servers are further to:

trim at least one of the completions by dropping one or more words from the at least one completion.

22. The system of claim 17, where the one or more servers are further to:

determine measures of importance of the completions based, at least in part, on at least one of a table of common beginnings of sentences or a table of common endings of sentences, and

where when outputting the completions, the one or more processors are to;

output the completions in an order based, at least in part, on the determined measures of importance.

23. The system of claim 17, where, when merging the two or more completions, the one or more servers are further to:

merge the two or more completions to form a merged completion, where, when scoring the completions, the one or more servers are further to;

score the completions including the merged completion, and

where, when outputting, for presentation, the scored completions, the one or more severs are further to;

output, for presentation, the scored completions, including the merged completion, as potential completions for the query.