SPACE PREDICTION FOR TEXT INPUT

• US 20150026628A1
• Filed: 08/05/2014
• Published: 01/22/2015
• Est. Priority Date: 10/22/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ouyang, Yu, Zhai, Shumin
• Granted Patent: US 10,019,435 B2
• Time in Patent Office: Days
• US Class Current: 715/773
• CPC Class Codes: G06F 3/0237 using prediction or retrieval techniques
• CPC Class Codes: G06F 3/0482 Interaction with lists of selectable items, e.g. menus
• CPC Class Codes: G06F 3/04886 by partitioning the display area of the touch-screen or the surface of the digitising tablet into independently controllable areas, e.g. virtual keyboards or menus
• CPC Class Codes: G06F 40/163 Handling of whitespace
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs
• CPC Class Codes: Y10S 715/968 interface for database querying and retrieval

Abstract

An example method includes displaying, at a presence-sensitive device, a virtual keyboard, receiving an indication of input entered at a presence-sensitive device indicating a plurality of characters, determining a sequence of at least three character strings in the plurality such that the sequence does not include any space characters, modifying the characters by inserting at least two space characters to demarcate the at least three character strings, and determining at least two suggested character strings based on first, second, and third character strings of the sequence. The method further includes outputting, for display at the presence-sensitive device and at a text-suggestion area of the GUI, the at least two suggested character strings, receiving a selection that indicates a selected character string of the at least two suggested character strings, and outputting, for display at the presence-sensitive device and at the text-entry area of the GUI, the selected character string.

Claims

1-20. -20. (canceled)

21. A method comprising:

receiving, by a computing device, an indication of input to select a sequence of three or more characters from a plurality of characters, wherein the plurality of characters is output by the computing device for display and the sequence of three or more characters includes no space characters;

inserting, by the computing device and based at least in part on a lexicon, first and second space characters in respective first and second locations within the sequence of three or more characters to form a modified sequence of characters, the modified sequence of characters comprising at least three character substrings, wherein each of the at least three character substrings includes no space characters, and wherein the at least three character substrings are separated from one another in the modified sequence of characters by one of the first or second space characters;

determining, by the computing device and based at least in part on the modified sequence of characters, one or more suggested character strings; and

outputting, by the computing device and for display, at least one suggested character string from the one or more suggested character strings.

22. The method of claim 21, wherein determining the one or more suggested character strings comprises at least one of:

correcting an insertion error in a character substring from the at least three character substrings, correcting an omission error in the character substring, or correcting a misspelling in the character substring.

23. The method of claim 22, wherein correcting the insertion error in the character substring, correcting the omission error in the character substring, and correcting the misspelling in the character substring are each based at least in part on at least one of the lexicon or an n-gram language model.

24. The method of claim 21, further comprising:

determining an entry age of at least one character substring from the at least three character substrings; and

responsive to determining that the entry age of the at least one character substring is greater than a threshold value;

removing the at least one character substring from the modified sequence of characters to form an updated sequence of characters,

determining, based at least in part on the updated sequence of characters, one or more updated suggested character strings, and

outputting, for display, at least one updated suggested character string from the one or more updated suggested character strings.

25. The method of claim 24, wherein outputting the at least one suggested character string comprises outputting the at least one suggested character string at a text-suggestion area of a graphical user interface (GUI), and wherein outputting the at least one updated suggested character string comprises outputting the at least one updated suggested character string at the text-suggestion area, the method further comprising:

responsive to determining that the entry age of the at least one character substring is greater than the threshold value, outputting, for display, a respective first portion of the at least one suggested character string in a text-entry area of the GUI, wherein the respective first portion of the at least one suggested character string is determined based on the at least one character substring.

26. The method of claim 21, wherein forming the modified sequence of characters comprises:

generating a first character substring within the modified sequence of characters such that the first character substring represents a current character substring; and

for each character from the sequence of three or more characters,

