PROVIDING RELEVANT TEXT AUTO-COMPLETIONS

• US 20080294982A1
• Filed: 05/21/2007
• Published: 11/27/2008
• Est. Priority Date: 05/21/2007
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Leung, Brian, Zhang, Qi
• Application Number:
  US11/751,121
• Publication Number:
  US 20080294982A1
• Time in Patent Office: Days
• US Class Current: 715/261
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

A processing device, such as, for example, a tablet PC, or other processing device, may receive non-textual language input. The non-textual language input may be recognized to produce one or more textual characters. The processing device may generate a list including one or more prefixes based on the produced one or more textual characters. Multiple text auto-completion predictions may be generated based on multiple prediction data sources and the one or more prefixes. The multiple text auto-completion predictions may be ranked and sorted based on features associated with each of the text auto-completion predictions. The processing device may present a predetermined number of best text auto-completion predictions. A selection of one of the presented predetermined number of best text auto completion predictions may result in a word, currently being entered, being replaced by the selected one of the predetermined number of best text auto completion predictions.

Claims

1. A machine-implemented method for providing text auto-completion predictions with respect to language input, the machine-implemented method comprising:

recognizing the language input and producing at least one textual character;

generating a list including at least one prefix based on the at least one textual character;

generating a plurality of text auto-completion predictions from a plurality of prediction sources based on the generated list;

sorting the plurality of text auto-completion predictions based on a plurality of features associated with each of the plurality of text auto-completion predictions; and

presenting a predetermined number of best text auto-completion predictions as possible text auto-completion predictions with respect to the language input.

2. The machine-implemented method of claim 1, wherein:

the language input is one of handwritten digital ink or speech.

3. The machine-implemented method of claim 1, wherein:

generating a plurality of text auto-completion predictions from the plurality of prediction sources based on the generated list further comprises;

generating respective feature vectors for each of the plurality of text auto-completion predictions, each of the respective feature vectors describing a plurality of features of corresponding ones of the plurality of text auto-completion predictions; and

sorting the plurality of text auto-completion predictions based on a plurality of features associated with each of the plurality of text auto-completion predictions further comprises;

performing a merge sort of the plurality of text auto-completion predictions based on comparing the respective feature vectors.

4. The machine-implemented method of claim 1, wherein:

generating a list including at least one prefix based on the at least one textual character further comprises;

generating the list based on textual data from a best predetermined number of recognition paths produced by the recognizing of the language input.

5. The machine-implemented method of claim 1, wherein the plurality of prediction data sources include an input history prediction data source built from recently-entered user data, a personalized lexicon prediction data source based on input user data, a domain lexicon prediction data source, and an ngram language model prediction data source based, at least partly, on the user data.

6. The machine-implemented method of claim 1, wherein the plurality of features associated with each of the plurality of text auto-completion predictions comprise:

a length of a prefix used to generate a respective text auto-completion prediction,

a length of the respective text auto-completion prediction,

whether the prefix is a word,

a unigram of the prefix and the respective text auto-completion prediction,

a bigram of the prefix, the respective text auto-completion prediction, and a word preceding the respective text auto-completion prediction,

a character unigram of a first character of the respective text auto-completion prediction, and

a character bigram of a last character in the prefix and the first character in the respective text auto-completion prediction.

7. The machine-implemented method of claim 1, further comprising:

exposing an application program interface for applications to request and receive text auto-completion prediction related data.

8. A tangible machine-readable medium having instructions recorded thereon for at least one processor of a processing device, the instructions comprising:

instructions for building and updating a plurality of prediction data sources based, at least in part, on user data,

instructions for recognizing user language input and producing a list including a plurality of prefixes based on a predetermined number of best recognition paths,

instructions for generating a plurality of text-auto completion predictions from the plurality of prediction data sources based on the plurality of prefixes,

instructions for generating a respective feature vector for each of the plurality of text auto-completion predictions, each of the respective feature vectors describing a plurality of features with respect to a corresponding one of the plurality of text auto-completion predictions,

instructions for ranking the plurality of text auto-completion predictions based on the respective feature vectors, and

instructions for presenting a predetermined number of best ones of the plurality of text auto-completion predictions as possible text auto-completions to the user language input.

9. The tangible machine-readable medium of claim 8, further comprising:

instructions for limiting a number of the plurality of predictions to consider by keeping ones of the plurality of text auto-completion predictions based on one of the plurality of prefixes from a best recognition path, and keeping most frequently predicted ones of the plurality of text auto-completion predictions based on ones of the plurality of prefixes other than the one of the plurality of prefixes from the best recognition path.

10. The tangible machine-readable medium of claim 8, wherein the user language input is handwritten digital ink.

11. The tangible machine-readable medium of claim 8, wherein the instructions for building and updating a plurality of prediction data sources based, at least in part, on user data comprise:

instructions for building an input-history prediction data source based on recent user data input,

instructions for building a personalized lexicon prediction data source based on stored user data, and

instructions for building an ngram language model based, at least in part, on the stored user data.

12. The tangible machine-readable medium of claim 8, wherein the instructions for generating a plurality of text auto-completion predictions from the plurality of prediction data sources based on the plurality of prefixes further comprise:

instructions for finding a respective grouping of characters in the plurality of prediction data sources that matches ones of the plurality of prefixes and generating a respective text auto-completion prediction based on one or more characters associated with the respective grouping of characters.

13. The tangible machine-readable medium of claim 8, wherein at least some of the plurality of text auto-completion predictions include at least one word following a current word of the user language input being entered.

14. The tangible machine-readable medium of claim 8, wherein the instructions for ranking the plurality of text auto-completion predictions based on the respective feature vectors comprise:

instructions for favoring longer predictions over shorter predictions.

15. The tangible machine-readable medium of claim 8, wherein the instructions further comprise:

instructions for exposing an application program interface to provide at least one text auto-completion prediction with respect to a result of recognizing user input language.

16. A processing device comprising:

at least one processor;

a memory;

a bus connecting the at least one processor with the memory, the memory comprising;

instructions for recognizing digital ink input, representing language input, to produce a recognition result,

instructions for generating a plurality of text auto-completion predictions based on the recognition result, at least some of the plurality of text auto-completion predictions predicting words following a current word being entered,

instructions for presenting up to a predetermined number of best ones of the plurality of text auto-completion predictions,

instructions for receiving a selection of one of the presented predetermined number of best ones of the plurality of text auto-completion predictions, and

instructions for providing the selected one of the presented predetermined number of best ones of the plurality of text auto-completion predictions as input.

17. The processing device of claim 16, wherein the instructions for generating a plurality of text auto-completion predictions based on the recognition result further comprise:

instructions for generating the plurality of text auto-completion predictions from a plurality of prediction data sources, at least some of the plurality of data sources being derived from stored user data.

18. The processing device of claim 16, wherein the instructions for generating a plurality of text auto-completion predictions based on the recognition result further comprise:

instructions for generating the plurality of predictions from a plurality of prediction data sources, at least some of the plurality of prediction data sources being derived from stored user data, and one of the plurality of prediction data sources being a generic lexicon-based prediction data source for a particular language or a domain lexicon prediction data source.

19. The processing device of claim 16, wherein the memory further comprises instructions for ranking the plurality of text auto-completion predictions according to a plurality of features associated with each of the plurality of text auto-completion predictions and a prefix based on the recognition result, a relevance of each of the plurality of features being previously trained based on previously provided text input.

20. The processing device of claim 16, wherein the memory further comprises:

instructions for using a comparative neural network to rank the plurality of text auto-completion predictions according to a plurality of features associated with each of the plurality of text auto-completion predictions and a prefix based on the recognition result.