Generating with lexical functional grammars

• US 20030163301A1
• Filed: 09/27/2002
• Published: 08/28/2003
• Est. Priority Date: 02/20/2002
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Maxwell, John T. III, Shemtov, Hadar
• Granted Patent: US 7,225,121 B2
• Time in Patent Office: Days
• US Class Current: 704/9
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking

Abstract

A process for generating with unification based grammars such as Lexical Functional Grammars which uses construction and analysis of generation guides to determine internal facts and eliminate incomplete edges prior to constructing a generation chart. The generation guide can then be used in the construction of the generation chart to efficiently generate with unification-based grammars such as Lexical Functional Grammars. The generation guide is an instance of a grammar that has been specialized to the input and only contains those parts of the grammar that are relevant to the input. When the generation guide is analyzed to determine internal facts a smaller generation chart is produced.

Claims

1. ) A computer controlled method for constructing a generation chart having a plurality of chart edges comprising steps of:

a) receiving a grammar and one or more facts wherein the grammar contains category information and wherein each of the one or more facts contains at least one identifier;

b) constructing a generation guide having a plurality of guide edges wherein at least one of the plurality of guide edges is indexed by the category information and at least one identifier, and has an associated set of facts;

c) detecting a set of internal facts for at least one of the plurality of guide edges wherein the set of internal facts is a subset of the associated set of facts; and

d) selecting the plurality of chart edges responsive to the set of internal facts of the plurality of guide edges.

2. ) The computer controlled method of claim 1 further comprising constructing a generation chart from the plurality of selected chart edges.

3. ) The computer controlled method of claim 1 wherein at least one of the plurality of chart edges corresponds to a guide edge from the plurality of guide edges and a chart edge is selected only if it contains all of the set of internal facts of its corresponding guide edge.

4. ) The computer controlled method of claim 3 wherein the corresponding chart edge and guide edge each have the same category information and at least one identifier is the same.

5. ) The computer controlled method of claim 3 wherein the corresponding chart edge and guide edge each have the same category information and semantic identifiers.

6. ) The computer controlled method of claim 3 wherein the step of detecting a set of internal facts for a given guide edge comprises selecting a fact from the associated set of facts as an internal fact if the fact is obligatory to the given guide edge.

7. ) The computer controlled method of claim 3 wherein the step of detecting a set of internal facts for a given guide edge comprises:

a) determining a first subset of the associated set of facts containing external facts; and

b) selecting a second subset of the associated set of facts a subset which contains the facts not determined to be external facts as the set of internal facts.

8. ) The computer controlled method of claim 3 wherein the step of detecting a set of internal facts for a given guide edge comprises:

a) determining a first subset of the associated set of facts containing external facts; and

b) removing the first subset from the associated set of facts to create a second subset of the associated set of facts as the set of internal facts.

9. ) The computer controlled method of claim 3 wherein the step of detecting a set of internal facts for a given guide edge comprises:

a) determining a first subset of the associated set of facts containing external facts;

b) selecting a second subset of the associated set of facts containing the facts not determined to be external facts;

c) selecting a third subset of the associated set of facts containing the facts obligatory to the given guide edge; and

d) constructing the union of the second subset and the third subset to form the set of internal facts.

10. ) The computer controlled method of claim 3 wherein the step of detecting a set of internal facts for at least one of the plurality of guide edges comprises selecting a given fact as an internal fact if the given fact is dependent on an obligatory parent fact of the given fact, and the obligatory parent fact is obligatory on a daughter of the guide edge, and the obligatory parent fact is optional on the guide edge.

11. ) The computer controlled method of claim 10 wherein a fact is an obligatory parent fact of a given fact if the fact is associated with every parent path of every edge in which the given fact occurs.

12. ) A computer controlled method for constructing a generation chart having a plurality of chart edges comprising the steps of:

a) receiving a grammar and one or more facts wherein the grammar contains category information and each of the one or more facts contains at least one identifier;

b) constructing a generation guide having plurality of guide edges, wherein at least one guide edge has at least one fact associated therewith;

c) determining which facts are an obligatory parent fact for at least one fact to form a set of obligatory parent facts;

d) selecting a given fact as an internal fact to form a set of internal facts if the given fact is dependent on an obligatory parent fact of the given fact, and the obligatory parent fact is obligatory on a daughter of the guide edge, and the obligatory parent fact is optional on the guide edge;

e) selecting the plurality of chart edges responsive to the set of internal facts.

13. ) The computer controlled method of claim 12 further comprising constructing a generation chart from the plurality of selected chart edges.

14. ) An apparatus having a central processing unit (CPU) and a memory coupled to said CPU for constructing a generation chart having a plurality of chart edges comprising:

a) an input module configured to receive a grammar and one or more facts wherein the grammar contains category information and wherein each of the one or more facts contains at least one identifier;

