Check-sum based method and apparatus for performing speech recognition

• US 6,122,612 A
• Filed: 11/20/1997
• Issued: 09/19/2000
• Est. Priority Date: 11/20/1997
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Goldberg, Randy G.
• Primary Examiner(s): Hudspeth, David R.
• Assistant Examiner(s): MCFADDEN, SUSAN IRIS
• Application Number:
  US08/975,589
• Time in Patent Office: 1,034 Days
• Field of Search: 704/231, 704/255, 704/256, 704/275, 704/272, 704/236, 704/243, 704/244, 704/245
• US Class Current: 704/231
• CPC Class Codes: G10L 15/08 Speech classification or search

Abstract

A method and apparatus for matching at least a first input identifier with a reference identifier. A user provides an input identifier into a system, and the system produces a recognized identifier based on the input identifier. The system of the present invention perform a check-sum operation to determine whether the recognized identifier was recognized correctly. If the check-sum operation reveals that the recognized identifier is incorrect, the system of the present invention generates a plurality of substitute identifiers. The substitute identifiers are compared to a set of pre-stored reference identifiers. If a match is found between a reference identifier and a substitute identifier, the matched reference identifier is selected as corresponding to the input identifier provided by the user.

Claims

1. A method of recognizing at least one input identifier, comprising:

a) providing a recognized identifier based on the input identifier;

b) determining whether the recognized identifier was recognized correctly by determining whether an information content of the recognized identifier corresponds to an information content of the input identifier;

c) generating a set of substitute identifiers only if the recognized identifier is incorrect, each one of the substitute identifiers being generated in accordance with a character arrangement that corresponds to a character arrangement of at least one of the input identifier and the recognized identifier;

d) determining which, if any, substitute identifiers match at least one member of a set of reference identifiers; and

e) selecting one of the matched reference identifiers as corresponding to the input identifier.

2. The method according to claim 1, wherein each one of the input identifier, the recognized identifier, and the substitute identifiers include at least one numeral.

3. The method according to claim 1, wherein each one of the input identifier, the recognized identifier, and the substitute identifiers include at least one alphabetical character.

4. The method according to claim 1, wherein each one of the input identifier, the recognized identifier, and the substitute identifiers include at least one numeral and at least one alphabetical character.

5. The method according to claim 1, wherein each one of the input identifier, the recognized identifier, and the substitute identifiers include at least one check-sum character and a set of non-check-sum characters, and wherein the step b) comprises:

i) determining whether the check-sum character and the non-check-sum characters of the recognized identifier correspond to a predetermined relationship;

ii) flagging the recognized identifier as incorrect if the check-sum character and the non-check-sum characters of the recognized identifier do not correspond to the predetermined relationship; and

iii) flagging the recognized identifier as correct if the check-sum character and the non-check-sum characters correspond to the predetermined relationship.

6. The method according to claim 5, wherein the check-sum character of each one of the input identifier, the recognized identifier, and the substitute identifiers comprises a check-sum digit, wherein the non-check-sum characters of each one of the input identifier, the recognized identifier, and the substitute identifiers comprise non-check-sum digits, and wherein the predetermined relationship comprises the check- sum digit of a particular identifier equaling a modulo-N sum of the non-check-sum digits of the same particular identifier, N comprising an integer greater than zero.

7. The method according to claim 6, wherein the step c) comprises:

iv) calculating a difference between the check-sum digit of the recognized identifier and the modulo-N sum of the non-check-sum digits of the recognized identifier; and

v) generating a plurality of new identifiers, each of the new identifiers having a check-sum digit and a set of non-check-sum digits, wherein the modulo-N sum of the non-check-sum digits of each new identifier equals its associated check-sum digit and wherein the modulo-N sum of the non-check-sum digits of each new identifier differs from the modulo-N sum of the non-check-sum digits of the recognized identifier by the difference calculated in step iv), the set of new identifiers corresponding to the set of substitute identifiers.