adding the character to the current character substring, and

responsive to determining that the character represents a terminal character of the current character substring;

inserting one of the first or second space characters into the modified plurality of characters subsequent to the character; and

generating a subsequent character substring within the modified sequence of characters such that the subsequent character substring represents the current character substring.

27. The method of claim 21, wherein inserting the first and second space characters in the respective first and second locations within the sequence of three or more characters to form the modified sequence of characters comprises inserting the first and second space characters in the respective first and second locations within the sequence of three or more characters to form a first modified sequence of characters, the method further comprising:

inserting, based at least in part on the lexicon, third and fourth space characters in respective third and fourth locations within the sequence of three or more characters to form a second modified sequence of characters, the second modified sequence of characters comprising at least three new character substrings, wherein;

each of the at least three new character substrings includes no space characters,

the at least three new character substrings are separated from one another in the second modified sequence of characters by one of the third or fourth space characters, and

at least one of the third or fourth locations is different than each of the first and second locations;

determining, based at least in part on the second modified sequence of characters, one or more new suggested character strings; and

outputting, for display, at least one new suggested character string from the one or more new suggested character strings.

28. The method of claim 21, further comprising outputting, for display, the sequence of three or more characters.

29. A computing device comprising:

at least one processor; and

at least one module operable by the at least one processor to;

receive an indication of input to select a sequence of three or more characters from a plurality of characters, wherein the plurality of characters is output by the computing device for display and the sequence of three or more characters includes no space characters;

insert, based at least in part on a lexicon, first and second space characters in respective first and second locations within the sequence of three or more characters to form a modified sequence of characters, the modified sequence of characters comprising at least three character substrings, wherein each of the at least three character substrings includes no space characters, and wherein the at least three character substrings are separated from one another in the modified sequence of characters by one of the first or second space characters;

determine, based at least in part on the modified sequence of characters, one or more suggested character strings; and

output, for display, at least one suggested character string from the one or more suggested character strings.

30. The computing device of claim 29, wherein the at least one module operable to determine the one or more suggested character strings is operable by the at least one processor to correct at least one of:

an insertion error in a character substring from the at least three character substrings, an omission error in the character substring, or a misspelling in the character substring.

31. The computing device of claim 30, wherein the at least one module operable to correct the at least one of:

the insertion error in the character substring, the omission error in the character substring, or the misspelling in the character substring is operable by the at least one processor to correct the at least one of;

the insertion error in the character substring, the omission error in the character substring, or the misspelling in the character substring based at least in part on at least one of the lexicon or an n-gram language model.

32. The computing device of claim 29 wherein the at least one module is further operable by the at least one processor to:

determine an entry age of at least one character substring from the at least three character substrings; and

responsive to determining that the entry age of the at least one character substring is greater than a threshold value;

remove the at least one character substring from the modified sequence of characters to form an updated sequence of characters,

determine, based at least in part on the updated sequence of characters, one or more updated suggested character strings, and

output, for display, at least one updated suggested character string from the one or more updated suggested character strings.

33. The computing device of claim 32, wherein:

the at least one module operable to output the at least one suggested character string is operable by the at least one processor to output the at least one suggested character string at a text-suggestion area of a graphical user interface (GUI);

the at least one module operable to output the at least one updated suggested character string is operable by the at least one processor to output the at least one updated suggested character string at the text-suggestion area; and

the at least one module is further operable by the at least one processor to;

responsive to determining that the entry age of the at least one character substring is greater than the threshold value, output, for display, a respective first portion of the at least one suggested character string in a text-entry area of the GUI, wherein the respective first portion of the at least one suggested character string is determined based on the at least one character substring.

34. The computing device of claim 29, wherein the at least one module operable to form the modified sequence of characters is operable by the at least one processor to:

generate a first character substring within the modified sequence of characters such that the first character substring represents a current character substring; and

for each character from the sequence of three or more characters,

