US5930746A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Parsing and translating natural language sentences automatically
Assignee: Government of Singapore
•
Filing: 1996-08-09
•
Granted: 1999-07-27
•
Expires: 2016-08-09
Abstract
Abstract A sentence of a natural language is automatically parsed by: defining a set of coded tags each corresponding to a respective part-of-speech of a word in a sentence of the language; building a small corpus of sentence dependency structures by annotating with the corresponding coded tags the words in each sentence of a set of sentences having respective exemplary dependency structures to obtain a set of sequences of coded tags representing the dependency structures; determining the statistical parameters of a corpus-based statistical tool, such as a hidden Markov model, from the corpus of sentence dependency structures; tagging the words of an input sentence to be parsed with the corresponding coded tags to obtain a sequence of coded tags to derive therefrom the most probable dependency structure for the input sentence; and generating a dependency parse tree of the sentence from the derived dependency structure and the words of the input sentence. The invention finds particular application in the automatic translation of a first natural language into a second language.
Inventors
- 👤 Hian Ann Ting
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 09:55
CPC Classifications
G; G06; G06F; G06F40/00; G06F40/20; G06F40/205; G06F40/211; G06F40/40; G06F40/42; G06F40/44; G06F40/49; G06F40/55
Claims Analysis
Total Claims: 56
Claim 1
Independent Claim
161 words
A method of automatically parsing a sentence of a natural language, comprising: defining a set of coded tags each corresponding to a respective part-of-speech of a word in a sentence of the language; building a corpus of sentence dependency structures by annotating with the corresponding coded tags the words in each sentence of a set of sentences having respective exemplary dependency structures to obtain a set of sequences of coded tags representing the dependency structures; determining the statistical parameters of a corpus-based statistical tool from the corpus of sentence dependency structures; tagging the words of an input sentence to be parsed with the corresponding coded tags to obtain a sequence of coded tags representing the input sentence; applying the corpus-based statistical tool to the sequence of coded tags to derive therefrom the most probable dependency structure for the input sentence; and generating a dependency parse tree of the sentence from the derived dependency structure and the words of the input sentence.
Claim 2
Independent Claim
161 words
A method of automatically parsing a sentence of a natural language, comprising: defining a set of coded tags each corresponding to a respective part-of-speech of a word in a sentence of the language; building a corpus of sentence dependency structures by annotating with the corresponding coded tags the words in each sentence of a set of sentences having respective exemplary dependency structures to obtain a set of sequences of coded tags representing the dependency structures; determining the statistical parameters of a corpus-based statistical tool from the corpus of sentence dependency structures; tagging the words of an input sentence to be parsed with the corresponding coded tags to obtain a sequence of coded tags representing the input sentence; applying the corpus-based statistical tool to the sequence of coded tags to derive therefrom the most probable dependency structure for the input sentence; and generating a dependency parse tree of the sentence from the derived dependency structure and the words of the input sentence.
Claim 3
Dependent Claim
28 words
The method according to claim 1, comprising: rendering electrical signals representing input text in the language into paragraphs and sentences; and tokenising the sentences into strings of words.
Claim 4
Dependent Claim
42 words
The method according to claim 1, comprising: storing a part-of-speech corpus consisting of words in the language associates with their corresponding coded tags; and tagging the words of the input sentence to be parsed using the part-of-speech corpus and the statistical tagger.
Claim 5
Dependent Claim
18 words
The method according to claim 3, wherein the statistical tagger is based on a first-order hidden Markov model.
Claim 6
Dependent Claim
29 words
The method according to claim 3, comprising using a dynamic context algorithm to assign a most probable coded tag to an unknown word not contained in the part-of-speech corpus.
Claim 7
Dependent Claim
21 words
The method according to claim 1, comprising determining the most probable dependency structure using a first-order double layer hidden Markov model.
Claim 8
Dependent Claim
42 words
The method according to claim 6, comprising: using a dynamic context algorithm to nominate candidate governors and generate a parse forest of dependency parse trees; pruning away invalid candidate governors; and selecting the most probable dependency structure from the remaining dependency trees.
Claim 9
Dependent Claim
22 words
The method according to claim 7, comprising pruning away the invalid governors using a first group of language-independent axioms of dependency structure.
Claim 10
Dependent Claim
51 words
The method according to claim 8, wherein the first group of axioms comprises a first axiom that each word depends on one and only one word in the same sentence and a second axiom that a word used as a conjunction or preposition cannot be a leaf of a dependency tree.
Claim 11
Dependent Claim
27 words
The method according to claim 8, comprising selecting a plurality of most likely dependency trees from the pruned forest of dependency trees using an enhanced Viterbi algorithm.
Claim 12
Dependent Claim
29 words
The method according to claim 10, comprising selecting as the most probable dependency structure that dependency tree which satisfies a second group of language independent axioms of dependency structure.
Claim 13
Dependent Claim
43 words
The method according to claim 11, wherein the second group of axioms comprises a third axiom that dependency structure is non-cyclic, a fourth axiom that dependency structure is non-crossing and a fifth axiom that a sentence can have at most one main verb.
Claim 14
Dependent Claim
27 words
The method according to claim 7, comprising extracting noun phrases from the input sentence after tagging of the input sentence and prior to generating the parse forest.
Claim 15
Dependent Claim
148 words
A machine for parsing a sentence of a natural language, comprising: a coder defining a set of coded tags each corresponding to a respective part-of-speech of a word in a sentence of the language; a corpus-based statistical tool having statistical parameters determined from a corpus of sentence dependency structures formed by annotating with the corresponding coded tags the words in each sentence of a set of sentences having respective exemplary dependency structures; a tagger for tagging the words of a sentence to be parsed with the corresponding coded tags to obtain a sequence of coded tags representing the input sentence; a processor for applying the corpus-based statistical tool to the sequence of coded tags to derive therefrom the most probable dependency structure for the input sentence and to generate a dependency parse tree of the sentence from the derived dependency structure and the words of the input sentence.
Claim 16
Dependent Claim
148 words
A machine for parsing a sentence of a natural language, comprising: a coder defining a set of coded tags each corresponding to a respective part-of-speech of a word in a sentence of the language; a corpus-based statistical tool having statistical parameters determined from a corpus of sentence dependency structures formed by annotating with the corresponding coded tags the words in each sentence of a set of sentences having respective exemplary dependency structures; a tagger for tagging the words of a sentence to be parsed with the corresponding coded tags to obtain a sequence of coded tags representing the input sentence; a processor for applying the corpus-based statistical tool to the sequence of coded tags to derive therefrom the most probable dependency structure for the input sentence and to generate a dependency parse tree of the sentence from the derived dependency structure and the words of the input sentence.
Claim 17
Dependent Claim
32 words
The machine according to claim 14, comprising an analyzer for rendering electrical signals representing input text in the language into paragraphs and sentences and for tokenising the sentences into strings of words.
Claim 18
Dependent Claim
43 words
The machine according to claim 14, comprising a first corpus memory storing a part-of-speech corpus consisting of words in the language associated with their corresponding coded tags; and a statistical tagger for tagging the words of the input sentence using the part-of-speech corpus.
Claim 19
Dependent Claim
18 words
The machine according to claim 16, wherein the statistical tagger is based on a first-order hidden Markov model.
Claim 20
Dependent Claim
28 words
The machine according to claim 16, comprising a dynamic context algorithm for assigning a most probable coded tag to an unknown word not contained in the part-of-speech corpus.
Claim 21
Dependent Claim
26 words
The machine according to claim 14, wherein the corpus-based statistical tool for determining the most probable dependency structure includes a first-order double layer hidden Markov model.
Claim 22
Dependent Claim
46 words
The machine according to claim 19, wherein a dynamic context algorithm is used to nominate candidate governors and generate a parse forest of dependency parse trees from which invalid candidate governors are pruned away, the most probable dependency structure being selected from the remaining dependency trees.
Claim 23
Dependent Claim
23 words
The machine according to claim 20, wherein the invalid governors are pruned away using a first group of language-independent axioms of dependency structure.
Claim 24
Dependent Claim
51 words
The machine according to claim 21, wherein the first group of axioms comprises a first axiom that each word depends on one and only one word in the same sentence and a second axiom that a word used as a conjunction or preposition cannot be a leaf of a dependency tree.
Claim 25
Dependent Claim
28 words
The machine according to claim 21, wherein a plurality of most likely dependency trees are selected from the pruned forest of dependency trees using an enhanced Viterbi algorithm.
Claim 26
Dependent Claim
38 words
The machine according to claim 23, wherein the most probable dependency structure is selected from the plurality of most likely dependency trees as being that dependency tree which satisfies a second group of language-independent axioms of dependency structure.
Claim 27
Dependent Claim
43 words
The machine according to claim 24, wherein the second group of axioms comprises a third axiom that dependency structure is non-cyclic, a fourth axiom that dependency structure is non-crossing and a fifth axiom that a sentence can have at most the main verb.
Claim 28
Dependent Claim
28 words
The machine according to claim 20, wherein noun phrases are extracted from the input sentence after tagging of the input sentence and prior to generating the parse forest.
Claim 29
Independent Claim
243 words
A method of automatically translating a first natural language into a second language, comprising the steps of: converting a spoken or written text in the first language into electrical signals representing the spoken or written words; rendering the text into sentences; processing each sentence by an automatic parsing method to generate a dependency parse tree for the sentence by defining a set of coded tags each corresponding to a respective part-of-speech of a word in a sentence of the language; building a corpus of sentence dependency structures by annotating with the corresponding coded tags the words in each sentence of a set of sentences having respective exemplary dependency structures to obtain a set of sequences of coded tags representing the dependency structures; determining the statistical parameters of a corpus-based statistical tool from the corpus of sentence dependency structures; tagging the words of an input sentence to be parsed with the corresponding coded tags to obtain a sequence of coded tags representing the input sequence; applying the corpus-based statistical tool to the sequence of coded tags to derive therefrom the most probable dependency structure for the input sentence; and generating a dependency parse tree of the sentence from the derived dependency structure and the words of the input sentence; synthesizing a sentence in a second language based on the words and the derived dependency tree of the sentence in the first language; and audibly or visually reproducing a synthesized sentence in the second language.
Claim 30
Independent Claim
243 words
A method of automatically translating a first natural language into a second language, comprising the steps of: converting a spoken or written text in the first language into electrical signals representing the spoken or written words; rendering the text into sentences; processing each sentence by an automatic parsing method to generate a dependency parse tree for the sentence by defining a set of coded tags each corresponding to a respective part-of-speech of a word in a sentence of the language; building a corpus of sentence dependency structures by annotating with the corresponding coded tags the words in each sentence of a set of sentences having respective exemplary dependency structures to obtain a set of sequences of coded tags representing the dependency structures; determining the statistical parameters of a corpus-based statistical tool from the corpus of sentence dependency structures; tagging the words of an input sentence to be parsed with the corresponding coded tags to obtain a sequence of coded tags representing the input sequence; applying the corpus-based statistical tool to the sequence of coded tags to derive therefrom the most probable dependency structure for the input sentence; and generating a dependency parse tree of the sentence from the derived dependency structure and the words of the input sentence; synthesizing a sentence in a second language based on the words and the derived dependency tree of the sentence in the first language; and audibly or visually reproducing a synthesized sentence in the second language.
Claim 31
Dependent Claim
28 words
The method according to claim 27, comprising rendering electrical signals representing input text in the language into paragraphs and sentences; and tokenising the sentences into strings of words.
Claim 32
Dependent Claim
42 words
The method according to claim 27, comprising storing a part-of-speech corpus consisting of words in the language associates with their corresponding coded tags; and tagging the words of the input sentence to be parsed using the part-of-speech corpus and the statistical tagger.
Claim 33
Dependent Claim
18 words
The method according to claim 29, wherein the statistical tagger is based on a first-order hidden Markov model.
Claim 34
Dependent Claim
29 words
The method according to claim 29, comprising using a dynamic context algorithm to assign a most probable coded tag to an unknown word not contained in the part-of-speech corpus.
Claim 35
Dependent Claim
21 words
The method according to claim 27, comprising determining the most probable dependency structure using a first-order double layer hidden Markov model.
Claim 36
Dependent Claim
42 words
The method according to claim 32, comprising using a dynamic context algorithm to nominate candidate governors and generate a parse forest of dependency parse trees; pruning away invalid candidate governors; and selecting the most probable dependency structure from the remaining dependency trees.
Claim 37
Dependent Claim
22 words
The method according to claim 33, comprising pruning away the invalid governors using a first group of language-dependent axioms of dependency structure.
Claim 38
Dependent Claim
51 words
The method according to claim 34, wherein the first group of axioms comprises a first axiom that each word depends on one and only one word in the same sentence and a second axiom that a word used as a conjunction or preposition cannot be a leaf of a dependency tree.
Claim 39
Dependent Claim
27 words
The method according to claim 34, comprising selecting a plurality of most likely dependency trees from the pruned forest of dependency trees using an enhanced Viterbi algorithm.
Claim 40
Dependent Claim
29 words
The method according to claim 36, comprising selecting as the most probable dependency structure that dependency tree which satisfies a second group of language independent axioms of dependency structure.
Claim 41
Dependent Claim
43 words
The method according to claim 37, wherein the second group of axioms comprises a third axiom that dependency structure is non-cyclic, a fourth axiom that dependency structure is non-crossing and a fifth axiom that a sentence can have at most one main verb.
Claim 42
Dependent Claim
26 words
The method according to claim 33 comprising extracting noun phrases from the input sentence after tagging of the input sentence prior to generating the parse forest.
Claim 43
Independent Claim
241 words
An apparatus for automatically translating a first natural language into a second language, comprising: a converter for converting a spoken or written text in the first language into electrical signals representing the spoken or written words; a means for rendering the text into sentences; an automatic parsing machine for processing each sentence to generate a dependency parse tree for the sentence comprising a coder defining a set of coded tags each corresponding to a respective part-of-speech of a word in a sentence of the language; a corpus-based statistical tool having statistical parameters determined from a corpus of sentence dependency structures formed by annotating with the corresponding coded tags the words in each sentence of a set of sentences having respective exemplary dependency structures; a tagger for tagging the words of a sentence to be parsed with the corresponding coded tags to obtain a sequence of coded tags representing the input sentence; a processor for applying the corpus-based statistical tool to the sequence of coded tags to derive therefrom the most probable dependency structure for the input sentence and to generate a dependency parse tree of the sentence from the derived dependency structure and the words of the input sentence; a synthesizer for synthesizing a sentence in the second language based on the words and the derived dependency tree of the sentence in the first language; and a reproduction device for audibly or visually reproducing the synthesized sentence in the second language.
Claim 44
Independent Claim
241 words
An apparatus for automatically translating a first natural language into a second language, comprising: a converter for converting a spoken or written text in the first language into electrical signals representing the spoken or written words; a means for rendering the text into sentences; an automatic parsing machine for processing each sentence to generate a dependency parse tree for the sentence comprising a coder defining a set of coded tags each corresponding to a respective part-of-speech of a word in a sentence of the language; a corpus-based statistical tool having statistical parameters determined from a corpus of sentence dependency structures formed by annotating with the corresponding coded tags the words in each sentence of a set of sentences having respective exemplary dependency structures; a tagger for tagging the words of a sentence to be parsed with the corresponding coded tags to obtain a sequence of coded tags representing the input sentence; a processor for applying the corpus-based statistical tool to the sequence of coded tags to derive therefrom the most probable dependency structure for the input sentence and to generate a dependency parse tree of the sentence from the derived dependency structure and the words of the input sentence; a synthesizer for synthesizing a sentence in the second language based on the words and the derived dependency tree of the sentence in the first language; and a reproduction device for audibly or visually reproducing the synthesized sentence in the second language.
Claim 45
Dependent Claim
32 words
The machine according to claim 40, comprising an analyzer for rendering electric signals representing input text in the language into paragraphs and sentences and for tokenising the sentences into strings of words.
Claim 46
Dependent Claim
43 words
The machine according to claim 40, comprising a first corpus memory storing a part-of-speech corpus consisting of words in the language associated with a corresponding coded tags; and a statistical tagger for tagging the words of the input sentence using the part-of-speech corpus.
Claim 47
Dependent Claim
18 words
The machine according to claim 42, wherein the statistical tagger is based on a first-order hidden Markov model.
Claim 48
Dependent Claim
28 words
The machine according to claim 42, comprising a dynamic context algorithm for assigning a most probable coded tag to an unknown word not contained in the part-of-speech corpus.
Claim 49
Dependent Claim
26 words
The machine according to claim 40, wherein the corpus-based statistical tool for determining the most probable dependency structure includes a first-order double layer hidden Markov model.
Claim 50
Dependent Claim
46 words
The machine according to claim 45, wherein a dynamic context algorithm is used to nominate candidate governors and generate a parse forest of dependency parse trees from which invalid candidate governors are pruned away, the most probable dependency structure being selected from the remaining dependency trees.
Claim 51
Dependent Claim
23 words
The machine according to claim 46, wherein the invalid governors are pruned away using a first group of language-independent axioms of dependency structure.
Claim 52
Dependent Claim
51 words
The machine according to claim 47, wherein the first group of axioms comprises a first axiom that each word depends on one and only one word in the same sentence and a second axiom that a word used as a conjunction or preposition cannot be a leaf of a dependency tree.
Claim 53
Dependent Claim
28 words
The machine according to claim 47, wherein a plurality of most likely dependency trees are selected from the pruned forest of dependency trees using an enhanced Viterbi algorithm.
Claim 54
Dependent Claim
38 words
The machine according to claim 49, wherein the most probable dependency structure is selected from the plurality of most likely dependency trees as being that dependency tree which satisfies a second group of language-independent axioms of dependency structure.
Claim 55
Dependent Claim
43 words
The machine according to claim 50, wherein the second group of axioms comprises a third axiom that dependency structure is non-cyclic, a fourth axiom that dependency structure is non-crossing and a fifth axiom that a sentence can have at most the main verb.
Claim 56
Dependent Claim
28 words
The machine according to claim 46, wherein noun phrases are extracted from the input sentence after tagging of the input sentence and prior to generating the parse forest.
References Cited (Backward Citations)
US4887212A
Cited
US5146405A
Cited
US5477451A
Cited
US5519608A
Cited
US5696962A
Cited
US5642522A
Cited
US5510981A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-07-26 | 2003-01-25 | 2003-07-27 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-07-26 | 2007-01-25 | 2007-07-27 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-07-26 | 2011-01-25 | 2011-07-27 | $7700.00 | Window Closed / Lapsed |