US5758024A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for encoding pronunciation prefix trees
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1996-06-25
•
Granted: 1998-05-26
•
Expires: 2016-06-25
Abstract
Abstract A computer system for linearly encoding a pronunciation prefix tree. The pronunciation prefix tree has nodes such that each non-root and non-leaf node represents a phoneme and wherein each leaf node represents a word formed by the phonemes represented by the non-leaf nodes in a path from the root node to the leaf node. Each leaf node has a probability associated with the word of the leaf node. The computer system creates a tree node dictionary containing an indication of the phonemes that compose each word. The computer system then orders the child nodes of each non-leaf node based on the highest probability of descendent leaf nodes of the child node. Then, for each non-leaf node, the computer system sets the probability of the non-leaf node to a probability based on the probability of its child nodes, and for each node, sets a factor of the node to the probability of the node divided by the probability of the parent node of the node. Finally, the computer system generates an encoded pronunciation entry for each leaf node of the pronunciation prefix tree. Each encoded pronunciation entry indicates the word represented by the leaf node and contains the factor of a nearest ancestor node with a factor other than 1.0.
Inventors
- 👤 Fileno A. Alleva
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 19:15
CPC Classifications
G; G10; G10L; G10L15/00; G10L15/08; G10L15/18; G10L15/183; G10L15/187; G06; G06F; G06F40/00; G06F40/20; G06F40/205; G06F40/216; G06F40/279
Claims Analysis
Total Claims: 72
Claim 1
Independent Claim
204 words
A method in a computer system for encoding a pronunciation prefix tree, the pronunciation prefix tree having a plurality of nodes, each non-root and non-leaf node representing a phoneme, each leaf node representing a word formed by the phonemes represented by the non-leaf nodes in a path from the root node to the leaf node, each leaf node having a probability, the method comprising: creating a tree node dictionary containing an indication of the phonemes that compose each word; ordering child nodes of each non-leaf node of the pronunciation prefix tree based on the highest probability of descendent leaf nodes of the child node; for each non-leaf node of the pronunciation prefix tree, setting the probability of the non-leaf node to a probability based on the probability of its child nodes; for each node of the pronunciation prefix tree, setting a factor of the node to the probability of the node divided by the probability of a parent node of the node; and generating an encoded pronunciation entry for each leaf node of the pronunciation prefix tree, the encoded pronunciation entry indicating the word represented by the leaf node and containing the factor of a nearest ancestor node with a factor less than 1.0.
Claim 2
Independent Claim
204 words
A method in a computer system for encoding a pronunciation prefix tree, the pronunciation prefix tree having a plurality of nodes, each non-root and non-leaf node representing a phoneme, each leaf node representing a word formed by the phonemes represented by the non-leaf nodes in a path from the root node to the leaf node, each leaf node having a probability, the method comprising: creating a tree node dictionary containing an indication of the phonemes that compose each word; ordering child nodes of each non-leaf node of the pronunciation prefix tree based on the highest probability of descendent leaf nodes of the child node; for each non-leaf node of the pronunciation prefix tree, setting the probability of the non-leaf node to a probability based on the probability of its child nodes; for each node of the pronunciation prefix tree, setting a factor of the node to the probability of the node divided by the probability of a parent node of the node; and generating an encoded pronunciation entry for each leaf node of the pronunciation prefix tree, the encoded pronunciation entry indicating the word represented by the leaf node and containing the factor of a nearest ancestor node with a factor less than 1.0.
Claim 3
Dependent Claim
61 words
The method of claim 1 wherein child nodes of a node are ordered by probability such that the child node that has a descendent leaf node with the highest probability is left-most and wherein the generating of an encoded pronunciation entry for each leaf node of the pronunciation prefix tree includes performing a depth-first, left-to-right traversal of the pronunciation prefix tree.
Claim 4
Dependent Claim
59 words
The method of claim 1 wherein the creating of a tree node dictionary includes: generating a unigram pronunciation prefix tree; assigning a unique identifier to each node of the generated unigram pronunciations prefix tree; and for each word, storing the unique identifier for each node on the path from the root node to the leaf node representing that word.
Claim 5
Dependent Claim
30 words
The method of claim 3 wherein the assigning of unique identifiers assigns sequential identifiers to the nodes as visited in a breadth-first, left-to-right traversal of the unigram pronunciation prefix tree.
Claim 6
Dependent Claim
16 words
The method of claim 1 wherein the pronunciation prefix tree is a bigram pronunciation prefix tree.
Claim 7
Dependent Claim
16 words
The method of claim 1 wherein the pronunciation prefix tree is a trigram pronunciation prefix tree.
Claim 8
Dependent Claim
21 words
The method of claim 1 wherein the pronunciation prefix tree is an n-gram pronunciation prefix tree, where n is any length.
Claim 9
Dependent Claim
22 words
The method of claim 1 wherein the probability in each non-leaf node is set to the maximum probability of its child nodes.
Claim 10
Dependent Claim
24 words
The method of claim 1 wherein the probability in each non-leaf node is set to the sum of the probability of its child nodes.
Claim 11
Dependent Claim
35 words
The method of claim 1 wherein each node has a depth within the pronunciation prefix tree and wherein the encoded pronunciation entry contains the depth of the nearest ancestor node with a factor less 1.0.
Claim 12
Independent Claim
173 words
A method in a computer system for linearly encoding a pronunciation prefix tree, the pronunciation prefix tree having a plurality of nodes, each non-root and non-leaf node representing a phoneme, each leaf node representing a word formed by the phonemes represented by the non-leaf nodes in a path from the root node to the leaf node, each leaf node having a probability, the method comprising: setting a probability of each non-leaf node to a probability based on the probability of its child nodes; setting a factor of each node to the probability of the node divided by the probability of the parent node of the node; and generating an encoded pronunciation entry for each leaf node of the pronunciation prefix tree, the encoded pronunciation entry indicating the word represented by the leaf node and containing the factor of a nearest ancestor node with a factor other than a predefined factor wherein the pronunciation prefix tree can be regenerated from the encoded pronunciation entries and a list of the phonemes that compose each word.
Claim 13
Independent Claim
173 words
A method in a computer system for linearly encoding a pronunciation prefix tree, the pronunciation prefix tree having a plurality of nodes, each non-root and non-leaf node representing a phoneme, each leaf node representing a word formed by the phonemes represented by the non-leaf nodes in a path from the root node to the leaf node, each leaf node having a probability, the method comprising: setting a probability of each non-leaf node to a probability based on the probability of its child nodes; setting a factor of each node to the probability of the node divided by the probability of the parent node of the node; and generating an encoded pronunciation entry for each leaf node of the pronunciation prefix tree, the encoded pronunciation entry indicating the word represented by the leaf node and containing the factor of a nearest ancestor node with a factor other than a predefined factor wherein the pronunciation prefix tree can be regenerated from the encoded pronunciation entries and a list of the phonemes that compose each word.
Claim 14
Dependent Claim
66 words
The method of claim 11 wherein child nodes of a node are ordered such that the child node that has a descendent leaf node with the highest probability is to the left of the other child nodes and wherein the generating of an encoded pronunciation entry for each leaf node of the pronunciation prefix tree includes performing a depth-first, left-to-right traversal of the pronunciation prefix tree.
Claim 15
Dependent Claim
64 words
The method of claim 11, including creating of a tree node dictionary by: generating a unigram pronunciation prefix tree; assigning a unique identifier to each node of the generated unigram pronunciation prefix tree; and for each word, storing the unique identifier for each node on the path from the root node of the unigram pronunciation prefix tree to the leaf node representing that word.
Claim 16
Dependent Claim
30 words
The method of claim 13 wherein the assigning of unique identifiers assigns sequential identifiers to the nodes as visited in a breadth-first, left-to-right traversal of the unigram pronunciation prefix tree.
Claim 17
Dependent Claim
16 words
The method of claim 11 wherein the pronunciation prefix tree is a bigram pronunciation prefix tree.
Claim 18
Dependent Claim
16 words
The method of claim 11 wherein the pronunciation prefix tree is a trigram pronunciation prefix tree.
Claim 19
Dependent Claim
21 words
The method of claim 11 wherein the pronunciation prefix tree is an n-gram pronunciation prefix tree, where n is any length.
Claim 20
Dependent Claim
22 words
The method of claim 11 wherein the probability in each non-leaf node is set to the maximum probability of its child nodes.
Claim 21
Dependent Claim
24 words
The method of claim 11 wherein the probability in each non-leaf node is set to the sum of the probability of its child nodes.
Claim 22
Dependent Claim
36 words
The method of claim 11 wherein each node has a depth within the pronunciation prefix tree and wherein the encoded pronunciation entry contains the depth of the nearest ancestor node with a factor less than 1.0.
Claim 23
Dependent Claim
11 words
The method of claim 11 wherein the predefined factor is 1.0.
Claim 24
Independent Claim
149 words
A method in a computer system for decoding a linearly encoded pronunciation prefix tree into a pronunciation prefix tree, the linearly encode pronunciation prefix tree having an entries, each entry corresponding to a word and having a factor of a nearest ancestor node with a factor less than 1.0 in the pronunciation prefix tree, the linear encoded pronunciation prefix tree having an associated listing of the phonemes of each word, the method comprising: for each entry, selecting the entry; retrieving the list of the phonemes of the word of the selected entry; adding a node to the pronunciation prefix tree corresponding to each phoneme in the retrieved list for which a node has not already been added; and setting the probability in each added node to the same probability that is the factor of the entry times the probability of the closest common ancestor node of the added nodes.
Claim 25
Independent Claim
149 words
A method in a computer system for decoding a linearly encoded pronunciation prefix tree into a pronunciation prefix tree, the linearly encode pronunciation prefix tree having an entries, each entry corresponding to a word and having a factor of a nearest ancestor node with a factor less than 1.0 in the pronunciation prefix tree, the linear encoded pronunciation prefix tree having an associated listing of the phonemes of each word, the method comprising: for each entry, selecting the entry; retrieving the list of the phonemes of the word of the selected entry; adding a node to the pronunciation prefix tree corresponding to each phoneme in the retrieved list for which a node has not already been added; and setting the probability in each added node to the same probability that is the factor of the entry times the probability of the closest common ancestor node of the added nodes.
Claim 26
Dependent Claim
63 words
The method of claim 22 wherein each node has a depth within the pronunciation prefix tree, wherein the entry contains the depth of the nearest ancestor node with a factor less than 1.0, and wherein when adding a node corresponding to each phoneme in the retrieved list, using the depth of the entry to indicate the depth of the first node to add.
Claim 27
Dependent Claim
16 words
The method of claim 22 wherein the pronunciation prefix tree is a bigram pronunciation prefix tree.
Claim 28
Dependent Claim
16 words
The method of claim 22 wherein the pronunciation prefix tree is a trigram pronunciation prefix tree.
Claim 29
Dependent Claim
21 words
The method of claim 22 wherein the pronunciation prefix tree is an n-gram pronunciation prefix tree, where n is any length.
Claim 30
Dependent Claim
72 words
The method of claim 22 wherein each node has a depth within the pronunciation prefix tree, wherein the entry contains the depth of the nearest ancestor node with a factor less than 1.0, and wherein the setting of the probability in each node includes setting the factor in the added node at the depth of the entry to the factor of the entry and the factor each other added node to 1.0.
Claim 31
Dependent Claim
26 words
The method of claim 22, including calculating the probability by multiplying the factor in each node by the probability in a parent node of the node.
Claim 32
Independent Claim
137 words
A method in a computer system for linearly encoding a tree, the tree having a plurality of nodes, the tree having a root node and leaf nodes, each leaf node having a value, the method comprising: for each leaf node, generating a list of an identification of the nodes in a path from the root node to the leaf node; setting a value of each non-leaf node to a value based on the value of its child nodes; setting a factor of each node to the value of the node divided by the value of a parent node of the node; and generating an encoded entry for each leaf node of the tree, the encoded entry identifying the leaf node and containing the factor of a nearest ancestor node with a factor other than a predefined factor.
Claim 33
Independent Claim
137 words
A method in a computer system for linearly encoding a tree, the tree having a plurality of nodes, the tree having a root node and leaf nodes, each leaf node having a value, the method comprising: for each leaf node, generating a list of an identification of the nodes in a path from the root node to the leaf node; setting a value of each non-leaf node to a value based on the value of its child nodes; setting a factor of each node to the value of the node divided by the value of a parent node of the node; and generating an encoded entry for each leaf node of the tree, the encoded entry identifying the leaf node and containing the factor of a nearest ancestor node with a factor other than a predefined factor.
Claim 34
Dependent Claim
24 words
The method of claim 29 wherein the tree can be regenerated from the encoded entries and the lists of the nodes in the paths.
Claim 35
Dependent Claim
33 words
The method of claim 29 wherein each node has a depth within the tree and wherein the encoded entry contains the depth of the nearest ancestor node with a factor less than 1.0.
Claim 36
Dependent Claim
48 words
The method of claim 31, including after generating the encoded entries, identifying the nodes at a certain depth within the tree by, for each encoded entry, selecting the identification of the node at the certain depth in the list for the leaf node identified by the encoded entry.
Claim 37
Dependent Claim
17 words
The method of claim 32 wherein the certain depth is used as an index into the list.
Claim 38
Dependent Claim
33 words
The method of claim 32 wherein the tree is a bigram pronunciation prefix tree and the identifying of the nodes at a certain depth is performed during recognition of a sequence of phonemes.
Claim 39
Dependent Claim
13 words
The method of claim 29 wherein the tree is a pronunciation prefix tree.
Claim 40
Dependent Claim
135 words
A computer-readable medium containing instructions for causing a computer system to encode a pronunciation prefix tree, the pronunciation prefix tree having a plurality of nodes representing phonemes that compose words, each leaf node having a probability, by: for each leaf node, generating a list of phonemes that compose the words; setting a probability of each non-leaf node to a probability based on the probability of its child nodes; setting a factor of each node to the probability of the node divided by the probability of a parent node of the node; and generating an encoded pronunciation entry for each leaf node of the pronunciation prefix tree, the encoded pronunciation entry indicating the word represented by the leaf node and containing the factor of a nearest ancestor node with a factor other than a predefined factor.
Claim 41
Dependent Claim
135 words
A computer-readable medium containing instructions for causing a computer system to encode a pronunciation prefix tree, the pronunciation prefix tree having a plurality of nodes representing phonemes that compose words, each leaf node having a probability, by: for each leaf node, generating a list of phonemes that compose the words; setting a probability of each non-leaf node to a probability based on the probability of its child nodes; setting a factor of each node to the probability of the node divided by the probability of a parent node of the node; and generating an encoded pronunciation entry for each leaf node of the pronunciation prefix tree, the encoded pronunciation entry indicating the word represented by the leaf node and containing the factor of a nearest ancestor node with a factor other than a predefined factor.
Claim 42
Dependent Claim
68 words
The computer-readable medium of claim 36 wherein child nodes of a node are ordered such that the child node that has a descendent leaf node with the highest probability is to the left of the other child nodes and wherein the generating of an encoded pronunciation entry for each leaf node of s the pronunciation prefix tree includes performing a depth-first, left-to-right traversal of the pronunciation prefix tree.
Claim 43
Dependent Claim
64 words
The computer-readable medium of claim 36, including generating the list of phonemes by: generating a unigram pronunciation prefix tree; assigning a unique identifier to each node of the generated unigram pronunciation prefix tree; and for each word, storing the unique identifier for each node on the path from the root node of the unigram pronunciation prefix tree to the leaf node representing that word.
Claim 44
Dependent Claim
31 words
The computer-readable medium of claim 36 wherein the assigning of unique identifiers assigns sequential identifiers to the nodes as visited in a breadth-first, left-to-right traversal of the unigram pronunciation prefix tree.
Claim 45
Dependent Claim
17 words
The computer-readable medium of claim 36 wherein the pronunciation prefix tree is a bigram pronunciation prefix tree.
Claim 46
Dependent Claim
17 words
The computer-readable medium of claim 36 wherein the pronunciation prefix tree is a trigram pronunciation prefix tree.
Claim 47
Dependent Claim
22 words
The computer-readable medium of claim 36 wherein the pronunciation prefix tree is an n-gram pronunciation prefix tree, where n is any length.
Claim 48
Dependent Claim
23 words
The computer-readable medium of claim 36 wherein the probability in each non-leaf node is set to the maximum probability of its child nodes.
Claim 49
Dependent Claim
25 words
The computer-readable medium of claim 36 wherein the probability in each non-leaf node is set to the sum of the probability of its child nodes.
Claim 50
Dependent Claim
37 words
The computer-readable medium of claim 36 wherein each node has a depth within the pronunciation prefix tree and wherein the encoded pronunciation entry contains the depth of the nearest ancestor node with a factor less than 1.0.
Claim 51
Dependent Claim
12 words
The computer-readable medium of claim 36 wherein the predefined factor is 1.0.
Claim 52
Dependent Claim
116 words
A computer system for encoding a tree, the tree having a plurality of nodes, the tree having a root node and leaf nodes, each leaf node having a value, the computer system comprising: a path listing with an identification of the nodes of each path from a root node to a leaf node; means for setting a factor of each node to a value of the node divided by a value of the parent node of the node; and means for generating an encoded entry for each leaf node of the tree, the encoded entry identifying the leaf node and containing the factor of a nearest ancestor node with a factor other than a predefined factor.
Claim 53
Dependent Claim
116 words
A computer system for encoding a tree, the tree having a plurality of nodes, the tree having a root node and leaf nodes, each leaf node having a value, the computer system comprising: a path listing with an identification of the nodes of each path from a root node to a leaf node; means for setting a factor of each node to a value of the node divided by a value of the parent node of the node; and means for generating an encoded entry for each leaf node of the tree, the encoded entry identifying the leaf node and containing the factor of a nearest ancestor node with a factor other than a predefined factor.
Claim 54
Dependent Claim
20 words
The computer system of claim 47 wherein the tree can be regenerated from the encoded entries and the path listings.
Claim 55
Dependent Claim
34 words
The computer system of claim 47 wherein each node has a depth within the tree and wherein the encoded entry contains the depth of the nearest ancestor node with a factor less than 1.0.
Claim 56
Dependent Claim
50 words
The method of claim 49, including means for, after generating the encoded entries, identifying the nodes at a certain depth within the tree by, for each encoded entry, selecting the identification of the node at the certain depth in the list for the leaf node identified by the encoded entry.
Claim 57
Dependent Claim
18 words
The computer system of claim 50 wherein the certain depth is used as an index into the list.
Claim 58
Dependent Claim
34 words
The computer system of claim 50 wherein the tree is a bigram pronunciation prefix tree and the identifying of the nodes at a certain depth is performed during recognition of a sequence of phonemes.
Claim 59
Dependent Claim
14 words
The computer system of claim 47 wherein the tree is a pronunciation prefix tree.
Claim 60
Dependent Claim
55 words
A computer system for recognizing speech comprising: a linear encoder for linearly encoding a pronunciation prefix tree; a phoneme recognizer for receiving speech to be recognized and identifying phonemes that compose the received speech; and recognizer for identifying the words which the identified phonemes correspond using probabilities encoded in the linearly encoded pronunciation prefix tree.
Claim 61
Dependent Claim
55 words
A computer system for recognizing speech comprising: a linear encoder for linearly encoding a pronunciation prefix tree; a phoneme recognizer for receiving speech to be recognized and identifying phonemes that compose the received speech; and recognizer for identifying the words which the identified phonemes correspond using probabilities encoded in the linearly encoded pronunciation prefix tree.
Claim 62
Dependent Claim
141 words
The computer system of claim 54 wherein the pronunciation prefix tree has plurality of nodes, each non-root and non-leaf node representing a phoneme, each leaf node representing a word formed by the phonemes represented by the non-leaf nodes in a path from the root node to the leaf node, each leaf node having a probability, by: setting a probability of each non-leaf node to a probability based on the probability of its child nodes; setting a factor of each node to the probability of the node divided by the probability of the parent node of the node; and generating an encoded pronunciation entry for each leaf node of the pronunciation prefix tree, the encoded pronunciation entry indicating the word represented by the leaf node and containing the factor of a nearest ancestor node with a factor other than a predefined factor.
Claim 63
Dependent Claim
67 words
The computer system of claim 55 wherein child nodes of a node are ordered such that the child node that has a descendent leaf node with the highest probability is to the left of the other child nodes and wherein the generating of an encoded pronunciation entry for each leaf node of the pronunciation prefix tree includes performing a depth-first, left-to-right traversal of the pronunciation prefix tree.
Claim 64
Dependent Claim
67 words
The computer system of claim 55 wherein the linear encoder creates a tree node dictionary by: generating a unigram pronunciation prefix tree; assigning a unique identifier to each node of the generated unigram pronunciation prefix tree; and for each word, storing the unique identifier for each node on the path from the root node of the unigram pronunciation prefix tree to the leaf node representing that word.
Claim 65
Dependent Claim
31 words
The computer system of claim 57 wherein the assigning of unique identifiers assigns sequential identifiers to the nodes as visited in a breadth-first, left-to-right traversal of the unigram pronunciation prefix tree.
Claim 66
Dependent Claim
17 words
The computer system of claim 55 wherein the pronunciation prefix tree is a bigram pronunciation prefix tree.
Claim 67
Dependent Claim
17 words
The computer system of claim 55 wherein the pronunciation prefix tree is a trigram pronunciation prefix tree.
Claim 68
Dependent Claim
22 words
The computer system of claim 55 wherein the pronunciation prefix tree is an n-gram pronunciation prefix tree, where n is any length.
Claim 69
Dependent Claim
23 words
The computer system of claim 55 wherein the probability in each non-leaf node is set to the maximum probability of its child nodes.
Claim 70
Dependent Claim
25 words
The computer system of claim 55 wherein the probability in each non-leaf node is set to the sum of the probability of its child nodes.
Claim 71
Dependent Claim
37 words
The computer system of claim 55 wherein each node has a depth within the pronunciation prefix tree and wherein the encoded pronunciation entry contains the depth of the nearest ancestor node with a factor less than 1.0.
Claim 72
Dependent Claim
12 words
The computer system of claim 55 wherein the predefined factor is 1.0.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-05-25 | 2001-11-24 | 2002-05-26 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-05-25 | 2005-11-24 | 2006-05-26 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-05-25 | 2009-11-24 | 2010-05-26 | $7700.00 | Window Closed / Lapsed |