8. The method according to claim 1, wherein, if more than one of the set of substitute identifiers has a match within the set of reference identifiers, the step e) comprises prompting a user with each one of the matched reference identifiers until the user confirms that one of the matched reference identifiers corresponds to the input identifier.

43. The method according to claim 1, wherein:

the step b) comprises;

i) performing a first calculation on at least one value derived from the input identifier in order to produce a first result,

ii) performing a second calculation on at least one value derived from the recognized identifier in order to produce a second result, and

iii) determining that the recognized identifier is incorrect if the first result and the second result exhibit a predetermined relationship with respect to each other, and

the step c) comprises;

i) generating the set of substitute identifiers such that each substitute identifier exhibits the predetermined relationship with respect to the recognized identifier.

9. A method of recognizing at least one input identifier, comprising:

a) providing a recognized identifier based on the input identifier;

b) determining whether the recognized identifier was recognized correctly by determining whether an information content of the recognized identifier corresponds to an information content of the input identifier;

c) generating a set of substitute identifiers only if the recognized identifier is incorrect, each one of the substitute identifiers being generated in accordance with a character arrangement that corresponds to a character arrangement of at least one of the input identifier and the recognized identifier;

d) reducing the set of substitute identifiers by eliminating a number of the substitute identifiers from the set of substitute identifiers;

e) determining which, if any, substitute identifiers match at least one member of a set of reference identifiers; and

f) selecting one of the matched reference identifiers as corresponding to the input identifier.

10. The method according to claim 9, wherein each one of the input identifier, the recognized identifier, and the substitute identifiers include at least one numeral.

11. The method according to claim 9, wherein each one of the input identifier, the recognized identifier, and the substitute identifiers include at least one alphabetical character.

12. The method according to claim 9, wherein each one of the input identifier, the recognized identifier, and the substitute identifiers include at least one numeral and at least one alphabetical character.

13. The method according to claim 9, wherein each one of the input identifier, the recognized identifier, and the substitute identifiers include at least one check-sum character and a set of non-check-sum characters, and wherein the step b) comprises:

i) determining whether the check-sum character and the non-check-sum characters of the recognized identifier correspond to a predetermined relationship;

ii) flagging the recognized identifier as incorrect if the check-sum character and the non-check-sum characters of the recognized identifier do not correspond to the predetermined relationship; and

iii) flagging the recognized identifier as correct if the check-sum character and the non-check-sum characters correspond to the predetermined relationship.

14. The method according to claim 13, wherein the check-sum character of each one of the input identifier, the recognized identifier, and the substitute identifiers comprises a check-sum digit, wherein the non-check-sum characters of each one of the input identifier, the recognized identifier, and the substitute identifiers comprise non-check-sum digits, and wherein the predetermined relationship comprises the check- sum digit of a particular identifier equaling a modulo-N sum of the non-check-sum digits of the same particular identifier, N comprising an integer greater than zero.

15. The method according to claim 14, wherein the step c) comprises:

iv) calculating a difference between the check-sum digit of the recognized identifier and the modulo-N sum of the non-check-sum digits of the recognized identifier; and

v) generating a plurality of new identifiers, each of the new identifiers having a check-sum digit and a set of non-check-sum digits, wherein the modulo-N sum of the non-check-sum digits of each new identifier equals its associated check-sum digit and wherein the modulo-N sum of the non-check-sum digits of each new identifier differs from the modulo-N sum of the non-check-sum digits of the recognized identifier by the difference calculated in step iv), the set of new identifiers corresponding to the set of substitute identifiers.

16. The method according to claim 9, wherein the step d) comprises:

i) determining, for each substitute identifier, a recognition probability of a user having provided that substitute identifier, given the recognized identifier; and

ii) eliminating the substitute identifier from the set of substitute identifiers if the recognition probability associated with the substitute identifier is no more than a predetermined threshold.

17. The method according to claim 16, wherein a recognition probability associated with a given substitute identifier is obtained from a confusion matrix.

18. The method according to claim 9, wherein, if more than one of the reduced set of substitute identifiers has a match within the set of reference identifiers, the step f) comprises prompting a user with each one of the matched reference identifiers until the user confirms that one of the matched reference identifiers corresponds to the input identifier.

