Automatic completion of fragments of text

• US 7,657,423 B1
• Filed: 10/31/2003
• Issued: 02/02/2010
• Est. Priority Date: 10/31/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Cheng, David R., Tong, Simon, Harik, Georges R.
• Primary Examiner(s): Hudspeth; David R
• Assistant Examiner(s): Spooner; Lamont M
• Application Number:
  US10/697,333
• Time in Patent Office: 2,286 Days
• Field of Search: 704/1, 704/9, 704/10, 707 1- 6, 715/534, 715/261, 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 performed by one or more server or client devices, comprising:

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

performing, using a processor associated with the one or more server or client devices, a search, based, at least in part, on the text fragment, to identify one or more documents;

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

determining, using a processor associated with the one or more server or client devices, sentence endings as text that is located within the identified sentences between the text fragment and an end of the identified sentences;

assigning, using a processor associated with the one or more server or client devices, scores to the sentence endings based, at least in part, on a location within the identified sentences at which the text fragment occurs; and

outputting, using a processor associated with the one or more server or client devices, the sentence endings as potential completions for the text fragment based, at least in part, on the scores.

2. The method of claim 1, where the text fragment includes a phrase.

3. The method of claim 1, where the obtaining a text fragment includes receiving the text fragment from a user.

4. The method of claim 1, where the obtaining a text fragment includes automatically detecting the text fragment.

5. The method of claim 1, where the performing a search includes searching for documents that include the text fragment as a phrase.

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

7. The method of claim 1, where the identifying sentences within the one or more documents includes determining boundaries of the identified sentences based, at least in part, on punctuation that borders the identified sentences in the one or more documents.

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

9. The method of claim 8, where the one or more words are dropped from the at least one sentence ending based, at least in part, on at least one of text or one or more symbols included in the at least one sentence ending.

10. The method of claim 9, 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.

11. The method of claim 9, where the trimming at least one of the sentence endings includes:

identifying the one or more symbols included in the at least one sentence ending, and

dropping one or more words from the at least one sentence ending based, at least in part, on the one or more identified symbols.

12. The method of claim 1, further comprising:

merging two or more of the sentence endings into a merged sentence ending.

13. The method of claim 12, where the merging two or more of the sentence endings includes:

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

merging the identified two or more sentence endings.

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

15. The method of claim 1, where assigning the scores to the sentence endings is further based, at least in part, on a measure of popularity associated with each of the sentence endings.

16. The method of claim 15, where the measure of popularity associated with the sentence endings is based, at least in part, on a number of times that the sentence endings occur within the one or more documents.

17. The method of claim 1, further comprising:

adjusting the scores of the sentence endings based, at least in part, on lengths of the sentence endings.

18. The method of claim 1, further comprising:

adjusting the scores of the sentence endings based, at least in part, on whether at least a portion of the sentence endings are included in a list of bad endings.

19. The method of claim 1, where the outputting the sentence endings includes:

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.

20. The method of claim 1, where the outputting the sentence endings includes:

inserting one of the sentence endings near a location of the text fragment, and

replacing the one of the sentence endings with a subsequent one or more of the sentence endings.

21. A system, comprising:

one or more devices comprising;

means for receiving a text fragment;

means for identifying documents that include the text fragment;

means for locating sentences within the documents that include the text fragment;

means for identifying sentence endings, associated with the located sentences, as text that is located within the located sentences between the text fragment and an end of the located sentences;

means for assigning scores to the sentence endings based, at least in part, on a measure of popularity associated with the sentence endings and a location at which the text fragment occurs within the located sentences, where the measure of popularity associated with one of the sentence endings is based, at least in part, on a number of times that the one of the sentence endings occurs within the documents; and

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

22. The system of claim 21, further comprising:

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

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

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

23. The method system of claim 22, where the means for shortening the text fragment includes means for dropping one or more words from a beginning or end of the text fragment.

24. The method system of claim 22, where the means for shortening the text fragment includes:

means for identifying one or more symbols within the text fragment, and

means for dropping one or more words from the text fragment based, at least in part, on the one or more identified symbols.

25. The method system of claim 22, where the means for shortening the text fragment includes:

means for analyzing a structure of the text fragment, and

means for dropping one or more words from the text fragment based, at least in part, on the analysis of the structure of the text fragment.

26. A system, comprising:

one or more servers to;

receive a text fragment, where the text fragment includes a plurality of words, identify documents that include the text fragment,

locate sentences within the documents that include the text fragment,

determine sentence completions, associated with the located sentences, as text that is located within the located sentences between the text fragment and an end of the located sentences,

trim one of the sentence completions by dropping one or more words from the one of the sentence completions, assign scores to the sentence completions based, at least in part, on a measure of popularity associated with the sentence completions and a location within the located sentences at which the text fragment occurs, and

provide a plurality of the sentence completions including the trimmed sentence completion as potential completions for the text fragment based, at least in part, on the scores.

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

discard one or more of the sentence completions when at least a portion of the one or more sentence completions is included in a list of bad completions.

28. The system of claim 26, where the one or more servers include a plurality of servers.

29. A computer device, comprising:

a memory to store instructions; and

a processor to execute the instructions in the memory to;

obtain a fragment of text,

search for documents that include the fragment of text,

identify sentences within the documents that include the fragment of text,

determine sentence completions as text located within the identified sentences between the fragment of text and an end of the identified sentences,

merge at least two of the sentence completions to form a single merged sentence completion, assign scores to the sentence completions based, at least in part, on a measure of popularity associated with the sentence completions and a location within the identified sentences at which the fragment of text occurs, and

provide a plurality of the sentence completions, including the merged sentence completion, as potential completions for the fragment of text based, at least in part, on the scores.

30. The device of claim 29, where, when providing the plurality of sentence completions, the processor is to:

present the plurality of sentence completions via a pop-up window.