Automatic completion of fragments of text

• US 8,024,178 B1
• Filed: 12/14/2009
• Issued: 09/20/2011
• Est. Priority Date: 10/31/2003
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Cheng, David R, Harik, Georges R, Tong, Simon
• Primary Examiner(s): Hudspeth; David R
• Assistant Examiner(s): SPOONER, LAMONT M
• Application Number:
  US12/636,926
• Time in Patent Office: 645 Days
• Field of Search: 707 1- 6, 715/261, 715/816, 704/9, 704/1, 704/10
• 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, performed by one or more server or client devices, for completing fragments of text, the method comprising:

obtaining, using one or more processors associated with the one or more server or client devices, a text fragment;

identifying, using one or more processors associated with the one or more server or client devices, one or more documents based, at least in part on the text fragment;

identifying, using one or more processors associated with the one or more server or client devices, sentences within the one or more documents that include the text fragment;

determining, using one or more processors associated with the one or more server or client devices, sentence endings associated with the identified sentences;

determining a measure of popularity for each of the sentence endings, where the measure of popularity for one of the sentence endings is based, at least in part, on a quantity of documents within a document corpus that includes the one of the sentence endings;

ordering the sentence endings based, at least in part, on the determined measure of popularity for each of the sentence endings; and

presenting, using one or more processors associated with the one or more server or client devices, the ordered sentence endings as potential completions for the text fragment.

2. The method of claim 1, where identifying one or more documents includes searching for documents that include the text fragment and synonyms of one or more words within the text fragment.

3. The method of claim 1, further comprising:

trimming at least one of the sentence endings by dropping one or more words from the at least one sentence ending.

4. The method of claim 3, further comprising:

generating an inverse document frequency table that includes words common to sentence endings; and

where the trimming at least one of the sentence endings includes;

comparing the text of the at least one sentence ending to words in the inverse document frequency table, and

dropping one or more words from the at least one sentence ending based, at least in part, on a result of the comparison.

5. The method of claim 1, further comprising:

identifying two or more of the sentence endings that have text in common; and

merging the identified two or more sentence endings into a merged sentence ending, and where presenting includes;

presenting the merged sentence ending as a potential completion for the text fragment.

6. The method of claim 1, where presenting the sentence endings comprises:

assigning scores to the sentence endings based on the measure of popularity,

ordering the sentence endings based, at least in part, on the scores, and

presenting the ordered sentence endings as potential completions for the text fragment.

7. The method of claim 1, further comprising:

determining quality ones of the sentence endings 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.

8. A computer-readable memory device including instructions for execution by one or more processors, the computer-readable memory device including instructions for performing a method, the method comprising:

receiving a text fragment;

identifying documents that include the text fragment;

locating sentences within the documents that include the text fragment;

identifying sentence endings associated with the located sentences;

determining a measure of popularity for each of the sentence endings, where the measure of popularity for one of the sentence endings, is based, at least in part, on a quantity of documents within a document corpus that includes the one of the sentence endings;

ordering the sentence endings based, at least in part, on the determined measure of popularity of the sentence endings; and

presenting ordered the sentence endings as potential completions for the text fragment.

9. The computer-readable memory device of claim 8, where the method further comprises:

determining whether a quantity of the documents is less than a threshold;

shortening the text fragment when the quantity of the documents is less than the threshold; and

performing a search, based, at least in part, on the shortened text fragment, to identify a set of documents.

10. The computer-readable memory device of claim 9, where shortening the text fragment includes:

dropping one or more words from a beginning or end of the text fragment.

11. The computer-readable memory device of claim 9, where shortening the text fragment includes:

identifying one or more symbols within the text fragment, and

dropping one or more words from the text fragment based on the one or more identified symbols.

12. The computer-readable memory device of claim 8, where receiving the text fragment includes automatically detecting the text fragment.

13. The computer-readable memory device of claim 8, where receiving the text fragment includes receiving the text fragment from a user.

14. The computer-readable memory device of claim 8, further comprising:

identifying two or more of the sentence endings that have text in common; and

merging the identified two or more sentence endings into a merged sentence ending, and

where presenting the sentence endings includes;

presenting the merged sentence endings as a potential completion for the text fragment.

15. A system comprising:

one or more servers to;

receive a text fragment;

perform a search, using the text fragment, to identify one or more documents;

locate sentences, within the one or more documents, that contain the text fragment;

identify sentence endings included in the located sentences;

assign scores to the sentence endings based, at least in part, on a location within the located sentences at which the text fragment occurs; and

present the identified sentence endings as potential completions for the text fragment based, at least in part, on the scores.

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

trim at least one of the sentence endings by dropping one or more words from the at least one sentence ending.

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

identify two or more of the sentence endings that have text in common; and

merge the identified two or more sentence endings into a merged sentence ending, and, when presenting the identified sentence endings, the one or more servers are further to;

present the merged sentence ending as a potential completion.

18. The system of claim 15, where, when presenting the identified sentence endings, the one or more servers are further to:

order the sentence endings based, at least in part, on the scores, and

present the ordered sentence endings as potential completions for the text fragment.

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

determine whether a quantity of the one or more documents is less than a threshold;

shorten the text fragment when the quantity of the one or more documents is less than the threshold; and

perform a search, based, at least in part, on the shortened text fragment, to identify a set of documents.

20. The system of claim 15, where, when shortening the text fragment, the one or more servers are further to:

identify one or more symbols within the text fragment, and

drop one or more words from the text fragment based on the one or more identified symbols.