44. The method according to claim 9, wherein:

the step b) comprises;

i) performing a first calculation on at least one value derived from the input identifier in order to produce a first result,

ii) performing a second calculation on at least one value derived from the recognized identifier in order to produce a second result, and

iii) determining that the recognized identifier is incorrect if the first result and the second result exhibit a predetermined relationship with respect to each other, and

the step c) comprises;

i) generating the set of substitute identifiers such that each substitute identifier exhibits the predetermined relationship with respect to the recognized identifier.

19. An apparatus for recognizing at least one input identifier, comprising:

a) first means for providing a recognized identifier based on the input identifier;

b) first means for determining whether the recognized identifier was recognized correctly by determining whether an information content of the recognized identifier corresponds to an information content of the input identifier;

c) means for generating a set of substitute identifiers only if the recognized identifier is incorrect, each one of the substitute identifiers being generated in accordance with a character arrangement that corresponds to a character arrangement of at least one of the input identifier and the recognized identifier;

d) second means for determining which, if any, substitute identifiers match at least one member of a set of reference identifiers; and

e) means for selecting one of the matched reference identifiers as corresponding to the input identifier.

20. The apparatus according to claim 19, wherein each one of the input identifier, the recognized identifier, and the substitute identifiers include at least one numeral.

21. The apparatus according to claim 19, wherein each one of the input identifier, the recognized identifier, and the substitute identifiers include at least one alphabetical character.

22. The apparatus according to claim 19, wherein each one of the input identifier, the recognized identifier, and the substitute identifiers include at least one numeral and at least one alphabetical character.

23. The apparatus according to claim 19, wherein each one of the input identifier, the recognized identifier, and the substitute identifiers include at least one check-sum character and a set of non-check-sum characters, and wherein the first means for determining comprises:

i) third means for determining whet her the check-sum character and the non-check-sum characters of the recognized identifier correspond to a predetermined relationship;

ii) means for flagging the recognized identifier as incorrect if the check-sum character and the non-check-sum characters of the recognized identifier do not correspond to the predetermined relationship; and

iii) means for flagging the recognized identifier as correct if the check-sum character and the non-check-sum characters correspond to the predetermined relationship.

24. The apparatus according to claim 23, wherein the check-sum character of each one of the input identifier, the recognized identifier, and the substitute identifiers comprises a check-sum digit, wherein the non-check-sum characters of each one of the input identifier, the recognized identifier, and the substitute identifiers comprise non-check-sum digits, and wherein the predetermined relationship comprises the check- sum digit of a particular identifier equaling a modulo-N sum of the non-check-sum digits of the same particular identifier, N comprising an integer greater than zero.

25. The apparatus according to claim 24, wherein the means for generating comprises:

iv) means for calculating a difference between the check-sum digit of the recognized identifier and the modulo-N sum of the non-check-sum digits of the recognized identifier; and

v) means for generating a plurality of new identifiers, each of the new identifiers having a check-sum digit and a set of non-check-sum digits, wherein the modulo-N sum of the non-check-sum digits of each new identifier equals its associated check-sum digit and wherein the modulo-N sum of the non-check-sum digits of each new identifier differs from the modulo-N sum of the non-check-sum digits of the recognized identifier by the difference calculated by the calculating means, the set of new identifiers corresponding to the set of substitute identifiers.

26. The apparatus according to claim 19, wherein the means for selecting comprises means for prompting a user with each one of the matched reference identifiers until the user confirms that one of the matched reference identifiers corresponds to the input identifier.

45. The apparatus according to claim 19, wherein:

the first means for determining comprises;

means for performing a first calculation on at least one value derived from the input identifier in order to produce a first result,

means for performing a second calculation on at least one value derived from the recognized identifier in order to produce a second result, and

means for determining that the recognized identifier is incorrect if the first result and the second result exhibit a predetermined relationship with respect to each other, and

the second means for providing comprises;

