omplete path through the tree graph has been identified and additional input is requested from the user (6-10). Any such additional input obtained from the user (6-4) is processed again as set forth in FIG. 7. If Npaths is greater than zero, at least one complete through the tree has been identified and the loop counter I is incremented by one (6-12).
For each complete path, I, the user is prompted (6-14) by a query to the user, to confirm the meaning of his utterance as determined by the system. The user's yes or no response (6-16) to the query is tested (6-18). An affirmative response to the query (6-16) means that the user's utterance has been identified and a contextually coherent response can be effected (6-20) by subsequent processing. A negative user response to the query (6-19) causes the next identified complete path, for I less than or equal to Npaths, to be considered for further processing.
Referring to FIG. 7, the number of keyword candidates not yet processed is determined (7-2). Stated alternatively, a determination of whether or not more keyword candidates exist in the utterance is made (7-2). If there is a keyword candidate in the utterance, it is tested (7-4) against the dictionary shown in FIG. 4 by reference numeral 40 and also shown in FIG. 1 by reference numeral 3-3 to determine if it is a keyword.
If the keyword candidate, T, in an utterance is not a keyword, (7-6) the keyword candidate is discarded and the next keyword candidate input by the utterance is tested (7-4). If the keyword candidate T is a keyword and therefore in the dictionary (40) shown in FIG. 4, the linked list pointed to by the keyword in the associative array (40) is identified and the linked list of nodes Q. By way of example, if the keyword candidate is the keyword “G” in the dictionary (40) “G” points to the linked list 4-26, the first element of which is the node “2”.
Each of the Q nodes is added to the node set, if it is not already present (7-10). For all of the Q nodes, an array NEW[Q] is true and a probability is assigned P[Q].
Where PT is the probability that an utterance is a token, T, which corresponds to node Q (8-24) and n is the number of nodes pointed to by the token T. The probability PT could be determined during pattern matching (1-8).
If there are no additional keyword candidates to process (7-2) a procedure Determine_paths, to identify paths is executed (7-14) and which is shown in FIG. 8. Identified paths are assigned a probability value to the path. The probability value assigned to a completed path represents the likelihood of the path being correct. The higher the probability value, denoted by variable PR (8-36), the more likely that the path corresponds to the correct meaning of the user's utterance. Upon the return of Determine_paths, the paths are sorted (7-16) based upon the probability values assigned by Determine_paths in descending order. After the paths are sorted, program control returns to the procedure shown in FIG. 6 (6-6).
An input token (keyword) is tested as it is accumulated (7-4) to determine if it is within the dictionary of recognizable keywords (7-4). A token (keyword) not within the dictionary is rejected (7-6). A token (keyword) that is within the dictionary is tested to determine the total number of nodes of the tree graph of FIG. 3 (70) that it can be mapped to (7-8). The nodes of the tree graph (70) that a keyword can be mapped to form a set of nodes that comprise a union (7-10) in the aforementioned array Node_Set. Additional instances of the token (keyword) in the input (7-2) do not accumulate in Node_Set. Probability values are assigned to nodes for detected keywords for subsequent processing (7-12) to determine the most likely meaning of the user's input and paths through the tree graph of FIG. 3 are determined (7-14) as shown in FIG. 8.
FIG. 8 depicts the processing for path determination.
A counter, M, is initialized (8-16) to zero to count the number of possible complete paths as determined by the process steps shown in FIG. 8.
For each node, R, (8-20) in Node_Set if the node