Method for detecting stylistic errors and generating replacement strings in a document containing Japanese text

• US 6,035,269 A
• Filed: 06/23/1998
• Issued: 03/07/2000
• Est. Priority Date: 06/23/1998
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Kim, Hyun-suk
• Primary Examiner(s): Thomas, Joseph
• Application Number:
  US09/103,207
• Time in Patent Office: 623 Days
• Field of Search: 704/9, 704/8, 704/10, 704/1, 707/535, 707/536, 707/532, 707/531, 707/533
• US Class Current: 704/9
• CPC Class Codes: G06F 40/232 Orthographic correction, e.g. spell checking or vowelisation
• CPC Class Codes: G06F 40/53 Processing of non-Latin text kana-to-kanji conversion G06F40/129; vowelisation G06F40/232

Abstract

Critiques are applied to phrase units included in morpho-syntactical information derived from the Japanese text. The critiques include a "trigger" and an "action," and are written in a special-purpose syntax that allows for easy specification of the error class and the rewrite generation. If a critique'"'"'s trigger condition is satisfied, the associated action is carried out in order to generate a replacement text string. The process of generating replacement text strings employs a morphological graph that reflects possible word formations. In a first pass through the graph, a breadth first search is used to identify intermediate nodes along a path whose morpheme transitions satisfy at least part of the attributes of the text. In a second pass, a depth first search is used to select only those morpheme transitions that completely satisfy the rewrite criteria specified in the critique, while traversing the nodes identified in the breadth first search. The morpheme transitions identified during the depth first search provide the text string that is used to replace the original phrase.

Claims

1. A computer-implemented method for generating a substitute text string, comprising the steps of:

providing a morphological graph including a first state, a last state, and at least one morpheme transition between the first state and the last state;

receiving morpho-syntactical data associated with an original phrase, the morpho-syntactical data including a stem corresponding to the first state, at least one bound morpheme, and attribute bits describing the original phrase;

applying a critique to the morpho-syntactical data, the critique including a trigger and an action;

determining whether the trigger is satisfied by the morpho-syntactical data; and

if the trigger is satisfied, performing the steps of;

preparing a morpheme list and a bit list corresponding to the action;

traversing the morphological graph by a first pass from the last state to the first state in a breadth-first manner, with a graph path of the first pass being determined by the contents of the morpheme list and the bit list;

traversing the morphological by a second pass from the first state to the last state in a depth-first manner, with a reconstructed graph path being determined by nodes of the graph path of the first pass; and

providing a substitute string corresponding to the reconstructed path.

2. The method of claim 1, wherein the substitute string includes the stem and replacement morphemes, the replacement morphemes being derived from the reconstructed path and corresponding to the morpheme transitions traversed along the reconstructed path.

3. The method of claim 1, wherein the first state corresponds to a stem and the last state corresponds to the rightmost edge of a phrase.

4. The method of claim 1, wherein the trigger defines a test condition associated with the attribute bits.

5. The method of claim 1, wherein preparing a morpheme list and a bit list comprises the steps of:

preparing an initial morpheme list and an initial bit list corresponding to state of morpho-syntactical data; and

altering the initial morpheme list and the initial bit list in accordance with the action.

6. A computer-readable medium, comprising:

morphological graph data representing a first state, a last state, and at least one morpheme transition between the first state and the last state; and

computer-executable instructions for performing steps comprising;

applying a critique to morpho-syntactical data associated with an original phrase, the critique including a trigger and an action, the morpho-syntactical data including a stem corresponding to the first state, at least one bound morpheme, and attribute bits describing the original phrase;

determining whether the trigger is satisfied by the morpho-syntactical data;

preparing a morpheme list and a bit list corresponding to state of morpho-syntactical data;

altering the morpheme list and the bit list in accordance with the action;

traversing the morphological graph data by a first pass from the last state to the first state in a breadth-first manner, with a graph path of the first pass being determined by the contents of the morpheme list and the bit list;

traversing the morphological graph by a second pass from the first state to the last state in a depth-first manner, with a reconstructed graph path being determined by nodes of the graph path of the first pass; and

providing a substitute string corresponding to the reconstructed path, the substitute string including the stem and replacement morphemes, the replacement morphemes being derived from the path and corresponding to the morpheme transitions traversed along the path.

7. The method of claim 6, wherein the first state corresponds to a stem and the last state corresponds to the rightmost edge of a phrase.

8. The method of claim 6, wherein the trigger defines a test condition associated with the attribute bits.

9. A computer-implemented method for generating a substitute text string, comprising the steps of:

providing a morphological graph including a stem state, a RNone state, and at least one morpheme transition between the stem state and the RNone state;

receiving morpho-syntactical data associated with an original phrase, the morpho-syntactical data including a stem corresponding to the stem state, at least one bound morpheme, and attribute bits;

applying a critique to the morpho-syntactical data, the critique including a trigger defining a test condition and an action to be taken is the test condition is satisfied;

determining whether the test condition is satisfied by the morpho-syntactical data; and

if the test condition is satisfied, performing the steps of;

preparing a morpheme list and a bit list corresponding to state of morpho-syntactical data;

altering the morpheme list and the bit list in accordance with the action;

traversing the morphological graph by a first pass from the RNone state to the stem state in a breadth-first manner, with a graph path of the first pass being determined by the contents of the morpheme list and the bit list;

traversing the morphological by a second pass from the stem state to the RNone state in a depth-first manner, with a reconstructed graph path being determined by nodes of the graph path of the first pass; and

providing a substitute string including the stem and replacement morphemes, wherein the replacement morphemes are derived from the reconstructed path and correspond to the morpheme transitions traversed along the path.

10. The method of claim 9, wherein the graph path of the first pass comprises a plurality of the nodes, including at least one intermediate node.