Source: http://www.google.de/patents/US9747272
Timestamp: 2018-01-18 06:03:11
Document Index: 380947137

Matched Legal Cases: ['Application No. 61', 'Application No. 13780034', 'Application No. 13780034', 'Application No. 201380052562', 'Application No. 13780034', 'Application No. 201380052562']

Patent US9747272 - Feature-based autocorrection - Google Patentsuche
A computing device is described that outputs for display at a presence-sensitive screen, a graphical keyboard having keys. The computing device receives an indication of a selection of one or more of the keys. Based on the selection the computing device determines a character string from which the computing...http://www.google.de/patents/US9747272?utm_source=gb-gplus-sharePatent US9747272 - Feature-based autocorrection
Veröffentlichungsnummer US9747272 B2
Anmeldenummer US 14/199,740
Eingetragen 6. März 2014
Prioritätsdatum 16. Okt. 2012
Auch veröffentlicht unter CN104718543A, EP2909703A1, US8713433, US20140104175, US20140188460, WO2014062453A1
Veröffentlichungsnummer 14199740, 199740, US 9747272 B2, US 9747272B2, US-B2-9747272, US9747272 B2, US9747272B2
Erfinder Yu Ouyang, Shumin Zhai
Patentzitate (111), Nichtpatentzitate (18), Klassifizierungen (13), Juristische Ereignisse (1)
US 9747272 B2
A computing device is described that outputs for display at a presence-sensitive screen, a graphical keyboard having keys. The computing device receives an indication of a selection of one or more of the keys. Based on the selection the computing device determines a character string from which the computing device determines one or more candidate words. Based at least in part on the candidate words and a plurality of features, the computing device determines a spelling probability that the character string represents an incorrect spelling of at least one candidate word. The plurality of features includes a spatial model probability associated with at least one of the candidate words. If the spelling probability satisfies a threshold, the computing device outputs for display the at least one candidate word.
receiving, by a computing device, a first user input at a keyboard;
responsive to receiving the first user input, outputting, by the computing device, for display, based on the first user input, an initial word from a lexicon;
responsive to receiving a second user input at the keyboard, outputting, by the computing device, for display, and based on the second user input, one or more subsequent words from the lexicon;
while displaying the initial word and the one or more subsequent words, determining, by the computing device, based on the one or more subsequent words, a language model probability associated with at least one candidate word that is determined to be a replacement for the initial word, wherein the language model probability associated with the at least one candidate word represents a likelihood that the at least one candidate word is a correct spelling of the initial word in a sequence of words in which the one or more subsequent words follow the initial word;
determining whether the language model probability associated with the at least one candidate word satisfies a threshold;
responsive to determining that the language model probability associated with the at least one candidate word satisfies the threshold, outputting, by the computing device, for display, the at least one candidate word within a predefined distance above, below, or adjacent to the initial word;
determining, by the computing device, based on a third user input, a selection of the at least one candidate word;
responsive to determining the selection of the at least one candidate word:
refraining from outputting, by the computing device, for display, the at least one candidate word within the predefined distance above, below, or adjacent to the initial word; and
outputting, by the computing device, for display, the at least one candidate word in place of the initial word.
prior to receiving the first user input, and prior to outputting the initial word for display, outputting, by the computing device, based at least in part on a fourth user input at the keyboard, and for display, one or more prior words from the lexicon,
wherein determining the language model probability associated with the at least one candidate word comprises, determining, by the computing device, based on at least one of the one or more prior words and the one or more subsequent words, the language model probability associated with the at least one candidate word,
wherein the language model probability associated with the at least one candidate word represents a likelihood that the at least one candidate word is a correct spelling of the initial word in a sequence of words in which the one or more prior words proceed the initial word and the one or more subsequent words follow the initial word.
3. The method of claim 1, wherein outputting the at least one candidate word for display comprises outputting, by the computing device, for display, a suggestion bar region that includes the at least one candidate word as at least one suggested word replacement for the initial word.
4. The method of claim 1, wherein outputting the at least one candidate word for display comprises:
outputting, by the computing device, for display, at an initial point in time, the at least one candidate word; and
responsive to determining that an elapsed time between the initial point in time and a later point in time exceeds a time threshold, refraining from outputting, by the computing device, for display, the at least one candidate word.
5. The method of claim 1, wherein the at least one candidate word comprises a first candidate word and a second candidate word, wherein outputting the at least one candidate word for display comprises:
determining, by the computing device, based at least in part on a lexicon, a spelling probability of the first candidate word representing a likelihood that the initial word comprises an incorrect spelling of the first candidate word;
determining, by the computing device, based at least in part on the lexicon, a spelling probability of the second candidate word representing a likelihood that the initial word comprises an incorrect spelling of the second candidate word;
determining, by the computing device, a value comprising a difference between the spelling probability of the first candidate word and the spelling probability of the second candidate word;
determining whether the value satisfies an ambiguity threshold; and
responsive to determining that the value does not satisfy the ambiguity threshold, outputting, by the computing device, for display, the first candidate word and the second candidate word.
6. The method of claim 5, wherein the value is a first value and the difference is a first difference, the method further comprising:
determining, by the computing device, a second value comprising a second difference between the spelling probability of the first candidate word and the spelling probability of the second candidate word;
determining whether the second value satisfies the ambiguity threshold; and
responsive to determining that the second value satisfies the ambiguity threshold, outputting, by the computing device, for display, the one of the first candidate word and the second candidate word that has the greater spelling probability.
7. The method of claim 1, wherein the at least one candidate word comprises an initial candidate word, the method further comprising:
receiving, by the computing device, a fourth user input detected at an input location of an input device that corresponds to a region of a display device at which the candidate word is displayed; and
responsive to receiving the third user input, outputting, by the computing device, for display, at least one additional candidate word that is determined to be a replacement for the initial word.
outputting, by the computing device, for display, a graphical keyboard, wherein the keyboard at which the computing device receives the first, second, and third user inputs comprises the graphical keyboard.
receive a first user input at a keyboard;
responsive to receiving the first user input, output, for display, based on the first user input, an initial word from a lexicon;
responsive to receiving a second user input at the keyboard, output, for display, and based on the second user input, one or more subsequent words from the lexicon;
while displaying the initial word and the one or more subsequent words, determine, based on at least one of the one or more subsequent words, a language model probability associated with at least one candidate word that is determined to be a replacement for the initial word, wherein the language model probability associated with the at least one candidate word represents a likelihood that the at least one candidate word is a correct spelling of the initial word in a sequence of words in which the one or more subsequent words follow the initial word;
determine whether the language model probability associated with the at least one candidate word satisfies a threshold;
responsive to determining that the language model probability associated with the at least one candidate word satisfies the threshold, output, for display, at an initial point in time, the at least one candidate word
determine whether an elapsed time between the initial point in time and a later point in time exceeds a time threshold; and
responsive to determining that the elapsed time between the initial point in time and the later point in time exceeds the time threshold, refraining from outputting, for display, the at least one candidate word.
10. The computing device of claim 9, wherein the instructions, when executed, further cause the at least one processor to:
prior to receiving the first user input, and prior to outputting the initial word for display:
receive a third user input at the keyboard; and
output, for display, one or more prior words from the lexicon,
wherein the language model probability associated with the at least one candidate word is determined by at least determining, based on at least one of the one or more prior words and the one or more subsequent words, the language model probability associated with the at least one candidate word, wherein the language model probability associated with the at least one candidate word represents a likelihood that the at least one candidate word is a correct spelling of the initial word in a sequence of words in which the one or more prior words proceed the initial word and the one or more subsequent words follow the initial word.
11. The computing device of claim 9, wherein the instructions, when executed, further cause the at least one processor to output the at least one candidate word for display by at least outputting, for display, the at least one candidate word within a predefined distance above, below, or adjacent to the initial word.
12. The computing device of claim 9, wherein the instructions, when executed, further cause the at least one processor to output the at least one candidate word for display by at least outputting, for display, a suggestion bar region that includes the at least one candidate word as at least one suggested word replacement for the initial word.
13. A computer-readable storage medium comprising instructions that, when executed, configure at least one processor of a computing device to:
responsive to receiving the first indication, output, for display, based on the first user input, an initial word from a lexicon;
14. The computer-readable storage medium of claim 13 comprising additional instructions that, when executed, further configure the at least one processor of the computing device to:
wherein the language model probability associated with the at least one candidate word is determined by at least determining, based on at least one of the one or more prior words and the one or more subsequent words, the language model probability associated with the at least one candidate word,
15. The computer-readable storage medium of claim 13, wherein the instructions, when executed, further configure the at least one processor of the computing device to output the at least one candidate word for display by at least outputting, for display, the at least one candidate word within a predefined distance above, below, or adjacent to the initial word.
16. The computer-readable storage medium of claim 13, wherein the instructions, when executed, further configure the at least one processor of the computing device to output the at least one candidate word for display by at least outputting, for display, a suggestion bar region that includes the at least one candidate word as at least one suggested word replacement for the initial word.
This application is a Continuation of application Ser. No. 13/733,701, filed on Jan. 3, 2013, which claims the benefit of U.S. Provisional Application No. 61/714,589, filed Oct. 16, 2012, the entire content of each of which are hereby incorporated by reference.
Computing devices (e.g., mobile phones, tablet computers, etc.) may provide a graphical keyboard as part of a graphical user interface for composing text using a presence-sensitive display. For instance, a presence-sensitive display of a computing device may output a graphical, or soft, keyboard that permits the user to enter data by tapping (or otherwise indicating) keys displayed at the presence-sensitive display. The graphical keyboard may enable a user of the computing device to compose and edit text included in, for example, an e-mail, a text message, a document, etc.
Some computing devices also include an auto-correction system to detect and correct spelling and grammar errors within user-entered text. Some auto-correction systems, however, may fail to detect non-spelling or non-grammar errors within the text and/or may make erroneous automatic corrections. Some auto-correction systems may fail to detect such errors because these systems perform exact word matching for misspelled dictionary words within the text. Consequently, such auto-detection systems may not detect an error so long as the entered text includes a valid word (e.g., a word found within a dictionary employed by the system). In addition, if a user intentionally types a non-dictionary word, the auto-correction system may automatically (and contrary to the user's intent) replace the misspelled word with a dictionary word.
In one example, the disclosure is directed to a method that may include outputting, by a computing device and for display at a presence-sensitive screen, a graphical keyboard comprising a plurality of keys. The method may further include receiving, by the computing device, an indication of a selection of one or more of the plurality of keys. The method may further include determining, by the computing device and based at least in part on the indication of the selection, a character string. The method may further include determining, by the computing device and based at least in part on the character string, a plurality of candidate words. The method may further include determining, by the computing device, and based at least in part on the plurality of candidate words and a plurality of features, a spelling probability that the character string comprises an incorrect spelling of at least one of the plurality of candidate words. The plurality of features may comprise at least a spatial model probability associated with at least one of the one or more candidate words. In response to determining that the spelling probability satisfies a threshold, the method may further include outputting, by the computing device, for display, the at least one of the plurality of candidate words.
In another example, the disclosure is directed to 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 a selection of one or more of a plurality of keys of a keyboard input device. The at least one module may be further operable by the at least one processor to determine, based at least in part on the indication of the selection, a character string. The at least one module may be further operable by the at least one processor to determine, based at least in part on the character string, a plurality of candidate words. The at least one module may be further operable by the at least one processor to determine, based at least in part on the plurality of candidate words and a plurality of features, a spelling probability that the character string comprises an incorrect spelling of at least one of the plurality of candidate words. The plurality of features may include at least a spatial model probability associated with each of the one or more candidate words. In response to determining that the spelling probability satisfies a threshold, the at least one module may be further operable by the at least one processor to output, for display, the at least one of the plurality of candidate words.
In another example, the disclosure is directed to a computer-readable storage medium encoded with instructions that, when executed, cause at least one processor of a computing device to output, for display at a presence-sensitive screen, a graphical keyboard comprising a plurality of keys. The instructions, when executed, may further cause the at least one processor of the computing device to receive an indication of a selection of one or more of the plurality of keys. The instructions, when executed, may further cause the at least one processor of the computing device to determine based at least in part on the indication of the selection, a character string. The instructions, when executed, may further cause the at least one processor of the computing device to determine based at least in part on the character string, a plurality of candidate words. The instructions, when executed, may further cause the at least one processor of the computing device to determine, based at least in part on the plurality of candidate words and a plurality of features, a spelling probability that the character string comprises an incorrect spelling of at least one of the plurality of candidate words. The plurality of features may comprise at least a spatial model probability associated with each of the one or more candidate words. In response to determining that the spelling probability satisfies a threshold, the instructions, when executed, may further cause the at least one processor of the computing device to output, the at least one of the plurality of candidate words.
FIG. 1 is a conceptual diagram illustrating an example computing device that is configured to detect errors within text and suggest corrections, in accordance with one or more aspects of the present disclosure.
FIGS. 3A-3B are conceptual diagrams illustrating example graphical user interfaces for presenting suggested corrections to text, in accordance with one or more aspects of the present disclosure.
FIG. 4 is a conceptual diagram illustrating an additional example graphical user interface for presenting suggested corrections to text, in accordance with one or more aspects of the present disclosure.
FIG. 5 is a flowchart illustrating an example operation of the computing device, in accordance with one or more aspects of the present disclosure.
A computing device (e.g., a laptop, a mobile phone, a tablet computer, a table top computer, etc.) may receive input at a presence-sensitive display that outputs a graphical keyboard. In response to receiving the input, the computing device may generate text for display at the presence-sensitive display. The text generated for display by the computing device may include intentional and unintentional spelling and grammar mistakes. In general, techniques of this disclosure may enable a computing device to detect a potential spelling error of a word within text generated responsive to user input and output suggested words that may correct a spelling error included in the user input.
In some examples, the computing device can detect a spelling error and determine suggested words to correct the error by utilizing several systems (e.g., a spatial model, a language model, etc.). Using these systems, the computing device may determine a probability that a word within the generated text is a misspelling of at least one of the suggested words. If the probability satisfies a threshold, the computing device may output one or more of the suggested words that a user can optionally ignore, or select to fix the spelling error within the word.
In this way the computing device may more efficiently generate text based on user input than other devices that use conventional word-matching techniques. Consequently, words suggested by the computing device upon detection of a spelling error may generally be more accurate than those suggested by other devices. As such, a user of the computing device may spend less time fixing auto-correction errors than a user of other devices, and may more quickly and easily select accurate suggested words for correction of a spelling error. By enabling more efficient text input at the graphical keyboard, the computing device may also perform fewer operations to process and generate text from such input, and thus consume less processing power than other computing devices.
In one example, a computing device receives a user input, as multiple finger taps or gestures in a sequential order, across locations of a presence-sensitive screen that present keys of a graphical keyboard. The computing device receives the user input as a selection of one or more keys of the graphical keyboard and generates multiple character strings (e.g., “my” “dead” “friend” “is” “visiting” “tomorrow”) based on the selection. The presence-sensitive screen may output each of the multiple character strings.
When determining whether one of the character strings includes an error, the computing device may determine one or more candidate words as replacement words for the character string. For example, the computing device may determine the word “dear” is a candidate word to replace the character string “dead”. For at least one candidate word, the computing device may determine a probability that the character string “dead” represents an incorrect spelling of the candidate word “dear”. In other words, the computing device may determine a likelihood (e.g., a probability) that the user intended to type “dear” instead of “dead”.
The computing device may base the spelling probability on a plurality of features including a spatial model probability (“SMP”) (e.g., a spatial model confidence score) associated with each of the one or more candidate words. In other words, if locations of a user's tap (or gesture shape) at a graphical keyboard (e.g., graphical keyboard 18) do not accurately match the key positions for the letters in the committed word (e.g., the character string), then there may be more uncertainty about this correction. In the tapping case this could mean that the user was typing an out-of-vocabulary word that was mistakenly corrected. As described below, computing device 10 may indicate this and offer the literal typed string as an alternative.
For example, the SMP associated with the candidate word “dear” may exceed the SMP associated with the character string “dead”. In other words, the locations of the presence-sensitive screen at which the user provided input to generate the character string “dead” may more closely correspond to key locations of the presence-sensitive screen that display the keys <D-key> <E-key> <A-key> <R-key> rather than the keys <D-key> <E-key> <A-key> <D-key>. If the spelling probability exceeds a threshold, the computing device may determine that the character string (e.g., dead) represents an error, and in response, output, for display (e.g., at the presence-sensitive screen) the at least one candidate word (e.g., dear) as a suggested replacement.
FIG. 1 is a conceptual diagram illustrating an example computing device 10 that is configured to detect errors within text and suggest corrections, in accordance with one or more aspects of the present disclosure. In the example of FIG. 1, computing device 10 is a mobile phone. However, in other examples, computing device 10 may be a tablet computer, a personal digital assistant (PDA), a laptop computer, a portable gaming device, a portable media player, an e-book reader, a watch, or another type of computing device.
As shown in FIG. 1, computing device 10 includes a user interface device (UID) 12. UID 12 of computing device 10 may function as an input device for computing device 10 and as an output device. UID 12 may be implemented using various technologies. For instance, UID 12 may function as an input device using a resistive touchscreen, a surface acoustic wave touchscreen, a capacitive touchscreen, a projective capacitance touchscreen, a pressure sensitive screen, an acoustic pulse recognition touchscreen, or another presence-sensitive screen technology. UID 12 may function as an output device using any one or more of a liquid crystal display (LCD), dot matrix display, light emitting diode (LED) display, organic light-emitting diode (OLED) display, e-ink, or similar monochrome or color display capable of outputting visible information to the user of computing device 10.
UID 12 of computing device 10 may include a presence-sensitive screen that may receive tactile user input from a user of computing device 10. UID 12 may receive the tactile user input by detecting one or more taps and/or gestures from a user of computing device 10 (e.g., the user touching or pointing to one or more locations of UID 12 with a finger or a stylus pen). The presence-sensitive screen of UID 12 may present output to a user. UID 12 may present the output as a user interface (e.g., user interface 14) which may be related to functionality provided by computing device 10. For example, UID 12 may present various functions and applications executing on computing device 10 such as an electronic message application, a map application, etc. UID 12 may present one or more information and control panels, such as a notification panel that includes notification information for a user and a settings panel that includes system settings information of computing device 10.
Computing device 10 may include user interface (“UI”) module 20, keyboard module 22, gesture module 24, and spatial model (“SM”) module 26. Modules 20, 22, 24, and 26 may perform operations described herein using software, hardware, or a mixture of both hardware and software residing in and executing on computing device 10. Computing device 10 may execute modules 20, 22, 24, and 26 with multiple processors. Computing device 10 may execute modules 20, 22, 24, and 26 as a virtual machine executing on underlying hardware.
Gesture module 24 of computing device 10 may receive from UID 12, one or more indications of user input detected at the presence-sensitive screen of UID 12. Gesture module 24 is described in more detail below under the description of FIG. 2, however in summary, each time UID 12 receives an indication of user input detected at a location of the presence-sensitive screen, gesture module 24 may receive information about the user input from UID 12. Gesture module 24 may assemble the information received from UID 12 into a time-ordered sequence of motion events. Each motion event in the sequence may include a location component corresponding to a location of UID 12, a time component related to when UID 12 detected user input at the location, and an action component related to whether the motion event corresponds to a lift up or a push down at the location. Gesture module 24 may determine the sequence of motion events represent characteristics of a gesture, such as a start location of a gesture, a length of a gesture, a velocity of a gesture, an end location of a gesture, etc. Based on the characteristics, gesture module 24 may determine a user input represents a tap gesture and/or a continuous swipe gesture. Gesture module 24 may transmit, as output to UI module 20, the sequence of motion events.
UI module 20 may cause UID 12 to present user interface 14. User interface 14 includes graphical elements displayed at various locations of UID 12. FIG. 1 illustrates edit region 16 of user interface 14 and graphical keyboard 18 of user interface 14. Graphical keyboard 18 includes graphical elements displayed as keys. Edit region 16 may include graphical elements such as images, objects, hyperlinks, characters of text, etc. In the example of FIG. 1, edit region 16 includes graphical elements displayed as characters of text and candidate word 30. A user of computing device 10 may enter text in edit region 16 by providing user input at locations of UID 12 that display the keys of graphical keyboard 18.
UI module 20 may act as an intermediary between various components of computing device 10 to make determinations based on input detected by UID 12 and generate output presented by UID 12. For instance, UI module 20 may receive, as an input from keyboard module 22, a representation of a keyboard layout of the keys included in graphical keyboard 18. UI module 20 may receive, as an input from gesture module 24, a sequence of motion events generated from information about user input detected by UID 12. UI module 20 may determine, based on the location components in the sequence motion events, one or more location components approximates a selection of one or more keys (e.g., UI module 20 may determine the location of each of the motion events corresponds to an area of UID 12 that presents graphical keyboard 18). UI module 20 may transmit, as output to keyboard module 22, the sequence of motion events received from gesture module 24, along with locations where UID 12 presents each of the keys. In response, UI module 20 may receive, as an input from keyboard module 22, a character string and one or more candidate words. UI module 20 may update user interface 14 to include the character string and the one or more candidate words within edit region 16 and cause UID 12 to display the updated user interface 14.
Keyboard module 22 of computing device 10 may transmit, as output to UI module 20 (for inclusion as graphical keyboard 18 of user interface 14) a keyboard layout including a plurality of keys related to one or more written languages (e.g., English, French, Russian, etc.). Keyboard module 22 may assign one or more characters or operations to each key of the plurality of keys in the keyboard layout. For instance, keyboard module 22 may generate a QWERTY keyboard layout including keys that represent characters used in typing the English language. The QWERTY keyboard layout may also include keys that represent operations used in typing the English language (e.g., backspace, delete, spacebar, enter, etc.).
Keyboard module 22 may receive data from UI module 20 that represents the sequence of motion events generated by gesture module 24. Keyboard module 22 may also receive data from UI module 20 that represents locations of the presence-sensitive screen of UID 12 where UID 12 presents each of the keys of graphical keyboard 18. Keyboard module 22 may determine, based on the locations of the keys, the sequence of motion events represents a selection of one or more keys. Keyboard module 22 may generate a character string based on the selection where each character in the character string corresponds to at least one key in the selection. Keyboard module 22 may send data indicating the character string to UI module 20 for inclusion in edit region 16 of user interface 14.
To determine the sequence of motion events represents a selection of one or more keys, keyboard module 22 includes SM module 26. SM module 26 may compare the location components (e.g., coordinates) in the sequence of motion events to respective locations of one or more keys of graphical keyboard 18 and generate a probability that a selection of a key occurred. SM module 26 may determine a probability (i.e., a spatial model probability or a SMP) that one or more motion events in the sequence indicate an individual selection of a key of graphical keyboard 18. For example, SM module 26 may compare the location component of each motion event in the sequence of motion events to a key location of a particular key of graphical keyboard 18. The location component of each motion event in the sequence may include one or more locations of UID 12. A key location (e.g., a centroid of a key) of a key in graphical keyboard 18 may include a different location of UID 12. SM module 26 may determine a probability based on the comparison that the motion event corresponds to a selection of the key based on a Euclidian distance between the two locations. SM module 26 may correlate a higher probability to a key that shares a smaller Euclidian distance with a motion event than a key that shares a greater Euclidian distance with the motion event (e.g., the probability of a key selection may exceed ninety nine percent when a key shares a near zero Euclidian distance to a motion event and the probability of the key selection may decrease approximately proportionate to an increase in the Euclidian distance). Based on the SMP associated with each key, keyboard module 22 may assemble the individual key selections with the highest spatial model probabilities into a time-ordered sequence of keys that keyboard module 22 may then determine represent a character string.
Keyboard module 22 may determine a sequence of characters and keyboard operations from the sequence of keys to determine a character string represented by the sequence of motion events. For example, each key of the keyboard may represent a character or a keyboard operation. Keyboard module 22 may determine, based on the sequence of keys, particular characters represented by one or more key selections by combining individual character key selections with keyboard operation key selections. A character such as a number or a lowercase letter may require a single character key selection (e.g., <letter-key>, <number-key>, etc.). A character such as a capitalized letter may require two key selections (e.g., <shift-key>+<letter-key>, etc.). Keyboard module 22 may determine a correction in the key sequence based on one or more character key selections followed by a keyboard operation key selection (e.g., <letter-key>+<backspace-key>, etc.). Keyboard module 22 may determine a character string from the sequence of keys by combining individual key presses into a sequence of characters that accounts for corrections.
Keyboard module 22 may access a lexicon of computing device 10 to autocorrect (e.g., spellcheck) the character string generated from the sequence of keys before outputting the character string to UI module 20 for inclusion within edit region 16 of user interface 14. The lexicon is described in more detail below. In summary, the lexicon of computing device 10 may include a list of words within a written language vocabulary. Keyboard module 22 may perform a lookup in the lexicon, of a character string, to generate one or more candidate words that include parts or all of the characters of the character string. In other words, the one or more candidate words may represent alternative spellings or arrangements of the characters in the character string based on a comparison with words within the lexicon.
For example, keyboard module 22 may determine the selection of keys corresponds to the sequence of letters “d-e-a-d” and as such, the character string “dead”. Keyboard module 22 may compare the string “dead” to one or more words in the lexicon. In some examples, techniques of this disclosure may use a Jaccard similarity coefficient that indicates a degree of similarity between a character string inputted by a user and a word in the lexicon. In general, a Jaccard similarity coefficient, also known as a Jaccard index, represents a measurement of similarity between two sample sets (e.g., a character string and a word in a dictionary). Based on the comparison, keyboard module 22 may generate a Jaccard similarity coefficient for each of the one or more words in the lexicon. Keyboard module 22 may determine one or more candidate words of the lexicon with a greatest Jaccard similarity coefficient (e.g., “dead”, “deaf”, “deal”, “dean”, “dear”, and “deadly”). Each candidate word may represent an alternative arrangement of some or all of the characters in the character string.
Keyboard module 22 may determine that the candidate word with the highest Jaccard similarity coefficient represents the autocorrected character string that keyboard module 22 outputs to UI module 20 for inclusion in edit region 16. In some examples, the candidate word with the highest Jaccard similarity coefficient matches the character string generated by keyboard module 22 from the key sequence (e.g., the lexicon may return “dead” as the highest ranking candidate word since the arrangement of the characters in “dead” correspond to a word in the lexicon).
Rather than relying only on a lexicon to autocorrect words based on spelling and/or grammar, techniques of the disclosure use a plurality of features including output from a spatial model(s) to determine if a character string input was erroneous. In some examples, to improve the accuracy with which a computing device decides whether to indicate an error to the user, techniques of the disclosure further determine, based on a probability, whether to indicate the character string input was erroneous. In other words, techniques of the disclosure use a plurality of features, and in some cases a probability, to improve autocorrections of character strings.
The techniques are now further described in detail with reference to FIG. 1. In the example of FIG. 1, UID 12 outputs for display graphical keyboard 18 comprising a plurality of keys. For example, keyboard module 22 may generate data that includes a representation of graphical keyboard 18. UI module 20 may generate user interface 14 and include graphical keyboard 18 in user interface 14 based on the data representing graphical keyboard 18. UI module 20 may send information to UID 12 that includes instructions for displaying user interface 14 on a presence-sensitive screen of UID 12. UID 12 may receive the information and cause the presence-sensitive screen of UID 12 to present user interface 14 including edit region 16 and graphical keyboard 18. Graphical keyboard 18 may include a plurality of keys.
Computing device 10 may receive an indication of a selection of one or more of the plurality of keys. For example, as UID 12 presents user interface 14 on the presence-sensitive screen, a user may provide input at a location on the presence-sensitive screen of UID 12 that displays graphical keyboard 18. Gesture module 24 may receive information indicating the user input from UID 12 and assemble the information into a time-ordered sequence of motion events. UI module 20 may receive the sequence of motion events from gesture module 24 and determine location components of each motion event in the sequence, correspond to an area of UID 12 that presents graphical keyboard 18. UI module 20 may determine UID 12 received an indication of a selection of one or more of the plurality of keys.
Computing device 10 may determine a character string based at least in part on the indication of the selection of the keys. For example, UI module 20 may transmit the sequence of motion events to keyboard module 22 along with locations where UID 12 presents each of the keys of graphical keyboard 18. Keyboard module 22 may receive the sequence of motion events along with the key locations from UI module 20. Keyboard module 22 may determine the location component of each motion event in the sequence of motion events and each key location to determine a key that shares the same location of UID 12 as the motion event. For example, for each motion event in the sequence, SM module 26 of keyboard module 22 may determine a Euclidian distance between the location component of the motion event and the location of each key. Based on the Euclidian distances, SM module 26 may determine a SMP that one or more motion events corresponds to a selection of a key. Keyboard module 22 may assemble the keys with the highest SMP into a sequence of keys. Keyboard module 22 may determine a character string that represents the sequence of selected keys. For example, keyboard module 22 may determine the sequence of selected keys includes “<D-key> <E-key> <A-key> <D-key>”. Keyboard module 22 may determine the sequence of selected keys corresponds to the character string “dead”.
Computing device 10 may determine, based at least in part on the character string, a plurality of candidate words. For example, keyboard module 22 may utilize a lexicon to generate one or more candidate words that share a similar sequence of characters as the character string (e.g., “dead”). Keyboard module 22 may pass the character string as input to the lexicon and receive a plurality of words that include a portion of or all of the characters within the character string. For example, the lexicon may assign a Jaccard similarity coefficient to each word in the lexicon based on a comparison between each word and the character string. Keyboard module 22 may select, as the plurality of candidate words, the words from the lexicon having the greatest Jaccard similarity coefficient (e.g., “dead”, “deaf”, “deal”, “dean”, “dear”, and “deadly”).
Computing device 10 may determine, based at least in part on the plurality of candidate words and a plurality of features, a spelling probability that the character string comprises an incorrect spelling of at least one of the plurality of candidate words. The plurality of features comprising at least a spatial model probability associated with each of the one or more candidate words. For example, keyboard module 22 may determine a spelling probability that the character string represents an incorrect spelling of at least one of the candidate words from the lexicon. A spelling probability that exceeds a threshold (e.g., fifty percent) may indicate to keyboard module 22 an error in the user input, such that the user may have intended to type one of the candidate words using graphical keyboard 18 and not the character string generated and determined previously by keyboard module 22 from the selection of the plurality of keys.
Keyboard module 22 may utilize various types of data about the user input and candidate words, including a SMP for each candidate word, to determine the spelling probability of the character string. For example, as described above, SM module 26 may determine, for each of the motion events in the sequence of motion events, a SMP of each key in graphical keyboard 18. In generating the character string, keyboard module 22 originally assembled only the keys with the highest SMP into a sequence of keys corresponding to the sequence of motion events. In some examples, a product of the SMP for each key included in the original sequence of keys may be referred to as a character string SMP. In other examples, a sum of the SMP for each key included in the original sequence of keys may be referred to as a character string SMP.
Keyboard module 22 can similarly determine a SMP associated with each of the candidate words (e.g., from the lexicon). For example, keyboard module 22 may determine a spatial-test sequence of keys for each candidate word. The spatial-test sequence of keys represents the key selections that, if typed on graphical keyboard 18 by a user, would correspond to characters of a candidate word. Keyboard module 22 may determine, for example, the product of the SMP of each key in the spatial-test sequence of keys represents the SMP associated with that candidate word. A high value SMP associated with a candidate word (e.g., greater than ninety percent) may indicate that the sequence of motion events originally received from gesture module 24 includes location components that share a close Euclidian distance to locations of the keys in the spatial-test sequence of keys. Keyboard module 22 may repeat these steps to determine the SMP associated with each candidate word.
From the SMP associated with each candidate word, and from other features discussed below with respect to the other figures, keyboard module 22 may determine the spelling probability of the character string. Keyboard module 22 may at first assign a zero spelling probability to the character string, indicating a zero chance or low likelihood the character string includes an error. In the case where the SMP of one or more candidate words exceeds fifty percent, keyboard module 22 may increment the spelling probability of the character string (e.g., using a weighted average of the SMP associated with each candidate word and probabilities determined from other features). A higher value spelling probability of the candidate word may indicate a greater chance than not that the character string represents an incorrect spelling of a candidate word.
In response to determining that the spelling probability satisfies a threshold, UI device 12 may output the at least one of the plurality of candidate words. In other words, keyboard module 22 may determine the character string represents an error if the spelling probability of the character string exceeds a threshold (e.g., approximately fifty percent). And in the case when the spelling probability does exceed the threshold, keyboard module 22 may command UI module 20 to update user interface 14 and cause UID 12 to output on the presence-sensitive screen suggested corrections to the character string. For example, keyboard module 22 may determine the spelling probability of the character string included exceeds ninety percent. Based on a determination that ninety percent exceeds a fifty percent threshold, keyboard module 22 may transmit, as output to UI module 20, at least one of the plurality of candidate words for inclusion in edit region 16 of user interface 14. UI module 20 may receive, as input from keyboard module 22, the at least one of the plurality of candidate words and modify edit region 16 of user interface 14 to include the at least one of the plurality of candidate words as a string of text. UI module 20 may cause UID 12 to present the modified user interface on the presence-sensitive screen. FIG. 1 includes candidate word 30 within edit region 16 of user interface 14 and above the character string “dead” to illustrate one way which computing device 10 may output candidate word 30 in response to determining the spelling probability of the character string “dead” satisfies a threshold.
In this way, computing device 10 may not output unlikely corrections to the presence-sensitive screen of UID 12 and therefore not unnecessarily distract a user. Computing device 10 may output a unique user interface 14 to the screen that highlights and presents alternative suggestions for each detected error. Without providing additional input, a user can quickly scan text within user interface 14 presented on the presence-sensitive screen of UID 12 to view any potential errors. A user may type faster on graphical keyboard 18, relying on the computing device to detect and highlight any typing errors that can easily be corrected later.
The techniques of the disclosure may enable a computing device to detect, highlight, and/or correct auto-correct errors and other types of typing errors. The techniques of the disclosure may be distinct from and/or complement a spell check feature of a computing device to correct errors that are commonly missed by a spell check feature.
Techniques of the disclosure are applicable to conventional keyboards and graphical keyboards that receive tap and/or gesture inputs where spell-check may not be generally helpful and/or where recognizing the correct key selection is inherently ambiguous. The techniques of the disclosure may therefore improve text input efficiency and confidence on computing devices (e.g., mobile computing devices).
The techniques of the disclosure may enable a computing device to present a user interface with highlights and alternative suggestions for words where an error is detected. One advantage of the user interface is that a user may more quickly scan the text presented in the user interface and view any potential errors. In some examples, the user may view the presented text and potential errors without having to perform any additional clicks or provide additional input to the computing device. In some examples, a user may type faster than before on a computing device such as this, knowing that any typing errors will be highlighted and easily corrected later.
While the techniques of the disclosure discuss the use of a presence-sensitive screen and a graphical keyboard, the techniques are also applicable to physical keyboards with physical keys (e.g., wired, wireless, etc.). The techniques of the disclosure may apply to any variety of tap, gesture, physical, and graphical keyboards. The techniques of the disclosure may be useful for gesture keyboards because gesture recognitions may be based on dictionary words (and thus pass the spell-check). Consequently, techniques of the disclosure may assist a user by reducing ambiguity and error rates when using gesture keyboards.
The techniques of the disclosure may be advantageous to a computing device that can receive phrase level input of text on a keyboard, where a user can type entire phrases and sentences without hitting the space bar. The computing device may present suggested corrections and a user may quickly type a large amount of text in one gesture, deferring error correction (e.g., selection of the corrections) until the end of a sentence.
The techniques of the disclosure may be advantageous for a computing device executing a standard spell check as well (e.g., by selectively displaying corrections on top of the underlined word, using spatial model information (touch and gesture) to inform corrections, and using past and future language context to inform corrections).
FIG. 2 is a block diagram illustrating an example computing device, in accordance with one or more aspects of the present disclosure. Computing device 10 of FIG. 2 is described below within the context of FIG. 1. FIG. 2 illustrates only one particular example of computing device 10, and many other examples of computing device 10 may be used in other instances and may include a subset of the components included in example computing device 10 or may include additional components not shown in FIG. 2.
As shown in the example of FIG. 2, computing device 10 includes user interface device 12 (“UID 12”), one or more processors 40, one or more input devices 42, one or more communication units 44, one or more output devices 46, and one or more storage devices 48. Storage devices 48 of computing device 10 also include UI module 20, keyboard module 22, gesture module 24, and lexicon data stores 60. Keyboard module 22 includes spatial model module 26 (“SM module 26”), language model module 28 (“LM module 28”). Communication channels 50 may interconnect each of the components 12, 13, 20, 22, 24, 26, 28, 40, 42, 44, 46, and 60 for inter-component communications (physically, communicatively, and/or operatively). In some examples, communication channels 50 may include a system bus, a network connection, an inter-process communication data structure, or any other method for communicating data.
One or more input devices 42 of computing device 10 may receive input. Examples of input are tactile, audio, and video input. Input devices 42 of computing device 10, in one example, includes a presence-sensitive screen, touch-sensitive screen, mouse, keyboard, voice responsive system, video camera, microphone or any other type of device for detecting input from a human or machine.
One or more output devices 46 of computing device 10 may generate output. Examples of output are tactile, audio, and video output. Output devices 46 of computing device 10, in one example, includes a presence-sensitive screen, sound card, video graphics adapter card, speaker, cathode ray tube (CRT) monitor, liquid crystal display (LCD), or any other type of device for generating output to a human or machine.
One or more communication units 44 of computing device 10 may communicate with external devices via one or more networks by transmitting and/or receiving network signals on the one or more networks. For example, computing device 10 may use communication unit 44 to transmit and/or receive radio signals on a radio network such as a cellular radio network. Likewise, communication units 44 may transmit and/or receive satellite signals on a satellite network such as a GPS network. Examples of communication unit 44 include a network interface card (e.g. such as an Ethernet card), an optical transceiver, a radio frequency transceiver, a GPS receiver, or any other type of device that can send and/or receive information. Other examples of communication units 44 may include Bluetooth®, GPS, 3G, 4G, and Wi-Fi® radios found in mobile devices as well as Universal Serial Bus (USB) controllers.
In some examples, UID 12 of computing device 10 may include functionality of input devices 42 and/or output devices 46. In the example of FIG. 2, UID 12 may be or may include a presence-sensitive screen. In some examples, a presence sensitive screen may detect an object at and/or near the presence-sensitive screen. As one example range, a presence-sensitive screen may detect an object, such as a finger or stylus that is within 2 inches or less of the presence-sensitive screen. The presence-sensitive screen may determine a location (e.g., an (x,y) coordinate) of the presence-sensitive screen at which the object was detected. In another example range, a presence-sensitive screen may detect an object 6 inches or less from the presence-sensitive screen and other exemplary ranges are also possible. The presence-sensitive screen may determine the location of the screen selected by a user's finger using capacitive, inductive, and/or optical recognition techniques. In some examples, presence sensitive screen provides output to a user using tactile, audio, or video stimuli as described with respect to output device 46. In the example of FIG. 2, UID 12 presents a user interface (such as user interface 14 of FIG. 1), and other various functions and applications executing on computing device 10 at the presence-sensitive screen of UID 12.
While illustrated as an internal component of computing device 10, UID 12 also represents and external component that shares a data path with computing device 10 for transmitting and/or receiving input and output. For instance, in one example, UID 12 represents a built-in component of computing device 10 located within and physically connected to the external packaging of computing device 10 (e.g., a screen on a mobile phone). In another example, UID 12 represents an external component of computing device 10 located outside and physically separated from the packaging of computing device 10 (e.g., a monitor, a projector, etc. that shares a wired and/or wireless data path with a tablet computer).
One or more storage devices 48 within computing device 10 may store information for processing during operation of computing device 10 (e.g., lexicon data stores 60 of computing device 10 may store data related to one or more written languages, such as words and common pairings of words, accessed by LM module 28 during execution on computing device 10). In some examples, storage device 48 is a temporary memory, meaning that a primary purpose of storage device 48 is not long-term storage. Storage devices 48 on computing device 10 may configured for short-term storage of information as volatile memory and therefore not retain stored contents if powered off. Examples of volatile memories include random access memories (RAM), dynamic random access memories (DRAM), static random access memories (SRAM), and other forms of volatile memories known in the art.
Storage devices 48, in some examples, also include one or more computer-readable storage media. Storage devices 48 may be configured to store larger amounts of information than volatile memory. Storage devices 48 may further be configured for long-term storage of information as non-volatile memory space and retain information after power on/off cycles. Examples of non-volatile memories include magnetic hard discs, optical discs, floppy discs, flash memories, or forms of electrically programmable memories (EPROM) or electrically erasable and programmable (EEPROM) memories. Storage devices 48 may store program instructions and/or data associated with UI module 20, keyboard module 22, gesture module 24, SM module 26, LM module 28, and lexicon data stores 60.
One or more processors 40 may implement functionality and/or execute instructions within computing device 10. For example, processors 40 on computing device 10 may receive and execute instructions stored by storage devices 48 that execute the functionality of UI module 20, keyboard module 22, gesture module 24, SM module 26, and LM module 28. These instructions executed by processors 40 may cause computing device 10 to store information, within storage devices 48 during program execution. Processors 40 may execute instructions of modules 20-28 to cause UID 12 to display user interface 14 with edit region 16 and graphical keyboard 18 at the presence-sensitive screen of UID 12. That is, modules 20-28 may be operable by processors 40 to perform various actions, including receiving user input detected at locations of the presence-sensitive screen of UID 12 and causing UID 12 to present user interface 14 at the presence-sensitive screen of UID 12.
In accordance with aspects of this disclosure computing device 10 of FIG. 2 may output for display at the presence-sensitive screen of UID 12, a graphical keyboard including a plurality of keys. For example during operation use of computing device 10, UI module 20 of computing device 10 may query keyboard module 22 for a keyboard layout (e.g., an English language QWERT keyboard, etc.). UI module 20 may transmit a request for a keyboard layout over communication channels 50 to keyboard module 22. Keyboard module 22 may receive the request and reply to UI module 20 with data associated with the keyboard layout. UI module 20 may receive the keyboard layout data over communication channels 50 and use the data to generate user interface 14. UI module 20 may generate user interface 14 including edit region 16 and the plurality of keys of the keyboard layout from keyboard module 22 as graphical keyboard 18. UI module 20 may transmit a display command and data over communication channels 50 to cause UID 12 to present user interface 14 at the presence-sensitive screen of UID 12. UI module 20 may send information to UID 12 that includes instructions for displaying user interface 14 at the presence-sensitive screen of UID 12. UID 12 may receive the display command and data from UI module 20 and cause the presence-sensitive screen of UID 12 to present user interface 14.
Computing device 10 may receive an indication of a selection of one or more of the plurality of keys. For example, a user of computing device 10 may provide input at UID 12 by tapping and/or swiping at locations of the presence-sensitive screen of UID 12 that present the keys of graphical keyboard 18. UID 12 may receive the user input detected at the presence-sensitive screen of UID 12 and send information about the user input over communication channels 50 to gesture module 24. UID 12 may virtually overlay a grid of coordinates onto the presence-sensitive screen of UID 12. The grid may not be visibly displayed by UID 12. The grid may assign a coordinate that includes a horizontal component (X) and a vertical component (Y) to each location. Each time UID 12 detects user input at the presence-sensitive screen of UID 12, gesture module 24 may receive information from UID 12. The information may include one or more coordinate locations and associated times indicating to gesture module 24 both, where UID 12 detects user input at the presence-sensitive screen of UID 12, and when UID 12 detects user input.
Gesture module 24 may order the information received from UID 12 into a time-ordered sequence of motion events. The sequence of motion events may represent a sequence of one or more taps and/or gestures (the sequence referred to simply as “a gesture”) performed by a user at the presence-sensitive screen of UID 12. Each motion event in the sequence may include a location component as the coordinate location of the user input, a time component as the time associated with the user input, and an action component. The action component may indicate whether the motion event corresponds to a push down at the presence-sensitive screen of UID 12 or a lift up at the presence-sensitive screen of UID 12.
Gesture module 24 may determine the action component of the first motion event in the sequence corresponds to a push down event. Gesture module 24 may determine the action component of a current motion event in the sequence (different from and subsequent to the first motion event) based on a previous motion event in the sequence. Gesture module 24 may compare the time and location components of the current motion event with the time and location components of a previous motion event. Gesture module 24 may determine that a large difference in time and/or distance (e.g., ten milliseconds and/or ten pixels) between two motion events indicates a lift up event, followed by a push down event. Gesture module 24 may determine a start location of a gesture as the location component of a first motion event in the sequence with a push down action component. Gesture module 24 may determine an end location of a gesture as the location component of a first motion event in the sequence with a lift up action component. Gesture module 24 may determine a start location of a second subsequent gesture as the location component of a first motion event in the sequence with a push down action component that follows a motion event in the sequence with a lift up action component.
Based on the sequence of motion events, gesture module 24 may determine the user input corresponds to one or more gestures and may determine one or more characteristics of each gesture including a length, a shape, a velocity, etc. Gesture module 24 may determine a length of a gesture as a physical distance at the presence-sensitive screen of UID 12 between the start location of the gesture and the location component of the last motion event in the sequence that occurs prior to the motion event in the sequence that includes the end location of the gesture. Gesture module 24 may determine a length of a gesture before detecting an end of the gesture. For example, the length of a gesture may increase as the location components of motion events in the sequence move away from the start of the gesture. Prior to the end of the gesture, the length of the gesture may decrease as the location components of the motion events in the sequence move toward the start location of the gesture.
Gesture module 24 may determine a shape of a gesture as a linear shape, an arc shape, etc. Gesture module 24 may determine the shape of the gesture as a linear shape by determining a common linear plane at the presence-sensitive screen of UID 12 associated with each location of the motion events in the sequence. Gesture module 24 may determine a common linear plane between ninety percent of the locations of the motion events in the sequence and determine the locations sufficiently approximate a linear shape. Gesture module 24 may further differentiate between a horizontal linear shape and a vertical linear shape (e.g., by determining the common linear plane between the locations to correspond to horizontal or vertical locations at the presence-sensitive screen of UID 12).
Gesture module 24 may determine the shape of the gesture as an arc shape by determining a common centroid point at the presence-sensitive screen of UID 12 associated with each location of the motion events in the sequence and common distance (i.e., radius) from the centroid point to the locations of each motion event. Gesture module 24 may determine a common centroid and distance between ninety percent of the locations of the motion events in the sequence and determine the locations sufficiently approximate an arc shape.
Gesture module 24 may determine a velocity of the gesture corresponds to the length of the gesture divided by an elapsed time of the gesture. As discussed above, gesture module 24 may determine the length of the gesture, the start location of the gesture, and the end of the gesture. When gesture module 24 determines the start location of the gesture, gesture module 24 may also determine a start time of the gesture. Gesture module 24 may determine the start time of the gesture corresponds to the time component of the motion event in the sequence corresponding to the start location of the gesture.
When gesture module 24 determines the end location of the gesture, gesture module 24 may also determine an end time of the gesture. Gesture module 24 may determine the end time of the gesture corresponds to the time component of the motion event in the sequence corresponding to the end location of the gesture. Gesture module 24 may determine the elapsed time of the gesture as a difference between the start time and the end time of the gesture. Gesture module 24 may determine the velocity of the gesture as the length of the gesture divided by the elapsed time of the gesture.
After determining such features corresponding to the user input (e.g., velocity, distance, etc.), gesture module 24 may transmit a sequence of one or more gestures over communication channels 50 to UI module 20. For each gesture in the sequence, gesture module 24 may include the characteristics of each gesture and the corresponding motion events. For example, each gesture in the sequence, regardless of whether the gesture represents a tap or a continuous swipe gesture, may include a start location, an end location, a length, a velocity, a shape, two or more action components, two or more time components, and two or more location components.
UI module 20 may receive the sequence of gestures from gesture module 24 and determine UID 12 received an indication of a selection of one or more of the plurality of keys. In other words, UI module 20 may compare the location components of each gesture in the sequence to an area of the presence-sensitive screen of UID 12 that presents graphical keyboard 18. Based on the comparison, UI module 20 may determine the location components of each gesture correspond to a location within graphical keyboard 18 and may determine each of the gestures approximates a selection of one or more keys of graphical keyboard 18. To decipher the selection of one or more keys, UI module 20 may transmit the sequence of gestures, along with locations where the presence-sensitive screen of UID 12 presents each of the keys, over communication channels 50 to keyboard module 22.
Computing device 10 may determine, based at least in part on the indication of the selection of keys, a character string. For example, keyboard module 22 may receive the sequence of gestures and key locations from UI module 20. Keyboard module 22 may generate a sequence of key selections based on the sequence of gestures. Based at least in part on the key sequence, keyboard module 22 may generate a character string that represents the selection of keys. Keyboard module 22 may transmit data about the character string to UI module 20 over communication channels 50. UI module 20 may include the character string within edit region 16 of user interface 14 and may cause UID 12 to update user interface 14 as displayed at the presence-sensitive screen of UID 12 to include the character string.
Keyboard module 22 may utilize SM module 26 to generate the key sequence from the gesture sequence and to generate the character string that represents the selection of keys. For example, keyboard module 22 may share the sequence of gestures and each key location with SM module 26. SM module 26 may determine, based on the location and time components of each of the gestures, whether the gesture represents one or more key selections. For instance, SM module 26 may compare the location components of each gesture in the sequence of gestures to each key location, and for each key, generate a SMP that a selection of the key occurred. The location components of each gesture in the sequence may include one or more locations of UID 12. A key location (e.g., a centroid of a key) may include a different location of UID 12.
SM module 26 may determine a probability that the gesture corresponds to a selection of a key based on a Euclidian distance between the key location and one or more of the gesture locations. SM module 26 may correlate a higher probability to a key that shares a smaller Euclidian distance with a location component of a gesture than a key that shares a greater Euclidian distance with a location component of a gesture (e.g., the probability of a key selection may exceed ninety nine percent when a key shares a near zero Euclidian distance to a location component of a gesture and the probability of the key selection may decrease proportionately with an increase in the Euclidian distance). Based on the SMP associated with each key, keyboard module 22 may assemble the individual key selections with the highest spatial model probabilities into a time-ordered sequence of keys for each gesture. Keyboard module 22 may concatenate the key sequences of the one or more gestures in the sequence of gestures into a single key sequence (e.g., the sequence of gestures may include multiple tap and/or swipe gestures and keyboard module 22 may determine a single key sequence to represent all of the gestures in the sequence). Per the example illustrated in FIG. 1, the key sequence may include the <D-key>, <E-key>, <A-key>, and <D-key>.
Keyboard module 22 may determine a sequence of characters and keyboard operations from the sequence of keys to determine a character string represented by the sequence of gestures. For example, each key of graphical keyboard 18 may represent a character or a keyboard operation. Keyboard module 22 may determine, based on the sequence of keys, particular characters represented by one or more key selections by combining individual character key selections with keyboard operation key selections. A character such as a number or a lowercase letter may require a single character key selection (e.g., <letter-key>, <number-key>, etc.). A character such as a capitalized letter may require two key selections (e.g., <shift-key>+<letter-key>, etc.). Keyboard module 22 may determine a correction in the key sequence based on one or more character key selections followed by a keyboard operation key selection (e.g., <letter-key>+<backspace-key>, etc.). Keyboard module 22 may determine a character string from the sequence of keys by combining individual key presses into a sequence of characters that accounts for corrections (e.g., <D-key>+<E-key>+<A-key>+<D-key> may correspond to the character string “dead”).
Computing device 10 may determine, based at least in part on the character string, a plurality of candidate words. For example, keyboard module 22 may autocorrect (e.g., spellcheck and/or grammar check) the character string generated from the sequence of keys based on data within lexicon data stores 60. Based on the autocorrection, keyboard module 22 may generate one or more candidate words that share a similar sequence of characters (e.g., a similar spelling) as the character string.
Lexicon data stores 60 may include one or more sorted databases (e.g., hash tables, linked lists, sorted arrays, graphs, etc.) that represent dictionaries for one or more written languages. Each dictionary may include a list of words and word combinations within a written language vocabulary. Keyboard module 22 may perform a lookup in lexicon data stores 60 for the character string by comparing the character string to each of the words in lexicon data stores 60. Keyboard module 22 may assign a Jaccard similarity coefficient to each word in the lexicon based on the comparison and determine one or more candidate words with a greatest Jaccard similarity coefficient. In other words, the one or more candidate words with the greatest Jaccard similarity coefficient may represent the words in lexicon data stores 60 with spellings that most closely correlate to the spelling of the character string. Keyboard module 22 may determine one or more candidate words that include parts or all of the characters of the character string and determine the candidate word with the highest Jaccard similarity coefficient represents the autocorrected character string. In some examples, the candidate word with the highest Jaccard similarity coefficient matches the character string generated from the key sequence. For example, the candidate words for the character string “dead” may include “dead”, “deaf”, “deal”, “dean”, “dear”, and “deadly”.
In addition to determining one or more candidate words using lexicon data stores 60, keyboard module 22 offload processing to an external computing source, such as a server or other remote computing device operatively coupled to computing device 10. In this way, computing device 10 may save computing resources, storage and/or memory space by not executing instructions to search for candidate words within lexicon data stores 60. For instance, computing device 10 may communicate with a server device or on the Internet using communication units 44. Computing device 10 may transmit and receive data via a local network or the Internet to one or more external computing devices, such as a server. Keyboard module 22 may send the character string to a server that processes the character string to remotely determine a list of one or more candidate words based on the character string. In response, keyboard module 22 may receive a plurality of candidate words (e.g., possible autocorrections) based on the character string.
Rather than relying only on a dictionary to determine if the character string generated from the sequence includes an error, keyboard module 22 of computing device 10 may use a plurality of features to determine a spelling probability that the character string input was erroneous. If the spelling probability satisfies a threshold, keyboard module 22 may cause UI module 20 to include, not only the autocorrected character string within edit region 16 of user interface 14, but also a suggested correction identified based on the plurality of features.
Computing device 10 may determine, based at least in part on the plurality of candidate words and a plurality of features, a spelling probability that the character string comprises an incorrect spelling of at least one of the plurality of candidate words. The plurality of features comprising at least a spatial model probability associated with each of the one or more candidate words. For example, keyboard module 22 may determine a spelling probability that the character string represents an incorrect spelling of at least one of the candidate words identified during the autocorrection. Keyboard module 22 may utilize a plurality of features (e.g., various types of data about the user input and candidate words) to determine the spelling probability associated with each candidate word. For example, for each candidate word, keyboard module 22 may determine a feature probability based on each of the plurality of features and, using a weighted average of all the feature probabilities, determine the spelling probability associated with the candidate word. If the spelling probability associated with a given candidate word satisfies a threshold, the character string may represent an incorrect spelling of the given candidate word.
The plurality of features may include a SMP for each candidate word, a language model probability (“LMP”) associated with each candidate word, a typing speed of the selection of one or more of the plurality of keys, a backspace usage backspace usage percentage associated with the selection of one or more of the plurality of keys, and a suggestion bar usage percentage. Each of the plurality of features is described in detail below.
In response to determining that the spelling probability associated with at least one of the plurality of candidate words satisfies a threshold, computing device 10 may cause the presence-sensitive screen of UID 12 to output for display the at least one of the plurality of candidate words. For example, based on the plurality of features and for each of the candidate words “dear”, “dead”, “dean”, etc., keyboard module 22 may determine a spelling probability that the character string (e.g., “dead”) represents an incorrect spelling of the candidate word. Keyboard module 22 may compare the spelling probability of the character string associated with each of the candidate words to a threshold (e.g., ninety percent). Keyboard module 22 may determine the spelling probability satisfies the threshold if a spelling probability of a candidate word exceeds the threshold.
In response to determining that the spelling probability associated with at least one candidate word exceeds the threshold, keyboard module 22 may cause computing device 10 to output the at least one candidate word at a location of the presence-sensitive screen of UID 12. For example, keyboard module 22 may determine the spelling probability associated with the character string “dead” exceeds ninety percent for candidate word 30 (e.g., “dear”). Keyboard module 22 may transmit data to UI module 20 over communication channels 50 that causes UI module 20 to update user interface 14. UI module 20 may command UID 12 to cause the presence-sensitive screen of UID 12 to present updated user interface 14 including candidate word 30 (e.g., “dear”) that represents a suggested correction to the character string “dead”.
One feature used by keyboard module 22 for determining the spelling probability of the character string, may include a SMP for each candidate word. Keyboard module 22 may determine a SMP for each candidate word using SM module 26. For example (as described above to determine the key sequence used to generate the character string) keyboard module 22 may cause SM module 26 to compare the location components of each gesture in the sequence of gestures to each key location, and for each key, generate a SMP that a selection of the key occurred. In other words, in generating the character string originally, keyboard module 22 may have generated a sequence of keys corresponding to the sequence of gestures that includes the keys with the highest SMP, as determined by SM module 26. Keyboard module 22 also determined the character string SMP of the character string (e.g., the product of the SMP for each key included in the original sequence of keys).
Keyboard module 22 can similarly determine a SMP associated with each of the candidate words generated based on the autocorrection of the character string. For example, keyboard module 22 may determine a spatial-test sequence of keys for each candidate word. The spatial-test sequence of keys may represent the key selections that, if typed on graphical keyboard 18 by a user, would cause keyboard module 22 to generate the candidate word as the character string. The product of the SMP for each key in the spatial-test sequence of keys represents the SMP associated with that candidate word. A high value SMP associated with a candidate word may indicate that the location components within the sequence of gestures share a close Euclidian distance to key locations of the keys in the respective spatial-test sequence of keys. Keyboard module 22 may repeat these steps to determine the SMP associated with each candidate word.
Another feature used by keyboard module 22 for determining the spelling probability of the character string, may include a LMP associated with each candidate word. Keyboard module 22 may determine whether the character string represents an unlikely word based on past context, and/or an unlikely words based on future context. If the corrected or typed word has a low probability given the prior words in a language model context (e.g., n-gram) then there is more uncertainty about this correction (e.g., the character string).
In other words, LM module 28 of keyboard module 22 may assign a probability (e.g., a LMP) that each candidate word is grammatically positioned subsequent to, prior to, and/or within, a sequence of words (e.g., a sentence) generated from user input received prior to and/or subsequent to receiving the indication of the selection corresponding to the character string. In some examples, LM module 28 may determine a probability that a candidate word is grammatically positioned, in a sentence, subsequent to one or more words received prior to the character string. LM module 28 may determine a probability that a candidate word is grammatically positioned, in a sentence, prior to one or more words received subsequent to the character string. LM module 28 may determine a probability that a candidate word is grammatically positioned subsequent to one or more previous words in a sentence and prior to one or more subsequent words in a sentence.
In some examples, LM 28 may use rules not based on grammar (e.g., patterns of slang or colloquial word use) to determine a probability that a candidate word is positioned either prior to, subsequent to, or within a sequence of words received prior to or subsequent to the character string. LM module 28 may determine a probability that a candidate word is positioned subsequent to one or more words received prior to the character string in a sequence of words comprising the one or more words received prior to the character string and the candidate word. LM module 28 may determine a probability that a candidate word is positioned prior to one or more words received subsequent to the character string in a sequence of words comprising the one or more words received subsequent to the character string and the candidate word. LM module 28 may determine a probability that a candidate word is positioned subsequent to one or more previous words and prior to one or more subsequent words in a sequence of words comprising the one or more words received prior to the character string, the one or more words received subsequent to the character string, and the candidate word.
To determine a LMP associated with each candidate word, LM module 28 may use one or more n-gram language models. An n-gram language model may provide a probability distribution for an item xi (letter or word) in a contiguous sequence of items based on the previous items in the sequence (i.e., P(xi|xi−(n-1), . . . , xi−1)) or a probability distribution for the item xi in a contiguous sequence of items based on the subsequent items in the sequence (i.e., P(xi|xi+1, . . . , xi+(n-1))). Similarly, an n-gram language model may provide a probability distribution for an item xi in a contiguous sequence of items based on the previous items in the sequence and the subsequent items in the sequence (i.e., P(xi|xi−(n-1), . . . xi+(n-1))). For instance, a bigram language model (an n-gram model where n=2), may provide a probability that the word “dead” follows the word “My” in a sequence (i.e., a sentence). A trigram language model (an n-gram model where n=3) may provide a probability that the word “dead” precedes the two words “friend is” in a sequence.
LM module 28 may use n-gram language models in combination with the data within lexicon data stores 60 to determine a LMP associated with the character string and each of the candidate words. Keyboard module 22 may use the LMP associated with the character string and each of the candidate words as one of the plurality of features to generate the spelling probability associated with each candidate word.
For example, computing device 10 may determine a plurality of words received at a time prior to receiving the indication of the selection (e.g., a user may provide user input at graphical keyboard 18 presented at the presence-sensitive screen of UID 12 and computing device 10 may determine the user input corresponds to the word “My”). Keyboard module 22 may determine, based on the plurality of words, the LMP of each of the one or more candidate words that each of the one or more candidate words is positioned subsequent to the plurality of words in a sequence of words comprising the plurality of words and each of the one or more candidate words. In other words, keyboard module 22 may cause LM module 28 of to determine a LMP associated with each of the candidate words, “dead”, “deaf”, “deal”, “dean”, “dear”, and “deadly”, appearing subsequent to the word “My” in a sequence (e.g., sentence) that includes the word “My” and the respective candidate word.
Computing device 10 may determine a plurality of words received at a time subsequent to receiving the indication of the selection (e.g., a user may provide additional user input at graphical keyboard 18 presented at the presence-sensitive screen of UID 12, and computing device 10 may determine the additional user input corresponds to the word “friend is visiting tomorrow”). Keyboard module 22 may determine, based on the plurality of words, the LMP of each of the one or more candidate words that each of the one or more candidate words is positioned prior to the plurality of second words in a sequence of words comprising the plurality of words and each of the one or more candidate words. In other words, keyboard module 22 may cause LM module 28 of to determine a LMP associated with each of the candidate words, “dead”, “deaf”, “deal”, “dean”, “dear”, and “deadly”, appearing prior to the words “friend is” in a sequence (e.g., sentence) that includes the words “friend is” and the respective candidate words.
Computing device 10 may determine a plurality of first words received at a time prior to receiving the indication of the selection and a plurality of second words received at a time subsequent to receiving the indication of the selection (e.g., keyboard module 22 may query LM module 28 for the LMP of the candidate words associated with “dead” when computing device 10 receives a user input corresponding to “My dead friend is visiting tomorrow”). Keyboard module 22 may determine, based on the plurality of first words and the plurality of second words, the LMP of each of the one or more candidate words that each of the one or more candidate words is positioned subsequent to the plurality of first words and is positioned prior to the plurality of second words in a sequence of words comprising the plurality of first words, each of the one or more candidate words, and the plurality of second words. In other words, keyboard module 22 may cause LM module 28 of to determine a LMP associated with each of the candidate words, “dead”, “deaf”, “deal”, “dean”, “dear”, and “deadly”, appearing subsequent to the word “My” and prior to the words “friend is” in a sequence (e.g., sentence) that includes the word “My”, the respective candidate word, and the words “friend is”.
Since computing device 10 may detect potential errors in past words (e.g., words determined from user input received prior to the character string), techniques of the disclosure may provide an advantage of accounting for future words in a language model context. For example, if computing device 10 initially predicted that “Do” is more likely than “So” for the first word, computing device 10 can determine and highlight the potential error when the next word typed is “happy”. Unlike conventional autocorrect mechanisms, techniques of the disclosure can use context of past and future words.
Another feature used by keyboard module 22 for determining the spelling probability of the character string, may include a typing speed of the selection of one or more of the plurality of keys that causes keyboard module 22 to generate the character string. If the word (e.g., the character string) was typed very quickly then computing device 10 may determine the word is both more likely to contain errors and less likely to be manually verified by the user. In other words, computing device 10 may associate a high typing speed (e.g. when a user types fast) to a higher spelling probability and a low typing speed (e.g. when a user types slow) to a lower spelling probability.
Keyboard module 22 may determine the typing speed associated with the indication of the selection, as a number of characters typed during an amount of time. In other words, keyboard module 22 may calculate the typing speed as a quantity of characters in the character string divided by a duration of time for a user to type the character string. Keyboard module 22 may adjust the spelling probability of the character string by a factor (e.g., plus or minus ten percent) based on the typing speed.
For example, the indication of the selection may begin at a first point in time (e.g., when a user first begins typing “dead” at the presence-sensitive screen of UID 12) and may end at a second point in time (e.g., when a user stops typing “dead” at the presence-sensitive screen of UID 12). As described previously, gesture module 24 may determine a sequence of gestures that each include a location and a time component associated with when and where UID 12 detected each gesture at the presence-sensitive screen of UID 12. The earliest time component in sequence may correspond to the beginning of the indication of the selection. The latest time component in the sequence may correspond to the ending of the indication of the selection.
Keyboard module 22 may determine a quantity of characters included in the character string (e.g., “dead” includes four characters). Keyboard module 22 may determine a duration of time from the first point in time to the second point in time. In other words, keyboard module 22 may determine the elapsed time between the beginning and ending of the indication of the selection. Keyboard module 22 may determine the typing speed of the selection based on the duration of time and the quantity of characters (e.g., if the duration of time to receive the selection corresponding to “d-e-a-d” is two seconds, keyboard module 22 may represent the typing speed of the character string “dead” as two characters per second).
Yet another feature used by keyboard module 22 for determining the spelling probability of the character string, may include backspace usage percentage associated with the selection of one or more of the plurality of keys that causes keyboard module 22 to generate the character string. If the user deleted and the retyped letters in the current word (e.g., the character string) then computing device 10 may determine the user is likely paying attention to the current word and manually verifying it. In other words, computing device 10 may associate a high backspace usage percentage (e.g. when a user frequently uses a delete key or a backspace key to manually edit a particular character string as the user types) to a lower spelling probability and a low backspace usage percentage to a lower spelling probability.
To determine the backspace usage percentage, keyboard module 22 may determine a total quantity of key selections included in the selection of one or more of the plurality of keys. For example, keyboard module 22 may determine the total quantity of key selections as being the total quantity of keys in the key sequence generated from the gesture sequence. Keyboard module 22 may determine a quantity of backspace key selections included in the selection of one or more of the plurality of keys and a quantity of delete key selections included in the selection of one or more of the plurality of keys. For example, keyboard module 22 may traverse the key sequence and for each selection of the delete key and selection of backspace key, increment value of a counter. Keyboard module 22 may determine, based on the quantity of backspace key selections, the quantity of delete key selections, and the total quantity of key selections the backspace usage percentage. For example, keyboard module 22 may determine the backspace usage percentage as being the counter value divided by the total quantity of keys.
Keyboard module 22 may determine one or more candidate words to output in place of the character string even if the character string corresponds to a valid dictionary word (e.g. a word in a lexicon). The character string may correspond to a first word in a lexicon, and in response to determining a context associated with the character string, keyboard module 22 may identify a second word in the lexicon as one candidate word of the plurality of candidate words, based at least in part on the context.
In other words, even though the character string may correspond to a valid dictionary word found in lexicon data stores 60, the words positioned before and/or after the character string (e.g., context) may indicate that the character string represents an incorrect spelling of a different valid dictionary word. Similarly, the locations associated with sequence of motion events based on the gesture input (e.g., context) may indicate an ambiguity in the selection of one of the keys of graphical keyboard 18 that the character string is based on.
Keyboard module 22 may utilize one or more of the techniques described above to determine a second word in the lexicon having a higher likelihood of representing the correct spelling of the character string. For instance, using an n-gram language model of LM module 28 described above, keyboard module 22 may determine a LM probability associated with the word “dead” positioned in a sequence of words after the words “My” and before the words “friend is”. Keyboard module 22 may determine a second word in lexicon data stores 60 “dear” and determine a LM probability associated with the word “dear” positioned in a sequence of words after the words “My” and before the words “friend is”. In response to determining the LM probability associated with the second word “dear” exceeding the first word “dead”, keyboard module 22 may include the second word “dear” within the plurality of candidate words.
In other instances, using SM module 26, keyboard module 22 may determine an ambiguity in the selection of one or more keys used to generate the character string “dead”. For instance, the sequence of motion events based on the gesture input may include locations associated with the “D” key, “E” key, “A” key, and locations in between the keys “D” and “R”. Even though keyboard module 22 may first identify the word “dead” as an accurate representation of the character string, using SM module 26, keyboard module 22 may identify the word “dear” in lexicon data stores 60 as an equally accurate representation of the character string and include the word “dear” as one of the candidate words in the plurality of candidate words.
FIGS. 3A-3B are conceptual diagrams illustrating example graphical user interfaces for presenting suggested corrections to text, in accordance with one or more aspects of the present disclosure. FIGS. 3A-3B are described below in the context of computing device 10 (described above) from FIG. 1 and FIG. 2.
Computing device 10 may output for display graphical user interface 80A including edit region 82A and graphical keyboard 84A. Graphical keyboard 84A may include suggestion bar 86 including suggested words 92A-92N (collectively referred to as “suggested words 92”) that can be included in edit region 82A. The plurality of features used by computing device 10 for determining the spelling probability of a character string may include a suggestion bar usage percentage. If the user employs the suggestion bar for this word (e.g., the character string) or neighboring words, computing device 10 may determine the user is more likely paying attention to the autocorrection suggestions and manually verifying them (e.g., manually verifying the character string and therefore a high suggestion bar usage lowers the spelling probability of the character string). Computing device 10 may determine the suggestion bar usage percentage as a quantity of selections suggested words 92 detected at the presence-sensitive screen within a duration of time as compared to a total quantity words generated by computing device 10 from user input received by computing device 10 within the duration of time.
One of the plurality of features computing device 10 may use to determine the spelling probability of a character string is a suggestion bar usage percentage. UI module 20 of computing device 10 may cause UID 12 to present user interface 80A at the presence-sensitive screen of UID 12 including edit region 82A and graphical keyboard 84A. UI module 20 may include suggestion bar 86 as part of graphical keyboard 84A. Suggestion bar 86 may include graphical elements that represent suggested words 92 that a user may select and cause computing device 10 to include as text within edit region 82A. For example, FIG. 3A illustrates a text string interpreted from user input as “give me fi”. As computing device 10 detects the user input, keyboard module 22 and UI module 20 may cause suggested word 92A, suggested word 92B, and suggested word 92N (e.g., “five”, “fib”, and “fig”) to appear at suggestion bar 86 as suggested words 92 to complete the partial word “fi”. A user may elect to continue to provide inputs at keys of graphical keyboard 84A to finish the word “fi” or the user may select one of suggested words 92 within suggestion bar 86.
Computing device 10 may determine that the spelling probability of a character string decreases for a high suggestion bar usage percentage. For example, if the user selects a suggested word from suggestion bar 86 during the input associated with the character string or a neighboring word (e.g., a previous word or subsequent word). In other words, computing device 10 may associate frequent usage of suggestion bar 86 with user input from a user that does not require assistance in verifying the spelling of the character string. A user that frequently selects suggested words 92 from suggestion bar 86 may focus more attention to the text presented in the edit region.
Computing device 10 may determine the suggestion bar usage percentage as a quantity of selections of the one or more suggested words 92 detected at the presence-sensitive screen within a duration of time as compared to a total quantity words generated by the computing device from user input received by computing device 10 within the duration of time. In other words, at some periodic rate (e.g., every 1-59 seconds, etc.) keyboard module 22 of computing device 10 may count the words generated from user input that appear within edit region 82A of user interface 80A. At the same periodic rate, keyboard module 22 may likewise count the subset of these words associated with user input detected at suggestion bar 86 (e.g. keyboard module 22 may count the number of words within edit region 82A corresponding to selections of suggested words 92 within suggestion bar 86). The suggestion bar usage percentage may correspond to the count of the subset of words as compared to the total words within edit region 82A. If the suggestion bar usage percentage exceeds a threshold (e.g., fifty percent) keyboard module 22 may decrease the spelling probability of a character string.
The techniques of the disclosure enable to the computing device to detect potential typing errors made by a user and/or autocorrect errors that are missed by a spell-check (e.g., when a word appears in a lexicon such as lexicon data stores 60 and yet also represents an error). Potential error detections are underlined. For recent detections, alternative suggestions are selectively shown in a box above the word.
In other words, computing device 10 may position a candidate word and format a character string associated with the candidate word, when outputting the candidate word for display at the presence-sensitive screen of UID 12. Computing device 10 may output the character string for display (e.g., at the presence-sensitive screen of UID 12) and output at least one candidate words above the character string.
Computing device 10 may output the character string with a format that includes at least one of an underline, a highlight, a font size, and a font color. For example, FIG. 3A illustrates candidate word 88A (“good”) appearing above the character string “food”. The character string food includes an underline format and the candidate word good appears in a word bubble, box, etc.
Tapping on a box will replace the underlined word with the suggestion. In other words, after computing device 10 presents a candidate word at the presence-sensitive screen of UID 12, a user may select the candidate word to replace the character string initially entered by the user. For example, computing device 10 may receive an indication of a user input detected at a location of the presence-sensitive screen of UID 12. Computing device 10 may determine, based at least in part on the indication of the user input, a selected candidate word. The selected candidate word is one of the plurality of candidate words that is outputted above the character string. Computing device 10 may output the selected candidate word in place of the character string in edit region 82A. For example, a user may provide a user input at a location of the presence-sensitive screen of UID 12 where the presence-sensitive screen of UID 12 presents candidate word 88A. Computing device 10 may determine the input is a selection of candidate word 88A. In response, computing device 10 may cause the presence-sensitive screen of UID 12 to present candidate word 88A (“good”) in place of the character string “food”.
FIG. 3B illustrates user interface 80B as an example of user interface 80A of FIG. 3A after a period of time. For purposes of illustration, it will be understood that computing device 10 may output user interface 80A, including candidate word 88A at the presence-sensitive screen of UID 12 at a first point in time. Computing device 10 may determine an elapsed time between the first point in time and a second point in time. In response to determining that the elapsed time exceeds a time threshold (e.g., one minute), computing device 10 may refrain from outputting candidate word 80A.
Computing device 10 may present user interface 80B at the presence-sensitive screen of UID 12 one minute after presenting user interface 80A. In presenting user interface 80B, dotted circular region 88B illustrates that candidate word 88A and the associated word bubble, box, etc. no longer appears at the presence-sensitive screen of UID 12. In other words, one minute after presenting candidate word 88A, and not receiving a user input corresponding to a selection of candidate word 88A for replacement of the character string “food”, candidate word 88A disappears from the presence-sensitive screen of UID 12.
FIG. 3B illustrates an example user interface 80B for presenting multiple candidate words. A user of computing device 10 may expand any of the boxes using a swipe-up gesture to reveal additional suggestions (e.g., candidate words). In other words, computing device 10 may receive an indication of a user input detected at a location of the presence-sensitive screen of UID 12 where at least one of the plurality of candidate words is displayed within edit region 82B. Responsive to receiving the indication of the user input, computing device 10 may output for display at the presence-sensitive screen of UID 12, at least one additional candidate word of the plurality of candidate words. For example, computing device 10 may receive an indication of user input 94. Gesture module 24 may process the indication and determine user input 94 corresponds to a swipe gesture. From information received from gesture module 24, UI module 20 may determine the start location of the swipe gesture begins at a location on the presence-sensitive screen of UID 12 where the presence-sensitive screen of UID 12 presents candidate word 90A of user interface 80A. UI module 20 may determine the swipe gesture represents a command from the user to present additional candidate words (e.g., not just candidate word 90A) as suggested replacements for the character string “nun”.
UI module 20 may query keyboard module 22 for additional candidate words to present at the presence-sensitive screen of UID 12. In other words, keyboard module 22 may determine the spelling probability associated with multiple candidate words exceeds the a threshold and at first may cause UI module 20 to only include the candidate word with the highest spelling probability in user interface 80A. The query from UI module 20 may cause keyboard module 22 to transmit the other candidate words with lower spelling probabilities to UI module 20 for inclusion in user interface 80B. Word bubble 90B illustrates multiple candidate word suggestions for the character string “nun”.
FIG. 4 is a conceptual diagram illustrating an example graphical user interface for presenting suggested corrections to text, in accordance with one or more aspects of the present disclosure. FIG. 4 is described below in the context of computing device 10 as previously described above in FIG. 1 and FIG. 2.
Computing device 10 may output for display at the presence-sensitive screen of UID 12 user interface 96 including edit region 98 and graphical keyboard 100. As described above, computing device 10 may receive user input at graphical keyboard 100 and generate a character string based on the user input. Computing device 10 may autocorrect the character string based on data within a lexicon (e.g., lexicon data stores 60). Furthermore, computing device 10 may generate a one or more candidate words as suggested replacements for the character string. In some examples, computing device 10 may determine the spatial model probability associated with each of the one or more candidate words is a candidate word SMP associated with each of the one or more candidate words. Computing device 10 may determine a character string SMP associated with the character string that the character string comprises a correct spelling of the selection of the plurality of keys. Computing device 10 may determine the character string is not included in a lexicon. Responsive to determining the character string is not included in the lexicon, computing device 10 may determine that the character string SMP of the character string exceeds a character string threshold. If the character string SMP of the character string exceeds the character string threshold, computing device 10 may determine the plurality of candidate words comprises the character string.
In other words, techniques of the disclosure enable computing device to detect erroneous autocorrected out-of-vocabulary words. A user may intentionally provide user input at the keys of graphical keyboard 100 to cause computing device 10 to generate a character string within edit region 98 that is not included in any lexicon (e.g., a non-dictionary character string not found in lexicon data stores 60). That is, the character string may be a personal name, a term of slang, etc. As described above with respect to FIG. 2, using SM module 26, computing device 10 may determine a SMP of each key of graphical keyboard 100 and generate a sequence of keys, with each key having a highest SMP. From the key sequence, computing device 10 may generate a character string SMP and an associated character string. The product of the SMP for each key included in the sequence of keys being the character string spatial model probability.
As further described above, computing device 10 may autocorrect the character string to be a word with a highest Jaccard similarity coefficient found in lexicon data stores 60. In other words, if the computing device 10 determines the character string is not within lexicon data stores 60, computing device 10 may autocorrect the character string to be a dictionary word with the highest Jaccard similarity coefficient as compared to the non-dictionary character string and determine one or more candidate words (also found in lexicon data stores 60). In addition, based on a plurality of features, computing device 10 may determine a spelling probability that the character string represents an incorrect spelling of the one or more candidate words.
Computing device 10 may determine the character string SMP (of the character string generated before the auto correction) exceeds a character string threshold. In other words, computing device 10 may determine the character string SMP of the non-dictionary character string corresponds to a SMP generally associated with a character string generated from intentional and/or accurate user input. If computing device 10 determines that the character string SMP exceeds the character string threshold computing device 10 may include the non-dictionary character string (e.g., the character string generated before the auto correction) in the plurality of candidate words that computing device 10 may display within edit region 98.
For example, FIG. 4 illustrates a character string within edit region 98 that computing device 10 autocorrected from “muggle” to “muffin”. The SMP associated with the character string “muggle” may exceed a character string threshold (e.g., a threshold value of fifty to ninety-nine percent may represent a minimum spatial model probability of a word corresponding to accurate key selections). Computing device 10 may present the autocorrected character string “muffin” while also presenting the uncorrected character string “muggle” as candidate word 102.
Computing device 10 may detect potential correction errors made by autocorrect of the character string based on a number of factors (e.g., features). One such factor or feature is correction ambiguity, that is, if the second best correction (e.g., candidate word) for the word (e.g., the character string) has a spelling probability approximately equivalent to (i.e., near) the top correction then there may have been an ambiguity in the decision made by computing device 10 determining the spelling probability. Computing device 10 may indicate an ambiguity detected and potentially display the second choice as a potential alternative.
In other words, computing device 10 may determine multiple candidate words as suggested replacements for a character string and also determine a spelling probability associated with each of the candidate words. Computing device 10 may determine a degree of uncertainty (e.g., an ambiguity) between two or more candidate words based on closeness in value between each associated spelling probability. When computing device 10 determines a degree of uncertainty, computing device 10 may output each of the candidate words as suggestions rather than just one with a spelling probability that may be slightly higher in value.
For example, computing device 10 may determine a first spelling probability that the character string comprises an incorrect spelling of a first word of the plurality of candidate words. Computing device 10 may determine a second spelling probability that the character string comprises an incorrect spelling of a second word of the plurality of candidate words. Computing device 10 may determine a difference between the first spelling probability and the second spelling probability. In response to determining the difference does not exceed an ambiguity threshold (e.g., one to five percent), computing device 10 may output for display at the presence-sensitive screen of UID 12, the first word and the second word as two suggested replacements for a character string.
FIG. 5 is a flowchart illustrating example operations of the computing device, in accordance with one or more aspects of the present disclosure. The process of FIG. 5 may be performed by one or more processors of a computing device, such as computing device 10 illustrated in FIG. 1 and FIG. 2. For purposes of illustration, FIG. 5 is described below within the context of computing devices 10 of FIG. 1 and FIG. 2.
In the example of FIG. 5, computing device 10 may output graphical keyboard 18 comprising a plurality of keys (110). For example, UI module 20 may command UID 12 to present user interface 14 at the presence-sensitive screen of UID 12 including graphical keyboard 18 with a plurality of keys. Computing device 10 may receive an indication of a selection of one or more of the plurality of keys (120). For example, gesture module 24 may receive information from UID 12 and assemble the information into a sequence of motion events and/or a sequence of gestures. UI module 20 may determine location components of the sequence of gestures indicate a user provided input at locations of the presence-sensitive screen of UID 12 where the presence-sensitive screen of UID 12 presents the plurality of keys of graphical keyboard 18.
As shown in FIG. 5, computing device 10 may determine a character string (130). For example, keyboard module 22 may compare the location components of each gesture in the sequence of gestures to locations of the plurality of keys (e.g., using SM module 26). Keyboard module 22 may generate a key sequence and from the key sequence, generate a character string corresponding to the sequence of keys. Computing device 10 may determine a plurality of candidate words (140). For example, keyboard module 22 may compare the character string with and assign a Jaccard similarity coefficient to each word within lexicon data stores 60. Keyboard module 22 may determine a subset of the words within lexicon data stores 60 associated with a highest Jaccard similarity coefficient represent the plurality of candidate words.
Computing device 10 may determine a spelling probability that the character string comprises an incorrect spelling of at least one of the plurality of candidate words (150). For example, keyboard module 22 may determine a spatial model probability associated with each of the candidate words. Based on the spatial model probability and a plurality of features, keyboard module 22 may determine a spelling probability for each candidate word, that the character string represents an incorrect spelling of the candidate word.
In the example of FIG. 5, computing device 10 may determine whether the spelling probability satisfies a threshold (160). For example, keyboard module 22 may compare the spelling probability associated with each of the candidate words and the character string to determine whether the spelling probability associated with each of the candidate words exceeds a threshold value (e.g., fifty percent).
If the spelling probability does not satisfy the threshold, computing device 10 may refrain from outputting a candidate word. If the spelling probability does satisfy the threshold, computing device 10 may output the at least one of the plurality of candidate words (170). For example, keyboard module 22 may determine the spelling probability associated with candidate word 30 exceeds the threshold and the spelling probability associated with the other candidate words does not exceed the threshold. Keyboard module 22 may send data to UI module 20 that may cause UI module 20 to update user interface 14 to include candidate word 30 above text of the character string within edit region 16. UI module 20 may cause UID 12 to present updated user interface 14 at the presence-sensitive screen of UID 12.
In some examples, the operations may include determining, by computing device 10, a plurality of words that were received by computing device 10 prior to receiving the indication of the selection of one or more of the plurality of keys. The operations may also include determining, by computing device 10 and based on the plurality of words, at least one language model probability for at least one of the one or more candidate words. The at least one language model probability may indicate whether the at least one of the one or more candidate words is positioned subsequent to the plurality of words in a sequence of words comprising the plurality of words and the at least one of the one or more candidate words.
In some examples, the operations may include determining, by computing device 10, a plurality of words that are received by computing device 10 subsequent to receiving the indication of the selection of one or more of the plurality of keys. The operations may also include determining, by computing device 10 and based on the plurality of words, at least one language model probability for at least one of the one or more candidate words. The at least one language model probability may indicate whether the at least one of the one or more candidate words is positioned prior to the plurality of words in a sequence of words comprising the plurality of words and the at least one of the one or more candidate words.
In some examples, the operations may include determining, by computing device 10, a first plurality of words that were received by computing device 10 prior to receiving the indication of the selection of one or more of the plurality of keys. The operations may further include determining, by computing device 10, a second plurality of words received by computing device 10 subsequent to receiving the indication of the selection of one or more of the plurality of keys. The operations may further include determining, by computing device 10 and based on the first and second pluralities of words, at least one language model probability for at least one of the one or more candidate words. The language model probability may indicate whether the at least one of the one or more candidate words is positioned subsequent to the first plurality of words and prior to the second plurality of words in a sequence of words comprising the first plurality of words, the at least one of the one or more candidate words, and the second plurality of words.
In some examples, the plurality of features may comprise a typing speed of the selection of one or more of the plurality of keys, and the operations may further include determining, by computing device 10, a first point in time when computing device 10 begins receiving the indication of the selection of one or more of the plurality of keys. The operations may further include determining, by computing device 10, a second point in time when the computing device stops receiving the indication of the selection of one or more of the plurality of keys. The operations may further include determining, by computing device 10, a quantity of characters included in the character string. The operations may further include determining, by computing device 10, a duration of time from the first point in time to the second point in time. The operations may further include determining, by computing device 10 and based on the duration of time and the quantity of characters, the typing speed of the selection.
In some examples, the plurality of features may comprise a backspace usage percentage associated with the selection of one or more of the plurality of keys. The operations may further include determining, by computing device 10, a quantity of key selections included in the selection of one or more of the plurality of keys. The operations may further include determining, by computing device 10, a quantity of backspace key selections included in the selection of one or more of the plurality of keys and a quantity of delete key selections included in the selection of one or more of the plurality of keys. The operations may further include determining the backspace usage percentage, by computing device 10 and based at least in part on: the quantity of backspace key selections, the quantity of delete key selections, and the total quantity of key selections.
In some examples, the plurality of features may comprise a suggestion bar usage percentage. The operations may further include outputting, by computing device 10 and for display at the presence-sensitive screen, a suggestion bar region that includes one or more suggested word replacements. The operations may further include determining, by computing device 10, the suggestion bar usage percentage comprises a ratio of a quantity of selections, within a duration of time, of the one or more suggested word replacements, and a total quantity words that are generated, within the duration of time, by computing device 10 and based at least in part on indications of user input received by computing device 10.
In some examples, the spatial model probability associated with the at least one of the one or more candidate words may be a candidate word spatial model probability associated with the at least one of the one or more candidate words. The operations may further include determining, by computing device 10, a character string spatial model probability that indicates whether the character string represents an accurate sequence of characters based on the selection of the one or more plurality of keys. The operations may further include determining, by computing device 10, the character string is not included in a lexicon. Responsive to determining the character string is not included in the lexicon, the operations may further include determining, by computing device 10, the character string spatial model probability of the character string is greater than a character string threshold. Responsive to determining the character string spatial model probability of the character string is greater than the character string threshold, the operations may further include determining by computing device 10 the plurality of candidate words comprises the character string.
In some examples, the indication of the selection of one or more of the plurality of keys may comprise at least one input location of the presence-sensitive screen, the operations may further include determining, by computing device 10, a Euclidian distance associated with the at least one input location and a key location associated with one of the plurality of keys. The operations may further include determining, by computing device 10 and based on the Euclidian distance, the character string spatial model probability of the character string.
In some examples, the indication of the selection may comprise at least one input location of the presence-sensitive screen. The operations may further include determining, by computing device 10, a Euclidian distance associated with the at least one input location and a key location of at least one of the plurality of keys. The operations may further include determining, by computing device 10 and based on the Euclidian distance, the spatial model probability associated with at least one of the candidate words.
In some examples, for the operations that may include outputting the at least one of the plurality of candidate words the operations may further comprise outputting, by computing device 10 and for display at the presence-sensitive screen, the character string. The operations may further include outputting, by computing device 10 and for display at the presence-sensitive screen, the at least one of the plurality of candidate words within a predefined distance above the character string.
In some examples for the operations that may include outputting the character string, the operations may further comprise outputting, by computing device 10 and for display at the presence-sensitive screen, the character string with a format, wherein the format includes at least one of an underline, a highlight, a font size, and a font color.
In some examples, the operations may further include receiving, by computing device 10, an indication of a user input detected at a location of the presence-sensitive screen. The operations may further include determining, by computing device 10 and based at least in part on the indication of the user input, a selected candidate word. The selected candidate word may be one of the plurality of candidate words that is outputted above the character string. The operations may further include outputting, by computing device 10 and for display at the presence-sensitive screen, the selected candidate word to replace the character string.
In some examples, the at least one of the plurality of candidate words may be outputted at a first point in time and the operations may further include determining, by computing device 10, an elapsed time between the first point in time and a second point in time. In response to determining that the elapsed time is greater than a time threshold, the operations may further include refraining from outputting for display, by computing device 10, the plurality of candidate words.
In some examples, the operations may further include sending, by computing device 10 and to a remote computing device that is operatively coupled to the computing device, the character string. The operations may further include receiving, by computing device 10 and from the computing system, the plurality of candidate words.
In some examples, the operations may further include determining, by computing device 10 and based at least in part on a lexicon, a first spelling probability that the character string comprises an incorrect spelling of a first word of the plurality of candidate words. The operations may further include determining, by computing device 10 and based at least in part on a lexicon, a second spelling probability that the character string comprises an incorrect spelling of a second word of the plurality of candidate words. The operations may further include determining, by computing device 10, a value comprising a difference between the first spelling probability and the second spelling probability. In response to determining the value does not exceed an ambiguity threshold, the operations may further include outputting, by computing device 10 and for display at the presence-sensitive screen, the first word and the second word.
In some examples, the operations may further include receiving, by computing device 10, an indication of a user input detected at a location of the presence-sensitive screen that outputs at least one of the plurality of candidate words. Responsive to receiving the indication of the user input, the operations may further include outputting, by computing device 10 and for display at the presence-sensitive screen, at least one additional candidate word of the plurality of candidate words.
In some examples, the operations may further include receiving, by computing device 10, the indication of the selection of one or more of the plurality of keys from a keyboard input device.
In some examples, the character string may be a first word in a lexicon and the operations may further include, in response to determining a context associated with the character string, selecting, by computing device 10 and based at least in part on the context, a second word in the lexicon as the at least one of the plurality of candidate words.
US4703425 17. Juli 1985 27. Okt. 1987 Nec Corporation Language processing dictionary for bidirectionally retrieving morphemic and semantic expressions
US4859091 15. Juni 1987 22. Aug. 1989 Canon Kabushiki Kaisha Word processor including spelling verifier and corrector
US4873634 27. März 1987 10. Okt. 1989 International Business Machines Corporation Spelling assistance method for compound words
US5148367 * 17. Dez. 1990 15. Sept. 1992 Sharp Kabushiki Kaisha European language processing machine with a spelling correction function
US5799269 17. Mai 1996 25. Aug. 1998 Mitsubishi Electric Information Technology Center America, Inc. System for correcting grammar based on parts of speech probability
US5802205 18. Dez. 1995 1. Sept. 1998 Motorola, Inc. Method and system for lexical processing
US5883986 * 2. Juni 1995 16. März 1999 Xerox Corporation Method and system for automatic transcription correction
US5940847 31. Jan. 1997 17. Aug. 1999 Microsoft Corporation System and method for automatically correcting multi-word data entry errors
US6292179 6. Mai 1999 18. Sept. 2001 Samsung Electronics Co., Ltd. Software keyboard system using trace of stylus on a touch screen and method for recognizing key code using the same
US6407300 11. Apr. 2001 18. Juni 2002 Catalytic Distillation Technologies Apparatus and process for hydrogenations
US6654733 * 18. Jan. 2000 25. Nov. 2003 Microsoft Corporation Fuzzy keyboard
US6801190 26. Mai 2000 5. Okt. 2004 America Online Incorporated Keyboard system with automatic correction
US7030863 20. Dez. 2004 18. Apr. 2006 America Online, Incorporated Virtual keyboard system with automatic correction
US7042443 11. Okt. 2002 9. Mai 2006 Woodard Scott E Speed Writer program and device with Speed Writer program installed
US7075520 12. Dez. 2001 11. Juli 2006 Zi Technology Corporation Ltd Key press disambiguation using a keypad of multidirectional keys
US7088345 9. Febr. 2004 8. Aug. 2006 America Online, Inc. Keyboard system with automatic correction
US7098896 16. Jan. 2003 29. Aug. 2006 Forword Input Inc. System and method for continuous stroke word-based text input
US7145554 20. Juli 2001 5. Dez. 2006 Speedscript Ltd. Method for a high-speed writing system and high -speed writing device
US7151530 20. Aug. 2003 19. Dez. 2006 Canesta, Inc. System and method for determining an input selected by a user through a virtual interface
US7199756 6. Nov. 2003 3. Apr. 2007 Samsung Electronics Co., Ltd. Planar antenna for wireless communication device and portable computer using the same
US7199786 13. Nov. 2003 3. Apr. 2007 Daniel Suraqui Reduced keyboards system using unistroke input and having automatic disambiguating and a recognition method using said system
US7250938 6. Jan. 2004 31. Juli 2007 Lenovo (Singapore) Pte. Ltd. System and method for improved user input on personal computing devices
US7251367 20. Dez. 2002 31. Juli 2007 International Business Machines Corporation System and method for recognizing word patterns based on a virtual keyboard layout
US7256770 * 13. März 2001 14. Aug. 2007 Microsoft Corporation Method for displaying information responsive to sensing a physical presence proximate to a computer input device
US7296019 * 25. Okt. 2004 13. Nov. 2007 Microsoft Corporation System and methods for providing runtime spelling analysis and correction
US7349987 * 23. Mai 2002 25. März 2008 Digital Doors, Inc. Data security system and method with parsing and dispersion techniques
US7453439 21. Juli 2004 18. Nov. 2008 Forward Input Inc. System and method for continuous stroke word-based text input
US7508324 22. März 2005 24. März 2009 Daniel Suraqui Finger activated reduced keyboard and a method for performing text input
US7602382 25. Aug. 2005 13. Okt. 2009 Microsoft Corporation Method for displaying information responsive to sensing a physical presence proximate to a computer input device
US7680649 17. Juni 2002 16. März 2010 International Business Machines Corporation System, method, program product, and networking use for recognizing words and their parts of speech in one or more natural languages
US7706616 27. Febr. 2004 27. Apr. 2010 International Business Machines Corporation System and method for recognizing word patterns in a very large vocabulary based on a virtual keyboard layout
US7716579 19. Mai 2005 11. Mai 2010 602531 British Columbia Ltd. Data entry for personal computing devices
US7813822 * 29. Jan. 2005 12. Okt. 2010 Hoffberg Steven M Intelligent electronic appliance system and method
US7831822 4. Dez. 2006 9. Nov. 2010 Electronics And Telecommunications Research Institute Real-time stateful packet inspection method and apparatus
US7853874 20. Juni 2007 14. Dez. 2010 SAS Institute Spelling and grammar checking system
US7953732 * 7. Juni 2005 31. Mai 2011 Nokia Corporation Searching by using spatial document and spatial keyword document indexes
US8036878 18. Mai 2005 11. Okt. 2011 Never Wall Treuhand GmbH Device incorporating improved text input mechanism
US8078978 21. Nov. 2007 13. Dez. 2011 Google Inc. Method and system for predicting text
US8135582 30. Nov. 2009 13. März 2012 Daniel Suraqui Keyboard system and method for global disambiguation from classes with dictionary database from first and last letters
US8176419 19. Dez. 2007 8. Mai 2012 Microsoft Corporation Self learning contextual spell corrector
US8179370 9. Febr. 2010 15. Mai 2012 Google Inc. Proximity based keystroke resolution
US8232973 30. Juni 2008 31. Juli 2012 Apple Inc. Method, device, and graphical user interface providing word recommendations for text input
US8239570 1. Okt. 2008 7. Aug. 2012 International Business Machines Corporation Using link send and receive information to select one of multiple links to use to transfer data for send and receive operations
US8239750 * 15. Sept. 2009 7. Aug. 2012 Erik Thomsen Extracting semantics from data
US8612213 23. Mai 2013 17. Dez. 2013 Google Inc. Correction of errors in character strings that include a word delimiter
US9460708 * 17. Sept. 2009 4. Okt. 2016 Microsoft Technology Licensing, Llc Automated data cleanup by substitution of words of the same pronunciation and different spelling in speech recognition
US20010011995 13. März 2001 9. Aug. 2001 Kenneth Hinckley Method for providing feedback responsive to sensing a physical presence proximate to a control of an electronic device
US20030014286 * 11. Juli 2002 16. Jan. 2003 Cappellini Pablo Dario Search and retrieval system of transportation-related flexibly defined paths
US20030016873 * 19. Juli 2001 23. Jan. 2003 Motorola, Inc Text input method for personal digital assistants and the like
US20040155869 * 9. Febr. 2004 12. Aug. 2004 Robinson B. Alex Keyboard system with automatic correction
US20050091033 19. März 2004 28. Apr. 2005 Microsoft Corporation System and method for performing analysis on word variants
US20060005017 * 22. Juni 2004 5. Jan. 2006 Black Alistair D Method and apparatus for recognition and real time encryption of sensitive terms in documents
US20060075044 * 30. Sept. 2004 6. Apr. 2006 Fox Kevin D System and method for electronic contact list-based search and display
US20060112066 * 22. Nov. 2004 25. Mai 2006 International Business Machines Corporation Spell checking URLs in a resource
US20060119582 2. März 2004 8. Juni 2006 Edwin Ng Unambiguous text input method for touch screens and reduced keyboard systems
US20060197685 * 22. Febr. 2005 7. Sept. 2006 Research In Motion Limited Handheld electronic device having reduced keyboard and multiple password access, and associated methods
US20060241944 25. Apr. 2005 26. Okt. 2006 Microsoft Corporation Method and system for generating spelling suggestions
US20070239426 7. Apr. 2006 11. Okt. 2007 Research In Motion Limited Handheld electronic device providing a learning function to facilitate correction of erroneous text entry in environment of text requiring multiple sequential actuations of the same key, and associated method
US20080114721 15. Nov. 2006 15. Mai 2008 Rosie Jones System and method for generating substitutable queries on the basis of one or more features
US20080182599 * 31. Jan. 2007 31. Juli 2008 Nokia Corporation Method and apparatus for user input
US20080195388 * 8. Febr. 2007 14. Aug. 2008 Microsoft Corporation Context based word prediction
US20080316183 22. Juni 2007 25. Dez. 2008 Apple Inc. Swipe gestures for touch screen keyboards
US20090006079 * 29. Juni 2007 1. Jan. 2009 Microsoft Corporation Regular expression word verification
US20090281787 * 11. Mai 2009 12. Nov. 2009 Xin Wang Mobile electronic device and associated method enabling transliteration of a text input
US20090292700 * 23. Mai 2008 26. Nov. 2009 Xerox Corporation System and method for semi-automatic creation and maintenance of query expansion rules
US20090306980 * 16. Jan. 2009 10. Dez. 2009 Jong-Ho Shin Mobile terminal and text correcting method in the same
US20090307584 16. Sept. 2008 10. Dez. 2009 Davidson Douglas R Automatic language identification for dynamic text processing
US20100070908 18. Sept. 2008 18. März 2010 Sun Microsystems, Inc. System and method for accepting or rejecting suggested text corrections
US20100106724 23. Okt. 2009 29. Apr. 2010 Ab Initio Software Llc Fuzzy Data Operations
US20100287486 7. Mai 2009 11. Nov. 2010 Microsoft Corporation Correction of typographical errors on touch displays
US20110022952 4. Okt. 2010 27. Jan. 2011 Google Inc. Determining Proximity Measurements Indicating Respective Intended Inputs
US20110035209 6. Juli 2010 10. Febr. 2011 Macfarlane Scott Entry of text and selections into computing devices
US20110099506 26. Okt. 2010 28. Apr. 2011 Google Inc. Predictive Text Entry for Input Devices
US20110161829 24. Dez. 2009 30. Juni 2011 Nokia Corporation Method and Apparatus for Dictionary Selection
US20110179353 * 19. Jan. 2010 21. Juli 2011 Research In Motion Limited Mobile Electronic Device and Associated Method Providing Proposed Spelling Corrections Based Upon a Location of Cursor At or Adjacent a Character of a Text Entry
US20110202836 * 20. Mai 2010 18. Aug. 2011 Microsoft Corporation Typing assistance for editing
US20110234524 25. März 2011 29. Sept. 2011 Longe Michael R Virtual Keyboard System with Automatic Correction
US20120036469 24. Juli 2011 9. Febr. 2012 Daniel Suraqui Reduced keyboard with prediction solutions when input is a partial sliding trajectory
US20120078616 * 30. Nov. 2011 29. März 2012 Research In Motion Limited Handheld Electronic Device and Associated Method Enabling Spell Checking in a Text Disambiguation Environment
US20120130706 * 18. Nov. 2011 24. Mai 2012 Weigen Qiu Systems and methods for character correction in communication devices
US20120166371 * 6. Jan. 2012 28. Juni 2012 Primal Fusion Inc. Knowledge representation systems and methods incorporating data consumer models and preferences
US20120196627 * 10. Apr. 2012 2. Aug. 2012 Nokia Corporation Messaging
US20120246133 * 23. März 2011 27. Sept. 2012 Microsoft Corporation Online spelling correction/phrase completion system
US20120290950 * 7. Febr. 2012 15. Nov. 2012 Jeffrey A. Rapaport Social-topical adaptive networking (stan) system allowing for group based contextual transaction offers and acceptances and hot topic watchdogging
US20130002553 * 29. Juni 2011 3. Jan. 2013 Nokia Corporation Character entry apparatus and associated methods
US20130232006 * 4. März 2013 5. Sept. 2013 Tim Holcomb Filtered Search Query Data for Context and User Intent within a Location-Based Search Engine
US20140058722 * 24. Aug. 2012 27. Febr. 2014 Microsoft Corporation Word Detection and Domain Dictionary Recommendation
CN1928860A 5. Sept. 2005 14. März 2007 日电（中国）有限公司 Method, search engine and search system for correcting key errors
CN100472600C 22. Dez. 2004 25. März 2009 美国在线服务公司 Virtual keyboard system with automatic text input correction
CN101605171A 13. März 2009 16. Dez. 2009 Lg电子株式会社 Mobile terminal and text correcting method in the same
EP1248183A2 24. Sept. 1998 9. Okt. 2002 Tegic Communications, Inc. Reduced keyboard disambiguating system
EP1248186A2 9. Jan. 2002 9. Okt. 2002 Infineon Technologies AG Carry-ripple adder
EP2592569A2 2. Nov. 2012 15. Mai 2013 Research In Motion Limited Touchscreen keyboard predictive display and generation of a set of characters
WO2005064587A2 22. Dez. 2004 14. Juli 2005 America Online, Inc. Virtual keyboard system with automatic correction
WO2009002772A2 18. Juni 2008 31. Dez. 2008 Algaedyne Corportion Bioreactor
WO2013184599A1 3. Juni 2013 12. Dez. 2013 Apple Inc. Multi-word autocorrection
1 Burns, "Nuance Supercharges Swype, Adds New Keyboard Options, XT9 Predictive Text, and Drangon-Powered Voice Input," Retrieved from http://techcrunch.com/2012/06/20nuance-supercharges-swype-adds-new-keyboard-options-xt9-predictive-text-and-dragon-powered-voice-input/?, Jun. 21, 2012, 2 pp.
2 Butcher, "Swiftkey Counters Swype With A Smarter Version, Makes An In-Road Into Healthcare Market," Retrieved from http://techrunch.com/2012/06/21/swiftkey-counters-swype-with-a-smarter-version-makes-an-in-road-into-healthcare-market/, Jun. 21, 2012, 2 pp.
3 Communication under Rule 71(3) EPC, Intention to Grant from counterpart European Application No. 13780034.8, dated May 26, 2017, 68 pp.
4 Examination Report from counterpart European Application No. 13780034.8, dated Nov. 11, 2015, 6 pp.
5 International Preliminary Report on Patentability of International Application No. PCT/US2013/064145, mailed Apr. 30, 2015 8 pp.
6 International Search Report and Written Opinion of International application No. PCT/US2013/064145, mailed Jan. 20, 2014, 10 pp.
7 Lomas, "Hey Apple, What the Next iPhone Really, Really Needs Is a Much Better Keyboard", Techcrunch [online], Apr. 21, 2013. Retrieved from the Internet: <http:1/techcrunch.com12013/04/21/the-iphone-keyboard-stinks/?> 6 pgs.
8 May, Jonathan Davis Louis, "Weighted tree automata and transducers for syntactic natural language processing," Dissertation Presented to the Faculty of the USC Graduate School of the University of Southern California, Aug. 2010, 231 pp.
9 Notification of First Office Action from counterpart Chinese Application No. 201380052562.4, issued Aug. 19, 2016 22 pgs.
10 Park et al., "Automated Whole Sentence Grammer Correction Using a Noisy Channel Model," Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, Jun. 19-24, 2011, 12 pp.
11 Prosecution History from U.S. Appl. No. 13/733,701, from Jul. 2, 2013 through Dec. 10, 2013, 40 pp.
12 Response to the Examination Report dated Nov. 11, 2015, from counterpart European Application No. 13780034.8, filed Apr. 27, 2016, 22 pp.
13 Second Office Action, and translation thereof, from counterpart Chinese Application No. 201380052562.4, dated May 3, 2017, 20 pp.
14 U.S. Appl. No. 13/733,701, filed Jan. 3, 2013, by Ouyang et al.
15 U.S. Appl. No. 14/083,131, filed Nov. 18, 2013, by Zhai et al.
16 U.S. Appl. No. 60/430,338, by Daniel Suraqui, filed Nov. 29, 2002.
17 U.S. Appl. No. 60/505,724, by Daniel Suraqui, filed Sep. 22, 2003.
18 Young et al., "Token Passing: a Simple Conceptual Model for Connected Speech Recognitions Systems," Cambridge University Engineering Department, Jul. 31, 1989, 23 pp.
Internationale Klassifikation G06F3/023, G06F17/00, G06F3/0488, G06F17/27
Unternehmensklassifikation H04L51/063, H04L51/02, G06F3/04886, G06F3/04883, G06F3/0237, G06F17/273, G06F17/2735, G06F17/2765, G06F17/274
6. März 2014 AS Assignment
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:OUYANG, YU;ZHAI, SHUMIN;REEL/FRAME:032370/0933