Unsupervised data-driven pronunciation modeling

• US 7,047,193 B1
• Filed: 09/13/2002
• Issued: 05/16/2006
• Est. Priority Date: 09/13/2002
• Status: Expired due to Fees

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Bellegarda, Jerome R.
• Primary Examiner(s): Abebe, Daniel
• Assistant Examiner(s): Opsasnick, Michael N
• Application Number:
  US10/243,017
• Time in Patent Office: 1,341 Days
• Field of Search: 704/254
• US Class Current: 704/254
• CPC Class Codes: G10L 15/063 Training
• CPC Class Codes: G10L 15/187 Phonemic context, e.g. pronunciation rules, phonotactical constraints or phoneme n-grams

Abstract

Pronunciation for an input word is modeled by generating a set of candidate phoneme strings having pronunciations close to the input word in an orthographic space. Phoneme sub-strings in the set are selected as the pronunciation. In one aspect, a first closeness measure between phoneme strings for words chosen from a dictionary and contexts within the input word is used to determine the candidate phoneme strings. The words are chosen from the dictionary based on a second closeness measure between a representation of the input word in the orthographic space and orthographic anchors corresponding to the words in the dictionary. In another aspect, the phoneme sub-strings are selected by aligning the candidate phoneme strings on common phoneme sub-strings to produce an occurrence count, which is used to choose the phoneme sub-strings for the pronunciation.

Claims

1. A computerized method comprising:

generating a set of candidate phoneme strings having pronunciations close to an input word in an orthographic space based on a first closeness measure between phoneme strings for words chosen from a dictionary and contexts within the input word, the choice of words from the dictionary based on a second closeness measure between a representation of the input word in the orthographic space and orthographic anchors corresponding to the words in the dictionary; and

selecting phoneme sub-strings from the set as a pronunciation for the input word.

2. The computerized method of claim 1 further comprising:

creating the representation of the input word in the orthographic space.

3. The computerized method of claim 2, wherein the representation of the input word and the orthographic anchors are feature vectors.

