Generating with Lexical Functional Grammars

• US 7,225,121 B2
• Filed: 09/27/2002
• Issued: 05/29/2007
• Est. Priority Date: 02/20/2002
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Maxwell, John T. III, Shemtov, Hadar
• Primary Examiner(s): {hacek over (S)}mits; Talivaldis Ivars
• Assistant Examiner(s): Pierre; Myriam
• Application Number:
  US10/260,652
• Publication Number:
  US 20030163301A1
• Time in Patent Office: 1,705 Days
• Field of Search: 704/9, 715/514
• 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 into a memory 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 in the memory 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 in the memory 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 from the memory responsive to the set of internal facts of the plurality of guide edges; and

e) generating strings of words based on the selected plurality of chart 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 Wit 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 into a memory 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 in the memory, wherein at least one guide edge has at least one fact associated therewith;

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

d) selecting a given fact in the memory 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 from the memory responsive to the set of internal facts; and

f) generating strings of words based on selected plurality of chart edges.

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;

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 and generating strings words based on the selected plurality of chart edges.

15. The apparatus of claim 14 farther 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 a 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 and generating strings of words based on the selected plurality of chart edges.

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 in a computer readable 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 in a computer readable 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 bas 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. An article of manufacture for constructing a generation chart having a plurality of chart edges, the article of manufacture comprising computer readable media including computer readable instructions embedded therein that causes a computer to perform a method, wherein the method comprises:

a) receiving a grammar and one or more facts into a memory 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 in the memory 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 in the memory 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 from the memory responsive to the set of internal facts of the plurality of guide edges.

41. The article of claim 40 further comprising the step of:

constructing a generation chart from the plurality of selected chart edges.