US6721697B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for reducing lexical ambiguity
Assignee: Sony Corp
•
Filing: 1999-10-18
•
Granted: 2004-04-13
•
Expires: 2019-10-18
Abstract
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.
Inventors
- 👤 Lei Duan
- 👤 Alexander Franz
- 👤 Keiko Horiguchi
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 13:26
CPC Classifications
G; G06; G06F; G06F40/00; G06F40/20; G06F40/279; G06F40/284; G06F40/40; G06F40/42; G06F40/44
Claims Analysis
Total Claims: 32
Claim 1
Independent Claim
105 words
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.
Claim 2
Independent Claim
105 words
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.
Claim 3
Dependent Claim
21 words
The method of claim 1 wherein a number of the at least one best path is either predefined or determined programmatically.
Claim 4
Dependent Claim
38 words
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.
Claim 5
Dependent Claim
28 words
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.
Claim 6
Dependent Claim
19 words
The method of claim 1 wherein the connection graph comprises a set of nodes and a set of arcs.
Claim 7
Dependent Claim
19 words
The method of claim 5 wherein each of the plurality of paths comprises a combination of nodes and arcs.
Claim 8
Dependent Claim
18 words
The method of claim 1 wherein the cost comprises lexical cost, unigram cost, bigram cost and connector cost.
Claim 9
Independent Claim
119 words
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.
Claim 10
Independent Claim
119 words
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.
Claim 11
Dependent Claim
21 words
The apparatus of claim 8 wherein a number of the at least one best path is either predefined or determined programmatically.
Claim 12
Dependent Claim
30 words
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.
Claim 13
Dependent Claim
20 words
The apparatus of claim 8 further comprising means for recognizing a multiword expression in the input stream using multiword information.
Claim 14
Dependent Claim
19 words
The apparatus of claim 8 wherein the connection graph comprises a set of nodes and a set of arcs.
Claim 15
Dependent Claim
18 words
The apparatus claim 12 wherein each of the plurality of paths comprises a combination of nodes and arcs.
Claim 16
Dependent Claim
18 words
The apparatus of claim 8 wherein the cost comprises lexical cost, unigram cost, bigram cost and connector cost.
Claim 17
Independent Claim
135 words
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.
Claim 18
Independent Claim
135 words
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.
Claim 19
Dependent Claim
21 words
The apparatus of claim 15 wherein a number of the at least one best path is either predefined or determined programmatically.
Claim 20
Dependent Claim
37 words
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.
Claim 21
Dependent Claim
25 words
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.
Claim 22
Dependent Claim
19 words
The apparatus of claim 15 wherein the connection graph comprises a set of nodes and a set of arcs.
Claim 23
Dependent Claim
19 words
The apparatus of claim 15 wherein each of the plurality of paths comprises a combination of nodes and arcs.
Claim 24
Dependent Claim
18 words
The apparatus of claim 15 wherein the cost comprises lexical cost, unigram cost, bigram cost and connector cost.
Claim 25
Independent Claim
132 words
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.
Claim 26
Independent Claim
132 words
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.
Claim 27
Dependent Claim
117 words
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.
Claim 28
Dependent Claim
117 words
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.
Claim 29
Dependent Claim
26 words
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.
Claim 30
Dependent Claim
35 words
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.
Claim 31
Dependent Claim
25 words
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.
Claim 32
Dependent Claim
23 words
The computer readable medium of claim 23 wherein a number of the at least one best path is either predefined or determined programmatically.
References Cited (Backward Citations)
US4974191A
Cited
US5033087A
Cited
US5088038A
Cited
US5418717A
Cited
US5535120A
Cited
US5768603A
Cited
US5528491A
Cited
US5677835A
Cited
US5864788A
Cited
US5426583A
Cited
US5873056A
Cited
US5510981A
Cited
US5659765A
Cited
US5642519A
Cited
US5963894A
Cited
US5644775A
Cited
US5799268A
Cited
US5806021A
Cited
US5907821A
Cited
US5983169A
Cited
EP0805403A2
Cited
US6161083A
Cited
US6212500B1
Cited
US5884247A
Cited
US6230153B1
Cited
US6243669B1
Cited
US6301554B1
Cited
US6330530B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-04-13 | 2007-10-13 | 2008-04-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-04-13 | 2011-10-13 | 2012-04-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-04-13 | 2015-10-13 | 2016-04-13 | $7700.00 | Window Closed / Lapsed |