Language processing method and apparatus

• US 5,943,643 A
• Filed: 12/01/1995
• Issued: 08/24/1999
• Est. Priority Date: 04/13/1995
• Status: Expired due to Term

• Current Assignee: Canon Ayutthaya Limited (Canon Inc.)
• Original Assignee: Canon Ayutthaya Limited (Canon Inc.)
• Inventors: Van De Veen, Evelyn
• Primary Examiner(s): Isen, Forester W.
• Assistant Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US08/566,170
• Time in Patent Office: 1,362 Days
• Field of Search: 704/1, 704/2, 704/4, 704/7, 704/9
• 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/253 Grammatical analysis; Style critique
• 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 data processing apparatus for generating from a plurality of data units corresponding to a string of elements of a first language, a string of elements of a second language representative of the meaning of the string of elements of the first language. Each data unit is indicative of the meaning of a corresponding element of the first language and includes one or more identifiers related to one or more identifiers of one or more other data units. The generator includes an instructor for storing processing instructions dependent on grammatical rules of the second language, and a processor for providing the elements of the second language in dependence upon the meaning indicated by the data units. The processor also orders the elements in the string of elements in the second language in dependence upon the meaning indicated by the data units, upon the related identifiers and upon the instructions stored in the instructor.

Claims

1. Data processing apparatus for generating, from a plurality of data units corresponding to a string of elements of a first language, a string of elements of a second language representative of the meaning of the string of elements of the first language, each data unit being indicative of the meaning of a corresponding element of the first language and including one or more identifiers related to one or more identifiers of one or more other said data units, said apparatus comprising:

(a) instruction means for storing processing instructions dependent on grammatical rules of the second language; and

(b) processing means for providing said elements of said second language in dependence upon the meaning indicated by said data units and for ordering said elements in said string of elements in said second language in dependence upon said meaning indicated by said data units, upon said related identifiers and upon said instructions stored in said instruction means.

2. Apparatus according to claim 1, wherein said data units comprise predicates and arguments, said arguments being used for said identifiers.

3. Apparatus according to claim 2, wherein a said identifer of one said data unit is related to a said identifier of another said data unit by assigning a common value to said related identifiers.

4. Apparatus according to claim 1, in combination with input means for receiving a natural language input and parser means for deriving said data units from said natural language input.

5. Apparatus according to claim 4, arranged for translating from a first natural language to a second natural language.

6. Apparatus according to claim 1, in combination with means for deriving said data units from a data source without the intervening step of generating said string of elements of said first language.

7. Apparatus according to claim 1 wherein said processing means is operable to create for at least some of said data units respective nodes containing selected search codes dependent upon the lexical category of the element of the second language corresponding to the data unit, to perform a search of said nodes utilising said search codes and said related identifiers and to order said elements of said second language in dependence upon the results of said search.

8. Apparatus according to claim 7, wherein one argument is selected for each of said data units in dependence upon the search code for which the search has succeeded.

9. Apparatus according to claim 7, wherein said instructions prescribe the order of said elements corresponding to one said data unit and another said data unit related to said search code in dependence upon the search code.

10. Apparatus according to claim 7, wherein the search is performed in reverse order starting from the last node.

11. Apparatus according to claim 7, wherein the search is terminated upon finding the first occurrence for each search code.

12. Apparatus according to claim 7, wherein said processing means is operable to store search codes for a future search with respective arguments in a search space.

13. Apparatus according to claim 7, wherein said processing means is operable to remove search codes from said search space in dependence upon the lexical category of the element of the second language.

14. A data processing method for generating, from a plurality of data units corresponding to a string of elements of a first language, a string of elements of a second language representative of the meaning of the string of elements of the first language, each data unit being indicative of the meaning of a corresponding element of the first language and including one or more identifiers related to one or more identifiers of one or more other said data units, said method comprising the steps of:

(a) storing processing instructions dependent on grammatical rules of the second language; and

(b) providing said elements of said second language in dependence upon the meaning indicated by said data units and ordering said elements in said string of elements in said second language in dependence upon said meaning indicated by said data units, upon said related identifiers, and upon said instructions stored in said storing step.

15. A method according to claim 14, wherein said data units comprise predicates and arguments, said arguments being used for said identifiers.

16. A method according to claim 15, wherein a said identifer of one said data unit is related to a said identifier of another said data unit by assigning a common value to said related identifiers.

17. A method according to claim 14, further comprising the steps of receiving a natural language input and parsing to derive said data units from said natural language input.

18. A method according to claim 17, for translating from a first natural language to a second natural language.

19. A method according to claim 14, further comprising the step of deriving said data units from a data source without the intervening step of generating said string of elements of said first language.

20. A method according to claim 14 wherein said processing step includes the step of creating for at least some of said data units respective nodes containing selected search codes dependent upon the lexical category of the element of the second language corresponding to the data unit, performing a search of said nodes utilising said search codes and said related identifiers and to order said elements of said second language in dependence upon the results of said search.

21. A method according to claim 20, wherein one argument is selected for each of said data units in dependence upon the search code for which the search has succeeded.

22. A method according to claim 20, wherein said instructions prescribe the order of said elements corresponding to one said data unit and another said data unit related to said search code in dependence upon the search code.

23. A method according to claim 20, wherein the search is performed in reverse order starting from the last node.

24. A method according to claim 20, wherein the search is terminated upon finding the first occurrence for each search code.

25. A method according to claim 20, wherein said search codes for a future search are stored with respective arguments in a search space.

26. A method according to claim 14, wherein said search codes are removed from said search space in dependence upon the lexical category of the element of the second language.

27. A storage medium or device having stored therein a computer program comprising instructions for the performance of the data processing method of claim 14.