Correction of errors in character strings that include a word delimiter

• US 8,612,213 B1
• Filed: 05/23/2013
• Issued: 12/17/2013
• Est. Priority Date: 10/16/2012
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Zhai, Shumin, Partridge, Kurt Edward, Ouyang, Yu
• Primary Examiner(s): Vo, Huyen X.
• Application Number:
  US13/901,259
• Time in Patent Office: 208 Days
• Field of Search: 704 1- 10, 704/251, 704/255, 704/257, 704/270, 704/272, 704/270.1
• US Class Current: 704/9
• 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 3/04895 Guidance during keyboard input operation, e.g. prompting
• CPC Class Codes: G06F 40/166 Editing, e.g. inserting or deleting
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation

Abstract

In response to determining that a first series of user inputs corresponds to a first character string, the computing device outputs, for display at a display device, the first character string. In response to determining that the first character string does not match a word in a lexicon and in response to determining that the first character string ends with a word delimiter, the computing device replaces the first character string with a second character string. After receiving the first series of user inputs, the computing device receives a second series of user inputs. In response to determining that the second series of user inputs corresponds to a third character string, the computing device outputs the third character string. The computing device determines, based at least in part on the first and second series of user inputs, a fourth character string and outputs, for display, the fourth character string.

Claims

1. A method comprising:

receiving, by a computing device, a first series of one or more user inputs;

outputting, by the computing device, for display at a display device, a first string of characters based on the first series of one or more user inputs;

in response to determining that the first string does not match a word in a lexicon and that the first string ends with a word delimiter, outputting, by the computing device and for display at the display device, a second string of characters in place of the first string of characters;

after receiving the first series of one or more user inputs, receiving, by the computing device, a second series of one or more user inputs;

outputting, by the computing device, for display at the display device, a third string of characters based on the second series of one or more user inputs;

determining, by the computing device and based at least in part on the first and second series of one or more user inputs, a fourth string of characters; and

outputting, by the computing device and for display at the display device, the fourth string in place of the second and third strings of characters.

2. The method of claim 1, wherein the fourth string does not include more than one word in the lexicon.

3. The method of claim 1, wherein the fourth string includes two or more words in the lexicon.

4. The method of claim 1, wherein:

the method further comprises outputting, by the computing device and for display at the display device, a suggestion element that includes the fourth string of characters; and

outputting the fourth string in place of the second and third strings comprises, in response to receiving an indication of a user input to select the suggestion element, outputting, by the computing device and for display at the display device, the fourth string in place of the second and third strings.

5. The method of claim 4, wherein:

the suggestion element is a first suggestion element;

determining the fourth string comprises;

determining, by the computing device and based at least in part on the first and second series of one or more user inputs, a plurality of replacement candidates, each of the replacement candidates being a string of characters; and

selecting, by the computing device, a portion of the plurality of replacement candidates, the portion of the plurality of replacement candidates including the fourth string; and

the method further comprises outputting a plurality of suggestion elements, the plurality of suggestion elements including the first suggestion element, each of the suggestion elements specifying a different replacement candidate in the portion of the plurality of replacement candidates.

6. The method of claim 1, wherein the word delimiter is a first word delimiter and outputting the fourth string comprises in response to determining that the third string ends with a second word delimiter, outputting, by the computing device and for display at the display device, the fourth string in place of the second and third strings.

7. The method of claim 1, wherein:

determining the fourth string comprises determining, by the computing device and based on the first and second series of one or more user inputs, a plurality of replacement candidates, the plurality of replacement candidates including the fourth string; and

the method further comprises determining, by the computing device, that the fourth string has a lowest replacement score among the plurality of replacement candidates.

8. The method of claim 1, wherein the first series of one or more user inputs comprises a series of one or more tapping gestures at a presence-sensitive display.

9. The method of claim 1, wherein the first series of one or more user inputs comprises a sliding movement of an input object at a presence-sensitive display.

10. The method of claim 1, wherein:

the word delimiter is a space character,

the third string comprises a first character followed by a substring,

the fourth string comprises the first string followed by the first character, followed by the word delimiter, followed by the substring, and

the first string followed by the first character and the substring match words in the lexicon.

11. The method of claim 1, wherein:

the word delimiter is a space character,

the first string comprises a substring followed by a misplaced character,

the fourth string comprises the substring, followed by the word delimiter, followed by the misplaced character, followed by the third string, and

the substring and the misplaced character followed by the third string match words in the lexicon.

12. The method of claim 1, wherein the fourth string matches a word in the lexicon and the fourth string matches the first string followed by an alphanumeric character followed by the third string.

13. The method of claim 1, wherein the fourth string matches a word in the lexicon, the word delimiter is a space character, and the fourth string matches the first string appended with the third string.

14. The method of claim 1, further comprising using, by the computing device, a finite state transducer (FST) to determine that the second series of one or more user inputs corresponds to the third string.

15. The method of claim 14, wherein using the FST comprises determining, by the computing device and based at least in part on cost values of tokens in an active beam, a highest-ranked token in the active beam, wherein the highest-ranked token in the active beam specifies the third string, wherein each of the tokens in the active beam is associated with a node in the FST.

16. The method of claim 15, wherein a particular token in the active beam is associated with a particular node of the FST and the fourth string includes a word that is associated with a terminal node of the FST that is reachable from the particular node.

17. The method of claim 1, wherein:

the method further comprises determining, by the computing device and based on the first series of one or more user inputs, a plurality of replacement candidates; and

outputting the second string in place of the first string comprises outputting, by the computing device, for display at the display device, and based at least in part on a comparison of a replacement score of the second string and a threshold, the second string in place of the first string.

18. A computing device that comprises one or more processors configured to:

receive a first series of one or more user inputs;

in response to determining that the first series of one or more user inputs corresponds to a first string of characters, output, for display at the display device, the first string of characters;

in response to determining that the first string does not match a word in a lexicon and in response to determining that the first string ends with a word delimiter, output, for display at the display device, a second string of characters in place of the first string of characters;

after receiving the first series of one or more user inputs, receive a second series of one or more user inputs;

in response to determining that the second series of one or more user inputs corresponds to a third string, output, for display at the display device, the third string;

determine, based at least in part on the first and second series of one or more user inputs, a fourth string of characters; and

output, for display at the display device, the fourth string of characters in place of the second and third strings.

19. The computing device of claim 18, wherein the one or more processors are configured to:

output, for display at the display device, a suggestion element that contains the fourth string of characters; and

in response to receiving an indication of a user input to select the suggestion element, output, for display at the display device, the fourth string of characters in place of the second and third strings of characters.

20. A non-transitory computer-readable storage medium that stores instructions that, when executed by one or more processors of a computing device, cause the computing device to:

in response to determining that a first series of one or more user inputs corresponds to a first string of characters, output, for display at a display device, the first string of characters;

in response to determining that the first string of characters does not match a word in a lexicon and in response to determining that the first string of characters ends with a word delimiter, output, for display at the display device, a second string of characters in place of the first string of characters;

in response to determining that a second series of one or more user inputs received after the first series of one or more user inputs corresponds to a third string of characters, output, for display at the display device, the third string of characters;

determine, based at least in part on the first and second series of one or more user inputs, a fourth string of characters; and

output, for display at the display device, the fourth string in place of the second and third strings of characters.