Concise dynamic grammars using n-best selection

Abstract

A method and apparatus derive a dynamic grammar composed of a subset of a plurality of data elements that are each associated with one of a plurality of reference identifiers. The present invention generates a set of selection identifiers on the basis of a user-provided first input identifier and determines which of these selection identifiers are present in a set of pre-stored reference identifiers. The present invention creates a dynamic grammar that includes those data elements that are associated with those reference identifiers that are matched to any of the selection identifiers. Based on a user-provided second identifier and on the data elements of the dynamic grammar, the present invention selects one of the reference identifiers in the dynamic grammar.

1 . A method comprising:
 receiving speech from a user;   recognizing the speech to yield a recognized identifier having a first character and a second character;   for the first character:
 identifying a first confusion set of characters having a probability of being confused with the first character, the first confusion set of characters having one or more substitute first confusion character; 
 iteratively substituting the first character with each respective one or more substitute first confusion character in the first confusion set of characters to yield N first selection identifiers; 
   for the second character:
 identifying a second confusion set of characters having a probability of being confused with the second character, the second confusion set of characters having one or more substitute second confusion character; 
 iteratively substituting the second character with each respective one or more substitute second confusion character in the second confusion set of characters to yield M second selection identifiers; 
   combining the N first selection identifiers and the M second selection identifiers into S selection identifiers;   forming a new grammar based on a match of the S selection identifiers with at least one reference identifier; and   prompting the user to provide second speech using the new grammar.   
     
     
         2 . The method of  claim 1 , further comprising:
 determining whether the second speech matches an element of the new grammar.   
     
     
         3 . The method of  claim 1 , wherein when the second speech matches an element of the new grammar, the method further comprises selecting a selection identifier with a matched element. 
     
     
         4 . The method of  claim 3 , wherein when the second speech does not match an element of the new grammar, the method further comprises prompting the user for a new input identifier. 
     
     
         5 . The method of  claim 1 , wherein a number S of the S selection identifiers is determined based on a predetermined value. 
     
     
         6 . The method of  claim 1 , wherein a number S of the S selection identifiers is determined based on how many replacement characters are in the first confusion set of characters and the second confusion set of characters. 
     
     
         7 . The method of  claim 1 , wherein the first confusion set of characters and the second confusion set of characters are generated using a confusion matrix. 
     
     
         8 . A system comprising:
 a processor; and   a computer-readable storage device storing instructions which, when executed by the processor, cause the processor to perform operations comprising:
 receiving speech from a user; 
 recognizing the speech to yield a recognized identifier having a first character and a second character; 
 for the first character: 
 identifying a first confusion set of characters having a probability of being confused with the first character, the first confusion set of characters having one or more substitute first confusion character; 
 iteratively substituting the first character with each respective one or more substitute first confusion character in the first confusion set of characters to yield N first selection identifiers; 
 for the second character: 
 identifying a second confusion set of characters having a probability of being confused with the second character, the second confusion set of characters having one or more substitute second confusion character; 
 iteratively substituting the second character with each respective one or more substitute second confusion character in the second confusion set of characters to yield M second selection identifiers; 
 combining the N first selection identifiers and the M second selection identifiers into S selection identifiers; 
 forming a new grammar based on a match of the S selection identifiers with at least one reference identifier; and 
 prompting the user to provide second speech using the new grammar. 
   
     
     
         9 . The system of  claim 8 , wherein the computer-readable storage device stores additional instructions which, when executed by the processor, cause the processor to perform further operations comprising:
 determining whether the second speech matches an element of the new grammar.   
     
     
         10 . The system of  claim 8 , wherein the computer-readable storage device stores additional instructions which, when executed by the processor, cause the processor to perform further operations comprising:
 when the second speech matches an element of the new grammar, selecting a selection identifier with a matched element.   
     
     
         11 . The system of  claim 10 , wherein the computer-readable storage device stores additional instructions which, when executed by the processor, cause the processor to perform further operations comprising:
 when the second speech does not match an element of the new grammar, prompting the user for a new input identifier.   
     
     
         12 . The system of  claim 8 , wherein a number S of the S selection identifiers is determined based on a predetermined value. 
     
     
         13 . The system of  claim 8 , wherein a number S of the S selection identifiers is determined based on how many replacement characters are in the first confusion set of characters and the second confusion set of characters. 
     
     
         14 . The system of  claim 8 , wherein the first confusion set of characters and the second confusion set of characters are generated using a confusion matrix. 
     
     
         15 . A computer-readable storage device storing instructions which, when executed by a processor, cause the processor to perform operations comprising:
 receiving speech from a user;   recognizing the speech to yield a recognized identifier having a first character and a second character;   for the first character:
 identifying a first confusion set of characters having a probability of being confused with the first character, the first confusion set of characters having one or more substitute first confusion character; 
 iteratively substituting the first character with each respective one or more substitute first confusion character in the first confusion set of characters to yield N first selection identifiers; 
   for the second character:
 identifying a second confusion set of characters having a probability of being confused with the second character, the second confusion set of characters having one or more substitute second confusion character; 
 iteratively substituting the second character with each respective one or more substitute second confusion character in the second confusion set of characters to yield M second selection identifiers; 
 combining the N first selection identifiers and the M second selection identifiers into S selection identifiers; 
 forming a new grammar based on a match of the S selection identifiers with at least one reference identifier; and 
 prompting the user to provide second speech using the new grammar. 
   
     
     
         16 . The computer-readable storage device of  claim 15 , wherein the computer-readable storage device stores additional instructions which, when executed by the processor, cause the processor to perform further operations comprising determining whether the second speech matches an element of the new grammar. 
     
     
         17 . The computer-readable storage device of  claim 15 , wherein the computer-readable storage device stores additional instructions which, when executed by the processor, cause the processor to perform further operations comprising:
 when the second speech matches an element of the new grammar, selecting a selection identifier with a matched element.   
     
     
         18 . The computer-readable storage device of  claim 17 , wherein the computer-readable storage device stores additional instructions which, when executed by the processor, cause the processor to perform further operations comprising:
 prompting the user for a new input identifier.   
     
     
         19 . The computer-readable storage device of  claim 15 , wherein a number S of the S selection identifiers is determined based on a predetermined value. 
     
     
         20 . The computer-readable storage device of  claim 15 , wherein a number S of the S selection identifiers is determined based on how many replacement characters are in the first confusion set of characters and the second confusion set of characters.