b) a guide generator responsive to the input module configured to construct a generation guide having a plurality of guide edges wherein at least one of the plurality of guide edges is indexed by the category information and at least one identifier, and has an associated set of facts;

c) a detector responsive to the guide generator configured to detect a set of internal facts for at least one of the plurality of guide edges wherein the set of internal facts is a subset of the associated set of facts; and

d) an edge selector responsive to the detector configured to select the plurality of chart edges responsive to the set of internal facts of the plurality of guide edges.

15. ) The apparatus of claim 14 further comprising a chart generator for constructing a generation chart from the plurality of selected chart edges.

16. ) The apparatus of claim 14 wherein at least one of the plurality of chart edges corresponds to a guide edge from the plurality of guide edges and a chart edge is selected only if it contains all of the set of internal facts of its corresponding guide edge.

17. ) The apparatus of claim 16 wherein the corresponding chart edge and guide edge each have the same category information and at least one identifier is the same.

18. ) The apparatus of claim 16 wherein the corresponding chart edge and guide edge each have the same category information and semantic identifiers.

19. ) The apparatus of claim 16 wherein the detector comprises a fact selector for selecting a fact from the associated set of facts as an internal fact if the fact is obligatory to the given guide edge.

20. ) The apparatus of claim 16 wherein the detector comprises:

a) an external fact selector for selecting a first subset of the associated set of facts containing external facts; and

b) an internal fact selector for selecting a second subset of the associated set of facts which contains the facts not determined to be external facts as the set of internal facts.

21. ) The apparatus of claim 16 wherein the detector comprises:

a) an external fact selector for selecting a first subset of the associated set of facts containing external facts; and

b) an internal fact selector for removing the first subset from the associated set of facts to create a second subset of the associated set of facts as the set of internal facts.

22. ) The apparatus of claim 16 wherein the detector comprises:

a) an external fact selector for determining a first subset of the associated set of facts containing external facts and selecting a second subset of the associated set of facts containing the facts not determined to be external facts;

c) an obligatory fact selector for selecting a third subset of the associated set of facts containing the facts obligatory to the given guide edge; and

d) an internal fact selector for constructing the union of the second subset and the third subset to form the set of internal facts.

23. ) The apparatus of claim 16 wherein the detector comprises a selector for selecting a given fact as an internal fact if the given fact is dependent on an obligatory parent fact of the given fact, and the obligatory parent fact is obligatory on a daughter of the guide edge, and the obligatory parent fact is optional on the guide edge.

24. ) The apparatus of claim 23 wherein a fact is an obligatory parent fact of a given fact if the fact is associated with every parent path of every edge in which the given fact occurs.

25. ) An apparatus having a central processing unit (CPU) and a memory coupled to said CPU for constructing a generation chart having a plurality of chart edges comprising:

a) an input module for receiving a grammar and one or more facts wherein the grammar contains category information and each of the one or more facts contains at least one identifier;

b) a guide generator responsive to the input module for constructing a generation guide having plurality of guide edges, wherein at least one guide edge has at least one fact associated therewith;

c) a detector responsive to the guide generator for determining which facts are an obligatory parent fact for at least one guide edge to form a set of obligatory parent facts;

d) a fact selector responsive to the detector for selecting facts as an internal fact for at least one one of the plurality of chart edges from the set of obligatory parent facts for at least one guide edge to form a set of internal facts;

e) a chart edge selector responsive to the fact selector for selecting the plurality of chart edges responsive to the set of internal facts.

26. ) The apparatus of claim 25 further comprising a chart generator for constructing a generation chart from the plurality of selected chart edges.

27. ) A computer program product comprising:

a computer usable storage medium having computer readable code embodied therein for causing a computer to construct a generation chart having a plurality of chart edges, the computer readable code comprising;

a) computer readable program code configured to cause the computer to effect an input module configured to receive a grammar and one or more facts wherein the grammar contains category information and wherein each of the one or more facts contains at least one identifier;

b) computer readable program code configured to cause the computer to effect a guide generator responsive to the input module configured to construct a generation guide having a plurality of guide edges wherein at least one of the plurality of guide edges is indexed by the category information and at least one identifier, and has an associated set of facts;

c) computer readable program code configured to cause the computer to effect a detector responsive to the guide generator configured to detect a set of internal facts for at least one of the plurality of guide edges wherein the set of internal facts is a subset of the associated set of facts; and

d) computer readable program code configured to cause the computer to effect an edge selector responsive to the detector configured to select the plurality of chart edges responsive to the set of internal facts of the plurality of guide edges.

28. ) The computer program product of claim 27 further comprising computer readable program code configured to cause the computer to effect a chart generator for constructing a generation chart from the plurality of selected chart edges.

29. ) The computer program product of claim 27 wherein at least one of the plurality of chart edges corresponds to a guide edge from the plurality of guide edges and a chart edge is selected only if it contains all of the set of internal facts of its corresponding guide edge.

