Method, device and system for generalized bidirectional island-driven chart parsing

• US 6,128,596 A
• Filed: 04/03/1998
• Issued: 10/03/2000
• Est. Priority Date: 04/03/1998
• Status: Expired due to Fees

• Current Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Mackie, Andrew William
• Primary Examiner(s): Hudspeth, David R.
• Assistant Examiner(s): ABEBE, DANIEL DEMELASH
• Application Number:
  US09/054,601
• Time in Patent Office: 914 Days
• Field of Search: 704/257, 704/256, 704/259, 704/9, 704/10
• US Class Current: 704/257
• CPC Class Codes: G10L 15/04 Segmentation; Word boundary detection
• CPC Class Codes: G10L 15/18 using natural language modelling

Abstract

A method (700), device (1101), and system (1100) provide generalized bidirectional island-driven chart parsing based on congruency checking to prevent edge overgeneration for robust and efficient parsing of a word graph. The method prevents edge overgeneration by selecting, in accordance with a predetermined scheme, a candidate edge with a starting vertex, an ending vertex, a label, and a congruence key for entry in a chart from an agenda of edges, selecting an edge equivalence set in the chart that matches the starting vertex, the ending vertex, and the label of the candidate edge, and entering the candidate edge into the chart if the congruence key of the candidate edge fails to match the congruence key of any edge in the edge equivalence set.

Claims

1. A method for processing natural language using generalized bidirectional island-driven chart parsing based on congruency checking to prevent edge overgeneration, comprising the steps of:

A) selecting, in accordance with a predetermined scheme, a candidate edge with a starting vertex, an ending vertex, a label, and a congruence key for determining edge congruency, wherein edge congruency exists when a plurality of equal edges dominate at least one identical tree, for entry in a chart from an agenda of edges;

B) selecting an edge equivalence set in the chart that match the starting vertex, the ending vertex, and the label of the candidate edge; and

C) entering the candidate edge into the chart if the congruence key of the candidate edge fails to match the congruence key of any edge in the edge equivalence set.

2. The method of claim 1 wherein Step C comprises the steps of:

A) determining if the congruence key of the candidate edge fails to match the congruence key of any edge in the edge equivalence set;

B) constructing a generated edge set corresponding to the candidate edge if the congruence key of the candidate edge fails to match the congruence key of any edge in the edge equivalence set; and

C) entering the candidate edge into the chart and the generated edge set into the agenda if the congruence key of the candidate edge fails to match the congruence key of any edge in the edge equivalence set.

3. The method of claim 2 wherein Step C comprises the steps of:

A) constructing the generated edge set according to a current state of the chart if the candidate edge is active; and

B) constructing the generated edge set according to the current state of the chart and relevant productions in grammar if the candidate edge is complete.

4. The method of claim 3 further including, for each extension edge constructed from an active edge and a complete edge, encoding of a congruence key by vector concatenation of the congruence key of the active edge and the congruence key of the complete edge.

5. The method of claim 3, Step B, further including, for each lexical edge constructed from an arc, labeled with a word, in a word graph, encoding of the congruence key from the starting vertex of the lexical edge, the ending vertex of the lexical edge, and a unique number identifying the word.

6. The method of claim 3, Step B, further including, for each production edge constructed from a complete edge and a production, encoding of a congruence key from the starting vertex of the production edge, the ending vertex of the production edge, and a unique number identifying the production.

7. The method of claim 2, Step A, where comparing the congruence key for an edge E₁ with the congruence key for an edge E₂ is accomplished by a pairwise comparison of a vector V₁ encoding the congruence key for the edge E₁ with a vector V₂ encoding the congruence key for the edge E₂ .

8. The method of claim 7 further including, prior to the pairwise comparison of the vector V₁ encoding the congruence key for the edge E₁ with the vector V₂ encoding the congruence key for the edge E₂, performing a threshold test comprising the steps of:

A) determining a length L₁ of the vector V₁ encoding the congruence key for the edge E₁ and a length L₂ of the vector V₂ encoding the congruence key for the edge E₂ ; and

B) comparing the length L₁ of the vector V₁ and the length L₂ of the vector V₂ ; and

C) signaling edge non-congruency if L₁ ≠

L₂ and signaling edge congruency if L₁ =L₂.

9. An article of manufacture/computer program/computer/speech recognizer for processing natural language using generalized bidirectional island-driven chart parsing based on a congruency checking to prevent edge overgeneration, having a computer usable medium with a computer readable program code thereon wherein the computer readable program code implements the steps of:

A) selecting, in accordance with a predetermined scheme, a candidate edge with a starting vertex, an ending vertex, a label, and a congruence key for determining edge congruency, wherein edge congruency exists when a plurality of equal edges dominate at least one identical tree, for entry in a chart from an agenda of edges;

B) selecting an edge equivalence set in the chart that match the starting vertex, the ending vertex, and the label of the candidate edge; and

C) entering the candidate edge into the chart if the congruence key of the candidate edge fails to match the congruence key of any edge in the edge equivalence set.

