Method and apparatus for improved grammar checking using a stochastic parser

• US 7,003,444 B2
• Filed: 07/12/2001
• Issued: 02/21/2006
• Est. Priority Date: 07/12/2001
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Weise, David Neal
• Primary Examiner(s): Knepper, David D.
• Assistant Examiner(s): Han, Qi
• Application Number:
  US09/904,232
• Publication Number:
  US 20030036900A1
• Time in Patent Office: 1,685 Days
• Field of Search: 704/9, 704/257, 707/533, 715/533
• US Class Current: 704/9
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique

Abstract

A method and grammar checking system are provided that generate a stochastic score, or a statistical goodness measure, for each of an input string of text and one or more alternative strings of text. An alternative generator generates the alternative strings of text, and a ranking parser produces parse trees and corresponding statistical goodness measures for each of the strings. The string of text having the highest goodness measure is selected for recommendation to a user.

Claims

1. A grammar checking system comprising:

an alternative generator configured to receive an input string of text, and in response, to generate alternative strings of text corresponding to different possible grammatical corrections of the input string of text;

a parse tree producer configured to generate parse trees for the input string of text and for each of the alternative strings of text;

a stochastic score generator configured to receive the parse trees for the input string of text and for each of the alternative strings of text and to generate separate parse scores for each of the strings of text by generating a separate statistical goodness measure for each of the strings of text using the corresponding parse tree, wherein the statistical goodness measure for each of the parse trees is an indicator of a likelihood that the particular parse tree represents the intended meaning of a human originating the text corresponding to the input string of text;

a string selector configured to determine which string of text, out of the input string of text and the alternative strings of text, has a greatest parse score and to select the string of text having the highest parse score; and

a grammar checker including the alternative generator and the string selector, the grammar checker further comprising;

string storage coupled to the alternative generator and to the stochastic score generator, and configured to store the input string of text and each of the alternative strings of text, and configured to store the statistical goodness measure generated for each string of text; and

a parceler coupled to the string storage and to the parse tree producer, and configured to call the parse tree producer and the stochastic score generator in order to produce a parse tree and a statistical goodness measure for each string of text.

2. The grammar checking system of claim 1, wherein the stochastic score generator is configured to generate the separate statistical goodness measure for each of the strings of text as functions of probabilities determined using a training corpus.

3. The grammar checking system of claim 2, wherein the stochastic score generator is configured to generate the separate statistical goodness measure for each of the strings of text by combining probabilities of each node in the corresponding parse tree, wherein the probabilities of each node are determined by the steps comprising:

receiving language-usage probabilities based upon appearances of instances of combinations of linguistic features within the training corpus; and

calculating the probabilities of each node based upon linguistic features of each node and the language-usage probabilities.

4. The grammar checking system of claim 1, and further comprising a stochastic ranking parser including the parse tree producer and the stochastic score generator.

5. The grammar checking system of claim 1, wherein the grammar checker is configured such that, if the selected string of text having the highest parse score is the input string of text, then the grammar checker does not recommend a grammar correction for the input string of text.