means for generating the set of substitute identifiers such that each substitute identifier exhibits the predetermined relationship with respect to the recognized identifier.

27. An apparatus for recognizing at least one input identifier, comprising:

a) first means for providing a recognized identifier based on the input identifier;

b) first means for determining whether the recognized identifier was recognized correctly by determining whether an information content of the recognized identifier corresponds to an information content of the input identifier;

c) means for generating a set of substitute identifiers only if the recognized identifier is incorrect, each one of the substitute identifiers being generated in accordance with a character arrangement that corresponds to a character arrangement of at least one of the input identifier and the recognized identifier;

d) means for reducing the set of substitute identifiers by eliminating a number of the substitute identifiers from the set of substitute identifiers;

e) second means for determining which, if any, substitute identifiers match at least one member of a set of reference identifiers; and

f) means for selecting one of the matched reference identifiers as corresponding to the input identifier.

28. The apparatus according to claim 27, wherein each one of the input identifier, the recognized identifier, and the substitute identifiers include at least one numeral.

29. The apparatus according to claim 27, wherein each one of the input identifier, the recognized identifier, and the substitute identifiers include at least one alphabetical character.

30. The apparatus according to claim 27, wherein each one of the input identifier, the recognized identifier, and the substitute identifiers include at least one numeral and at least one alphabetical character.

31. The apparatus according to claim 27, wherein each one of the input identifier, the recognized identifier, and the substitute identifiers include at least one check-sum character and a set of non-check-sum characters, and wherein the first means for determining comprises:

i) third means for determining whether the check-sum character and the non-check-sum characters of the recognized identifier correspond to a predetermined relationship;

ii) means for flagging the recognized identifier as incorrect if the check-sum character and the non-check-sum characters of the recognized identifier do not correspond to the predetermined relationship; and

iii) means for flagging the recognized identifier as correct if the check-sum character and the non-check-sum characters correspond to the predetermined relationship.

32. The apparatus according to claim 31, wherein the check-sum character of each one of the input identifier, the recognized identifier, and the substitute identifiers comprises a check-sum digit, wherein the non-check-sum characters of each one of the input identifier, the recognized identifier, and the substitute identifiers comprise non-check-sum digits, and wherein the predetermined relationship comprises the check- sum digit of a particular identifier equaling a modulo-N sum of the non-check-sum digits of the same particular identifier, N comprising an integer greater than zero.

33. The apparatus according to claim 32, wherein the means for generating comprises:

iv) means for calculating a difference between the check-sum digit of the recognized identifier and the modulo-N sum of the non-check-sum digits of the recognized identifier; and

v) means for generating a plurality of new identifiers, each of the new identifiers having a check-sum digit and a set of non-check-sum digits, wherein the modulo-N sum of the non-check-sum digits of each new identifier equals its associated check-sum digit and wherein the modulo-N sum of the non-check-sum digits of each new identifier differs from the modulo-N sum of the non-check-sum digits of the recognized identifier by the difference calculated by the calculating means, the set of new identifiers corresponding to the set of substitute identifiers.

34. The apparatus according to claim 27, wherein the means for reducing comprises:

i) third means for determining, for each substitute identifier, a recognition probability of a user having provided that substitute identifier, given the recognized identifier; and

ii) means for eliminating the substitute identifier from the set of substitute identifiers if the recognition probability associated with the substitute identifier is no more than a predetermined threshold.

35. The apparatus according to claim 34, wherein a recognition probability associated with a given substitute identifier is obtained from a confusion matrix.

36. The apparatus according to claim 27, wherein the means for selecting comprises means for prompting a user with each one of the matched reference identifiers until the user confirms that one of the matched reference identifiers corresponds to the input identifier.

46. The apparatus according to claim 27, wherein:

the first means for determining comprises;

means for performing a first calculation on at least one value derived from the input identifier in order to produce a first result,

means for performing a second calculation on at least one value derived from the recognized identifier in order to produce a second result, and

means for determining that the recognized identifier is incorrect if the first result and the second result exhibit a predetermined relationship with respect to each other, and

the second means for providing comprises;