10. The article of manufacture/computer program/computer/speech recognizer of claim 9 wherein entering the candidate edge into the chart if the congruence key of the candidate edge fails to match the congruence key of any edge in the edge equivalence set includes:

A) determining if the congruence key of the candidate edge fails to match the congruence key of any edge in the edge equivalence set;

B) constructing a generated edge set corresponding to the candidate edge if the congruence key of the candidate edge fails to match the congruence key of any edge in the edge equivalence set; and

C) entering the candidate edge into the chart and the generated edge set into the agenda if the congruence key of the candidate edge fails to match the congruence key of any edge in the edge equivalence set.

11. The article of manufacture/computer program/computer/speech recognizer of claim 10 wherein determining if the congruence key of the candidate edge fails to match the congruence key of any edge in the edge equivalence set includes comparing the congruence key for an edge E₁ with the congruence key for an edge E₂ and is accomplished by a pairwise comparison of a vector V₁ encoding the congruence key for the edge E₁ with a vector V₂ encoding the congruence key for the edge E₂.

12. The article of manufacture/computer program/computer/speech recognizer of claim 11 further including, prior to the pairwise comparison of the vector encoding the congruence key for the edge E₁ with the vector encoding the congruence key for the edge E₂, performing a threshold test comprising the steps of:

A) determining a length L₁ of the vector V₁ encoding the congruence key for the edge E₁ and a length L₂ of the vector V₂ encoding the congruence key for the edge E₂ ;

B) comparing the length L₁ of the vector V₁ and the length L₂ of the vector V₂ ; and

C) signaling edge non-congruency if L₁ ≠

L₂ and signaling edge congruency if L₁ =L₂.

13. The article of manufacture/computer program/computer/speech recognizer of claim 9 further including, for each lexical edge constructed from an arc, labeled with a word, in a word graph, encoding of the congruence key from the starting vertex of the lexical edge, the ending vertex of the lexical edge, and a unique number identifying the word.

14. The article of manufacture/computer program/computer/speech recognizer of claim 9 further including, for each production edge constructed from a complete edge and a production, encoding of a congruence key from the starting vertex of the production edge, the ending vertex of the production edge, and a unique number identifying the production.

15. The article of manufacture/computer program/computer/speech recognizer of claim 9 further including, for each extension edge constructed from an active edge and a complete edge, encoding of a congruence key by vector concatenation of the congruence key of the active edge and the congruence key of the complete edge.

16. An article of manufacture/application specific integrated circuit/microprocessor for processing natural language using generalized bidirectional island-driven chart parsing based on congruency checking to prevent edge overgeneration, comprising:

A) a parse controller, coupled to receive a word graph, for generating a parse forest;

B) a memory unit, coupled to the parse controller; and

C) an edge congruency detector, coupled to the parse controller, for determining if a pair of edges is congruent by comparing a pair of congruence keys associated with the pair of edges.

17. The article of manufacture/application specific integrated circuit/microprocessor of claim 16 wherein the parse controller comprises:

A) an agenda controller, coupled to an agenda in the memory unit and coupled to receive the word graph and a generated edge set, for generating a candidate edge; and

B) a chart controller, coupled to the edge congruency detector and to a grammar and a chart in the memory unit, and coupled to receive the candidate edge, for generating the generated edge set and the parse forest.

18. The article of manufacture/application specific integrated circuit/microprocessor of claim 17 wherein the chart controller comprises:

A) an edge equivalence set selector, coupled to the edge congruency detector and to the chart in the memory unit, and coupled to receive the candidate edge, an edge equivalence set, and a congruency signal, for producing an edge pair and a noncongruent candidate edge; and

B) a generated edge set constructor, coupled to the chart and the grammar in the memory unit, and coupled to receive the noncongruent candidate edge, for generating the generated edge set and a parse forest.

19. The article of manufacture/application specific integrated circuit/microprocessor of claim 18 wherein the generated edge set constructor comprises:

A) an extensible edge set selector, coupled to the chart and the grammar in the memory unit, and coupled to receive the noncongruent candidate edge, a constructed edge, and a relevant production set, for generating an edge specification, a root edge, a noncongruent candidate edge, and the generated edge set;

B) an edge constructor, coupled to receive the edge specification, for generating the constructed edge; and

C) a parse forest constructor, coupled to the chart in the memory unit, and coupled to receive a root edge and a parsed edge set, for constructing the parse forest and providing the root edge to the chart.

20. The article of manufacture/application specific integrated circuit/microprocessor of claim 18 wherein the edge constructor for constructing one of a lexical edge, an extension edge, and a production edge, comprises:

A) a lexical edge constructor, coupled to receive a lexical edge specification, for producing a lexical edge;

B) an extension edge constructor, coupled to receive an extension edge specification, for producing an extension edge; and

C) a production edge constructor, coupled to receive a production edge specification, for producing a production edge.

21. The article of manufacture/application specific integrated circuit/microprocessor of claim 16 wherein the edge congruency detector comprises:

A) a threshold tester, coupled to receive an edge pair, for producing a congruency signal; and

B) a congruency tester, coupled to receive the edge pair, for producing the congruency signal.