30. ) The computer program product of claim 29 wherein the corresponding chart edge and guide edge each have the same category information and at least one identifier is the same.

31. ) The computer program product of claim 29 wherein the corresponding chart edge and guide edge each have the same category information and semantic identifiers.

32. ) The computer program product of claim 29 wherein the computer readable program code configured to cause the computer to effect a detector comprises a fact selector for selecting a fact from the associated set of facts as an internal fact if the fact is obligatory to the given guide edge.

33. ) The computer program product of claim 29 wherein the computer readable program code configured to cause the computer to effect a detector comprises:

a) computer readable program code configured to cause the computer to effect an external fact selector for selecting a first subset of the associated set of facts containing external facts; and

b) computer readable program code configured to cause the computer to effect an internal fact selector for selecting a second subset of the associated set of facts which contains the facts not determined to be external facts as the set of internal facts.

34. ) The computer program product of claim 29 wherein the computer readable program code configured to cause the computer to effect detector comprises:

a) computer readable program code configured to cause the computer to effect an external fact selector for selecting a first subset of the associated set of facts containing external facts; and

b) computer readable program code configured to cause the computer to effect an internal fact selector for removing the first subset from the associated set of facts to create a second subset of the associated set of facts as the set of internal facts.

35. ) The computer program product of claim 29 wherein the computer readable program code configured to cause the computer to effect detector comprises:

a) computer readable program code configured to cause the computer to effect an external fact selector for determining a first subset of the associated set of facts containing external facts and selecting a second subset of the associated set of facts containing the facts not determined to be external facts;

c) computer readable program code configured to cause the computer to effect an obligatory fact selector for selecting a third subset of the associated set of facts containing the facts obligatory to the given guide edge; and

d) computer readable program code configured to cause the computer to effect an internal fact selector for constructing the union of the second subset and the third subset to form the set of internal facts.

36. ) The computer program product of claim 29 wherein the computer readable program code configured to cause the computer to effect detector comprises computer readable program code configured to cause the computer to effect a selector for selecting a given fact as an internal fact if the given fact is dependent on an obligatory parent fact of the given fact, and the obligatory parent fact is obligatory on a daughter of the guide edge, and the obligatory parent fact is optional on the guide edge.

37. ) The computer program product of claim 36 wherein a fact is an obligatory parent fact of a given fact if the fact is associated with every parent path of every edge in which the given fact occurs.

38. ) A computer program product comprising:

a computer usable storage medium having computer readable program code embodied therein for causing a computer to construct a generation chart having a plurality of chart edges comprising;

a) computer readable program code configured to cause the computer to effect an input module for receiving a grammar and one or more facts wherein the grammar contains category information and each of the one or more facts contains at least one identifier;

b) computer readable program code configured to cause the computer to effect a guide generator responsive to the input module for constructing a generation guide having plurality of guide edges, wherein at least one guide edge has at least one fact associated therewith;

c) computer readable program code configured to cause the computer to effect a detector responsive to the guide generator for determining which facts are an obligatory parent fact for at least one guide edge to form a set of obligatory parent facts;

d) computer readable program code configured to cause the computer to effect a fact selector responsive to the detector for selecting facts as an internal fact for at least one one of the plurality of chart edges from the set of obligatory parent facts for at least one guide edge to form a set of internal facts;

e) computer readable program code configured to cause the computer to effect a chart edge selector responsive to the fact selector for selecting the plurality of chart edges responsive to the set of internal facts.

39. ) The computer program product of claim 38 further comprising computer readable program code configured to cause the computer to effect a chart generator for constructing a generation chart from the plurality of selected chart edges.

40. ) A computer program product comprising:

a computer data signal embodied in a carrier wave having computer readable code embodied therein for causing a computer to construct a generation chart having a plurality of chart edges, the computer readable code comprising;

a) computer readable program code configured to cause the computer to effect an input module configured to receive a grammar and one or more facts wherein the grammar contains category information and wherein each of the one or more facts contains at least one identifier;

b) computer readable program code configured to cause the computer to effect a guide generator responsive to the input module configured to construct a generation guide having a plurality of guide edges wherein at least one of the plurality of guide edges is indexed by the category information and at least one identifier, and has an associated set of facts;

c) computer readable program code configured to cause the computer to effect a detector responsive to the guide generator configured to detect a set of internal facts for at least one of the plurality of guide edges wherein the set of internal facts is a subset of the associated set of facts; and

d) computer readable program code configured to cause the computer to effect an edge selector responsive to the detector configured to select the plurality of chart edges responsive to the set of internal facts of the plurality of guide edges.

41. ) The computer program product of claim 40 further comprising computer readable program code configured to cause the computer to effect a chart generator for constructing a generation chart from the plurality of selected chart edges.