Method and system for encoding pronunciation prefix trees

• US 5,758,024 A
• Filed: 06/25/1996
• Issued: 05/26/1998
• Est. Priority Date: 06/25/1996
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Alleva, Fileno A.
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): Wieland, Susan
• Application Number:
  US08/674,656
• Time in Patent Office: 700 Days
• Field of Search: 395/2.6, 395/2.63, 395/2.64, 395/2.65
• US Class Current: 704/254
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/279 Recognition of textual entities
• CPC Class Codes: G10L 15/187 Phonemic context, e.g. pronunciation rules, phonotactical constraints or phoneme n-grams

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.

Claims

1. 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.

2. 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.

3. 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.

4. 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.

5. The method of claim 1 wherein the pronunciation prefix tree is a bigram pronunciation prefix tree.

6. The method of claim 1 wherein the pronunciation prefix tree is a trigram pronunciation prefix tree.

7. The method of claim 1 wherein the pronunciation prefix tree is an n-gram pronunciation prefix tree, where n is any length.

8. The method of claim 1 wherein the probability in each non-leaf node is set to the maximum probability of its child nodes.

9. 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.

10. 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.

11. 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.

12. 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.

13. 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.

14. 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.

15. The method of claim 11 wherein the pronunciation prefix tree is a bigram pronunciation prefix tree.

16. The method of claim 11 wherein the pronunciation prefix tree is a trigram pronunciation prefix tree.

17. The method of claim 11 wherein the pronunciation prefix tree is an n-gram pronunciation prefix tree, where n is any length.

18. The method of claim 11 wherein the probability in each non-leaf node is set to the maximum probability of its child nodes.

19. 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.

20. 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.

21. The method of claim 11 wherein the predefined factor is 1.0.

22. 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.

23. 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.

24. The method of claim 22 wherein the pronunciation prefix tree is a bigram pronunciation prefix tree.

25. The method of claim 22 wherein the pronunciation prefix tree is a trigram pronunciation prefix tree.

26. The method of claim 22 wherein the pronunciation prefix tree is an n-gram pronunciation prefix tree, where n is any length.

27. 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.

28. 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.

29. 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.

30. The method of claim 29 wherein the tree can be regenerated from the encoded entries and the lists of the nodes in the paths.

31. 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.

32. 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.

33. The method of claim 32 wherein the certain depth is used as an index into the list.

34. 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.

35. The method of claim 29 wherein the tree is a pronunciation prefix tree.

36. 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.

37. 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.

38. 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.

39. 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.

40. The computer-readable medium of claim 36 wherein the pronunciation prefix tree is a bigram pronunciation prefix tree.

41. The computer-readable medium of claim 36 wherein the pronunciation prefix tree is a trigram pronunciation prefix tree.

42. The computer-readable medium of claim 36 wherein the pronunciation prefix tree is an n-gram pronunciation prefix tree, where n is any length.

43. 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.

44. 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.

45. 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.

46. The computer-readable medium of claim 36 wherein the predefined factor is 1.0.

47. 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.

48. The computer system of claim 47 wherein the tree can be regenerated from the encoded entries and the path listings.

49. 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.

50. 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.

51. The computer system of claim 50 wherein the certain depth is used as an index into the list.

52. 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.

53. The computer system of claim 47 wherein the tree is a pronunciation prefix tree.

54. 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.

55. 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.

56. 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.

57. 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.

58. 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.

59. The computer system of claim 55 wherein the pronunciation prefix tree is a bigram pronunciation prefix tree.

60. The computer system of claim 55 wherein the pronunciation prefix tree is a trigram pronunciation prefix tree.

61. The computer system of claim 55 wherein the pronunciation prefix tree is an n-gram pronunciation prefix tree, where n is any length.

62. The computer system of claim 55 wherein the probability in each non-leaf node is set to the maximum probability of its child nodes.

63. 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.

64. 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.

65. The computer system of claim 55 wherein the predefined factor is 1.0.