8. The method of claim 1 , wherein: determining the combined set of candidate strings comprises: ranking, 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, candidate strings in the set of in-lexicon candidate strings and the set of out-of-lexicon candidate strings; and selecting, by the computing device, a highest-ranked candidate string from the in-lexicon candidate strings and the out-of-lexicon candidate strings.
10. The method of claim 8 , wherein ranking the candidate strings comprises ranking, by the computing device and based at least in part on the scores of the first in-lexicon candidate strings and the scores for the out-of-lexicon candidate strings, and based at least in part on a probability that an out-of-lexicon character string follows a preceding character string, the candidate strings, wherein the out-of-lexicon character string is not in the lexicon.