means for generating the set of substitute identifiers such that each substitute identifier exhibits the predetermined relationship with respect to the recognized identifier.

37. An apparatus for recognizing at least a first input identifier, comprising:

a processing device;

a recognizing device coupled to the processing device, the recognizing device including an input for receiving an input identifier;

a reference identifier database coupled to the processing device;

a check-sum correction module coupled to the processing device and for determining whether an information content of a recognized identifier corresponds to an information content of the input identifier; and

a substitute identifier database coupled to the processing device and provided with at least one generated substitute identifier only if a recognized identifier generated based on the first input identifier is determined to be incorrect, the substitute identifier being generated in accordance with a character arrangement that corresponds to a character arrangement of at least one of the input identifier and the recognized identifier.

38. The apparatus according to claim 37, further comprising:

a data input device coupled to the processing device; and

a display device coupled to the processing device.

39. An apparatus for recognizing at least a first input identifier, comprising:

a processing device;

a recognizing device coupled to the processing device, the recognizing device including an input for receiving an input identifier;

a reference identifier database coupled to the processing device;

a check-sum correction module coupled to the processing device;

a substitute identifier database coupled to the processing device;

a confusion matrix memory coupled to the processing device; and

a substitute set pruning module coupled to the processing device.

40. The apparatus according to claim 39, further comprising:

a data input device coupled to the processing device; and

a display device coupled to the processing device.

41. The apparatus according to claim 39, wherein the recognizing device comprises a speech recognition device.

42. The apparatus according to claim 39, wherein the recognizing device comprises a touch-tone recognizing device.

47. A method of recognizing at least one input identifier, comprising:

a) performing an input identifier recognition operation in order to produce a non-intermediate set of information corresponding to a recognized identifier based on the input identifier;

b) after the performance of the input identifier recognition operation is completed, determining whether the recognized identifier was recognized correctly;

c) generating a set of substitute identifiers if the recognized identifier is incorrect;

d) determining which, if any, substitute identifiers match at least one member of a set of reference identifiers; and

e) selecting one of the matched reference identifiers as corresponding to the input identifier.

48. A method of recognizing at least one input identifier, comprising:

a) performing an input identifier recognition operation in order to produce a non-intermediate set of information corresponding to a recognized identifier based on the input identifier;

b) after the performance of the input identifier recognition operation is completed, determining whether the recognized identifier was recognized correctly;

c) generating a set of substitute identifiers if the recognized identifier is incorrect;

d) reducing the set of substitute identifiers by eliminating a number of the substitute identifiers from the set of substitute identifiers;

e) determining which, if any, substitute identifiers match at least one member of a set of reference identifiers; and

f) selecting one of the matched reference identifiers as corresponding to the input identifier.

49. A system for recognizing at least one input identifier, comprising:

a) an arrangement for performing an input identifier recognition operation in order to produce a non-intermediate set of information corresponding to a recognized identifier based on the input identifier;

b) an arrangement for determining, after the performance of the input identifier recognition operation is completed, whether the recognized identifier was recognized correctly;

c) an arrangement for generating a set of substitute identifiers if the recognized identifier is incorrect;

d) an arrangement for determining which, if any, substitute identifiers match at least one member of a set of reference identifiers; and

e) an arrangement for selecting one of the matched reference identifiers as corresponding to the input identifier.

50. A system for recognizing at least one input identifier, comprising:

a) an arrangement for performing an input identifier recognition operation in order to produce a non-intermediate set of information corresponding to a recognized identifier based on the input identifier;

b) an arrangement for determining, after the performance of the input identifier recognition operation is completed, whether the recognized identifier was recognized correctly;

c) an arrangement for generating a set of substitute identifiers if the recognized identifier is incorrect;

d) an arrangement for reducing the set of substitute identifiers by eliminating a number of the substitute identifiers from the set of substitute identifiers;

e) an arrangement for determining which, if any, substitute identifiers match at least one member of a set of reference identifiers; and

f) an arrangement for selecting one of the matched reference identifiers as corresponding to the input identifier.