Machine translation system utilizing bilingual equivalence statements

• US 5,696,980 A
• Filed: 04/27/1993
• Issued: 12/09/1997
• Est. Priority Date: 04/30/1992
• Status: Expired due to Fees

• Current Assignee: Sharp Kabushiki Kaisha (Hon Hai Precision Industry Co., Ltd.)
• Original Assignee: Sharp Kabushiki Kaisha (Hon Hai Precision Industry Co., Ltd.)
• Inventors: Brew, Christopher Hardie
• Primary Examiner(s): Weinhardt, Robert A.
• Application Number:
  US08/054,440
• Time in Patent Office: 1,687 Days
• Field of Search: 364/419.02, 364/419.08, 364/419.03, 395/752, 395/759, 395/753
• US Class Current: 704/273
• CPC Class Codes: G06F 40/253 Grammatical analysis; Style critique
• CPC Class Codes: G06F 40/45 Example-based machine translation; Alignment
• CPC Class Codes: G06F 40/55 Rule-based translation
• CPC Class Codes: G06F 40/56 Natural language generation

Abstract

A machine translation system which operates by analyzing a source text to deduce information about the usage and meaning of the words of a source language text as they occur in context. This information is passed to an equivalencing module, which determines a set of equivalent target language words from which may be constructed a target language text by a generation module. The generation module has internal structure, including a tree construction module and a constraint checking module. The two modules operate in parallel. The tree constructor builds legal target language structures from which the translated text may be extracted. The constraint checker ensures that each structure which is built will be part of a global structure that uses all the words which appear in the input to the generation module.

Claims

1. A machine translation system, comprising:

means for reading a source language text including source language words from an input source, an analysis module for processing the text by drawing on information from at least one of source language grammars and dictionaries provided in the system to deduce source word information about the usage and meaning of the source language words of the source language text as they occur in context,

means for entering said text into the analysis module;

means for matching the source language words against source language sides of a set of bilingual equivalence statements provided within a bilingual dictionary of the system, the bilingual equivalence statements being rules that a word or words on a source language side corresponds to or translates as a word or words in a target language side,

means for collecting target language words obtained as a result of said matching performed by said matching means,

generation module means included in said system for combining target word information collected by said means for collecting to construct one or more candidate target language texts corresponding to the source language text and the deduced source word information, and

characterized in that the generation module means is split into first and second separate functional components, the first of which is dedicated to the processing of information which is independent of the eventual order of words in the target language text and the details of associations between the component parts of the target language words, and the second of which is dedicated to the construction of structures which respect constraints of word order, associations between the words of the target language text and the deduced source word information, and wherein the first functional component verifies that the constructed structures are part of a global structure which incorporates all the target language words introduced during the matching via the bilingual equivalence statements, and in that the second component communicates with the first component in order to synchronize the construction and verification of the structures.

2. A machine translation system according to claim 1, further characterised in that the first component is operable to implement a constraint propagation algorithm to assist in the direction of the operation of the second functional component by communicating to the second functional component a failed constructed structure, thereby ensuring that the failed constructed structure not be constructed again and eliminating a portion of a structure construction space that cannot lead to a solution.

3. A machine translation system according to claim 1, further characterised in that the first component uses standard graph algorithms to test for the existence of spanning trees containing one or more edges proposed by the second component, failing when no such spanning tree can be constructed and communicating to the second functional component a failed edge proposal, thereby ensuring that the failed edge proposal will not be proposed again and eliminating a portion of a spanning tree edge proposal space that cannot lead to a solution.

4. A method for translating from a source language to a target language, comprising:

(A) reading a text of said source language;

(B) entering said source language text into an analysis module;

(C) processing said source language text with the analysis module by drawing on information from at least one of source language grammars and dictionaries to deduce source word information about the usage and meaning of the words of said source language text as they occur in context;

(D) matching the source language words against source language sides of a set of bilingual equivalence statements provided within a bilingual dictionary, the bilingual equivalence statements being rules that a word or words on a source language side corresponds to or translates as a word or words in a target language side;

(E) collecting target language words obtained as a result of said matching procedure;

(F) combining target word information collected in (E) by way of a generation module to construct one or more target language texts corresponding to said source language text and the deduced source word information, said generation module having first and second functional components;

(G) processing information which is independent of the eventual order of words in said target language text or on the details of associations between the component parts of the target language words in said first functional component;

(H) constructing structures which respect constraints of word order and associations between the words of the target language text in said second functional component;

(I) verifying that the constructed structures are part of a global structure which incorporates all the target language words during matching via the bilingual equivalence statements in said first functional component; and

(J) synchronizing the first and second components in the steps (G), (H) and (I) to construct said one or more target language texts corresponding to said source language text.

5. A method according to claim 4 further comprising implementing a constraint propagation algorithm in said first functional component for assisting in the direction of the operation of said second functional component by communicating to the second functional component a failed constructed structure, thereby ensuring that the failed constructed structure not be constructed again and eliminating a portion of a structure construction space that cannot lead to a solution.

6. A method according to claim 4 further comprising using standard graph algorithms in said first functional component to test for the existence of spanning trees containing one or more edges proposed by said second functional component, and failing when no such spanning tree can be constructed and communicating to the second functional component a failed edge proposal, thereby ensuring that the failed edge proposal will not be proposed again and eliminating a portion of a spanning tree edge proposal space that cannot lead to a solution.