Method and system for reducing lexical ambiguity

• US 6,721,697 B1
• Filed: 10/18/1999
• Issued: 04/13/2004
• Est. Priority Date: 10/18/1999
• Status: Expired due to Fees

• Current Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Original Assignee: Sony Corporation (Sony Group Corp.), Sony Electronics Inc. (Sony Group Corp.)
• Inventors: Duan, Lei, Franz, Alexander, Horiguchi, Keiko
• Primary Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US09/420,517
• Time in Patent Office: 1,639 Days
• Field of Search: 704/1, 704/9, 704/10, 704/270, 704/275, 707/530, 707/531, 707/4, 707/5
• US Class Current: 704/9
• CPC Class Codes: G06F 40/284 Lexical analysis, e.g. tokenisation or collocates
• CPC Class Codes: G06F 40/44 Statistical methods, e.g. probability models

Abstract

A method and system for reducing lexical ambiguity in an input stream are described. In one embodiment, the input stream is broken into tokens. The tokens are used to create a connection graph comprising a number of paths. Each of the paths is assigned a cost. At least one best path is defined based upon a corresponding cost to generate an output graph. The generated output graph is provided to reduce lexical ambiguity.

Claims

1. A method for reducing lexical ambiguity in an input stream, comprising:

breaking the input stream into at least two tokens;

compiling lexical grammar rules to generate lexical functions;

creating a plurality of segments from the at least two tokens based upon lexical information and the lexical functions,

defining a plurality of paths using the plurality of segments;

assigning a cost to each of the plurality of paths;

defining at least one best path based upon a corresponding cost to generate an output graph; and

providing the output graph to a syntactic analysis module for subsequent syntactic analysis of the input stream to reduce lexical ambiguity.

2. The method of claim 1 wherein a number of the at least one best path is either predefined or determined programmatically.

3. The method of claim 1 wherein creating a connection graph using the at least two tokens comprises assigning at least one part of speech tag to at least one of the at least two tokens using lexical information.

4. The method of claim 1 wherein creating a connection graph using the at least two tokens comprises recognizing a multiword expression in the input stream using multiword information.

5. The method of claim 1 wherein the connection graph comprises a set of nodes and a set of arcs.

6. The method of claim 5 wherein each of the plurality of paths comprises a combination of nodes and arcs.

7. The method of claim 1 wherein the cost comprises lexical cost, unigram cost, bigram cost and connector cost.

8. An apparatus for reducing lexical ambiguity in an input stream, comprising:

means for breaking the input stream into at least two tokens;

means for compiling lexical grammar rules to generate lexical functions;

means for creating a plurality of segments from the at least two tokens based upon lexical information and the lexical functions,

means for defining a plurality of paths using the plurality of segments;

means for assigning a cost to each of the plurality of paths;

means for defining at least one best path based upon a corresponding cost to generate an output graph; and

means for providing the output graph to a syntactic analysis module for subsequent syntactic analysis of the input stream to reduce lexical ambiguity.

9. The apparatus of claim 8 wherein a number of the at least one best path is either predefined or determined programmatically.

10. The apparatus of claim 8 further comprising means for assigning at least one part of speech tag to at least one of the at least two tokens using lexical information.

11. The apparatus of claim 8 further comprising means for recognizing a multiword expression in the input stream using multiword information.

12. The apparatus of claim 8 wherein the connection graph comprises a set of nodes and a set of arcs.

13. The apparatus claim 12 wherein each of the plurality of paths comprises a combination of nodes and arcs.

14. The apparatus of claim 8 wherein the cost comprises lexical cost, unigram cost, bigram cost and connector cost.

15. An apparatus for reducing lexical ambiguity in an input stream, comprising:

a tokenizer to break the input stream into at least two tokens;

a grammar programming language (GPL) compiler to compile lexical grammar rules to generate lexical functions;

a segmentation engine to create a plurality of segments from the at least two tokens based upon lexical information and the lexical functions;

a path designator to define a plurality of paths using the plurality of segments;

a cost assignor to assign a cost to each of the plurality of paths;

a path calculator to define at least one best path based upon a corresponding cost to generate an output graph; and

a graph provider to provide the output graph to a syntactic analysis module for subsequent syntactic analysis of the input stream to reduce lexical ambiguity.

16. The apparatus of claim 15 wherein a number of the at least one best path is either predefined or determined programmatically.

17. The apparatus of claim 15 wherein the token connector comprises a part of speech tagger for assigning at least one part of speech tag to at least one of the at least two tokens using lexical information.

18. The apparatus of claim 15 wherein the token connector comprises a multiword recognizer for recognizing a multiword expression in the input stream using multiword information.

19. The apparatus of claim 15 wherein the connection graph comprises a set of nodes and a set of arcs.

20. The apparatus of claim 15 wherein each of the plurality of paths comprises a combination of nodes and arcs.

21. The apparatus of claim 15 wherein the cost comprises lexical cost, unigram cost, bigram cost and connector cost.

22. A system for reducing lexical ambiguity, comprising:

a processor;

an input coupled to the processor, the input capable of receiving an input stream, the processor configured to break the input stream into at least two tokens, compile lexical grammar rules to generate lexical functions, create a plurality of segments from the at least two tokens based upon lexical information and the lexical functions, define a plurality of paths using the plurality of segments, assign a cost to each of the plurality of paths, and define at least one best path based upon a corresponding cost to generate an output graph; and

an output coupled to the processor, the output capable of providing the output graph to a syntactic analysis module for subsequent syntactic analysis of the input stream to reduce lexical ambiguity.

23. A computer readable medium comprising instructions, which when executed on a processor, perform method for reducing lexical ambiguity in an input stream, comprising:

breaking an input stream into at least two tokens;

compiling lexical grammar rules to generate lexical functions;

creating a plurality of segments from the at least two tokens based upon lexical information and the lexical functions;

defining a plurality of paths using the plurality of segments;

assigning a cost to each of the plurality of paths;

defining at least one best path based upon a corresponding cost to generate an output graph; and

providing the output graph to a syntactic analysis module for subsequent syntactic analysis of the input stream to reduce lexical ambiguity.

24. The computer readable medium of claim 23 wherein creating a connection graph further comprises providing segmentation of the input stream using lexical information and lexical functions.

25. The computer readable medium of claim 23 wherein creating a connection graph further comprises assigning at least one part of speech tag to at least one of the at least two tokens using lexical information.

26. The computer readable medium of claim 23 wherein creating a connection graph further comprises recognizing a multiword expression in the input stream using lexical information.

27. The computer readable medium of claim 23 wherein a number of the at least one best path is either predefined or determined programmatically.