Tree transformation system in machine translation system

• US 4,599,691 A
• Filed: 05/13/1983
• Issued: 07/08/1986
• Est. Priority Date: 05/20/1982
• Status: Expired due to Term

• Current Assignee: Kokusai Denshi Denwa Company Limited (KDDI Corporation)
• Original Assignee: Kokusai Denshi Denwa Company Limited (KDDI Corporation)
• Inventors: Hashimoto, Kazuo, Sakaki, Hiroshi
• Primary Examiner(s): Smith, Jerry
• Assistant Examiner(s): Jablon, Clark A.
• Application Number:
  US06/494,361
• Time in Patent Office: 1,152 Days
• Field of Search: 434/157, 364/419, 364/900 MS File
• US Class Current: 704/2
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06F 40/55 Rule-based translation

Abstract

A mechanical translation system is provided to obtain a sentence of target language from the tree expression of source language. The processing progresses as follows: First, a pattern which coincides with partial structure, including the highest node, of the tree fragment chosen, is selected among patterns previously contained in the pattern dictionary. The pattern has a production rule attached to the pattern. The production rule takes "extraction information" which is composed of information in the source language tree fragment concerning the part outside of and under the above mentioned partial structure and "instruction information" which is attached to the highest node of the tree fragment, as input information and generates a tree fragment in target language corresponding to the source language tree fragment and also "instruction information" to be attached to the border nodes of the partial structure and other parts in the source language tree fragment which consists of memorizing the target language tree fragment and erasing the partial structure from the source language tree fragment and bringing back to the memory to contain target language tree fragments, thus produced normally plural "child" tree fragments. After processing a plurality of target language tree fragments contained in the corresponding memory and uniting them into a single tree producing the tree of target language tree, from which the sentence in target language is obtained immediately.

Claims

1. A machine translation system (FIG. 7) which generates sentences in target language using tree structure expression in source language comprising;

a pattern dictionary (PTD, FIG.

     7) for storing a table of target language and source language,

means (PPD, FIG.

     7) having at least a first shift register (PPA) having source tree patterns from said pattern dictionary, a second shift register (PPB) having source tree which is to be translated, a coincidence detector (CSD) for comparing outputs of said first (PPA) and second (PPB) shift registers;

for providing coincident pattern of patterns contained in the pattern dictionary and partial pattern of tree structure in source language including the topmost mode of said tree structure;

means (SDS, FIG.

     7) for producing a pattern in said target language and an instruction to lower layer utilizing the information of information from instruction from upper layer, extraction information (EXG, FIG.

     7), and production rule (stored in PRT, FIG.

     7) peculiar to said coincident pattern;

means (INA, MPE, FIG.

     7) having a first shift register (AAA) storing said instruction to lower layer, a second shift register (AAB) storing said tree structure, AND-OR logic means for coupling the output of said first shift register (AAA) to the output of said second shift register (AAB) to eliminate said coincident pattern;

means (SPC, FIG.

     7) having a first shift register (UAA) storing separated partial target trees, a second arithmetic register (UAB) for performing operation to signal in said first shift register (UAA), and a third shift register (UAC) for storing the output of said second register (UAB), so as to produce a final target language tree which is connected to the result of said partial target tree through repeating said means (SPC) until the whole of said tree structure is eliminated; and

means (SPL, FIG.

     7) for receiving the output of said SPC means and generating final sentence in target language.