Patent Document ID: 9047268
Application ID: 13774656

Base Claim:
1. A method comprising: receiving, by a computing device, an indication of user-inputted text; storing, by the computing device, a lexicon that includes a set of in-lexicon candidate strings and does not include a set of out-of-lexicon candidate strings, wherein each of the in-lexicon candidate strings and each of the out-of-lexicon candidate strings is a respective word in a particular language; for each respective in-lexicon candidate string of the set of in-lexicon candidate strings, determining, by the computing device, a respective score for the respective in-lexicon candidate string, wherein: the respective score is based at least in part on a probability of the respective in-lexicon candidate string as a whole being entered, and the probability of the respective in-lexicon candidate string being entered is affected by a word-level context of the respective in-lexicon candidate string that includes one or more character strings that precede the respective in-lexicon candidate string in the user-inputted text; for each respective out-of-lexicon candidate string of the set of out-of-lexicon candidate strings, determining, by the computing device, a respective score for the respective out-of-lexicon candidate string, wherein the respective score for the respective out-of-lexicon candidate string is based at least in part on respective probabilities of individual characters in the respective out-of-lexicon candidate string being entered and is not based on word-level probabilities; determining, by the computing device and based at least in part on the scores for the in-lexicon candidate strings and the scores for the out-of-lexicon candidate strings, a combined set of candidate strings from the set of in-lexicon candidate strings and the set of out-of-lexicon candidate strings, the combined set of candidate strings including at least one in-lexicon candidate string from the set of in-lexicon candidate strings and at least one out-of-lexicon candidate string from the set of out-of-lexicon candidate strings; outputting, by the computing device, at least a portion of the combined set of candidate strings for display; and responsive to an indication of a selection of a candidate string from the combined set of candidate strings, outputting, by the computing device, for display in place of the user-inputted text, the selected candidate string.

---

Claim 15:
15. The method of claim 1 , wherein: a finite state transducer (FST) includes arcs that correspond to characters; and determining the scores for the out-of-lexicon candidate strings comprises determining, by the computing device and based at least in part on scores associated with followed arcs in the FST, a score for a particular out-of-lexicon candidate string in the set of out-of-lexicon candidate strings, wherein the followed arcs of the FST are arcs of the FST that correspond to characters of the particular out-of-lexicon candidate string, wherein for each respective one of the followed arcs, the score that corresponds to the respective followed arc is based at least in part on a probability of the character that corresponds to the respective followed arc.