4. The computerized method of claim 3, wherein the feature vector {overscore ({tilde over (v)}_p for the input word {tilde over (w)}_p is calculated as

${\widetilde{\stackrel{\_}{v}}}_p={\tilde{v}}_p$

S = w ~ p T ⁢

U

where, S is a singular diagonal matrix, U is a left singular matrix, {tilde over (v)}_p is a vector within a right singular matrix V^T corresponding to the input word, and ^T denotes matrix transposition.

5. The computerized method of claim 3, wherein creating the representation comprises:

mapping the input word onto the feature vector in the orthographic vector space.

6. The computerized method of claim 5, wherein mapping the input word comprises:

weighing occurrences of each of a set of letter patterns within the input word.

7. The computerized method of claim 6, wherein weighing occurrences comprises:

calculating a weight for the input word {tilde over (w)}_p as

${\tilde{w}}_p=\left(1-{\mathrm{\epsilon <br><br>}}_i\right)<br><br>\frac{c_{i,j}}{n_j}$

where c_i,j is the number of times letter pattern t_i occurs in the input word {tilde over (w)}_p, n_j is the total number of letter patterns present in this word, and ε

_i is the normalized entropy of t_i in the words of the dictionary.

8. The computerized method of claim 1, wherein choosing the words comprises:

filtering the orthographic anchor for each word against a pre-determined closeness threshold; and

forming an orthographic neighborhood from words corresponding to orthographic anchors that meet the threshold.

9. The computerized method of claim 8, wherein choosing the words further comprises:

ranking each word based on the second closeness measure.

10. The computerized method of claim 8 further comprising:

creating a pronunciation neighborhood from the phoneme strings for the words in the orthographic neighborhood, the candidate phoneme strings being generated from the pronunciation neighborhood.

11. The computerized method of claim 8, wherein the first closeness measure is a distance between an orthographic anchor corresponding to a word in the orthographic neighborhood and a context.

12. The computerized method of claim 1, wherein the second closeness measure comprises the cosine of the angle between the representation of the input word and an orthographic anchor.

13. The computerized method of claim 12, wherein the cosine K between the representation of the input word {overscore ({tilde over (v)}_p and an orthographic anchor {overscore (v)}_j is calculated using

$K=\left({\widetilde{\stackrel{\_}{v}}}_p,{\stackrel{\_}{v}}_j\right)=\cos$

( v ~ p ⁢

S , v j ⁢

S ) = v ~ p ⁢

S 2 ⁢

v j T 

v ~ p ⁢

S 

⁢



v j ⁢

S 

for any 1≦

j≦

M, where M is the number of words in the dictionary, S is a singular diagonal matrix, {tilde over (v)}_p is a column vector within a right singular matrix V^T corresponding to the input word, v_j is a column vector in V for the word corresponding to the orthographic anchor {overscore (v)}_j, and ^T denotes matrix transposition.

14. The computerized method of claim 1, wherein the contexts are letter-based strings.

15. The computerized method of claim 14, wherein a length for the contexts and a length for the letter patterns are the same length and the first and second closeness measures are the same closeness measure.

16. The computerized method of claim 1 further comprising:

mapping the words in the dictionary and a set of letter patterns that are characteristic of the words into the orthographic space to create the orthographic anchors.

17. The computerized method of claim 16, wherein mapping the words comprises:

creating a matrix of feature vectors from the letter patterns and the words;

decomposing the matrix into row vectors and column vectors; and

selecting vectors from one of the row vectors and column vectors as the orthographic anchors.

18. The computerized method of claim 16 further comprising:

determining the letter patterns based on the words in the dictionary.

19. The computerized method of claim 1, wherein the contexts are of different lengths.

20. The computerized method of claim 1, wherein selecting phoneme sub-strings comprises:

aligning the candidate phoneme strings on common phoneme sub-strings to produce occurrence counts; and

choosing the phoneme sub-strings for the pronunciation based on the occurrence counts.

21. The computerized method of claim 20, wherein aligning candidate phoneme strings comprises:

calculating a minimum cost alignment A(k, l) between two candidate phoneme strings φ

₁ . . . φ

_k . . . φ

_K and ψ

₁ . . . ψ

_l . . . ψ

_L having a length K and L respectively.

22. The computerized method of claim 21, wherein the minimum cost alignment is calculated as

A(k, l)=min {A(k−

1, l−

1)+C(k, l),G(i, k), H(j, l)}

where C(k, l) is the cost of substituting phoneme ψ

_l for phoneme φ

_k, g(i, k) is the cost of a gap φ

_i . . . φ

_k, h(j, l) is the cost of a gap ψ

_j . . . ψ

_l,

$G<br><br>\left(i,k\right)=\underset{0\le <br><br>i\le <br><br>k-1}{\min }<br><br>\left\{A<br><br>\left(i,l\right)+g<br><br>\left(i,k\right)\right\},$

and

$H<br><br>\left(j,l\right)=\underset{0\le <br><br>j\le <br><br>l-1}{\min }<br><br>\left\{A<br><br>\left(k,j\right)+h<br><br>\left(j,l\right)\right\},$

with initial conditions A(k,

     0)=h(0, k), 1≦

k≦

K and A(0, l)=g(0, l), 1≦

l≦

L.

23. The computerized method of claim 20, wherein aligning the candidate phoneme strings produces an occurrence count for each context within the input word.

24. The computerized method of claim 23 further comprising:

merging the chosen phoneme sub-strings for adjacent contexts when the phoneme sub-strings overlap.

25. A machine-readable medium having instructions to cause a machine to perform a method comprising:

generating a set of candidate phoneme strings having pronunciations close to an input word in an orthographic space based on a first closeness measure between phoneme strings for words chosen from a dictionary and contexts within the input word, the choice of words from the dictionary based on a second closeness measure between a representation of the input word in the orthographic space and orthographic anchors corresponding to the words in the dictionary; and

selecting phoneme sub-strings from the set as a pronunciation for the input word.

26. The machine-readable medium of claim 25, wherein the method further comprises:

creating the representation of the input word in the orthographic space.

27. The machine-readable medium of claim 26, wherein the representation of the input word and the orthographic anchors are feature vectors.

28. The machine-readable medium of claim 27, wherein the feature vector {overscore ({tilde over (v)}_p for the input word {tilde over (w)}_p is calculated as

${\widetilde{\stackrel{\_}{v}}}_p={\tilde{v}}_p$

S = w ~ p T ⁢

U

where, S is a singular diagonal matrix, U is a left singular matrix, {tilde over (v)}_p is a vector within a right singular matrix V^T corresponding to the input word, and ^T denotes matrix transposition.

29. The machine-readable medium of claim 27, wherein creating the representation comprises:

mapping the input word onto the feature vector in the orthographic vector space.

30. The machine-readable medium of claim 29, wherein mapping the input word comprises:

weighing occurrences of each of a set of letter patterns within the input word.

31. The machine-readable medium of claim 30, wherein weighing occurrences comprises calculating a weight for the input word {tilde over (w)}_p as

${\tilde{w}}_p=(1-{\epsilon }_{}$

i ) ⁢

c i , j n j

where c_i,j is the number of times letter pattern t_i occurs in the input word {tilde over (w)}_p, n_j is the total number of letter patterns present in this word, and ε

_i is the normalized entropy of t_i in the words of the dictionary.

32. The machine-readable medium of claim 25, wherein choosing the words comprises:

filtering the orthographic anchor for each word against a pre-determined closeness threshold; and

forming an orthographic neighborhood from words corresponding to orthographic anchors that meet the threshold.

33. The machine-readable medium of claim 32, wherein choosing the words further comprises:

ranking each word based on the second closeness measure.

34. The machine-readable medium of claim 32, wherein the method further comprises:

creating a pronunciation neighborhood from the phoneme strings for the words in the orthographic neighborhood, the candidate phoneme strings being generated from the pronunciation neighborhood.

35. The machine-readable medium of claim 32, wherein the first closeness measure is a distance between an orthographic anchor corresponding to a word in the orthographic neighborhood and a context.

36. The machine-readable medium of claim 25, wherein the second closeness measure comprises the cosine of the angle between the representation of the input word and an orthographic anchor.

37. The machine-readable medium of claim 36, wherein the cosine K between the representation of the input word {overscore ({tilde over (v)}_p and an orthographic anchor {overscore (v)}_j is calculated using

$K=\left({\widetilde{\stackrel{\_}{v}}}_p,{\stackrel{\_}{v}}_j\right)=\cos$

( v ~ p ⁢

S , v j ⁢

S ) = v ~ p ⁢

S 2 ⁢

v j T 

v ~ p ⁢

S 

⁢



v j ⁢

S 

for any 1≦

j≦

M, where M is the number of words in the dictionary, S is a singular diagonal matrix, {tilde over (v)}_p is a column vector within a right singular matrix V^T corresponding to the input word, v_j is a column vector in V for the word corresponding to the orthographic anchor {overscore (v)}_j, and ^T denotes matrix transposition.

38. The machine-readable medium of claim 25, wherein the contexts are letter-based strings.

39. The machine-readable medium of claim 38, wherein a length for the contexts and a length for the letter patterns are the same length and the first and second closeness measures are the same closeness measure.

40. The machine-readable medium of claim 25, wherein the method further comprises:

mapping words in a dictionary and a set of letter patterns that are characteristic of the words into an orthographic space to create orthographic anchors.

41. The machine-readable medium of claim 40, wherein mapping words comprises:

creating a matrix of feature vectors from the letter patterns and the words;

decomposing the matrix into row vectors and column vectors; and

selecting vectors from one of the row vectors and column vectors as the orthographic anchors.

42. The machine-readable medium of claim 41, wherein the method further comprises:

determining the letter patterns based on the words in the dictionary.

43. The machine-readable medium of claim 25, wherein the contexts are of different lengths.

44. The machine-readable medium of claim 25, wherein selecting phoneme sub-strings comprises:

aligning the candidate phoneme strings on common phoneme sub-strings to produce occurrence counts; and

choosing the phoneme sub-strings for the pronunciation based on the occurrence counts.

45. The machine-readable medium of claim 44, wherein aligning candidate phoneme strings comprises:

calculating a minimum cost alignment A(k, l) between two candidate phoneme strings φ

₁ . . . φ

_k . . . φ

_K and ψ

₁ . . . ψ

_l . . . ψ

_L having a length K and L respectively.

46. The machine-readable medium of claim 45, wherein the minimum cost alignment is calculated as

A(k, l)=min {A(k−

1, l−

1)+C(k, l), G(i, k), H(j, l)}

where C(k, l) is the cost of substituting phoneme ψ

_l for phoneme φ

_k, g(i, k) is the cost of a gap φ

_i . . . φ

_k, h(j, l) is the cost of a gap ψ

_j . . . ψ

_l,

$G<br><br>\left(i,k\right)=\underset{0\le <br><br>i\le <br><br>k-1}{\min }<br><br>\left\{A<br><br>\left(i,l\right)+g<br><br>\left(i,k\right)\right\},$

and

$H<br><br>\left(j,l\right)=\underset{0\le <br><br>j\le <br><br>l-1}{\min }<br><br>\left\{A<br><br>\left(k,j\right)+h<br><br>\left(j,l\right)\right\},$

with initial conditions A(k,

     0)=h(0, k), 1≦

k≦

K and A(0, l)=g(0, l), 1≦

l≦

L.

47. The machine-readable medium of claim 44, wherein aligning the candidate phoneme strings produces an occurrence count for each context within the input word.

48. The machine-readable medium of claim 47, wherein the method further comprises:

merging the chosen phoneme sub-strings for adjacent contexts when the phoneme sub-strings overlap.

49. A system comprising:

a processing unit coupled to a memory through a bus; and

a pronunciation modeling process executed from the memory by the processing unit to cause the processing unit to generate a set of candidate phoneme strings having pronunciations close to an input word in an orthographic space based on a first closeness measure between phoneme strings for words chosen from a dictionary and contexts within the input word, the choice of words from the dictionary based on a second closeness measure between a representation of the input word in the orthographic space and orthographic anchors corresponding to the words in the dictionary, and select a common phoneme sub-string as a pronunciation for each context based on occurrences of the common sub-strings for the context.

50. The system of claim 49, wherein the pronunciation modeling process further causes the processing unit to create the representation of the input word in the orthographic space.

51. The system of claim 50, wherein the representation of the input word and the orthographic anchors are feature vectors.

52. The system of claim 51, wherein the feature vector for the input word {overscore ({tilde over (v)}_p is calculated as

${\widetilde{\stackrel{\_}{v}}}_p={\tilde{v}}_p$

S = w ~ p T ⁢

U

where, S is a singular diagonal matrix, U is a left singular matrix, {tilde over (v)}_p is a vector within a right singular matrix V^T correspond to the input word, and ^T denotes matrix transposition.

53. The system of claim 51, wherein the pronunciation modeling process further causes the processing unit, when creating the representation, to map the input word onto the feature vector in the orthographic vector space.

54. The system of claim 53, wherein the pronunciation modeling process further causes the processing unit, when mapping the input word, to weigh occurrences of each of a set of letter patterns within the input word.

55. The system of claim 54, wherein the pronunciation modeling process further causes the processing unit, when weighing occurrences, to calculate a weight for the input word {tilde over (w)}_p as

${\tilde{w}}_p=(1-{\epsilon }_{}$

i ) ⁢

c i , j n j

where c_i,j is the number of times letter pattern t_i occurs in the input word {tilde over (w)}_p, n_j is the total number of letter patterns present in this word, and ε

_i is the normalized entropy of t_i in the words of the dictionary.

56. The system of claim 49, wherein the pronunciation modeling process further causes the processing unit, when choosing the words, to filter the orthographic anchor for each word against a pre-determined closeness threshold and form an orthographic neighborhood from words corresponding to orthographic anchors that meet the threshold.

57. The system of claim 56, wherein the pronunciation modeling process further causes the processing unit, when choosing the words, to rank each word based on the second closeness measure.

58. The system of claim 56, wherein the pronunciation modeling process further causes the processing unit to create a pronunciation neighborhood from the phoneme strings for the words in the orthographic neighborhood, the candidate phoneme strings being generated from the pronunciation neighborhood.

59. The system of claim 56, wherein the first closeness measure is a distance between an orthographic anchor corresponding to a word in the orthographic neighborhood and a context.

60. The system of claim 49, wherein the second closeness measure comprises the cosine of the angle between the representation of the input word and an orthographic anchor.

61. The system of claim 60, wherein the cosine K between the representation of the input word {overscore ({tilde over (v)}_p and an orthographic anchor {overscore (v)}_j is calculated using

$K=\left({\widetilde{\stackrel{\_}{v}}}_p,{\stackrel{\_}{v}}_j\right)=\cos$

( v ~ p ⁢

S , v j ⁢

S ) = v ~ p ⁢

S 2 ⁢

v j T 

v ~ p ⁢

S 

⁢



v j ⁢

S 

for any 1≦

j≦

M, where M is the number of words in the dictionary, S is a singular diagonal matrix, {tilde over (v)}_p is a column vector within a right singular matrix V^T correspond to the input word, v_j is a column vector in V for the word correspond to the orthographic anchor {overscore (v)}_j and ^T denotes matrix transposition.

62. The system of claim 49, wherein the contexts in the input word are letter-based strings.

63. The system of claim 62, wherein a length for the contexts and a length for the letter patterns are the same length and the first and second closeness measures are the same closeness measure.

64. The system of claim 49, wherein the pronunciation modeling process further causes the processing unit to map the words in the dictionary and a set of letter patterns that are characteristic of the words into the orthographic space to create the orthographic anchors.

65. The system of claim 64, wherein the pronunciation modeling process further causes the processing unit, when mapping the words, to create a matrix of feature vectors from the letter patterns and the words, decompose the matrix into row vectors and column vectors, and select vectors from one of the row vectors and column vectors as the orthographic anchors.

66. The system of claim 64, wherein the pronunciation modeling process further causes the processing unit to determine the letter patterns based on the words in the dictionary.

67. The system of claim 49, wherein the contexts are of different lengths.

68. The system of claim 49, wherein the pronunciation modeling process further causes the processing unit, when selecting phoneme sub-strings, to align the candidate phoneme strings on common phoneme sub-strings to produce occurrence counts, and choose the phoneme sub-strings for the pronunciation based on the occurrence counts.

69. The system of claim 68, wherein the pronunciation modeling process further causes the processing unit, when aligning candidate phoneme strings, to calculate a minimum cost alignment A(k, l) between two candidate phoneme strings φ

₁ . . . φ

_k . . . φ

_K and ψ

₁ . . . ψ

_l . . . ψ

_L having a length K and L respectively.

70. The system of claim 69, wherein the minimum cost alignment is calculated as

A(k, l)=min {A(k−

1, l−

1)+C(k, l)G(i, k), H(j, l)}

where C(k, l) is the cost of substituting phoneme ψ

_l for phoneme φ

_k, g(i, k) is the cost of a gap φ

_i . . . φ

_k, h(j, k) is the cost of a gap ψ

_j . . . ψ

_l,

$G<br><br>\left(i,k\right)=\underset{0\le <br><br>i\le <br><br>k-1}{\min }<br><br>\left\{A<br><br>\left(i,l\right)+g<br><br>\left(i,k\right)\right\},$

and

$H<br><br>\left(j,l\right)=\underset{0\le <br><br>j\le <br><br>l-1}{\min }<br><br>\left\{A<br><br>\left(k,j\right)+h<br><br>\left(j,l\right)\right\},$

with initial conditions A(k,

     0)=h(0, k), 1≦

k≦

K and A(0, l)=g(0, l), 1≦

l≦

L.

71. The system of claim 68, wherein the pronunciation modeling process further causes the processing unit, when aligning candidate phoneme strings, to produce an occurrence count for each context within the input word.

72. The system of claim 71, wherein the pronunciation modeling process further causes the processing unit to merge the chosen phoneme sub-strings for adjacent contexts when the phoneme sub-strings overlap.

73. An apparatus comprising:

means for generating a set of candidate phoneme strings having pronunciations close to an input word in an orthographic space based on a first closeness measure between phoneme strings for words chosen from a dictionary and contexts within the input word, the choice of words from the dictionary based on a second closeness measure between a representation of the input word in the orthographic space and orthographic anchors corresponding to the words in the dictionary; and

means for selecting phoneme sub-strings from the set as a pronunciation for the input word.

74. The apparatus of claim 73, wherein the means for generating further comprises:

means for creating the representation of the input word in the orthographic space.

75. The apparatus of claim 74, wherein the representation of the input word and the orthographic anchors are feature vectors.

76. The apparatus of claim 75, wherein the means for creating the representation calculates the feature vector {overscore ({tilde over (v)}_p for the input word {tilde over (w)}_p as

${\widetilde{\stackrel{\_}{v}}}_p={\tilde{v}}_p$

S = w ~ p T ⁢

U

where, S is a singular diagonal matrix, U is a left singular matrix, {tilde over (v)}_p is a vector within a right singular matrix V^T corresponding to the input word, and ^T denotes matrix transposition.

77. The apparatus of claim 75 wherein the means for creating the representation maps the input word onto the feature vector in the orthographic vector space.

78. The apparatus of claim 77, wherein the means for creating the representation further weighs occurrences of each of a set of letter patterns within the input word.

79. The apparatus of claim 78, wherein weighing occurrences comprises:

calculating a weight for the input word {tilde over (w)}_p as

${\tilde{w}}_p=\left(1-{\mathrm{\epsilon <br><br>}}_i\right)<br><br>\frac{c_{i,j}}{n_j}$

where c_i,j is the number of times letter pattern t_i occurs in the input word {tilde over (w)}_p, n_j is the total number of letter patterns present in this word, and ε

_i is the normalized entropy of t_i in the words of the dictionary.

80. The apparatus of claim 73, wherein the means for generating further comprises:

means for filtering the orthographic anchor for each word against a pre-determined closeness threshold to form an orthographic neighborhood from words corresponding to orthographic anchors that meet the threshold.

81. The apparatus of claim 80, wherein the means for generating further comprises:

means for ranking each word based on the second closeness measure.

82. The apparatus of claim 80, wherein the means for generating further comprises:

means for creating a pronunciation neighborhood from the phoneme strings for the words in the orthographic neighborhood, the candidate phoneme strings being generated from the pronunciation neighborhood.

83. The apparatus of claim 80, wherein the first closeness measure is a distance between an orthographic anchor corresponding to a word in the orthographic neighborhood and a context.

84. The apparatus of claim 73, wherein the second closeness measure comprises the cosine of the angle between the representation of the input word and an orthographic anchor.

85. The apparatus of claim 84, wherein the cosine K between the representation of the input word {overscore ({tilde over (v)}_p and an orthographic anchor {overscore (v)}_j is calculated using

$K=\left({\widetilde{\stackrel{\_}{v}}}_p,{\stackrel{\_}{v}}_j\right)=\cos$

( v ~ p ⁢

S , v j ⁢

S ) = v ~ p ⁢

S 2 ⁢

v j T 

v ~ p ⁢

S 

⁢



v j ⁢

S 

for any A1≦

j≦

M, where M is the number of words in the dictionary, S is a singular diagonal matrix, {tilde over (v)}_p is a column vector within a right singular matrix V^T corresponding to the input word, v_j is a column vector in V for the word corresponding to the orthographic anchor {overscore (v)}_j, and ^T denotes matrix transposition.

86. The apparatus of claim 73, wherein the contexts are letter-based strings.

87. The apparatus of claim 86, wherein a length for the contexts and a length for the letter patterns are the same length and the first and second closeness measures are the same closeness measure.

88. The apparatus of claim 73 further comprising:

means for mapping the words in the dictionary and a set of letter patterns that are characteristic of the words into the orthographic space to create the orthographic anchors.

89. The apparatus of claim 88, wherein the means for mapping further comprises:

means for creating a matrix of feature vectors from the letter patterns and the words; and

means for decomposing the matrix into row vectors and column vectors, vectors from one of the row vectors and column vectors being selected as the orthographic anchors.

90. The apparatus of claim 88, further comprising:

means for determining the letter patterns based on the words in the dictionary.

91. The apparatus of claim 73, wherein the contexts are of different lengths.

92. The apparatus of claim 73, wherein the means for selecting phoneme sub-strings comprises:

means for aligning the candidate phoneme strings on common phoneme sub-strings to produce occurrence counts; and

means for choosing the phoneme sub-strings for the pronunciation based on the occurrence counts.

93. The apparatus of claim 92, wherein the means for aligning candidate phoneme strings comprises:

means for calculating a minimum cost alignment A(k, l) between two candidate phoneme strings φ

₁ . . . φ

_k . . . φ

_K and ψ

₁ . . . ψ

_l . . . ψ

_L having a length K and L respectively.

94. The apparatus of claim 93, wherein the minimum cost alignment is calculated as

A(k, l)=min {A(k−

A1, l−

A1)+C(k, l)G(i, k), H(j, l)}

where C(k, l) is the cost of substituting phoneme ψ

_l for phoneme φ

_k, g(i, k) is the cost of a gap φ

_i . . . φ

_k, is the cost of a gap ψ

_j . . . ψ

_l,

$G<br><br>\left(i,k\right)=\underset{0\le <br><br>i\le <br><br>k-1}{\min }<br><br>\left\{A<br><br>\left(i,l\right)+g<br><br>\left(i,k\right)\right\},$

and

$H<br><br>\left(j,l\right)=\underset{0\le <br><br>j\le <br><br>l-1}{\min }<br><br>\left\{A<br><br>\left(k,j\right)+h<br><br>\left(j,l\right)\right\},$

with initial conditions A(k,

     0)=h(0, k), A1≦

k≦

K and A(0, l)=g(0, l), A1≦

l≦

L.

95. The apparatus of claim 92, wherein the means for aligning the candidate phoneme strings produces an occurrence count for each context within the input word.

96. The apparatus of claim 95 further comprising:

means for merging the chosen phoneme sub-strings for adjacent contexts when the phoneme sub-strings overlap.