Method and system for providing alternatives for text derived from stochastic input sources

• US 6,789,231 B1
• Filed: 10/05/1999
• Issued: 09/07/2004
• Est. Priority Date: 10/05/1999
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kim, Paul Kyong Hwan, Rucker, Erik, Reynar, Jeffrey C.
• Primary Examiner(s): Shah, Sanjiv
• Assistant Examiner(s): Bashore, William L.
• Application Number:
  US09/412,822
• Time in Patent Office: 1,799 Days
• Field of Search: 715/533, 715/501.1, 715/500, 704/4, 704/9
• US Class Current: 715/256
• CPC Class Codes: G06F 40/274 Converting codes to words; Guess-ahead of partial word inputs

Abstract

A computer-implemented method for providing a candidate list of alternatives for a text selection containing text from multiple input sources, each of which can be stochastic (such as a speech recognition unit, handwriting recognition unit, or input method editor) or non-stochastic (such as a keyboard and mouse). A text component of the text selection may be the result of data processed through a series of stochastic input sources, such as speech input that is converted to text by a speech recognition unit before being used as input into an input method editor. To determine alternatives for the text selection, a stochastic input combiner parses the text selection into text components from different input sources. For each stochastic text component, the combiner retrieves a stochastic model containing alternatives for the text component. If the stochastic text component is the result of a series of stochastic input sources, the combiner derives a stochastic model that accurately reflects the probabilities of the results of the entire series. The combiner creates a list of alternatives for the text selection by combining the stochastic models retrieved. The combiner may revise the list of alternatives by applying natural language principles to the text selection as a whole. The list of alternatives for the text selection is then presented to the user. If the user chooses one of the alternatives, then the word processor replaces the text selection with the chosen candidate.

Claims

1. A computer-implemented method for correcting text, comprising the steps of:

receiving a text selection comprising a plurality of text components derived from different input sources, wherein at least one of the text components comprises a stochastic text component derived from a stochastic input source or a series of stochastic input sources;

receiving a command to display alternatives for the text selection;

parsing the text selection into the text components;

retrieving a stochastic model for the stochastic text component from its associated stochastic input source or series of input sources;

combining the stochastic model with other text components to produce a list of alternatives for the text selection;

displaying the list of alternatives for the text selection on a display device;

receiving user input into a first stochastic input source in a series of stochastic input sources;

selecting a stochastic result comprising a plurality of alternatives produced by the first stochastic input source;

producing a plurality of stochastic results for a second stochastic input source in the series by using each alternative of the stochastic result produced by the first stochastic input source as input into the second stochastic input source to produce a stochastic result for the second stochastic input source;

if any stochastic result for the second stochastic input source does not comprise an “

n-best”

alternatives list, converting that stochastic result to an “

n-best”

alternatives list; and

combining the stochastic results for the second stochastic input source to create a totalized alternatives list for the second stochastic input source.

2. The method of claim 1, further comprising the steps of:

receiving a user command selecting one of the displayed alternatives; and

replacing the text selection with the selected alternative.

3. The method of claim 1, further comprising the steps of:

receiving an edit to the text selection;

producing a revised list of alternatives for the edited text selection; and

displaying the revised list of alternatives for the edited text selection.

4. The method of claim 1, further comprising the steps of:

receiving an edit to one of the stochastic text components;

retrieving a revised stochastic model for the edited stochastic text component from its associated stochastic input source or series of input sources;

combining the revised stochastic model with another stochastic model associated with the text selection to produce a revised list of alternatives for the edited text selection; and

displaying the revised list of alternatives for the edited text selection.

5. The method of claim 1, wherein the text selection comprises a portion of text in a file within an application selected from the group consisting of a word processor, a spreadsheet, a browser, an electronic mail program, a music transcription program, a CAD program, a presentation program, and an operating system.

6. The method of claim 1, wherein the step of displaying the alternatives for the text selection further comprises the steps of:

ranking the alternatives for the text selection in probability order; and

displaying the alternatives in their rank order on the display device.

7. The method of claim 6, wherein the step of displaying the alternatives in their rank order further comprises the steps of:

selecting a pre-determined number of highest ranked alternatives; and

displaying the selected alternatives in their rank order on the display device.

8. The method of claim 1, wherein the text selection comprises a plurality of stochastic text components and the step of combining the stochastic models further comprises the steps of:

combining the stochastic models for each stochastic text component to produce an interim list of alternatives for the text selection;

providing the interim list of alternatives to a natural language model;

receiving a revised list of alternatives for the text selection from the natural language model, the revised list of alternatives comprising a reevaluation of the interim list of alternatives based on natural language principles applied by the natural language model to the text selection as a whole; and

displaying the revised list of alternatives as the list of alternatives for the text selection.

9. The method of claim 8, wherein the revised list of alternatives also comprises additional alternatives formed by the natural language model that are not found in the interim list of alternatives provided to the natural language model.

10. The method of claim 8, further comprising the step of providing the stochastic model retrieved for one or more stochastic text components to a natural language model for reevaluation based on natural language principles.

11. The method of claim 8, further comprising the step of providing the stochastic model for each stochastic text component to the natural language model for use in creating the revised list of alternatives.

12. The method of claim 1, wherein the text selection comprises a plurality of stochastic text components and the stochastic models for the text components comprise lattices, and wherein the step of combining the stochastic models to produce a list of alternatives for the text selection further comprises the steps of:

concatenating the lattices into a metalattice that includes information about any text components that are derived from a non-stochastic source; and

producing the list of alternatives for the text selection from the metalattice.

13. The method of claim 1, wherein the text selection comprises a plurality of stochastic text components and one of the stochastic models comprises an “

n-best”

candidate list and another stochastic model comprises a lattice, and wherein the step of combining the stochastic models to produce a list of alternatives for the text selection further comprises the steps of;

creating an “

n-best”

candidate list corresponding to the lattice; and

producing the list of alternatives for the text selection by combining the “

n-best”

candidate lists for the text components.

14. The method of claim 1, wherein the step of retrieving a stochastic model for a text component originating from a stochastic input source further comprises the steps:

determining if the text component is derived from stochastic input sources configured in series;

if the text component is derived from stochastic input sources configured in series, deriving a series stochastic model by combining together a stochastic model from each stochastic input source in the series; and

retrieving the series stochastic model as the stochastic model for the text component.

15. The method of claim 1, wherein the step of combining the plurality of stochastic results for the second stochastic input source to create the totalized alternatives list for the second stochastic input source further comprises the steps of:

creating a single entry in the totalized alternatives list for each unique alternative appearing in the plurality of stochastic results for the second stochastic input source;

calculating a probability for each alternative in the totalized alternatives list by summing all probabilities assigned to that alternative in the plurality of stochastic results for the second stochastic input source; and

assigning each calculated probability to its associated alternative.

16. A computer-readable medium having computer-executable instructions for performing the method of claim 15.

17. A computer adapted to perform the method of claim 15.

18. A computer-readable medium having computer-executable instructions for performing the method of claim 1.

19. A computer adapted to perform the method of claim 1.