Abstract:
A method for automatically generating a minimal set of test phrases for testing a natural commands grammar includes the steps of selecting a line of text in the natural commands grammar; forming a test phrase for the selected line of text; detecting a previous inclusion of the test phrase in the minimal set of test phrases; and, adding the test phrase to the minimal set of test phrases only if the test phrase has not been detected as having been previously included in the minimal set of test phrases in the detecting step.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     (Not Applicable) 
     STATEMENT REGARDING FEDERALLY SPONSORED RESEARCH OR DEVELOPMENT 
     (Not Applicable) 
     BACKGROUND OF THE INVENTION 
     1. Technical Field 
     This invention relates to the field of computer speech recognition and more particularly to a method and system for generating a minimal set of test phrases for testing a natural commands grammar. 
     2. Description of the Related Art 
     Speech recognition, also referred to as speech-to-text, is the technology that enables a computer to transcribe spoken words into computer recognized text equivalents. In practice, speech recognition has been employed in spoken command recognition and dictation. Spoken command recognition finds its greatest utility when incorporated in computer game applications, multimedia titles, and application navigation programs. Spoken command recognition can support the recognition of single words or short phrases spoken with continuous speech, such as “Open File”. In contrast, the dictation function is most evident in word processing and document generation applications. 
     During the past decade there has been significant progress in the development of speech recognition systems. In consequence of technical advances in speech modeling techniques and recognition search strategies combined with the increased processing power of workstations and personal computers, large vocabulary continuous speech recognition is now feasible. In conjunction with advances in Natural Language Understanding (NLU), these new technical capabilities have made possible the incorporation of more natural styles of human-computer verbal interactions. 
     NLU technology represents the next generation of speech technology to come to market. Specifically, NLU technology permits a computer to understand the meaning of spoken or typed words. Moreover, NLU can render possible a computer&#39;s understanding of a query or statement put forth in natural human language. Simply put, using NLU technology a computer can understand not merely spoken words, but the meaning behind each spoken word. Software applications that seek to exploit this technology include expert systems, applications having user “wizards”, database access systems for problem resolution, database search engines including the Internet, and combined query and response systems. 
     Related to NLU technology, natural command grammars bridge the gap between the simple command grammar and the NLU technology of the future. Natural command grammars, to some extent, represent the middle ground between the simple command grammar and NLU. Specifically, the natural command grammar is a finite state grammar that allows NLU-like flexibility in the number of allowable expressions per function. Presently, the nature of continuous speech recognizers necessitates a grammar&#39;s specification of every possible utterance potentially provided to the application. Significantly, the constraints on word choice imposed by these grammars can reduce perplexity and, accordingly, can lower the recognition error rate. 
     Although there are a number of approaches to structuring a natural commands grammar, the recognizer grammar commonly specified using Backus-Naur Form (BNF) seems most logical and has become widely used. The structure of the BNF grammar has comments, a root node branching out to sentence set nodes, sentence set nodes that branch out to sentences, or natural commands, variables in sentences that connect to phrase nodes, and a translation rule at the end of each line of grammar. It is the translation rule that translates the natural command into a functional statement which can be used by a back-end program to execute the program&#39;s functions without requiring a separate parsing program. 
     While simple grammars are relatively easy to develop and test, more complex grammars, including NLU and natural command grammars, are very difficult to develop and test comprehensively. For natural command grammars, the number of valid commands is for all practical purposes infinite, precluding exhaustive testing. Hence, testing every possible phrase in a natural commands grammar to verify correct interpretation by a translation rule interpreter, or other parsing technique, can be extraordinarily difficult and extremely inefficient. Current methods provide only for manual testing of each translation rule. Moreover, manual testing has proven error prone and time consuming. No present method can automatically create a minimum set of test sentences. 
     SUMMARY OF THE INVENTION 
     The invention concerns a method and system for automatically generating a minimal set of test phrases for testing a natural commands grammar. The invention as taught herein has advantages over all known methods now used to produce test cases for a natural commands grammar, and provides a novel and nonobvious system, including apparatus and method, for automatically generating a minimal set of test phrases for testing a natural commands grammar. The method involves selecting a line of text, the line having a valid phrase for the natural commands grammar and a translation rule for translating the valid phrase into a functional statement; forming a test phrase for the selected line of text; detecting a previous inclusion of the test phrase in the minimal set of test phrases; and, adding the test phrase to the minimal set of test phrases only if the test phrase has not been previously included in the minimal set of test phrases. 
     Additionally, the forming step can include identifying the selected line as either a sentence line or sub-sentence line; searching the natural commands grammar for a sentence line having a valid phrase incorporating the identified sub-sentence line; repeating the searching step and the determining step if the sentence line found in the searching step is determined to have been previously considered in the searching step; and, composing a test phrase from the valid phrase of the sentence line found in the searching step. As part of the forming step, the composing step can comprise determining whether the sentence line is a terminal node or non-terminal node; extracting from the sentence line of a node determined to be non-terminal, each variable incorporated in the sentence line; obtaining a valid phrase from each sub-sentence line corresponding to each extracted variable; combining each valid phrase obtained in the obtaining step with the valid phrase of the selected sentence line determined to be a non-terminal node in the determining step; and, designating the combined valid phrase as a test phrase. Finally, the detecting step can include detecting the test phrase in the minimal set of test phrases; and, determining a previous use of the test phrase detected in the minimal set of test phrases. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     There are presently shown in the drawings embodiments which are presently preferred, it being understood, however, that the invention is not limited to the precise arrangements and instrumentalities shown. 
     FIG. 1 is an example of a BNF natural commands grammar. 
     FIGS. 2A-2C taken together, are a flow chart illustrating a process for generating a minimal set of test phrases for testing a natural commands grammar. 
     FIG. 3 is a minimal set of test phrases created by the process illustrated in FIGS. 2A-2C for the BNF natural commands grammar listed in FIG.  1 . 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     A grammar contains a representation of the valid expressions for a speech-enabled computer program. FIG. 1 illustrates a BNF grammar, although the inventive arrangements are not restricted to use with a BNF grammar. Rather, it will be appreciated by one skilled in the art that the inventive arrangements will work for any grammar. Although many approaches exist with respect to structuring a natural commands grammar, the approach illustrated in FIG. 1 has been used in practice, for example in IBM&#39;s ViaVoice ′98®. In FIG. 1, the structure of the BNF grammar includes comments  51 , a root node  52  branching out to sentence set nodes  53 , sentence set nodes  53  that branch out to sentences or natural commands  54 , variables  55  in sentences  54  that connect to phrase nodes  56 , and a translation rule  57  at the end of each line of grammar. One skilled in the art will recognize that there is no limit to the extent to which the designer of a grammar can use variables in one node that point to a lower node. For instance, FIG. 1 shows variables  55  in phrase nodes  56  point to subphrase nodes  58 . At some point, however, all variables  55  connect to a node with no variables—a terminal node  59  as shown in FIG.  1 . 
     In FIG. 1, the root node  52  points to three sentence set nodes  53 , defined below root node  52 . Each sentence set node  53  contains the valid phrase for the grammar, and a translation rule  57  that translates the natural command into a functional statement. One skilled in the art will observe that translation rules are a convenience in a grammar for getting the spoken phrase into a form that auxiliary programs can use to execute program functions without necessitating a separate parsing program. A grammar with translation rules provides a clear indication of the location of the sentence set nodes. All valid phrases in a grammar correspond to a sentence in a sentence set node. When a speaker utters a valid phrase, a speech recognition system employing a BNF grammar can transmit the translation rule, complete with parameters as indicated by the variable content of the valid phrase, to a translation rule interpreter. Once interpreted, the system performs the actions as defined by the translation rule&#39;s function. The translation rules provide a way to unambiguously identify phrases that have the same functional consequences—they identify the alternate ways to say something in a given grammar. 
     For instance, with the code shown in FIG. 1, if a user said “Go to the start of the line,” the translation rule would be “go(begline).” Likewise, if a user said “Go to the beginning of the line,” the translation rule produced would also be “go(begline).” If a user said something with a different meaning, however, then the translation rule produced would be different. For example, “Go to the top” would produce “go(topfile).” It will be recognized by those skilled in the art that many different translation rules are possible for use with different commands and formats, all such rules being within the scope of the invention. Significantly, methods other than those which utilize translation rules exist which can translate the spoken phrase into a computer recognizable command. For instance, it is well known in the art to use both annotations which facilitate the development of parsing routines, and parsing routines which do not require annotations. Nevertheless, the preferred embodiment operates best using a conventional BNF grammar. 
     From a logical analysis, it is clear that all translation rules will be exercised by a set of sentences that number the same as the number of lines, excluding comments, in the command grammar. Simply put, there should be a test phrase for each translation rule in the grammar. In the example of FIG. 1, for instance, a complete set of test phrases would number thirty, Yet, the act of testing translation rules at the sentence set level eliminates the need for a specific test case for the translation rules at the root node level. Again, in the example of FIG. 1, an equally comprehensive set of test phrases would number  27 . 
     Recognizing that the act of testing sub-sentence translation rules necessarily involves creating a test phrase leads to the realization that it is possible to further reduce the required number of test phrases. The amount of reduction corresponds to the specific grammar structure to be tested. At one extreme, if it were possible to create test phrases for sub-sentence translation rules using all of the sentence level translation rules, then the number of required test phrases would be reduced by the number of sentence-level translation rules. In contrast, if it were possible only to test all sub-sentence translation rules using a single sentence-level translation rule, then the number of required test phrases would be reduced only by one. 
     The parts of FIG. 2 are a flow chart illustrating the various steps of a method  60  for testing a natural commands grammar in accordance with the inventive arrangements. As shown in FIG. 2A, the method  60  begins in step  1  at the bottom node of the command language grammar. Following path  2  to block  3 , a line of text is selected for evaluation. In decision block  5 , if the selected line of text is a comment line, the selected line of text is ignored and, following path  4  to block  3 , another line of text is selected for evaluation. Continuing along path  8  to decision block  7 , in the event the selected line of text is a sub-sentence, the method  60  branches along path  12  to jump circle C. Otherwise, following along path  10  to decision block  9 , in the event the selected line of text is a sentence, the method  60  branches along path  14  to jump circle B. In all other cases, following path  50  to jump circle A, the selected line of text is ignored and another line of text is selected for evaluation. 
     FIG. 2B is a continuation of path  14  connected by jump circle B of FIG. 2A, where the selected line of text is a sentence line of text. In that event, a valid phrase is extracted from the sentence line in block  13 . Subsequently, a partial test phrase is formed in block  15  from the valid phrase extracted in block  13 . Following path  24  to decision block  17 , if the partial test phrase has already been added to the minimal set of test phrases for the command language grammar, the test phrase is discarded and, following path  18  to block  3 , a new line of text is selected for examination. If, in decision block  17 , the partial test phrase does not appear in the minimal set of test phrases, following path  20  to block  11  in FIG. 2A, the test phrase is added to the minimal set of test phrases. 
     FIG. 2C is a continuation of path  12  connected by jump circle C of FIG. 2A, where the selected line of text is a sub-sentence line of text. In that event, the variable name of the node containing the selected sub-sentence line of text is extracted in block  19 . Following path  26  to block  21 , a valid phrase is extracted from the sub-sentence line of text and a partial test phrase is formed from the valid phrase. In block  23 , the preceding line is read in for examination. If, in decision block  25 , the preceding line of text does not contain the variable extracted in block  19 , the next preceding line of text is read in for examination. In contrast, if the preceding line of text does contain the variable extracted in block  19 , the line preceding line is identified as either a sub-sentence or sentence in decision block  27 . 
     If the preceding line containing the extracted variable is a sub-sentence, following path  38  to block  31 , the partial test phrase is re-formed by combining the valid phrase of the preceding line with the previously formed test phrase. Subsequently, the variable name of the node containing the previously extracted variable is extracted in block  29 . following path  42  to block  23 , the next preceding line is read in for examination and the process repeats, the partial test phrase continually being re-formed, until a sentence node is encountered in decision block  27 . In accordance with the inventive arrangements, it is particularly advantageous to produce test phrases by beginning with the last node in the grammar and working up because to iterate up through the grammar, it is necessary only to check the variable name of the node, find it referenced higher in the grammar, check the variable name of that node, find it referenced higher in the grammar, and continue until hitting a node that produces a sentence-level translation rule. 
     When the preceding line containing the extracted variable is determined to be a sentence according to decision block  27 , following path  36  to decision block  33 , the variable name extracted in block  29  is tested for previous use in the current sentence line during the current search. If the variable name has been incorporated during the current search in the current sentence line, following the path  48  to block  23 , the next preceding line is read in for examination and the process is repeated. Otherwise, following the path  44  to block  37 , the partial test phrase formed in either block  31  or  21  is re-formed to create a new partial test phrase. Following path  46  to the decision block  35 , the contents of the minimal set of test phrases are examined for the listing of the newly re-formed partial test phrase. If the partial test phrase appears in the minimal set of test phrases, the partial test phrase is discarded and, following path  18  to block  3 , a new line of text is selected for examination. Otherwise, following path  20  to block  11 , the partial test phrase is added to the minimal set of test phrases. 
     FIG. 3 is a list of a minimal set of test phrases  70  generated using method  60  illustrated in FIGS. 2A-2C as applied to the BNF grammar described in FIG.  1 . It can be seen from the list  70  that a minimal set of test phrases needs to include only 21 valid test phrases. So, to create this minimal set of test phrases, the strategy differs depending on whether the line for which the test phrase is being created is a sub-sentence or sentence-level line. For sub-sentence level lines, the appropriate strategy includes tracking previously used sentence-level lines used in those test phrases and, as new test phrases are developed, seek to use unused sentences. In contrast, for sentence-level lines, the appropriate strategy includes developing new test cases only for those lines unused in sub-sentence level test cases.