add the character to the current character substring, and

responsive to determining that the character represents a terminal character of the current character substring;

insert one of the first or second space characters into the modified plurality of characters subsequent to the character; and

generate a subsequent character substring within the modified sequence of characters such that the subsequent character substring represents the current character substring.

35. The computing device of claim 29, wherein the at least one module operable to insert the first and second space characters in the respective first and second locations within the sequence of three or more characters to form the modified sequence of characters is operable by the at least one processor to insert the first and second space characters in the respective first and second locations within the sequence of three or more characters to form a first modified sequence of characters, the at least one module further operable by the at least one processor to:

insert, based at least in part on the lexicon, third and fourth space characters in respective third and fourth locations within the sequence of three or more characters to form a second modified sequence of characters, the second modified sequence of characters comprising at least three new character substrings, wherein;

each of the at least three new character substrings includes no space characters,

the at least three new character substrings are separated from one another in the second modified sequence of characters by one of the third or fourth space characters, and

at least one of the third or fourth locations is different than each of the first and second locations;

determine, based at least in part on the second modified sequence of characters, one or more new suggested character strings; and

output, for display, at least one new suggested character string from the one or more new suggested character strings.

36. A computer-readable storage medium encoded with instructions that, when executed, cause at least one processor to:

receive an indication of input to select a sequence of three or more characters from a plurality of characters, wherein the plurality of characters is output by the computing device for display and the sequence of three or more characters includes no space characters;

insert, based at least in part on a lexicon, first and second space characters in respective first and second locations within the sequence of three or more characters to form a modified sequence of characters, the modified sequence of characters comprising at least three character substrings, wherein each of the at least three character substrings includes no space characters, and wherein the at least three character substrings are separated from one another in the modified sequence of characters by one of the first or second space characters;

determine, based at least in part on the modified sequence of characters, one or more suggested character strings; and

output, for display, at least one suggested character string from the one or more suggested character strings.

37. The computer-readable storage medium of claim 36, wherein the instructions that cause the at least one processor to determine the one or more suggested character strings comprise instructions that, when executed, cause the at least one processor to correct at least one of:

an insertion error in a character substring from the at least three character substrings, an omission error in the character substring, or a misspelling in the character substring.

38. The computer-readable storage medium of claim 37, wherein the instructions that cause the at least one processor to correct the at least one of:

the insertion error in the character substring, the omission error in the character substring, or the misspelling in the character substring comprise instructions that, when executed, cause the at least one processor to correct the at least one of;

the insertion error in the character substring, the omission error in the character substring, or the misspelling in the character substring based at least in part on at least one of the lexicon or an n-gram language model.

39. The computer-readable storage medium of claim 36, further encoded with instructions that, when executed, cause the at least one processor to:

determine an entry age of at least one character substring from the at least three character substrings; and

responsive to determining that the entry age of the at least one character substring is greater than a threshold value;

remove the at least one character substring from the modified sequence of characters to form an updated sequence of characters,

determine, based at least in part on the updated sequence of characters, one or more updated suggested character strings, and

output, for display, at least one updated suggested character string from the one or more updated suggested character strings.

40. The computer-readable storage medium of claim 39, wherein:

the instructions that cause the at least one processor to output the at least one suggested character string comprise instructions that, when executed, cause the at least one processor to output the at least one suggested character string at a text-suggestion area of a graphical user interface (GUI);

the instructions that cause the at least one processor to output the at least one updated suggested character string comprise instructions that, when executed, cause the at least one processor to output the at least one updated suggested character string at the text-suggestion area; and

the computer-readable storage medium is further encoded with instructions that, when executed, cause the at least one processor to;

responsive to determining that the entry age of the at least one character substring is greater than the threshold value, output, for display, a respective first portion of the at least one suggested character string in a text-entry area of the GUI, wherein the respective first portion of the at least one suggested character string is determined based on the at least one character substring.