Apparatus and method for generating processor usable data from natural language input data

• US 6,505,157 B1
• Filed: 02/23/2000
• Issued: 01/07/2003
• Est. Priority Date: 03/01/1999
• Status: Expired due to Fees

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Elworthy, David
• Primary Examiner(s): Banks-Harold, Marsha D.
• Assistant Examiner(s): MCFADDEN, SUSAN IRIS
• Application Number:
  US09/511,385
• Time in Patent Office: 1,049 Days
• Field of Search: 704/1, 704/2, 704/9, 704/10, 704/255, 704/256, 704/257
• US Class Current: 704/257
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates

Abstract

Apparatus generates data in processor usable form from natural language input data units in different unit categories. Input data categorized into categories generates data units having unit identification data and corresponding unit category data for input to a cascaded plurality of matching processing stages. Each matching processing stage of this cascade except the first uses any unmatched unit category data and group category data from previous matching processing stages in place of matched category data to match the unit and/or group category data with at least one predetermined pattern of unit and/or group category data. New group category data is output for any unit and/or group category matching each predetermined pattern of unit and/or group category data. At least one of the matching processing stages outputs unit data corresponding to matched unit category data as a plurality of variables. At least one of these variables is indexed by another of the variables.

Claims

1. Processing apparatus for generating data in a processor usable form from input data in the form of units in a natural language in which the units are of a plurality of different categories, the processing apparatus comprising:

data unit generating means for categorizing units of input data into respective categories to generate processor usable data units comprising unit data and corresponding unit category data, said data units comprising one of a group consisting of words, lexical units and semantic units and said unit category data comprising one of a group consisting of parts of speech, words and lexical features; and

a cascaded plurality of finite state matching means, each of said finite state matching means being configured in accordance with grammar rules for the natural language, a first of said cascaded plurality of finite state matching means being operable to match said unit category data with at least one predetermined pattern of unit category data and to output group category data for any said unit category data found to match said at least one predetermined pattern of unit category data, the or each other said finite state matching means of the cascade being operable to use any unmatched unit category data and said group category data from at least one previous said finite state matching means of the cascade in place of matched category data to match said unit and/or group category data with at least one predetermined pattern of unit and/or group category data and to output new group category data for any unit and/or group category data found to match said at least one predetermined pattern of unit and/or category data;

wherein at least one of said finite state matching means is operable to output said unit data corresponding to matched unit category data as a plurality of variables, at least one said variable being indexed by another said variable.

2. Processing apparatus according to claim 1, wherein at least one of said finite state matching means is operable to index the indexed variables by variables output from a previous said finite state matching means in the cascade.

3. Processing apparatus according to claim 1, wherein said finite state matching means are deterministic.

4. Processing apparatus according to claim 1, wherein said finite state matching means are configured to output said variables when said finite state matching means transit from one state to another, each transition corresponding to a matching of unit or group category data from the input data with unit or group category data in a said pattern.

5. Processing apparatus according to claim 1, and wherein said at least one finite state matching means is adapted to output said unit data as variables defining head units and modifier units of segments of the data units, the or each corresponding indexed variable defining a unit data of a modifier unit.

6. Processing apparatus according to claim 1, wherein said at least one finite state matching means is adapted to output one or more said indexed variable with an index comprising the unit data of a unit of data being modified.

7. Processing apparatus according to claim 5, wherein said at least one finite state matching means is adapted to output said variables as a plurality of different variables, each variable defining a different syntactic modification.

8. Processing apparatus according to claim 1, wherein at least one of said finite state matching means is operable to index the indexed variables by variables output from said finite state matching means.

9. Processing apparatus according to claim 1, wherein said group category data defines syntactic structures in the input data.

10. Processing apparatus according to claim 1, wherein said data units comprise one of a group consisting of words, lexical units and semantic units.

11. Processing apparatus according to claim 1, wherein said finite state matching means are adapted to output non indexed variables for said input data and then output said indexed variables for said input data.

12. Processing apparatus according to claim 1, wherein said finite state matching means are adapted to store said variables and instructions for indexing said indexed variables for said input data, and to subsequently implement said instructions to index said indexed variables.

13. Processing apparatus according to claim 1, wherein said data unit generating means includes a lexicon containing lexical units and corresponding parts of speech data, and a lexical processor for receiving said input data in the form of text words, matching the text words with lexical units, outputting the matched lexical units as said unit data, and outputting said corresponding parts of speech data as said unit category data.

14. Processing apparatus according to claim 13, including means for correcting any incorrectly assigned parts of speech data by a statistical context analysis.

15. Control apparatus for controlling the operation of a system, the control apparatus comprising:

the processing apparatus according to claim 1;

comparing means for comparing said variables generated from said input data with variables generated from reference data by comparing variables starting from a variable indicated to be the head of said input data or reference data which does not modify any others of said input data or reference data in accordance with relationships defining equivalence between said variables; and

control means for controlling the operation of a system in accordance with the result of the comparison.

16. A processor implemented method of generating data in processor usable form from input data in the form of units in a natural language in which the units are of a plurality of different categories, the method comprising:

categorizing units of input data into respective categories to generate processor usable data units comprising unit data and corresponding unit category data, said data units comprising one of a group consisting of words, lexical units and semantic units and said unit category data consisting of parts of speech, words and lexical features;

a first matching step of using a cascaded plurality of finite state matching means to match said unit category data with at least one predetermined pattern of unit category data and to output group category data for any said unit category data found to match said at least one predetermined pattern of unit category data, each of said finite state matching means being configured in accordance with grammar rules for the natural language;

at least one further matching step using a finite state matching means of using any unmatched said unit category data and said group category data from at least one previous matching step in place of matched category data to match said unit and/or group category data with at least one predetermined pattern of unit and/or group category data, and outputting new group category data for any unit and/or group category data found to match said at least one predetermined pattern of unit and/or category data;

wherein at least one of said matching step outputs said unit data corresponding to matched unit category data as a plurality of variables, and at least one said variable is indexed by another said variable.

17. A method according to claim 16, wherein said finite state matching means are deterministic.

18. A method according to claim 16, wherein said finite state matching means output said variables when said finite state machines transit from one state to another, each transition corresponding to a matching of unit or group category data from the input data with unit or group category data in a said pattern.

19. A method according to claim 16, wherein said unit data is output as said variables defining head units and modifier units of segments of the data units, the or each indexed variable defining a unit data of a corresponding modifier unit.

20. A method according to claim 19, wherein at least one said matching step outputs one or more said indexed variable with an index comprising the unit data of a unit of data being modified.

21. A method according to claim 16, wherein said at least one further matching step outputs said variables as a plurality of different variables, each variable defining a different syntactic modification.

22. A method according to claim 16, wherein in at least one of said matching steps the indexed variables are indexed by variables output from the matching step.

23. A method according to claim 16, wherein in at least one of said matching steps the indexed variables are indexed by variables output from a previous matching step.

24. A method according to claim 16, wherein said unit category data comprises one of a group consisting of parts of speech, words, and lexical units.

25. A method according to claim 16, wherein said group category data defines syntactic structures in the input data.

26. A method according to claim 16, wherein said data units comprise one of a group consisting of words, lexical units and semantic units.

27. A method according to claim 16, wherein the matching steps output non indexed variables for said input data and then repeat to output indexed variables for said input data.

28. A method according to claim 16, wherein the matching steps store said variables and instructions for indexing said indexed variables for said input data, and said instructions are subsequently executed to index said indexed variables.

29. A method according to claim 16, wherein said data units are generated by receiving said input data as text words, looking up said text words in a lexicon containing lexical units and corresponding parts of speech to output matched lexical units as said unit data and corresponding parts of speech data as said unit category data.

30. A method according to claim 29 including the step of correcting any incorrectly assigned parts of speech by a statistical context analysis.

31. A method of controlling a system comprising the method of claim 16;

comparing said variables generated from said input data with variables generated from reference data by comparing variables starting from a variable indicated to be the head of said input data or reference data which does not modify any others of said input data or reference data respectively, in accordance with relationships defining equivalence between said variables; and

controlling the operation of a system in accordance with the result of the comparison.

32. A carrier medium carrying processor implementing instructions for controlling a processor to carry out the method according to claim 16.

33. A signal carrying processor implementing instructions for controlling a processor to carry out the method according to claim 16.